C++ collect algorithm?

Question

Every now and then I need to iterate over a subset of the elements of a container or just want to extract them and neglect the rest. I end up using boost::range::adaptors::filtered to create this lazy collections.

for(auto&& i : container | filtered(predicate)) {
  // .. do stuff
}

Is there a reason for the lack of a collect algorithm (as in Ruby's collect) in the STL (we only have copy_if which is not the same)? Or any reason against using it?

A possible implementation could be:

template<class Container, class Predicate>
Container collect(Container&& c, Predicate&& p) {
  Container n;
  for(auto&& i : c) {
    if(p(i)) {
      n.push_back(i);
    }
  }
  return n;
}

but a lazy_collect might also be useful to avoid copying.

All answers below are great. I wish I could mark all of them. I didn't knew about std::back_inserter. Collecting stuff is now as easy as:

boost::copy( orig | filtered(predicate), std::back_inserter(collection));

Answer 1

Standard algorithms don't operate directly on containers (creating or destroying them, or changing their sizes). They operate on iterator ranges, and the only changes the algorithm make are via assignment through iterators.

So, your proposed operation is entirely outside the scope of the standard algorithms. Maybe there "should" be a large extra set of generic container-operations in the standard, including this one, but the "STL philosophy" is to operate on iterators.

The non-lazy operation you propose can be done using std::back_inserter and std::copy_if (optionally using move iterators) or move_if (if you roll that yourself). std::copy_if was missing from C++03, but that was an accidental oversight.

The lazy version can't be done just by plugging together standard components -- there's no clean way to chain the "output" of one algorithm straight into the "input" of another algorithm without intermediate storage. That's why Boost provides such an interesting variety of iterators, as well as Ranges.

I don't know why they weren't incorporated into C++11, but one thing to note about C++11 was that it was rather late. Proposals were dropped for lack of time, so the reason might be as simple as "it was never considered important enough to propose, given the known existing workload".

Regarding your particular implementation, not all containers have push_back, and so you probably shouldn't use Container as the template parameter name. PushBackSequence would be more descriptive of the requirements.

Answer 2

How about this:

#include <algorithm>
#include <iterator>

std::copy_if(container.begin(), container.end(), std::back_inserter(result), []{...})

Where container is the container you want to collect from, and result is the container which will store the collection.

Answer 3

From the comments:

When using copy_if you need to know before hand how much space you will need

That's not true. You can use std::copy_if with a back inserter:

#include <algorithm> // For std::copy_if
#include <iterator> // For std::back_inserter
#include <vector>
#include <iostream>

int main()
{
    std::vector<int> v(10);
    std::iota(begin(v), end(v), 0); // Fills the vector with 0..9

    std::vector<int> out;
    std::copy_if(begin(v), end(v), back_inserter(out), [] (int x) 
    //                             ^^^^^^^^^^^^^^^^^^
    {
        return x > 4; 
    });

    for (auto x : out) { std::cout << x << " "; }
}

Here is a live example.

And if you want a function that works directly on a container rather than on a range defined by a pair of iterators, you could write the following helper:

template<typename C1, typename C2, typename P>
void cont_copy_if(C1&& src, C2&& dst, P&& p)
{
    std::copy_if(
        begin(std::forward<C1>(src)),
        end(std::forward<C1>(src)),
        back_inserter(std::forward<C2>(dst)),
        std::forward<P>(p)
        );
}

Which you would just use this way:

int main()
{
    std::vector<int> v(10);
    std::iota(begin(v), end(v), 0);

    std::list<int> out;
//  ^^^^^^^^^
//  You could use a different destination container

    cont_copy_if(v, out, [] (int x) { return x > 4; });
//  ^^^^^^^^^^^^

    for (auto x : out) { std::cout << x << " "; }
}

And of course the live example.