是否有 c++ std 解决方案来过滤和减少而不创建副本？

Question

我想找到筛选列表的最小元素。在 Python 中，我会写：

it = (x for x in [1, 8, 4, 3] if x % 2 == 0)
min(it, default=None)

我希望 c++ 的等价物是这样的：

const std::vector<int> array {1, 8, 4, 3};

const auto arr_end = std::end(array);
auto it = std::find_if(std::begin(array), arr_end, [](int value) { return value % 2 == 0; });
auto jt = std::min_element(it, arr_end);

if (jt != arr_end) {
    std::cout << "Min even element is: " << *jt << std::endl;
} else {
    std::cout << "No even element exists!" << std::endl;
}

预期结果是4，实际结果当然是3。原因：find_if跳到8。然后从8到结束选择min元素，也就是3。

我的问题：有没有一种方法可以创建一个遍历所有偶数的迭代器，用于查找最小元素？我不允许使用 boost、创建副本或写入 array。我们正在使用 c++17.

Answer 1

std::find_if 不过滤向量。它只是 return 谓词为 true 的第一个元素。我想有一个使用范围的优雅解决方案。相当不优雅的方法是使用带有 min_element:

的自定义比较器

#include <vector>
#include <algorithm>
#include <iostream>

int main() {
    const std::vector<int> array {1, 8, 4, 3};
    std::vector<float> x;
    if (array.size()) {
        auto it = std::min_element(begin(array),end(array),
         [](auto a, auto b){
             if ((a % 2) && (b % 2)) return a < b;
             if (a % 2) return false;
             if (b % 2) return true;
             return a < b;
         });
         if (*it % 2 == 0) std::cout << *it;
    }

}

奇数元素被认为不比其他元素<。当两者都是奇数或两者都是偶数时，使用“正常”<。输出为：

请注意，我必须检查 if (*it % 2 == 0)，因为当没有偶数元素时，对 min_element 的调用将 return 一个指向最小奇数元素的迭代器。

PS：自定义比较器的棘手部分是让 strict weak ordering 正确。上面的比较器可以写成更简洁的方式（感谢 Jarod42），如下所示：

return std::tuple{ bool{a%2} , a} < std::tuple{ bool{b%2} , b};

元组有一个 operator< 实现了严格的弱排序（假设元素类型提供了一个），因此以这种方式编写它更容易让自己相信比较器确实是严格的弱排序.

Answer 2

自 C++17 起，std 中没有答案。在 C++20 中，您可以使用 std::ranges::filter_view，在 std 之外，您可以使用 range-v3 library 中的 ranges::filter_view，这是 C++20 范围提案的演示实现.

auto filtered = ranges::filter_view(array, [](int value) { return value % 2 == 0; });
auto it = std::min_element(filtered.begin(), filtered.end());

if (it != filtered.end()) {
    std::cout << "Min even element is: " << *jt << std::endl;
} else {
    std::cout << "No even element exists!" << std::endl;
}

Answer 3

My question: Is there a way to create an iterator over all even values that can be used to find the minimum element?

是的！

稍微不幸的是，您仅限于没有 Boost 的 C++17，因为您理想情况下想要 ranges - 特别是 ranges::filter_view 等，它被添加到C++20，前面是 Boost.Range 库。

您也许可以使用中间件 experimental range extension。

如果其中 none 可行，您当然可以编写自己的 filtered_iterator 与 std::min_element 一起使用。

这没什么好玩的：虽然它可能比将所有逻辑编码到一个 lambda 中更可重用（也更容易测试），但是如果你不是打算重复使用。此外，C++ 迭代器并不非常适合模拟 Python 样式的生成器，正如冗余结束迭代器 e_ 和复制赋值运算符所证明的那样。您也不能省略过滤结束迭代器的结束和谓词成员，因为两个迭代器通常需要是相同的类型。

template <typename BaseIterator, typename UnaryPredicate>
class filter_iterator
{
    BaseIterator i_;
    BaseIterator e_;
    UnaryPredicate pred_;
public:
    using reference = typename std::iterator_traits<BaseIterator>::reference;
    using value_type = typename std::iterator_traits<BaseIterator>::value_type;

    filter_iterator(filter_iterator &&) = default;
    filter_iterator(filter_iterator const&) = default;
    filter_iterator(BaseIterator i, BaseIterator e, UnaryPredicate p)
    : i_(i), e_(e), pred_(p)
    {}
    filter_iterator& operator=(filter_iterator &&) = default;
    filter_iterator& operator=(filter_iterator const& other) {
        i_ = other.i_;
        e_ = other.e_;
        // This is questionable, because we can't copy the predicate without adding
        // a level of indirection (ie, always wrapping it in std::function).
        // For now, just assume it is stateless for convenience.
        return *this;
    }

    bool operator==(filter_iterator const& other) const
    {
        return i_ == other.i_;
    }
    filter_iterator& operator++() {
        // We could check i_ is not already e_ here,
        // but the caller is required to check this outside anyway
        i_ = find_if(next(i_), e_, pred_);
        return *this;
    }
    filter_iterator operator++(int) const {
        filter_iterator i(*this);
        ++i;
        return i;
    }

    reference operator*() { return *i_; }
    std::add_const_t<reference> operator*() const { return *i_; }
};
template <typename BaseIterator, typename UnaryPredicate>
bool operator!=(filter_iterator<BaseIterator, UnaryPredicate> const& a,
                filter_iterator<BaseIterator, UnaryPredicate> const& b)
{
    return !(a == b);
}

然后包装函数为我们隐藏了大部分丑陋之处：

template <typename BaseIterator, typename UnaryPredicate>
std::pair<filter_iterator<BaseIterator, UnaryPredicate>,
          filter_iterator<BaseIterator, UnaryPredicate>>
          filter(BaseIterator b, BaseIterator e, UnaryPredicate p)
{
    using f = filter_iterator<BaseIterator, UnaryPredicate>;
    auto fbegin = find_if(b, e, p);
    return {f{fbegin, e, p}, {e, e, p}};
}

我们可以像这样使用它：

int main() {
    std::vector<int> a {7, 1, 8, 4, 3, 2};
    auto be = filter(a.begin(), a.end(),
                     [](int i){ return (i%2) == 0;});
    auto min = std::min_element(be.first, be.second);
    return *min;
}

是否有 c++ std 解决方案来过滤和减少而不创建副本？

Is there a c++ std solution to filter and reduce without creating a copy?

c++

algorithm

std