# Implementing filter and map with C++11

## Tags: programming, howtos

« Previous post: A git hook to keep your emotions in … — Next post: Fun with unsequenced operations »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.