how to select a subset from a std::vector or list?

Question

c++ gurus:

there are quite some useful c++ stl algorithms such as find or search. However, it seems that they only return one single interator.

what if i want to do a SQL style 'select' for a STL container? say, a vector (might be extended to list or map). something like

std::pair<vector::iterator, vector::iterator> select(std::vector::iterator begin, std::vector::iterator end, Comparor equal_to)

the output should be a range, something like a std::pair, which is similiar to the return value of the methods in boost::multi-index

is there anything like this in stl? or any solid libararies similiar?

Answer 1

You have basically two approaches:

1) The thing you say in a comment above, write (iterators pointing at) the results into a container of iterators. That's going to look something like this:

template <typename ForwardIterator, typename OutputIterator, typename UnaryPredicate>
void select_iterators(ForwardIterator first, ForwardIterator last, 
                      OutputIterator out, UnaryPredicate pred) {
    while (first != last) {
        if pred(*first) *out++ = first;
        ++first;
    }
}

Then you call it like:

vector<Foo> myfoos;
vector<vector<Foo>::iterator> results;
select_iterators(myfoos.begin(), myfoos.end(), std::back_inserter(results), some_comparator);

You could actually define select_iterators in terms of other algorithms, using copy_if and boost::counting_iterator, but I don't think it's worth it when the direct implementation is so simple. It would look like:

template <typename ForwardIterator, typename OutputIterator, typename UnaryPredicate>
void select_iterators(ForwardIterator first, ForwardIterator last, 
                      OutputIterator out, UnaryPredicate pred) {
    std::copy_if(
        boost::make_counting_iterator(first), 
        boost::make_counting_iterator(last),
        out,
        [&](ForwardIterator it) { return pred(*it); }
    );
}

2) Instead of testing all the values up front and writing the results somewhere, define an iterator that advances over the original range each time it is incremented until it finds the next match. Boost provides two ways of doing this, boost::filter_iterator and boost::adaptors::filter. So you could write:

auto results = boost::adaptors::filter(myfoos, some_comparator);

Then whatever you want to do with your results, you can iterate from results.begin() to results.end() as if it were a container. It's not a container, it doesn't satisfy the whole container interface. It satisfies an interface defined by Boost, named Range, which amounts to "can be iterated over". It's actually just a filtered view of myfoos, so no Foo object is copied or even moved.

Answer 2

If you can modify your vector std::partition would be the choice. Here how you would call it:

std::vector<int>::iterator p =
    std::partition(v.begin(), v.end(), you_predicate);

You're answer lie between v.begin() and p.