# Quote of the week – correctness

Correctness is clearly the prime quality. If a system does not do what it is supposed to do, then everything else about it matters little.

Bertrand Meyer

# No raw loops 4 – std::transform

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.

# Quote of the week – wisdom

The road to wisdom?
Well its plain and simple to express:
Err and err and err again,
but less and less and less.

Piet Hein

Piet Hein predicted the iterative model of development found in agile programming techniques, as well as inventing the board game hex.

# No raw loops 3 – member functions

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.

# Quote of the week – guidelines

Good programmers use their brains, but good guidelines save us having to think out every case.

Francis Glassborow

I have spent way too many hours in arguments over coding guidelines – where do we put the braces, are we using underscores or camel case? I have come to the conclusion that within reasonable boundaries I don’t care, but I really like the guidelines to be consistently applied. I don’t want to spend any time thinking about how we differentiate member variables, or what the convention for naming include guards is. There are much more interesting problems in the world.

# Pros and cons

The pros and cons technique is a way of comparing proposed solutions to a problem. It forces you to think through the implications of each solution and increases your understanding of the solution. (Incidentally, I am sure that this technique has a much better name than “pros and cons”, and that someone else has written about it in greater depth – if anyone knows of any good references please post them in the comments).

The technique consists of two steps:

1. For each proposed solution make a list of all advantages and disadvantages, however (apparently) trivial.
2. Weight the advantages and disadvantages and use that information to inform your decision.

Step #1 involves intellectual honesty. Even if you have a preference for a given solution you should consider yourself honour-bound to come up with all the reasons to oppose your preferred solution (consider it similar to preparing for a debate – you should be able to argue your opponents case as well as you can argue your own).

Typical things that might appear on the pros and cons lists for a proposed solution include:

• How easy is it to convert from the problem statement to the code?
• How easy is it to covert from the code to the problem statement?
• How easy is it to modify the code in the future?
• Does it keep the code together?
• Does it split things into separate functions?
• How easy is it to debug?
• How comprehensible are the error messages?
• How close is it to the standard language or common idioms?
• Does it use compiler specific extensions?
• Does it add extra levels of nesting?
• How much typing / boilerplate does it involve?
• Does it pollute the global namespace?
• Does it use deprecated features?
• Is it consistent with existing code?

There are many more, some of which inevitably will be project specific.

Several of these items can appear both in the pros and the cons lists – those are often the interesting items that show up particularly important areas that need to be carefully explored. Often some of the entries on the list contradict each other – that’s an opportunity to look for the balance between opposing forces.

Sometimes coming up with an absolute pro or con (or an absolute weighting) is difficult. In that case it is useful to compare solutions against each other and see how much better or worse one of them is in a particular area.

Step #2 does not involve assigning numerical weights, adding them all up and picking “the winner” (at least it never has in my experience). Notice that it states “use that information to inform your decision”. This isn’t a short cut or a mechanical process, it’s a way of learning more about the problems and potential solutions.

In practice I have found that step #2 ends up identifying the key factors that matter to your company, project or team. Those factors are often different between different projects, and can vary over time on the same project. For example, I was on a project at Adobe that supplied libraries to After Effects and Photoshop. “Don’t pollute the global namespace” was a hard and fast rule. There were a couple of times when we had to break that rule – we had a very small number of macros in public header files. With the macros we used a poor man’s namespacing and put the name of the project at the beginning of each macro name. On other projects we controlled everything in the project so we didn’t worry about polluting the global namespace (although in a couple of cases we should really have done some namespacing to help with the internal organization).

Even if the right solution is relatively clear I think it is still important to know what the disadvantages of that solution are. If you don’t know what the drawbacks are you won’t be able to mitigate them (as with the macro name’s “poor man’s namespacing” I mentioned above) and if you don’t know the drawbacks you don’t have a full understanding of the solution.

Years ago I read an interview with a woman who was the secretary for the original UNIX team (I do not have a cite for this – if anyone has any details please let me know). One of her tasks was taking notes during design meetings. The interviewer asked her a very perceptive question – “what was the most useful information you recorded during those meetings?”. Her equally perceptive answer – “the reasons why we didn’t do something”. Let’s face it, if there is any documentation at all about the design process it will focus on the solutions that were used, not the ones that were discarded, yet I have been in many meetings where we tried to remember why a particular solution wasn’t chosen. It might have been dismissed for the right reasons, or the wrong reasons, or the right reasons at the time but the situation has changed so that those reasons no longer apply. Pros and cons gives a format where at least some of those reasons can be recorded – even if it is just via an email discussion or  in the comments of a task or bug tracker.

# No raw loops 2 – arguments

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:

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