Transform each element of a container by passing it through a function and putting the result into another container

So far we’ve only looked at one algorithm – std::for_each. That’s allowed me to lay the groundwork for using lambdas and std::bind, but there are many more algorithms avilable in the standard library. In fact, in this thread , John Potter refers to std::for_each as “the goto of algorithms” (and that is far from the worst thing he says about std::for_each).

You can use std::for_each to simulate pretty much every algorithm, but as usual, just because you can do something doesn’t mean that you should. There are more specific algorithms we can use to express our intent directly, and being able to express our intent directly when we’re writing code is a Good Thing.

In this installment we move on from just calling a function with each element, now we’re going to call a function, get a result back from that function, then store that result.

Our declarations have a new function – f_int_T – a function that takes an object of type T and returns an integer.

class T
{
   ...
};

std::vector< T > v_T;
std::vector< int > v_int;

int f_int_T( T const& t );

Here’s the old way of solving our problem:

Solution #0

std::vector< T >::iterator i;
std::vector< int >::iterator j;

for( 
    i = std::begin( v_T ), 
    j = std::begin( v_int );
    i != std::end( v_T ); 
    ++i, ++j )
{
    *j = f_int_T( *i );
}

I am assuming that our output container v_int has sufficient size for each element being assigned to it. It is easy to change this code to call push_back on the output container if necessary.

We now have two iterators – one for the source range and one for the output. We call the function f_int_T for each element of the source and we write the result of the function to the output. We don’t need to explicitly use the end of the output range – std::end( v_int ) doesn’t appear anywhere in the example.

We can implement the same algorithm using range-based for:

Solution #1

std::vector< int >::iterator j( std::begin( v_int ) );
for( T const& t : v_T )
{
    *j++ = f_int_T( t );
}

Using range-based for works, but we have to increment the output iterator j inside the body of the loop. This example would be simpler if push_back was appropriate.

So let’s introduce std::transform and see what we get:

Solution #2

std::transform( 
    std::begin( v_T ), 
    std::end( v_T ), 
    std::begin( v_int ), 
    []( T const& t ) 
    {
        return f_int_T( t );
    } );

The lambda function is overkill, but I wanted to reinforce the fact that lambdas are functions, which means they can have a return value. In this case because the lambda consists of a single return statement the compiler will automatically deduce the type of the return value (there is a way of explicitly specifying the type of the return value but I am not going into that here).

Here’s something interesting. The blocks of code in solutions #0 and #1 look like this:

{
    *j = f_int_T( *i );
}

{
    *j++ = f_int_T( t );
}

There’s an assignment in both of them and they both dereference the output iterator. The range-based for version has to increment the output iterator itself. Contrast that with the block of code in the solution #2, the lambda function:

{
    return f_int_T( t );
}

The code inside the lambda is doing nothing other than calling f_int_T and returning the result. All of the iteration, the dereferencing, the assignment is being handled by the std::transform algorithm.

As I said, the lambda is overkill, we can just use the function directly as an argument:

Solution #3

std::transform( 
    std::begin( v_T ), 
    std::end( v_T ), 
    std::begin( v_int ), 
    f_int_T );

This solution makes the intent of the code clear. We have the algorithm completely separated from the action to take each time through the loop. When I look at this code and see std::transform I know how the iteration will work. I know that the number of elements placed into the output will be the same as the number of elements in the source range. I know that no elements in the source range will be skipped. Short of exceptions I know that there will be no early exit from the loop. (Many of these arguments can be applied to std::transform with a lambda function, but I think the intent is even more pronounced here).

The function that does the transformation is entirely separate and can be tested in isolation (this is the advantage of the named function over a lambda). We have separated things that used to be commingled.

We can simplify things even more using adobe::transform:

Solution #4

adobe::transform( 
    v_T, 
    std::begin( v_int ), 
    f_int_T );

Solution #4 strips things down to their basics – we have our source, the place where the output will go and what we’re going to do to each element. There is almost no boilerplate.

