C++ "select" algorithm

Question

Among the functionalities found in std::algorithm I can't seem to find one of the most basic I can think of: selected a subset of a collection (for example, return all the odd numbers, all the employees that have status == 'employed', all items that cost less that 20 dollars).

So, given a list of ints like

vector<int> ints {1, 9, 3, 27, 5, 19, 3, 8, 2, 12};

vector<int> evens = ?
vector<int> greaterThan7 = ?

How to find those that are even and those that are greater than 7?

Answer 1

If you want something more functional, you can check out the boost range library. Specifically, filtered:

for (int i : ints | filtered([](int i){return i > 7;}))
{
    ...
}

This gives you a lazy view, without constructing a new container.

---

You can get the same from Eric Niebler's range-v3:

for (int i : view::filter(ints, [](int i){return i > 7;})
{
    ...
}

with the benefit that you can just assign that to a vector too (so you can choose if it's lazy or eager, which Boost.Ranges does not allow).

std::vector<int> greaterThan7 = view::filter(ints, [](int i){return i > 7;});
std::vector<int> sameThing    = ints | view::filter([](int i){return i > 7;});

Answer 2

For example

vector<int> ints {1, 9, 3, 27, 5, 19, 3, 8, 2, 12};
vector<int> evens;

std::copy_if( ints.begin(), ints.end(), std::back_inserter( evens ),
              []( int x ) { return x % 2 == 0; } );

Here is a demonstrative program

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

int main()
{
    std::vector<int> ints { 1, 9, 3, 27, 5, 19, 3, 8, 2, 12 };
    std::vector<int> evens;

    std::copy_if( ints.begin(), ints.end(), std::back_inserter( evens ),
                  []( int x ) { return x % 2 == 0; } );

    for ( int x : evens ) std::cout << x << ' ';
    std::cout << std::endl;
}        

Its output is

8 2 12

Answer 3

Depending on what your exact requirements are, consider std::stable_partition (or std::partition). It reorders elements in the range such that all which satisfy a predicate come first. You can think of it as splitting the range into a "subset" and a "not subset" part. Here is an example:

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

int main()
{
    using std::begin;
    using std::end;
    using std::cbegin;
    using std::cend;

    std::vector<int> ints { 1, 9, 3, 27, 5, 19, 3, 8, 2, 12 };

    auto const greater_than_7 = [](int number) { return number > 7; };

    auto const iter_first_not_greater_than_7 = std::stable_partition(begin(ints), end(ints), greater_than_7);

    for (auto const_iter = cbegin(ints); const_iter != iter_first_not_greater_than_7; ++const_iter)
    {
        std::cout << *const_iter << "\n";
    }
}

If, however, you are fine with copying each matching element to a new collection, for example because the source range must not be modified, then use std::copy_if.

---

Perhaps what you are really looking for is a view of an unmodifiable range. In this case, you are approaching the problem from the wrong direction. You don't need a particular algorithm; a more natural solution to the problem would be a filtering iterator, like for example Boost's Filter Iterator. You can use the one in Boost or study its implementation to learn how you could write filtering iterators yourself.