How can I create iterators of a filtered vector?

Question

Suppose I have a vector named spot_deals of SpotDeal that is a class:

class SpotDeal
{
public:
    int deal_id_; // primary key, and vector is sorted by id
    string ccy_pair_; // ccy pair, e.g. GBPUSD, AUDUSD
    double amount_;
}

Say I need to pass two subset of spot_deals to a function foo for some computation. I could make copies, however, that would cost memory and time. Actually foo only needs iterators of deals. So can I make 2 iterators of vector<SpotDeal>, namely it1 and it2 and pass them to foo?

The two subset of spot_deals could be filtered by ccy_pair_, e.g. deals of GBPUSD and AUDUSD, or by other conditions. So I'm looking for a way to define an iterator defined by a vector and a lambda function (could equivalently be a functor though).

Is there a way to write a helper function make_filtered_iterator so that I can have something like below?

auto it1 = make_filtered_iterator(spot_deals, filter_lambda1);
auto it2 = make_filtered_iterator(spot_deals, filter_lambda2);
foo(it1, it2);

Answer 1

The answer is certainly "yes." C++ iterators in the STL style can be made to do all sorts of tricks. A common but basic one is making an iterator for std::map which when dereferenced gives only the key or the value.

In your particular case, a simple implementation might be like this:

template <typename BaseIterator>
struct filtered_iterator : BaseIterator
{
    typedef std::function<bool (const value_type&)> filter_type;

    filtered_iterator() = default;
    filtered_iterator(filter_type filter, BaseIterator base, BaseIterator end = {})
        : BaseIterator(base), _end(end), _filter(filter_type) {
        while (*this != _end && !_filter(**this)) {
            ++*this;
        }
    }

    filtered_iterator& operator++() {
        do {
            BaseIterator::operator++();
        } while (*this != _end && !_filter(**this));
    }

    filtered_iterator operator++(int) {
        filtered_iterator copy = *this;
        ++*this;
        return copy;
    }

private:
    BaseIterator _end;
    filter_type _filter;
};

template <typename BaseIterator>
filtered_iterator<BaseIterator> make_filtered_iterator(
        typename filtered_iterator<BaseIterator>::filter_type filter,
        BaseIterator base, BaseIterator end = {}) {
    return {filter, base, end};
}

I set a default value for end because typically you can use a default-constructed iterator for that. But in some cases you might want to filter only a subset of the container, in which case specifying the end makes it easy.

Answer 2

Yes, it would be possible to create an iterator type. However, I suspect your question is an example of an XY problem (https://meta.stackexchange.com/questions/66377/what-is-the-xy-problem) - you want to find a way to operate differently on two subsets of a vector (X), have decided the solution must involve implementing a special-purpose iterator (Y), and have asked how to do Y rather than X. I am going to provide an option to do X without needing to do Y.

I suggest it would be easier to use standard algorithm std::stable_partition() to separate the container into two ranges.

 auto false_partition = std::stable_partition(your_vector.begin(), your_vector.end(), your_filter);

The begin() and end() iterators of the vector do not change (i.e. are not invalidated), but the elements between them are reorganised into two ranges, such that the elements for which your_filter returns true precedes the set of elements for which your_filter returns false. false_partition is therefore simultaneously the "past the end" iterator for the first range, and the beginning of the second range. The order of elements in each range is the same as in the original vector.

These can be used as follows

 //   a loop to operates on the elements for which your_filter returned true

 for (auto i = your_vector.begin(); i != false_partition; ++i)
 {
      // do whatever
 }

 //   a loop to operates on the elements for which your_filter returned false

 for (auto i = false_partition; i != your_vector.end(); ++i)
 {
      // do whatever
 }

Before C++11, the auto keyword can be replaced with appropriate iterator types (e.g. std::vector<int>::iterator or std::vector<int>::const_iterator, depending on whether you want the elements to be changed using the iterators).

Answer 3

I may suggest viewers of this question get a crash course with Eric Nibbler's rangev3 because that's the paradigm adopted for C++20 standard lib.

https://github.com/ericniebler/range-v3

How to do your filter iteration:

for (auto element : spot_deals | views::filter([](auto i) { return condition(i); }))
{ //....
}