Incidentally, the output range can be the same as the source range. If the function changes the value but not the type of its argument (or the return type of the function can be converted to the argument type), we can run std::transform to change every element of a container in place.

I have chosen a simple example to illustrate the use of std::transform. The function we are calling is a non-member function and has a single parameter of the correct type. Refer to part 2 and part 3 of this series for more information about using std::bind to call more complex functions.

Variation #1

My examples all assumed that we had enough space in the output container, but what if we don’t? Perhaps we are trying to build the output container from scratch or append elements to an existing container. We don’t want to have to resize the container first and incur the cost of constructing default constructed objects that are going to get overwritten. We won’t be able to resize it at all if the type we are constructing doesn’t have a default constructor, or if we don’t know how many elements we are going to put into it (e.g. we are using input iterators). What if we want to use push_back on every new element?

Solutions #0 and #1 are easy. Because they handle the dereferencing and assignment within their loop body it is easy to change them to use push_back. E.g.:

Solution #0.1

std::vector< T >::iterator i;

for( 
    i = std::begin( v_T );
    i != std::end( v_T ); 
    ++i )
{
    v_int.push_back( f_int_T( *i ) );
}

In fact this is simpler than our original solution #0 since we don’t need an iterator for the output at all.

If we want the effect of push_back when we use std::transform (or any other algorithm that writes to iterators) we use an insert iterator. An insert iterator looks like an iterator (i.e. it has the operations we would expect from an iterator – although many of them have no effect for an insert iterator) but when we assign to it, it will call a function on the container – in our case we want it to call push_back.

It’s easier to show than talk about (see Josuttis “The C++ Standard Library” 2nd edition for a proper description):

adobe::transform(
    v_T,
    std::back_inserter( v_int ),
    f_int_T );

The iterator created by std::back_inserter will call push_back every time it is assigned to. The standard library also contains std::front_inserter which will call push_front, and std::inserter which calls insert.

One drawback of push_back is that it might cause the output container’s memory to be reallocated and all of the container’s contents copied over – in fact depending on the reallocation strategy it might have to reallocate several times as elements are appended. Assuming that we know the ultimate size of the output container we can call reserve which will set aside the appropriate amount of memory but without default constructing any additional elements. This lets us use push_back and know that there will only be a single memory reallocation.

Variation #2

What if we don’t necessarily want to process every element? What if we want something like this:

std::vector< T >::iterator i;
std::vector< int >::iterator j;

for( 
    i = std::begin( v_T ), 
    j = std::begin( v_int );
    i != std::end( v_T ); 
    ++i, ++j )
{
    if( somePredicate( *i ) )
    {
        *j = f_int_T( *i );
    }
}

Some of the algorithms have “if” versions – we pass in a predicate and their action is only taken if that predicate returns true. Among others, std::copy, std::remove and std::count all have “if” variants that take predicates. There isn’t a transform_if provided in the standard, but it isn’t difficult to write one:

template<
    class InputIterator,
    class OutputIterator,
    class UnaryOperation,
    class UnaryPredicate >
OutputIterator transform_if(
    InputIterator first,
    InputIterator last,
    OutputIterator result,
    UnaryOperation op,
    UnaryPredicate test)
{
    while( first != last )
    {
        if( test( *first ) )
        {
            *result++ = op( *first );
        }
        ++first;
    }
    return result;
}

[ Edit: Guvante points out in the comments here that my implementation of transform_if does not match the for_each version. ]

To my mind, this is the real beauty of the STL – as well as providing a large set of containers and algorithms, it is extensible. The framework it provides makes it possible to add new algorithms or containers which interact seamlessly with existing parts of the STL. transform_if is a new algorithm, but because it follows existing practice it doesn’t take a lot of additional work to understand it.

Loop over all the elements in a container and call a member function (with arguments) on each element

I want to introduce one more std::bind trick. In part 1 and part 2 the functions called were non-member functions and we were passing each element of the container into the function as an argument. In this installment we are going to call a member function on each element in the container. We’ll extend our set of declarations to include a member function on class T:

