Implementing filter and map with C++11

Tags: programming, howtos

I am a fan of “higher-order functions” such as filter and map. To me, they are much more elegant and concise than the corresponding constructions with for-loops and the like. Of course, I wanted to use them in my daily C++ grind as well. Until recently, this turned out to be rather clunky—C++98 and C++03 did not include std::copy_if, which can be used to implement filter. Furthermore, std::transform, which is the equivalent of apply or map, takes an output iterator as an additional argument. This does not yield concise code.

Luckily, with C++11 the situation became better. First, let’s implement filter:

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

template <
  class InputIterator,
  class Functor>
std::vector<typename std::iterator_traits<InputIterator>::value_type>
filter( InputIterator begin, InputIterator end, Functor f )
{
  using ValueType = typename std::iterator_traits<InputIterator>::value_type;

  std::vector<ValueType> result;
  result.reserve( std::distance( begin, end ) );

  std::copy_if( begin, end,
                std::back_inserter( result ),
                f );

  return result;
}

This snippet permits us to take any range, apply a functor to it, and get a vector in return that only contains those elements for which the functor returned true. I realize that this is not as flexible as the STL output iterator concept, but be honest—when was the last time you actually wanted anything other than a vector to store stuff? Just as ed is the standard text editor, vector is the standard container in my opinion.

We can use the new implementation in the following manner:

std::vector<unsigned> a = { 2,3,4,5,6 };
auto b = filter( a.begin(), a.end(),
                 [] ( unsigned i ) { return i % 2 == 0; } );

That is pretty concise in my opinion.

Let’s implement map next:

#include <algorithm>
#include <iterator>
#include <type_traits>
#include <vector>

template <
  class InputIterator,
  class Functor>
auto map( InputIterator begin, InputIterator end, Functor f )
  -> std::vector<typename std::result_of< Functor( typename std::iterator_traits<InputIterator>::value_type ) >::type>
{
  using FunctorValueType = typename std::result_of< Functor( typename std::iterator_traits<InputIterator>::value_type ) >::type;

  std::vector<FunctorValueType> functorValues;
  functorValues.reserve( unsigned( std::distance( begin, end ) ) );

  std::transform( begin, end,
                  std::back_inserter( functorValues ), f );

  return functorValues;
}

That contains two awesome C++11 features: Trailing return types and std::result_of. We need this because the value type of the returned vector depends on the result of applying the functor to one of the values in the range! To be honest, the trailing return type is not really necessary, but I always wanted to use it somewhere. Again, I think that this implementation results in quite concise code:

std::vector<unsigned> a = { 2,3,4,5,6 };
auto b = map( a.begin(), a.end(),
              [] ( unsigned i ) { return i * 2; } );

The holy grail would of course be the possibility to return the same type of container that is used as the input, but the iterators do not permit this—for very good reasons. In any case, I am now happily using these constructions in my code and hope that you will, too.