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

Viewed 1124

I want to find the minimum element of a filtered list. In Python, I would write:

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

I hoped that the c++ equivalent would read something like:

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;
}

The expected result is 4, but of course the actual result is 3. The reason: find_if skips to 8. Then from 8 to end the min element is chosen, which is 3.

My question: Is there a way to create an iterator over all even values that can be used to find the minimum element? I am not allowed to use boost, create a copy or to write to array. We are using c++17.

4 Answers

There isn't an answer in std as of C++17. In C++20 you can use std::ranges::filter_view, outside of std you can use ranges::filter_view from the range-v3 library, which was the demonstration implementation for the C++20 ranges proposal.

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;
}

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

Yes!

It's slightly unfortunate that you're limited to C++17 with no Boost, because you ideally want ranges - specifically ranges::filter_view etc. which was added in C++20, and preceded by the Boost.Range library.

You may possibly be able to use the intermediate experimental range extension.

If none of those are viable, you can of course write your own filtered_iterator to use with std::min_element.

It's not much fun: although it's probably more reusable (and easier to test) than encoding all the logic into a single lambda, it's a lot of work if you're not planning to reuse it. Also, C++ iterators aren't ideally suited to emulating a Python-style generator, as demonstrated by the redundant end iterator e_ and the copy-assignment operator. You can't elide the end & predicate members of the filtered end iterator either, because both iterators usually need to be the same type.

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);
}

Then the wrapper function hides most of this ugliness for us:

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}};
}

and we can use it like:

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;
}

std::find_if does not filter the vector. It only returns the first element for which the predicate is true. I suppose there is an elegant solution using ranges. The rather inelegant way is to use a custom comparator with 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;
    }

}

Odd elements are considered to be not < than other elements. When both are odd or both are even the "normal" < is used. Output is:

4

Note that I have to check if (*it % 2 == 0) because when there is no even element then the call to min_element will return an iterator to the smallest odd element.

PS: The tricky part of custom comparators is to get strict weak ordering correct. The above comparator can be written in a more concise way (thanks to Jarod42) like this:

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

Tuples have a operator< that implements a strict weak ordering (given that the elements type provide one), hence writing it this way it is much easier to convice yourself that the comparator really is a strict weak ordering.

If you are limited at c++17 there is no solution without making a copy.

If you can transition to C++ 20 the solution is pretty easy. C++ 20 introduced the std::views concept and added the <ranges> library. The concept of std::view is to not create a copy of the underlying container, and it does not modifies the actual values of the container. Behind the scenes the views are actually iterators(actually it is a bit more but lets stay at the basics)

So in your case you could something like this

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

auto isEven = [](auto i) { return i % 2 == 0; };

//This is actually an iterator pair(begin, end)
//No copies of the container ever made, the container does not change
auto filtered = array | std::views::filter(isEven);
auto min = std::ranges::min_element(filtered );

if (min != filtered .end())
    std::cout << "Min " << *min << std::endl;
else
    std::cout << "No min\n";

//You can try to print the vector, it will be unchanged!!!
Related