class T
{
public:
   void mf_int( int ) const;
   ...
};

std::vector< T > v_T;

We have a vector full of objects of type T, we want to call the member function mf_int on each object in that vector, and we have to pass an integer argument to mf_int (I am skipping the example where we don’t have to pass any additional arguments to the function).

Let’s start off with the “old style” solution:

Solution #0

int j( 7 );
for( std::vector< T >::iterator i( std::begin( v_T ) ); 
    i != std::end( v_T ); 
    ++i )
{
    i->mf_int( j );
}

The range-based for version of the solution is as expected:

Solution #1

for( T const& t : v_T )
{
    t.mf_int( j );
}

The lambda function version also holds no surprises:

Solution #2

std::for_each( 
    std::begin( v_T ), 
    std::end( v_T ), 
    [ j ]( T const& t )
{
    t.mf_int( j );
} );

The std::bind version looks a little different though:

Solution #3

using namespace std::placeholders;
std::for_each( 
    std::begin( v_T ), 
    std::end( v_T ), 
    std::bind( &T::mf_int, _1, j ) );

The std::bind statement includes something new. &T::mf_int refers to a member function of class T – the function T::mf_int. When std::bind sees a member function (as opposed to a regular function) as its first argument, it expects the second argument to be the object on which to call the member function. In this case since the second argument is _1, it will call the member function T::mf_int on every element of the container. There is an additional argument to std::bind (j) which will be passed as a parameter to T::mf_int.

Having said above that I was skipping the example where we don’t have to pass any additional arguments to the function I want to mention that example briefly in connection with std::mem_fn, another function adapter (std::bind is a function adapter).

std::mem_fn provides a shorter way to specify that you want to call a member function with no arguments. Let’s add a new declaration to class T:

class T
{
public:
   void mf_int( int ) const;
   void mf_void() const;
   ...
};

When we use std::mem_fn we don’t need to specify the placeholder _1:

std::for_each( 
    std::begin( v_T ), 
    std::end( v_T ), 
    std::mem_fn( &T::mf_void ) );

std::mem_fn only works for member functions taking no arguments.

We can also use adobe::for_each:

Solution #4

adobe::for_each( v_T, std::bind( &T::mf_int, _1, j ) );

Wrap up

When we’re using std::bind we always specify the function we are going to call as the first argument. If the function we are going to call is a member function we specify the object on which we are going to call the member function second. Any additional parameters follow.

Loop over all the elements in a container and call a function with each element and additional values as arguments

In part 1 of this series we looked at the simplest case we could, a case that is tailor-made for std::for_each – calling a function with each element of a container as an argument. That particular case is easy, but it obviously doesn’t cover everything so we’ll move on to a (slightly) more complex example.

Our previous problem statement was: “loop over all the elements in a container and call a function with each element as an argument”: We’ll extend the problem so that now the function doesn’t just take a single argument of the same type as the element, it takes an additional argument.

As before we have a few declarations:

class T
{
   ...
};

void f_T_int( T const& t, int i )

std::vector< T > v_T;

Notice that f_T_int takes an object of type T and an int.

First of all, our raw loop version of the solution.

Solution #0

int j( functionReturningInt() );

for( std::vector< T >::iterator i( std::begin( v_T ) ); 
    i != std::end( v_T ); 
    ++i )
{
    f_T_int( *i, j );
}

Solution #0 has the same set of pros and cons as solution #0 did in part 1.

As before, there is a range-based for solution:

Solution #1

for( T const& t : v_T )
{
    f_T_int( t, j );
}

Again, similar pros and cons to the range-based for in part 1.

How about using for_each? In part 1 , turning the explicit loop into an application of std::for_each was easy. std::for_each expects to be given a function (and I’ll include “function object” in the definition of function) that takes a single argument. In part 1 that was exactly the function we wished to call. Now, however, we want to call a function that takes an additional parameter – as well as taking an object of type T it takes an integer.

Back in the bad old days before C++11 we would set up a function object like this:

Solution #2

class C_T_int
{
public:
    C_T_int( int j ) : j_( j )
    {
    }

    void operator ()( T const& t )
    {
        f_T_int( t, j_ );
    }
private:
    int j_;
};

std::for_each( 
    std::begin( v_T ), 
    std::end( v_T ), 
    C_T_int( j ) );

The function object C_T_int takes our additional argument (the integer) in its constructor, then defines operator () to accept the argument from our container. When operator () is called it has both arguments that it needs to be able to call f_T_int.

The function object allows us to use std::for_each, and the line of code that calls std::for_each is very straightforward, however solution #1 has a massive “con”: the overhead is horrible, there is lots of boilerplate.

If only we had some way of generating the function object without having to write all of the boilerplate. The C++11 standard provides us with exactly that: lamda functions. As the standard says “Lambda expressions provide a concise way to create simple function objects”. Using lambdas leads to:

Solution #3

std::for_each( 
    std::begin( v_T ), 
    std::end( v_T ), 
    [ j ]( T const& t ) 
{ 
    f_T_int( t, j ); 
} );

(This is a minimal introduction to lambda functions, there is much more to them than I am going to cover. Herb Sutter’s talk Lambdas, Lambdas Everywhere has much more information.)

The lambda function consists of three parts, contained in three different types of brackets. It starts with square brackets – [] – moves on to round brackets – () – then finishes off with curly brackets – {}.

The three parts correspond to the three essential features of the function object we created for solution #2:

1. The value(s) passed into the constructor of the function object appear in the square brackets – []
2. The value(s) passed into operator () appear in the round brackets – ()
3. The code in operator () appears in the curly brackets – {}

Notice the unusual looking piece of syntax at the end:

} );

That occurs because the lambda is being passed as an argument to std::for_each.

This first four solutions have one thing in common, they each contain a block of code looking something like this:

{
    f_T_int( t, j );
}

The difference is in the surrounding boilerplate. Assuming that we ignore solution #2, the hand-coded function object (which is sufficiently horrible that I feel justified in dismissing it), all of these solutions keep the code to be executed each time during the loop in the same place as the loop – they keep everything together (although if you take that to the extreme then we end up with one enormous “main” function – it’s another entry in both the “pros”” and “cons” column). The range-based for and std::for_each solutions separate out the loop from what happens each time around the loop. Looking at the code and seeing a range-based for or std::for_each tells us that exceptions and early returns aside, we will iterate over every member of the given range.

The block of code can easily be extended to do something else. As before, this falls into both “pros” and “cons”.

C++11 gives us another option, a way of taking a function with N arguments and turning it into a function with M arguments (where M < N). For those of you who think that this sounds like currying, you’re right – it’s like currying.

Solution #4

using namespace std::placeholders;
std::for_each( 
    std::begin( v_T ), 
    std::end( v_T ), 
    std::bind( f_T_int, _1, j ) );

std::bind started life as boost::bind and was adopted into the C++11 standard. In solution #4 it takes three arguments:

1. f_T_int – The function we ultimately want to call.
2. _1 – The first argument to be passed to f_T_int. _1 is a special value, a placeholder. std::bind is going to produce a function object – in this case a function object that takes a single argument. That single argument (the first argument) will be passed on to f_T_int in the position that _1 is in.
3. j – The second argument to be passed to f_T_int. In this case it’s the value of the variable j.

In this example, std::bind took a function that takes two parameters – f_T_int and turned it into a function object that takes a single parameter by binding one of the arguments to j. This single parameter function is exactly what we want for std::for_each.

(As with the lambdas, I am skipping over many, many details about std::bind.)

(Aside – I am not normally a fan of using statements, and in particular I won’t use them much in this series because I want to be very clear about where everything is coming from, however if I were to keep this rule up I would have to write std::placeholders::_1 and std::placeholders::_2 and that is too ugly even for me.)

We can also use adobe::for_each with lambda or std::bind:

Solution #5

adobe::for_each( v_T, [ j ]( T const& t ) 
{ 
    f_T_int( t, j ); 
} );

Solution #6

adobe::for_each( v_T, std::bind( f_T_int, _1, j ) );

So we have our original raw loop solution (#0) and 6 other possibilities:

0. The raw loop – we are trying to get away from this.
1. Range based for loop
2. Old style C++ function object
3. std::for_each with a lambda
4. std::for_each with std::bind
5. adobe::for_each with a lambda
6. adobe::for_each with std::bind

#0 is the version we are trying to get away from, #2 has so much boilerplate that I am prepared to drop it without further consideration. std::for_each and adobe::for_each are variations on a theme, and the choice between them will depend on (a) whether you are prepared to include the Adobe Source Libraries in your project and (b) whether you want to operate over the entire container. That leaves three solutions:

1. Range based for loop
3. std::for_each with a lambda
4. std::for_each with std::bind

Range-based for and lambda both have a block of code that (more or less) matches the block of code in the original raw solution:

{
    f_T_int( t, j );
}

Range-based for lambda differ in the boilerplate surrounding this block of code, although there are still similarities (for example, they both have T const& t declarations).

The main difference is that the range-based for models one type of loop – std::for_each (yes, you can achieve the same effect as other algorithms but it takes additional code). For solving this particular problem that isn’t an issue, that is exactly the type of loop we want. Later in this series we’ll be looking at other algorithms.

The fact that range-based for and lambda both have a block of code means that they can both put extra things into that block of code. In fact, they could put the definition of f_T_int right into the loop block itself. std::bind doesn’t let us do that – once we have bound a particular function the only thing that can be done each time around the loop is to call that function. Let’s look at the pros and cons of the code block vs. std::bind:

Code block pros:

• Keeps the code together – the loop code and the action to take on each iteration is in the same place.
• Makes it easy to change the operation that is taking place on each iteration of the loop.
• Easy to step through in a debugger
• Clear error messages (at least as clear as C++ error messages ever are)
• “Normal” syntax – basically the same syntax as if we were calling the function once.

Code block cons:

• Keeps the code together – the loop code and the action to take on each iteration is in the same place.
• Too easy to change. Making something easy to change makes it more likely to be changed. Keeping code working as it is maintained is a problem.
• Difficult to test the body of the loop separately from the loop itself.

std::bind pros:

• Forces you to split the code into separate functions and manage complexity. The loop is separate from the action taken on each iteration.
• Easy to test the body of the loop separately from the loop itself.

std::bind cons:

• Forces you to split the code into separate functions.
• Tricky to step through in the debugger.
• Error messages are verbose and almost incomprehensible.

Wrap up

I like std::bind. I think that currying is an elegant solution to many problems, and I like the fact that std::bind forces me to split the looping construct from the action taken on each iteration. I have to come up with a good function name which means I have to think through the problem fully and clearly. Naming is difficult but the payoff of having a well named function is worth it. I like the fact that I can test the function executed for each element independently of the loop.

Sadly (for me anyway), I think I am in a minority of one here. Bjarne Stroustrup writes about bind:

These binders … were heavily used in the past, but most uses seem to be more easily expressed using lambdas.

The C++ Programming Language – Fourth Edition, page 967.

I think that the title of Herb Sutter’s talk Lambdas, Lambdas Everywhere is intended as an expression of optimism rather than as a dire warning.

My biggest concern with lambdas is that they’re going to be used in the same way that function bodies are now – to contain vast amounts of deeply nested code.

I took the title of this series “No raw loops” from a talk by Sean Parent at Going Native 2013. In that same talk (starting at around 29:10) he makes suggestions about when and how to use range-based for loops and lambda functions. The summary is, “keep the body short”, he suggests limiting the body to the composition of two functions with an operator. If I was confident that lambda and range-based for bodies were never going to exceed this level of complexity I would be more positive about them. For myself, having some limits on what I can do often leads to a better organized, more thought through design.