# Algorithms in action – iota and shuffle

When I was working on my sorting code for this post, I wanted a vector of randomly ordered, unique integers for testing.

The code is straightforward:

```std::vector< int >
getRandomVector( int n )
{
std::vector< int > v_i( n );

std::iota( std::begin( v_i ), std::end( v_i ), 0 );

std::default_random_engine dre;
std::shuffle( std::begin( v_i ), std::end( v_i ), dre );

return v_i;
}
```

C++11 added std::iota – an algorithm that assigns incrementing values to a sequence. In my example the values are integers starting at zero.

I was confused when I first saw `iota`. Initially I thought someone had misspelt `itoa` (not a standard function but sometimes available as an extension), then I thought since `iota` is `atoi` backwards there must be a link between them.

I was wrong on all counts. std::iota represents the Greek letter iota ( Ι, &#x03B9 ) which (depending on your font and which case you are examining) looks similar to a lower case “L”, an upper case “i”, a one “1”, or a vertical bar “|”.

The Greek letter iota is used in the programming language APL to generate a sequence of consecutive integers. APL has a wild and wonderful character set described here. My favourite part of the Wikipedia article is the statement “Most APL symbols are present in Unicode”. In other words, some APL symbols are not present in Unicode (the article goes on to identify the missing symbols). I think this is wonderful. There are over 100,000 characters in Unicode and you still can’t use it to write APL (I realize that APL predates Unicode so was not trying to fit into its character set, and also that there are implementations of APL that do limit themselves to characters generally available on a modern computer). I thought digraphs and trigraphs were bad enough – C++ programmers have it easy compared to APL programmers.

std::iota uses prefix `operator ++` to generate successive values. I wish I had a good example other than integers to show. I don’t, but I’ll look out for one.

One final point, std::iota assumes that you have a sequence already created – it isn’t possible to use it with std::back_inserter (or any other inserter) to create the sequence. For my example it really doesn’t make any difference, but if there is a use case with a more complicated type, possibly one that doesn’t support a default constructor, it would be nice not to have to default construct the sequence first. Of course, if this ever becomes a real problem it is easy enough to write `iota_n`.

I am using std::shuffle (added in C++11) rather than std::random_shuffle (available since C++98) so that I can use the bright shiny new random number generators we get in C++11. (See Stephan T. Lavavej’s talk rand() Considered Harmful for more on why the new C++ random number generators are much better than `rand`).

For this example I haven’t bothered to seed the random number generator, and I am not that worried about perfect randomness anyway but I am trying to drag my programming style into the C++11 world. I suspect I will succeed at embracing C++11 at about the same time C++14 is unleashed.

While we are on the subject of randomness, here’s an interesting note from the C++11 standard. The description of the three shuffle algorithms includes this phrase:

Effects: Permutes the elements in the range `[first,last)` such that each possible permutation of those elements has equal probability of appearance.

Given a perfect random number generator the output from any of the shuffles should be perfectly uniform. Sounds reasonable enough, however there is at least one “obvious” shuffling algorithm that fails this test:

Iterate over the elements of the sequence and swap each element with a randomly chosen element (possibly itself).

Jeff Atwood goes into more details here, and also mentions a common algorithm which does produce uniform results, the Fisher–Yates shuffle, also known as the Knuth shuffle (both links take you to the same Wikipedia page).

Roughly speaking the Fisher–Yates shuffle is:

Pick an element randomly from the input sequence, add it to the result sequence and remove it from the input sequence. Repeat until the input sequence is empty.

It’s equivalent to picking a card at random from the deck, putting it into a separate “shuffled” pile and repeating until all the cards are in the “shuffled” pile.

Many years ago I looked at a couple of standard library implementations of shuffle algorithms and they were using the Fisher–Yates shuffle. I assumed this would still be true. Once again I was wrong. Both Visual Studio and GCC are using another shuffle algorithm which I haven’t been able to track down the name of (if anyone knows, please post a comment). As far as I can tell, the algorithms works something like this:

Assume you have a perfectly shuffled sequence of n elements. Add another element to the end of the sequence, then swap it with a randomly chosen element of the new (size n + 1) sequence (possibly itself).

I assume that this procedure produces another perfectly shuffled sequence (although I can’t prove it). Since we can start with a single element (perfectly shuffled) we can build up to any number of elements.

References for shuffling:

• The C++11 standard Section 25.3.12 Random shuffle
• Knuth: The Art of Computer Programming Volume 2, Seminumerical Algorithms 3rd edition Section 3.4.2 Random Sampling and Shuffling
• Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms 2nd edition Section 5.3 Randomized algorithms

# std::bind and lambda functions 6

This is the last post in this series, and I am going to use it to wrap up a few things that didn’t quite fit in anywhere else.

As I said at the start, this series is not the ultimate guide to std::bind and lambda, it has focused on a few things that I find interesting. As always, if you want definitive information look at these three references:

As you’d expect, Herb Sutter has written and spoken about lambdas many times.

## Passing values by reference

All of my examples have assumed that bound or captured arguments are captured by value. Take a look at this code:

```double add( int i, float f )
{
return i + f;
}

typedef std::function< double( int ) > SingleArgumentAdd;
```
```float f( 10.0f );

SingleArgumentAdd fn0( std::bind( add, _1, f ) );
SingleArgumentAdd fn1( [ f ]( int i )
{
return add( i, f );
} );

f = 20.0;

std::cout << fn0( 5 ) << ", ";
std::cout << fn1( 5 ) << "\n";
```

It writes out `15, 15` showing that the value of `f` that is used is the value when the function object is created.

We could pass in a pointer to `f` rather than `f` itself:

```double add1( int i, float* pF )
{
return i + *pF;
}
```
```float f( 10.0f );
float* pF( &f );

SingleArgumentAdd fn0( std::bind( add1, _1, pF ) );
SingleArgumentAdd fn1( [ pF ]( int i )
{
return add1( i, pF );
} );

f = 20.0;

std::cout << fn0( 5 ) << ", ";
std::cout << fn1( 5 ) << "\n";
```

This time we get `25, 25` - the pointer is not dereferenced until `fn0` and `fn1` are called.

What about passing `f` by reference? That should give us the same result as passing by pointer - the value of `f` is the value when the function is called. Here's the code:

```float f( 10.0f );

SingleArgumentAdd fn0( std::bind( add, _1, std::cref( f ) ) );
SingleArgumentAdd fn1( [ &f ]( int i )
{
return add( i, f );
} );

f = 20.0;

std::cout << fn0( 5 ) << ", ";
std::cout << fn1( 5 ) << "\n";
```

The code prints out `25, 25`, just as we'd expect. We had to do two things differently though:

1. We have to explicitly tell std::bind that `f` must be passed by reference (a const reference in this case). If we don't do this, std::bind will dereference `f` and use whatever value is in `f` when std::bind is called. std::cref is a function that returns an object that wraps the reference and makes sure that the reference is not dereferenced until `fn0` and `fn1` are called. See The C++ Programming Language, 4th Edition, section 33.5.1 for more information.
2. Lambdas are much simpler. We write `&f` in the capture block to indicate that `f` should be captured by reference.

Whether we are using pointers, references, lambdas or std::bind there is one thing we need to keep in mind - when we dereference the reference, the object it refers to must still exist.

## Nesting and chaining functions

When we have an object of type std::function it is a first class object in C++. We can copy it, pass it to functions, return it from functions, store it as a member variable and treat it like any other object.

This means that we can set up nested functions, we can chain functions together and we can use std::function objects for callbacks. As always, just because you can doesn't mean that you should. I am experimenting with chains of functions for my current project and, while I can make it work, it isn't pretty and it isn't clear what is going on.

## `operator ()` should be const for predicates

I am not going to go into this in detail because others have done a better job than I have. In general, when you write your own predicate function object, `operator ()` should be `const` - it cannot update any stored state in the function object. There are two reasons for this:

1. The standard does not place any restrictions on the number of times a predicate is copied (I think that std::for_each is the one exception). As Josuttis points out in The C++ Standard Library: A Tutorial and Reference (2nd Edition) section 10.1.4, a typical implementation of std::remove_if does copy the predicate and will give the wrong result if the predicate is storing state.
2. By default, there is no guarantee that the algorithm will traverse the list from the beginning to the end. As far as I can tell, these are the only algorithms which are guaranteed to traverse from beginning to end: std::for_each, std::copy, std::move, std::accumulate, std::inner_product, std::partial_sum and std::adjacent_difference. I found these by searching the standard for the phrases starting from first and proceeding to last, and in order.

By default, the function object constructed by a lambda expression has a `const` `operator ()`. If you really want it to be non-const you can declare the lambda `mutable`.

## Why do we need std::find_if and std::count_if?

There are algorithms which have an overloaded predicate and non-predicate version, for example, std::is_sorted :

```bool
is_sorted( ForwardIterator beg, ForwardIterator end );

bool
is_sorted( ForwardIterator beg, ForwardIterator end, BinaryPredicate op );
```

If we look at std::find we see why we can't overload it with a predicate and non-predicate version:

```InputIterator
find( InputIterator beg, InputIterator end, const T& value );
```

Despite the fact that we can supply template specializations that will match a function, we can't know whether we are supplying a function because we are searching for a function in a container of functions or whether we are supplying a function to act as a predicate. That means we have to have a separate std::find_if (and std::count_if) function.

## std::bind and member functions

In part 2 we looked at pointers to member functions, but I never demonstrated how these work with std::bind.

```class MemberFunctionDemo
{
public:
double add( int i, float f )
{
return i + f;
}

MemberFunctionDemo()
{
std::cout << std::bind(
&MemberFunctionDemo::add,
this,
_1,
20.0f )( 10 );
}
};
```

The first argument to std::bind is always the function that will be called. For member functions we have to use `&` to get a pointer to the function, and the function name must be fully qualified. The second argument is the object to call the function on - it can be a pointer or a reference to the object, in my example, I am using `this`.

## std::bind as a way of limiting scope

A colleague at Adobe pointed out that we can use a lambda to create a block of code that does not have access to all variables in the surrounding scope:

```int i, j, k;

// Some code here...

[ i, j ](){
// Only have access to i & j here.
// No access to k
}();
```

I am not sure whether this is a Good Thing, a Bad Thing or just a Thing.

# std::bind and lambda functions 5

Let’s start with a quick reminder of what a lambda expression looks like:

```std::vector< int > v_i( functionReturningVector() );
std::vector< double > v_d;

float f = functionReturningFloat();

std::transform(
std::begin( v_i ),
std::end( v_i ),
std::back_inserter( v_d ),
[ f ]( int i ){
return i + f;
} );
```

The lambda expression is this part:

```[ f ]( int i ){
return i + f;
}
```

The standard says “Lambda expressions provide a concise way to create simple function objects”. The lambda expression we have just seen corresponds to the `Adder` function object that we looked at earlier in this series:

```class Adder
{
public:
Adder( float f )
: f_( f )
{}

double operator()( int i ) const
{
return i + f_;
}

private:
float f_;
};
```

Repeating what I said in this post:

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 – {}

If we take our three options: a custom function object; std::bind wrapping a function and a lambda expression, we can find the commonality between them:

• `f` is the value passed in to the constructor of our function object.
• `f` is the value bound by std::bind.
• `f` is the value we place in the square brackets of the lambda (in standardese, the square brackets are called a lambda-capture, `f` is a capture-list with a single element).
• `i` is the value passed to the function call operator defined on the callable object. An object of type `Adder` is a callable object, the result of std::bind is a callable object and a lambda expression is a callable object.
• ` { return i + f; } ` is the code that we actually want to execute. For std::bind the code we want to execute has to be wrapped in a function, for a custom function object or a lambda we can just use the code directly.

If we want to, we can invoke the function call operator on a lambda directly:

```float f = functionReturningFloat();

double d = [ f ]( int i )
{
return i + f;
}( 7 );
```

(we probably don’t want to, although I am sure somebody has already come up with a use for this)

A lambda-expression is an expression, and expressions have a type. We tried to work out what the type of the result of std::bind was last time – let’s try the same exercise with a lambda expression.

Section 5.1.2 of the standard talks about the type of a lambda expression. The type is a unique, unnamed nonunion class type. The standard tells us plenty about the properties of the type without ever revealing what the type actually is. As with std::bind I can force a compiler error and see what type the compiler is using. For Visual Studio I get this:

```test_bl5_1::<lambda_d35a8a85fcf19231607c0773125e04ed>
```

For GCC I get this:

```test_bl5_1()::__lambda1
```

(The lambda in question is declared in function `test_bl5_1`)

As with the type of the return value of std::bind, we are clearly not meant to use these types deliberately – the standard is telling us so, they are different between different compilers, in the case of Visual Studio, the “type” isn’t really a type at all – it is some implementation magic, the GCC type starts with an underscore, and, in case I haven’t mentioned it enough, the standard tells us that we can’t use these types. Believe the standard – it’ll make life easier. This diversion into the actual types of std::bind and lambda has been exactly that – a diversion from our main purpose of actually using these things.

So we are in the same situation as we were with std::bind. We can’t use the type directly, we don’t know what it is. We do know what the properties of the type are – in particular we can apply `operator ()` to objects of that type.

We can use the type deduction facilities of C++11 to handle lambdas without needing to know their type. We have already used a lambda with a templated function (std::transform) and `auto` and `decltype` work exactly as we would expect:

```auto fn = [ f ]( int i ){ return i + f; };
typedef decltype( fn ) SingleArgumentAdd;
```

Last week we looked at std::function and saw that std::function can wrap a callable object. Since a lambda expression is a callable object, std::function can wrap a lambda expression:

```typedef std::function< double( int ) > SingleArgumentAdd;

SingleArgumentAdd fn;

fn = [ f ]( int i ){ return i + f; };

std::cout << fn( 42 ); // And of course we can call it
```

If we need to save callable objects, std::function is the way to go. std::function can be the type of a member variable, it can be passed to and returned from functions. std::function is our all purpose "thing that supports `operator ()`"

Finally, there is one thing that I have glossed over. When I was describing the commonality between std::bind, a function object and a lambda I looked at every variable and every type except one - the type of the result of invoking `operator ()`.

If we look at the lambda we've been working with, we can see that if we remove the capture block (the bit inside square brackets) we have something that is very close to being a function declaration:

```( int i )
{
return i + f;
};
```

It is missing the function name (which is what we'd expect - a lambda is an unnamed function), but it is also missing the return type. In this case, because the lambda consists of a single statement that is just a return we don't have to specify the return type, the compiler will deduce it for us - that gives us another place where the compiler does type deduction.

In our case, the result of `i + f` is a double - that is exactly what we want. But what if we did need a return type, either because the type of the expression was not what we wanted, or because we had more complicated code within the lambda?

Lambdas use the new trailing-return-type syntax so if we wanted to be explicit about the function call operator returning a `double` we would write this:

```[ f ]
( int i ) -> double
{
return i + f;
};
```

That's it for this post, and almost it for this series. I have one more post in mind which will tie up a few loose ends then I'll move on to something else.

# std::bind and lambda functions 4

I have been sloppy in my use of language. I am going to try to be less sloppy. Instead of using function or function object (and I suspect getting them reversed in some cases) I am going to start using the standard-approved term callable object. As always, the standard provides a strict definition, for us it will be good enough to say that a callable object allows us to apply `operator()` to it. Callable objects include functions, function objects, whatever it is we get back from std::bind, and lambda functions.

In part 3 I said I would reveal the return type of std::bind. If we look up the relevant section of the standard (20.8.9.1.2) we see the following declaration:

```template
unspecified bind(F&& f, BoundArgs&&... bound_args);
```

Unspecified. That doesn’t seem terribly helpful. Of course, this being the standard, there is a definition for unspecified. Section 1.3.25 of the standard states:

unspecified behavior behavior, for a well-formed program construct and correct data, that depends on the implementation [ Note: The implementation is not required to document which behavior occurs. The range of possible behaviors is usually delineated by this International Standard. —end note ]

Still not terribly helpful. Perhaps we can find a way to determine the type anyway. By setting up an error condition I can force the compiler to tell me what type it is actually using for the result of std::bind. Assuming that I am binding `add` in the same way I have been doing, on Visual Studio 2013 I get this for the type:

```std::_Bind<true,double,double (__cdecl *const ) (int,float),int,float &>
```

and on GCC I get this:

```std::_Bind_helper<false, double (&)(int, float), int, float&>::type
{aka std::_Bind<double (*(int, float))(int, float)>}
```

There are only three problems.

1. The types are different on the two different compilers (because they use different implementations of the standard library).
2. Both compilers use types beginning with an underscore – any name starting with an underscore is reserved for the implementation (see 17.6.4.3.2 in the standard).
3. The standard has already told us clearly and explicitly that the type is unspecified – it can vary between compilers, it can vary between releases of the same compiler, it can vary between updates to the standard library. We cannot rely on the type staying the same.

However much we twist and turn, determining the actual type of the returned value from std::bind is a non starter. Even when we can find out what the type is, we can’t rely on it.

Fortunately, C++11 gives us a way of avoiding knowing the actual type – we can do type deduction.

We can assign the result of std::bind to a variable using `auto`:

```auto fn = std::bind( add, _1, f );
```

That works for the situations where we can use `auto`, but doesn’t help us when we want to store the object in a (non-template) class or pass it to a (non-template) function – we can’t declare a parameter as `auto`.

We’ve already seen one of the other ways we can use type deduction with std::bind. We used std::bind successfully with std::transform, because std::transform is a template function and does type deduction. If we are passing the result to a template function or template class we might can use the result of std::bind without ever needing to know what type it is.

There is a third option. C++11 added `decltype`. You hand `decltype` an expression (which it does not evaluate, it just uses it to deduce the type), and it gives us the type of that expression. For example:

```auto fn = std::bind( add, _1, f );
typedef decltype( fn ) SingleArgumentAdd;
```

`decltype( fn )` evaluates to the type of `fn` (at compile time), and we typedef the result to `SingleArgumentAdd`. This is useful, finally we have an actual type (as in type of an object) that we can type (as in hit keys on the keyboard). It still isn’t perfect though. The example above only works within the current scope – we can’t put the typedef into a header file (at least not without doing other things in the header file that we really shouldn’t). Turns out there is a solution to this problem too. We can do this:

```typedef decltype(
std::bind(
add,
_1,
std::declval< float >() ) ) SingleArgumentAdd;
```

We have something new – std::declval. Let’s work out what’s going on here. `decltype` requires an expression. In our first example of its use we gave it the expression `fn`. In the second example we want to give it an expression involving std::bind. This means that we need to pass arguments of the right type to std::bind. The first argument is easy – it’s the callable object that we’re trying to wrap. The whole point of this exercise is to wrap that callable object so we need to have it visible. The second argument is also easy, it’s the placeholder `_1`. For the third argument we must pass it a float value (not the float type, but a value of type float). If we happened to have a float variable in the current scope we could use that. We could also pass it a float constant such as `1.0f`. The constant would work well here because it is a nice simple value, but what if it wasn’t a float? What if it was something which required several arguments to its constructor? We don’t want an actual value, just something that represents the value and has the correct type. For that, we can use std::declval. To quote Stroustrup:

The intent is to use `declval< X >` as a type where the type of a variable of type `X` is needed.

(The C++ Programming Language Fourth Edition, section 35.4.2)

std::declval does return a value, but we cannot use that value. Since `decltype` does not evaluate its expression we are safe.

Having jumped through all of those hoops to get the type `SingleArgumentAdd` it turns out to be a pain to use. When we looked at the definition of unspecified from the standard it stated:

The range of possible behaviors is usually delineated by this International Standard.

That range of possible behaviors for `SingleArgumentAdd` is pretty small. We already know that the result of std::bind can have `operator ()` applied to it, the standard adds requirements for MoveConstructable and CopyConstructable, but it adds no other requirements. In particular, default construction and assignment are not available:

```float f( functionReturningFloat() );
float f1( otherFunctionReturningFloat() );

SingleArgumentAdd fn; // Error, cannot default construct

SingleArgumentAdd fn2 = std::bind( add, _1, f );

fn2 = std::bind( add, _1, f1 ); // Error, cannot assign
```

Even if we could default construct and assign `SingleArgumentAdd` it would still be unsatisfactory. Our current definition of `SingleArgumentAdd` only lets us store the return value from std::bind. Wouldn’t it be nice to have a type that will allow us to store any callable object that has the correct call signature.

A call signature is the name of a return type followed by a parenthesized comma-separated list of zero or more argument types. – C++11 standard, section 20.8.1

The C++11 standard gives us exactly what we want – `std::function`. Let’s set up a function with the correct parameter and return types:

```double singleArgAdd( int i )
{
return i + 7;
}
```

Now let’s look at what we can do with `std::function`:

```typedef std::function< double( int ) > SingleArgumentAdd;

SingleArgumentAdd fn; // We can default construct it

fn = std::bind( add, _1, f );  // We can assign the result
// of std::bind to it

fn = singleArgAdd;  // We can assign a function
// of the correct signature to it

std::cout << fn( 42 ); // And of course we can call it
```

std::function wraps a callable object. When we call `operator ()` on a std::function object, it calls `operator ()` on the callable object it is wrapping, known as the target. std::function therefore needs to know what the return type and the parameter types are for `operator ()`. The syntax that we use for the call signature is very similar to the syntax for declaring a function pointer - `std::function< double( int ) >`

Finally, an uninitialized std::function object is known as empty (and is even displayed like that in the Visual Studio debugger). If we attempt to call an empty std::function, it will throw the exception std::bad_function_call. Fortunately, it is easy to test a std::function object to see if it is empty or not:

```SingleArgumentAdd fn2;

// Some code that might or might not assign something to fn2

if( fn2 )
{
fn2( 42 );
}
```

That's it for this week, next week we will finally get to lambda functions.

# std::bind and lambda functions 3

In part 2 we saw that by wrapping a function inside a function object we could take a function that requires two arguments and turn it into a function object that requires one argument. The code we ended up with looks like this:

```class Adder
{
public:
Adder( float f )
: f_( f )
{}

double operator()( int i ) const
{
return add( i, f_ );
}

private:
float f_;
};
```
```std::vector< int > v_i( functionReturningVector() );
std::vector< double > v_d;

float f = functionReturningFloat();

std::transform(
std::begin( v_i ),
std::end( v_i ),
std::back_inserter( v_d ),
Adder( f ) );
```

There is a problem here – we had to write a lot of boilerplate in order to wrap one function – `Adder` is 15 lines long, the call to `add` is a single line. Fortunately, C++11 gives us a couple of ways to get the same effect but with much less boilerplate. We can use std::bind to adapt `add` as follows:

```std::vector< int > v_i( functionReturningVector() );
std::vector< double > v_d;

float f = functionReturningFloat();

std::transform(
std::begin( v_i ),
std::end( v_i ),
std::back_inserter( v_d ),
std::bind( add, std::placeholders::_1, f ) );
```

[ Aside:

I have put in the fully scoped name of the placeholder `_1` just to show where it comes from. Even though I am normally a fan of using the fully qualified name this one is just so ugly I will assume that:

```using namespace std::placeholders;
```

is in use for the rest of my examples. This simplifies our loop to:

```std::transform(
std::begin( v_i ),
std::end( v_i ),
std::back_inserter( v_d ),
std::bind( add, _1, f ) );
```

End aside ]

We have two std::transform loops, one of which uses `Adder( f )`, the other of which uses `std::bind( add, _1, f )`.

We know what the code `Adder( f )` does. It creates a function object of type `Adder` which implements `operator ()` to call `add` with one argument that comes from the function call operator, and another argument that was supplied in the constructor. We need the code `std::bind( add, _1, f )` to do something very similar.

Let’s remove std::bind from the context of std::transform so we can focus on one thing at a time. Here’s some code we can use to look at std::bind in isolation:

```float f = functionReturningFloat();
auto fn = std::bind( add, _1, f );
std::cout << fn( 7 ) << "\n";
```

The call to std::bind returns a function object that we assign to the variable fn. I am using `auto` because I don't want to get into the question of what the type of the return value of std::bind is yet (we'll look at it later). `fn` is a function object that takes a single argument to its function call operator. We can therefore invoke the function call operator with a single argument - `fn( 7 )` and write out the result, which will be a `double` because the return value of `add` is a double.

There are a lot of moving parts here. I am going to walk through them.

We have three functions in play:

• `add` The function we ultimately want to call. The function we are going to wrap.
• `fn` The function (object) that wraps `add`. This is the thing that converts a two argument function into a single argument function.
• std::bind The function that creates `fn` from `add`.

We call std::bind to create `fn`. Later we call `fn` which in turn will call `add`.

The function we want to wrap - `add` - is a two argument function. Anything that calls `add` must call it with two arguments. Therefore, `fn` must call `add` with two arguments. Since std::bind is creating `fn`, std::bind must know what the two arguments are. When we call std::bind we not only supply it with the function to be wrapped - `add` - we also supply it with the two arguments that must be passed to `add`. These two arguments are `_1` and `f`.

The second argument is easy. `f` is a variable of type `float` and we already know that the second argument to `add` must be of type float. It all matches just as it should.

The first argument is more interesting - `_1`. Arguments of the form `_n` are called placeholders, that's why they live in the std::placeholders namespace. The placeholder argument links the argument we pass when we call `fn` to the first argument that gets passed to `add`. Let's look at the code again:

```auto fn = std::bind( add, _1, f );
std::cout << fn( 7 ) << "\n";
```

`_1` says "take the first argument that is passed to `fn` and pass it to `add` as the first argument". In this example, when we call `fn( 7 )`, that ultimately results in a call to `add( 7, f )`

Any argument that is passed to `fn` can be passed on to `add` in any position. The placeholder we use (`_1`, `_2` etc.) tells us which argument to use from the argument list passed to `fn::operator ()`. The position of the placeholder in the call to std::bind tells us which position that argument will end up in when we call `add`.

Let me lay out the code slightly differently:

```float f = 10.0f;
auto fn = std::bind(
add,        // `add` is the function we are wrapping
_1, f       // `add` has two arguments therefore
// we supply two arguments here.
);

// At this point, std::bind has been called but
// `add` and `fn` have not been called

std::cout << fn( 7 ) << "\n";   // Call `fn`, which in
// turn calls `add`.
```

Here's an example with a different placeholder:

```float f = 10.0f;
auto fn = std::bind( add, _2, f );
std::cout << "result = " << fn( 7, 12 ) << "\n";
```

We are now using placeholder `_2`. This means that we have to supply the call to `fn` with two arguments (and if we don't we get an unfriendly error message). The output of this piece of code is:

```result = 22
```

showing that the second argument from the call `fn` is the one that is used. Of course this is a nonsensical example because there is no point in passing two arguments to `fn` in the first place - the first argument is ignored so there was no point in supplying it.

There are plenty of other cute tricks we can play. Since an `int` is convertible to a `float` we can do this:

```auto fn = std::bind( add, _1, _2 );
std::cout << "result = " << fn( 7, 12 ) << "\n";
```
```result = 19
```

or this:

```auto fn = std::bind( add, _2, _1 );
std::cout << "result = " << fn( 7, 12 ) << "\n";
```
```result = 19
```

Since `add` is commutative the result is the same - I am just showing that we can change the order in which the arguments are supplied to std::bind (and therefore the order of the arguments supplied to `add`).

We can use a placeholder more than once:

```auto fn = std::bind( add, _1, _1 );
std::cout << "result = " << fn( 7 ) << "\n";
```
```result = 14
```

Or not use a placeholder at all (yes, doing this in real life is a waste of time, I just want to show all the possibilities):

```auto fn = std::bind( add, 6, 5 );
std::cout << "result = " << fn() << "\n";
```
```result = 11
```

I can call the object returned from std::bind directly:

```float f = 10.0f;
double d = std::bind( add, _1, f )( 10 );
std::cout << "result = " << d << "\n";
```
```result = 20
```

For a not-pointless example, back in this post I used placeholders to swap the order of arguments to a comparator in order to reverse the sorting order:

```std::partial_sort(
ReverseIter( pivotElementIterator ),
ReverseIter( displayBegin ),
ReverseIter( std::begin( files ) ),
std::bind( comparator, _2, _1 ) );
```

## Errors

There are a number of things we can do wrong.

We can specify too many arguments in the std::bind call. `add` takes two arguments, let's try giving it three:

```double d = std::bind( add, _1, f0, f1 )( 10 );
```

Visual Studio gives the surprisingly helpful error message:

```// error C2197: 'double (__cdecl *)(int,float)' : too many arguments for call
```

The message from GCC is longer and more confusing, but does include the words "too many arguments to function".

We can specify too few arguments in the std::bind call:

```double d = std::bind( add, _1 )( 10 );
```

I get the following (also very helpful) error message from Visual Studio:

```error C2198: 'double (__cdecl *)(int,float)' : too few arguments for call
```

As before, the GCC message is more verbose, but does include the words "too few arguments to function".

We can specify too few arguments in the call to `fn`:

```auto fn = std::bind( add, _1, f );
std::cout << "result = " << fn() << "\n";
```

Sadly the resulting error message is almost incomprehensible.

Specifying too many arguments in our call to `fn` does not result in an error:

```auto fn = std::bind( add, _1, f );
std::cout << "result = " << fn(
7, 15.6,
std::complex< double >( 1.0, 2.0 ) ) << "\n";
```

As always, just because you can do something doesn't mean that you should do it.

We can give an argument of the wrong type to std::bind:

```std::complex< double > c( 1.0, 2.0 );
auto fn = std::bind( add, _1, c );
fn( 7.0 );   // Error reported here
```
```error C2664: 'double (int,float)' : cannot convert argument 2 from 'std::complex' to 'float'
```

Interestingly, the error is not reported until we try and call `fn`.

We can give an argument of the wrong type when we call `fn`:

```std::complex< double > c( 1.0, 2.0 );
auto fn = std::bind( add, _1, f );
fn( c );
```
```error C2664: 'double (int,float)' : cannot convert argument 1 from 'std::complex' to 'int'
```

Finally, let's get back to our std::transform call:

```std::transform(
std::begin( v_i ),
std::end( v_i ),
std::back_inserter( v_d ),
std::bind( add, _1, f ) );
```

std::transform is a function. When we call a function, we evaluate all of the arguments to that function. One of those arguments is the result of a call to std::bind. As we have seen, the result of calling std::bind is a function object that wraps `add` and turns it into a single argument function. Look at the definition of std::transform (this is from the GCC implementation. I have removed some error checking and done some reformatting):

```template<
typename _InputIterator,
typename _OutputIterator,
typename _UnaryOperation >
_OutputIterator
transform(
_InputIterator __first,
_InputIterator __last,
_OutputIterator __result,
_UnaryOperation __unary_op)
{
for (; __first != __last; ++__first, ++__result)
*__result = __unary_op(*__first);

return __result;
}
```

std::transform loops from `__first` to `__last`, and each time around the loop invokes the function call operator on `__unary_op` with a single argument - `__unary_op(*__first)`. We must supply std::transform with a thing-that-supports-the-function-call-operator-taking-a-single-argument. That is exactly what we have done using std::bind.

More to come in part 4, including the mysterious type of the return value of std::bind.

# What header?

I am bad at remembering what header file I need to include to use which standard library facility. I can handle the obvious ones like `vector`, but that still leaves many where I have to go and look it up. To make looking it up a little easier, I have created a page that lists all of the symbols in the standard library sorted by various criteria – including what header file they are in. There is a C++98 version and a C++11 version. I am sure there are mistakes in the pages, I will correct any mistakes I am told about.

# std::bind and lambda functions 2

In part 1 we looked at various things we can do with functions in C. Since C++ is mostly a superset of C we can do those things in C++ as well. C++ also gives us some other ways of creating functions though. Let’s dispense with the easy options quickly then get on to the more interesting possibilities.

## A function in a namespace

```namespace arithmetic
{
double add( int i, float f )
{
return i + f;
}
}
```
```double (*pFn)( int, float ) = arithmetic::add;
```

## A static function in a class

```class TestClass
{
public:
static double add( int i, float f )
{
return i + f;
}

};
```
```double (*pFn)( int, float ) = TestClass::add;
```

Nothing tricky about putting functions into a namespace, or a class acting as a namespace.

## Overloaded functions

```double add( int i, float f )
{
return i + f;
}

double add( int i, double f )
{
return i + f;
}
```
```double (*pFn)( int, float ) = add;
```

Even overloaded functions work just as we’d expect. Section 13.4 of the C++11 standard states:

The function selected is the one whose type is identical to the function type of the target type required in the context.

Let’s not get too confident though, overloads are going to return to trouble us later.

## Pointer to member function

```class TestClass2
{
public:
double add( int i, float f )
{
return i + f;
}

};
```

Ignore the fact that `add` makes absolutely no sense as a member function (very few of these examples make any sense outside of a narrow context).

What is the type of a pointer to member function? We already know what the type of add would be if it wasn’t a member function:

```double (*)( int, float );
```

The key thing missing is the name of the class of which the function was a member. The type has to specify the class for type safety – you don’t want anyone trying to call the add function for an object that doesn’t even have an add function (and yes, you can force this with casting, but you can force almost anything with casting). Given that `*` is in the place where the function name used to go, we put the class name in the obvious (ish) place:

```double (TestClass2::*)( int, float );
```

We can write this code to get the address of the add function:

```double (TestClass2::*pFn)( int, float ) = &TestClass2::add;
```

And we can call it like this:

```TestClass2 c;
(c.*pFn)( 10, 20.0f );
TestClass2* p = &c;
(p->*pFn)( 10, 20.0f );
```

We have two new operators `.*` and `->*`.

Notice that this time we had to use the address-of operator `&` to get the address of the function and, because the function call operator `()` is higher precedence than `.*` and `->*`, we need the brackets around `c.*pFn` and `p->*pFn`.

(This also works with virtual functions).

There is one more trick we need to know about before we can start applying our knowledge to std::bind and lambda. At the beginning of part 1 I wrote:

The round brackets are known as the function call operator.

At the time, referring to the function call operator might have seemed like overkill. It’s a C function, you just call the thing by passing in the arguments in the brackets. That nomenclature is important though because C++ supplies us with a function call operator that we can use as a member function of a class:

```class Adder
{
public:
double operator()( int i, float f ) const
{
return add( i, f );
}

};
```

(There is a reason why I am calling the `add` function rather than just doing the addition correctly – that reason will become apparent later).

We call the member function `operator()` by applying the function call operator to an object of type `Adder` :

```Adder a;
a( 10, 20.0f );
```

While describing a function in part 1 I said:

we take a thing with a name … and apply an operator – `()` – to it.

Well, that’s what we have here. We have a thing with a name (`a`) and we’re applying the function call operator (`()`) to it. That calls the member function `operator()`.

We have a thing that is acting like a function but is actually an object. It is often known as a function object or functor. At first glance a function object seems like a rather heavyweight way of creating a function, but objects have a really useful property – they can store state.

Let’s look at what we can do with that property of storing state. We don’t have to pass in both arguments to `operator()`, we can have one of the arguments specified at construction time:

```class Adder
{
public:
Adder( float f )
: f_( f )
{}

double operator()( int i ) const
{
return add( i, f_ );
}

private:
float f_;
};
```
```Adder a( 20.0f );
a( 10 );
```

Again, this just looks like a heavyweight way of creating a function-like thing. It’s more work, it’s not as convenient to call – why should we bother? We bother because we have taken a function that takes two arguments to the function call operator – `add` – and turned it into a function (object) that takes a single argument to the function call operator. The second argument is supplied in the constructor. This is the C++ version of currying.

The one-argument version is useful because there are algorithms that expect a function that takes a single argument, for example the single source sequence version of std::transform :

```std::vector< int > v_i( functionReturningVector() );
std::vector< double > v_d;

float f = functionReturningFloat();
Adder a( f );
std::transform(
std::begin( v_i ),
std::end( v_i ),
std::back_inserter( v_d ),
a );
```

We don’t even need to create a named `Adder` object, we can just use a temporary:

```std::transform(
std::begin( v_i ),
std::end( v_i ),
std::back_inserter( v_d ),
Adder( f ) );
```

The call to std::transform is equivalent to doing this:

```for(
std::vector< int >::iterator i( std::begin( v_i ) );
i != std::end( v_i );
++i )
{
v_d.push_back( add( *i, f ) );
}
```

And this is why the fact that we took a two argument function and turned it into a single argument function is important. std::transform requires a single argument function. By wrapping `add` in a function object and specifying the second argument in the constructor we ended up with a single argument function (a unary operation in standardese).

If we take a look at the declaration of std::transform in the standard (again, just the single-source-sequence one), we see this:

```template<
class InputIterator,
class OutputIterator,
class UnaryOperation >
OutputIterator
transform(
InputIterator first,
InputIterator last,
OutputIterator result,
UnaryOperation op);
```

The final parameter of the function std::transform is a unary operation – it takes one argument. Internally, std::transform is going to use the function call operator on `op`, i.e. it is going to perform `op( elem )` for each element in the input sequence. It is all templated, and `op` follows the normal rules when passing an object to a templated parameter – whatever functions are called on `op` must be supported by the type of `op` type. Since the function that std::transform calls is `operator()` with a single argument, the type of `op` must support that. We know of two “things” in C++ world that can support the function call operator – functions and function objects.

What I have been trying to say in multiple different ways is that by wrapping a function (in this case `add`) in a function object we can turn a function into something requiring fewer arguments at the point where the function call operator is invoked. Of course the extra arguments have to come from somewhere, and in this case they are specified in the constructor of the function object. We can give the standard algorithm exactly what it needs (an `operator()` with the right number and type of parameters) but supply any necessary extra paraeters via the constructor of the function object.

Here’s another example. Let’s take the file metadata structure I used in a previous post:

```struct FileMetaData
{
std::string fileName_;
std::string directory_;

std::size_t size_;
std::time_t lastWriteTime_;
};
```

Assume we have an unsorted vector of file metadata objects and we want to search for a file with a given file name. std::find_if looks like the obvious choice since it lets us specify our own predicate for the search.

It seems like this function would be useful:

```bool compareFileName(
FileMetaData const& metaData,
std::string const& fileName )
{
return metaData.fileName_ == fileName;
}
```

`compareFileName` will be useful, but it is a two argument function and std::find_if takes a `UnaryPredicate`. Unary means it expects a single argument, and according to Merriam-Webster a predicate is:

something that is affirmed or denied of the subject in a proposition in logic

For our purposes that comes down to “something returning a bool”. `compareFileName` is a predicate (it will affirm or deny whether the file names match), but it is not unary.

We’re going to use our “wrap it in a function object” trick to turn `compareFileName` into a single argument function (object):

```class CompareFileName
{
public:
CompareFileName( std::string const& fileName )
: fileName_( fileName )
{
}

bool operator()( FileMetaData const& metaData ) const
{
return compareFileName( metaData, fileName_ );
}

private:
std::string fileName_;
};
```

Then we can use `CompareFileName` like this:

```std::vector< FileMetaData > files( getFiles() );
std::string fileNameToFind( getFileName() );

std::vector< FileMetaData >::iterator i(
std::find_if(
std::begin( files ),
std::end( files ),
CompareFileName( fileNameToFind ) ) );
```

There is one more thing. When we looked at overloaded functions before we had no problem assigning them to a function pointer. If we try and use overloaded functions in an algorithm we run into trouble.

Here is a pair of overloaded functions:

```double negate( int i )
{
return -i;
}

double negate( float f )
{
return -f;
}
```

And here is a way in which we might want to use the integer version:

```std::vector< int > v_i( functionReturningVector() );
std::vector< double > v_d;

std::transform(
std::begin( v_i ),
std::end( v_i ),
std::back_inserter( v_d ),
negate );
```

Just using the name of the function directly doesn’t work, we get this error message from Visual Studio:

```error C2914: 'std::transform' : cannot deduce template argument as function argument is ambiguous
```

How come it worked before but doesn’t work now? The reason it worked before was because of this clause in the standard:

The function selected is the one whose type is identical to the function type of the target type required in the context.

The important words are target type. When we are supplying an argument to a template function we don’t know what the target type is. We can’t have a target type until we know the function type, but in order to pick the right function (and hence find out its type) we need to know the target type.

There are at least three ways around this. One is to assign the function to a function pointer where we know the target type and therefore won’t get an error:

```double (*pNegateFn)( int ) = negate;

std::transform(
std::begin( v_i ),
std::end( v_i ),
std::back_inserter( v_d ),
pNegateFn );
```

Secondly, we can use what is possibly the most legitimate cast ever:

```std::transform(
std::begin( v_i ),
std::end( v_i ),
std::back_inserter( v_d ),
static_cast< double (*)( int ) >( negate ) );
```

And finally we can specify the template arguments to std::transform explicitly. We don’t normally do this with functions, but in this case it gives us the target type that the compiler is looking for:

```std::transform<
std::vector< int >::const_iterator,
std::back_insert_iterator< std::vector< double > >,
double (*)( int ) >(
std::begin( v_i ),
std::end( v_i ),
std::back_inserter( v_d ),
negate );
```

Note that I had to specify the type of std::back_inserter for this to compile. When you are specifying template arguments explicitly you need to get them right.

In practice I rarely run into problems with overloaded functions, when I do, I use `static_cast` to get around them.

We’ve reached the end of part 2 and still haven’t talked about std::bind or lambda. At least we’re looking at the right language now, and we have laid all of the groundwork for the next exciting episode where I promise we will get to std::bind (and maybe lambda).

# std::bind and lambda functions 1

In the “no raw loops” series I have been glossing over the details of std::bind and lambda. I want to dive a little more deeply into some of those details.

I am not going to explore all of the details, as with everything I post I am going to focus on the parts that are interesting and useful to me. If you are looking for definitive descriptions of what is going on, I highly recommend these three references:

The standard looks intimidating, it is written in a very precise subset of English, but with a little practice at reading “standardese” it is very approachable, well written and useful. It is worth taking the time to get used to it.

Let’s go back to basics. If you understand C function pointers skip this installment, the C++ stuff won’t arrive until later.

Let’s go back to C and a simple function in C:

```double add( int i, float f )
{
return i + f;
}
```

What can we do with this function? The first obvious thing we can do is to call it:

```int i = 7;
float f = 10.5f;
double d = add( i, f );
printf( "%f\n", d );
```

How do we call it? We follow the name of the function with round brackets `()` and put the list of arguments to the function inside the round brackets. The result of the expression `add( i, f )` is the return value and type of the function.

The round brackets are known as the function call operator. Notice that word operator, it’s a word that comes up a lot in C and C++. In general you have something being operated upon (maybe several somethings) and an operator that defines what is happening. For example:

```int i = 7;
++i;
```

We take a thing with a name – `i` – of type `int` and apply an operator – `++` – to it.

In the case of our function we take a thing with a name – `add` – of type unknown (at least at the moment it’s unknown, we’ll get to it soon) and apply an operator – `()` – to it.

There is definitely some common ground between an int and our function. Is there more common ground? C provides us with something else we can do with functions. We can create a function pointer and point it at a function. The syntax is wacky (but if we had a problem with wacky syntax we shouldn’t be programming in C or C++):

```double (*pFn)( int, float ) = &add;
```

To obtain the type of the function pointer we take the function prototype and remove the function name `double ( int, float )`, then we add `(*)` where the function name used to be to indicate that this is a pointer to a function `double (*)( int, float )`. That gives us the type of the function. In order to get a variable of that type we put in the name of the variable next to the `(*)``double (*pFn)( int, float )`.

So we have `pFn` – a pointer to a function. We can dereference the pointer and apply the function call operator to it:

```int i = 7;
float f = 10.5f;
double d = (*pFn)( i, f );
printf( "%f\n", d );
```

Given that it’s a pointer we should be able to change the function that it is pointing at. Here’s an unrealistic but illustrative example:

```double mul( int i, float f )
{
return i * f;
}

enum Operator
{
OPERATOR_ADD,
OPERATOR_MUL
};

double callOperator( enum Operator op, int i, float f )
{
double (*pFn)( int, float );
if( op == OPERATOR_ADD )
{
pFn = &add;
}
else
{
pFn = &mul;
}

return (*pFn)( i, f );
}
```

Since `pFn` is a pointer, we might wonder what happens if we set it to NULL, then try to call it:

```pFn = NULL;
d = (*pFn)( i, f );
```

As you might expect, calling a NULL function pointer falls squarely in the “don’t do that” category. In fact, it’s like attempting to dereference any other NULL pointer. On Visual Studio we get this:

`Unhandled exception at 0x0000000000000000 in Blog.exe: 0xC0000005: Access violation executing location 0x0000000000000000.`

On cygwin we get this:

`Segmentation fault (core dumped)`

We can make life simpler for ourselves in a couple of ways. The C standard allows us to omit the `&` (address of) operator when we assign a function to a pointer so instead of:

```pFn = &add;
```

We can write:

```pFn = add;
```

In a similar vein, we can omit the `*` (indirection) operator. Instead of:

```d = (*pFn)( i, f );
```

We can write:

```d = pFn( i, f );
```

Finally, we can use `typedef` to keep the wacky function pointer type syntax in one place:

```typedef double (*FunctionPtr)( int, float );
FunctionPtr pFn = add;
```

We can now store a pointer to a function in a variable. That means we can save that function and use it later. We can pass the pointer to a function into another function, and return it from a function. Orginally the only thing we could do with our function was to call it (apply the function call operator to it), now we can pass it around in the same way as we pass ints around. This gets us into the world of “first class citizens” or “first class functions”.

There doesn’t appear to be a precise definition for a first class function, but it is safe to assume that if a function can only be called it is not a first class function, the function must be able to be stored and passed around to have any hope of being a first class function. There are a couple of Wikipedia articles with useful information:

That’s it for part #1. We haven’t mentioned std::bind and lambdas yet, in fact we haven’t even made it into the right language. Stay tuned for part #2 where we move on to C++.

# Algorithms in action – sorting

I like to have a personal project that I use to explore different programming ideas – my current personal project is an editor. A couple of features I am adding require the use of a list – for example, the editor is working on a certain set of files and I want to be able to see the files, perhaps sorted by file name: Perhaps sorted by directory: This is completely typical list control behaviour – click on a column header to sort on that column and scroll through the list to see every element in its correct place. Of course I want this to be highly responsive, and I also want to be able to have many millions of elements in the list – I probably won’t ever have a project with a million files in it but I might well have a million symbols.

I am using a virtual list control – the list control itself does not have most of the data for the list. It knows how many elements are in the list and which block of elements it is displaying, then it calls back into my code to get the text for the elements it is displaying. The list control does not have to deal with millions of elements, it just has to deal with the elements it is currently displaying.

For my definition of “responsive” I am going to use Jakob Nielsen’s values from his article Response Times: The 3 Important Limits:

< 0.1 second for that instantaneous feeling
< 1 second to avoid interrupting the user’s flow of thought
< 10 seconds to avoid losing the user’s attention altogether.

## Useful definitions

For this example we have a very simple struct containing file metadata, and a comparator class that gives us an ordering of FileMetaData objects. I have left out the details of the comparator class, but we can tell it to compare on filename, directory, size or last write time.

```struct FileMetaData
{
std::string fileName_;
std::string directory_;

std::size_t size_;
std::time_t lastWriteTime_;
};

class Comparator
{
public:
bool operator()(
FileMetaData const& a,
FileMetaData const& b )
}
```

There are also a few typedefs that will come in useful:

```typedef std::vector< FileMetaData > FMDVector;
typedef FMDVector::iterator         Iter;
typedef FMDVector::reverse_iterator ReverseIter;
typedef FMDVector::size_type        UInt;
```

The problem

When we click on a column header the list should be resorted on the data in that column. We should be able to scroll through the list and see every list element in the correct place.

Solution #0

Since we need to sort the elements in the list why not just use std::sort? The code is simple and obvious:

```void
sortAllElements(
Comparator const& comparator,
FMDVector& files )
{
std::sort(
std::begin( files ),
std::end( files ),
comparator );
}
```

(I know that the sort barely deserves to be inside its own function but it’ll make it consistent with our more complicated sorting later).

Whenever we click on a column header we update the comparator and call `sortAllElements`. The code is simple and it works.

The catch comes when we look at performance. Here are the times to sort different numbers of elements:

# elements sort all
1,000 0.000s
10,000 0.000s
100,000 0.187s
1,000,000 2.480s
10,000,000 33.134s

The timings look great up to 10,000, even sorting 100,000 elements is acceptable. Once we get into the millions though the numbers get much worse. We really don’t want to be waiting around for 2 seconds, let alone 30+ seconds.

The C++ standard tells us that std::sort has a complexity of O( n * log n ). As we have just seen, we get good results with small numbers of elements, but much worse results as n gets larger.

So the straightforward sort works well for smaller numbers of elements, but we are going to need something smarter for millions of elements. There are several possibilities:

1. Offload some of the work onto separate threads – even if we didn’t speed up the overall sort time we would at least avoid locking up the main UI thread.
2. Use previous knowledge of the ordering to avoid having to do a complete re-sort.
3. Keep multiple copies of the list, each sorted by a different column so that the right one can be instantly swapped in.

For the purposes of this blog post I am going to avoid #1 because threading opens up its own can of worms. I will declare that #2 is invalid because we don’t have any previous knowledge (or at least we have to have a solution that works responsively even if we don’t have any previous knowledge of the ordering). I am not going to consider #3 because I don’t want to make that particular speed / space tradeoff.

Instead I am going to take my cue from the virtual list control. It only needs to know about the elements it is displaying – those are the only elements that need to be in sorted order.

The problem has now moved from “sort the entire list” to “sort that portion of the list that is displayed”. If we can always guarantee that the portion of the list that is displayed is sorted correctly, the user will never know the difference. This has the potential to be much quicker – the number of displayed elements is relatively small. I can get around 70 lines on my monitor, let’s round that up to 100 – we need to get the 100 displayed elements correctly sorted and in their right place.

Solution #1

We’ll start with a straightforward case, the 100 elements we want to display are right at the beginning of the list (quite possibly the case when the list is first displayed). The standard library supplies us with many more sorting related algorithms than std::sort, and for this case it gives us std::partial_sort. As the name suggests, it partially sorts the list – we tell it how much of the beginning of the list we want it to sort:

```void
sortInitialElements(
UInt k,
Comparator const& comparator,
FMDVector& files )
{
std::partial_sort(
std::begin( files ),
std::begin( files ) + k,
std::end( files ),
comparator );
}
```

(There is no error handling in the function itself – I am assuming that the caller has ensured the values being passed in are within range.)

We have an additional parameter – `k`, the number of elements we want sorted correctly. We use `k` to create an iterator that we pass to std::partial_sort.

According to the standard, std::partial_sort has a complexity of O( n * log k ). Since k is likely to be much smaller than n (we’re assuming that k is 100) we should get better performance:

# elements sort all sort initial
1,000 0.000s 0.000s
10,000 0.000s 0.000s
100,000 0.187s 0.000s
1,000,000 2.480s 0.047s
10,000,000 33.134s 0.406s

This is looking much better. We are still in the instantaneous category at one million elements and even though 10 million is pushing us to around half a second it is still a vast improvement over sorting the entire list.

Moving on, it’s all very well being able to sort the beginning of the list correctly but we also want to be able to scroll through the list. We want to be able to display any arbitrary range of the list correctly.

Solution #2

Once again, the standard provides us with a useful algorithm. The function std::nth_element lets us put the nth element of a list into its correct place, and also partitions the list so that all of the elements before the nth element come before that element in sort order, and all of the elements after come after the nth element in sort order.

So, we can use std::nth_element to get the element at the beginning of the range into the correct place, then all we have to do is sort the k elements afterwards to get our range sorted. The code looks like this:

```void
sortElementsInRange(
UInt firstElementIndex,
UInt k,
Comparator const& comparator,
FMDVector& files )
{
std::nth_element(
std::begin( files ),
std::begin( files ) + firstElementIndex,
std::end( files ),
comparator );

std::partial_sort(
std::begin( files ) + firstElementIndex,
std::begin( files ) + firstElementIndex + k,
std::end( files ),
comparator );
}
```

and the performance data:

# elements sort all sort initial sort range
1,000 0.000s 0.000s 0.000s
10,000 0.000s 0.000s 0.016s
100,000 0.187s 0.000s 0.016s
1,000,000 2.480s 0.047s 0.203s
10,000,000 33.134s 0.406s 2.340s

A million elements pushes us outside the “instantaneous” limit, but still acceptable. Unfortunately, 10 million elements isn’t great.

There is one more feature of sorting lists that I love. I use it in my email all the time. By default, my email is sorted by date – I want to see the most recent emails first. Sometimes though I’ll be looking at an email and want to see other emails from that sender. When that happens, I can click on the “sender” column header and have the email I currently have selected stay in the same place while the rest of the list sorts itself around the selected email. The selected element acts like a pivot and the rest of the lists moves around the pivot.

Mouse over this image to see an example of this sort on our list of files: Solution #3

WARNING – the code I am about to present does not work under all circumstances. I want to focus on the sorting algorithms so for the time being I am not going to clutter the code up with all of the checks needed to make it general. DO NOT USE THIS CODE. I will write a follow up blog post presenting a correct version of this function with all of the checks in place.

Sorting around a pivot element is a more complicated function than the others so I’ll walk through it step by step.

```void
sortAroundPivotElementBasic(
UInt nDisplayedElements,
UInt topElementIndex,
UInt pivotElementIndex,
Comparator const& comparator,
UInt& newTopElementIndex,
UInt& newPivotElementIndex,
FMDVector& files )
```
• `nDisplayedElements` The number of elements displayed on screen.
• `topElementIndex` The index of the top displayed element of the list.
• `pivotElementIndex` The index of the pivot element.
• `comparator` Same as the other sort functions – the object that lets us order the list.
• `newTopElementIndex` An output parameter – the index of the top element after sorting.
• `newPivotElementIndex` The index of the pivot element after sorting.
• `files` The list of files we are sorting.

Our first job is to find out the new position of the pivot element. Previously we had used std::nth_element to partition the range, this time, since we actually know the value of the element, we’ll use std::partition:

```FileMetaData const pivotElement(
files[ pivotElementIndex ] );

Iter pivotElementIterator(
std::partition(
std::begin( files ),
std::end( files ),
std::bind( comparator, _1, pivotElement ) ) );
```

Notice that although we are using the same comparator we have used for all of our sort operations we are binding the pivot element to the comparator’s second argument. std::partition expects a unary predicate – it moves all elements for which the predicate returns true to the front, and all elements for which the predicate returns false to the back. It then returns an iterator corresponding to the point between the two partitions. By binding our pivot element to the second parameter of comparator we get a unary predicate that returns true if an element is less than the pivot element and false otherwise.

We know where the pivot element ends up in the list, and we also know where it ends up on the display – we want it to stay in the same position on the display. This means we can work out the range of elements that are displayed.

```UInt const pivotOffset(
pivotElementIndex - topElementIndex );

Iter displayBegin( pivotElementIterator - pivotOffset );
Iter displayEnd( displayBegin + nDisplayedElements );
```

Now we can fill in two of our return values.

```newTopElementIndex = displayBegin - std::begin( files );
newPivotElementIndex =
pivotElementIterator - std::begin( files );
```

To recap, we have two iterators that tell us the range of elements that are displayed – `displayBegin` and `displayEnd`. We have a third iterator that tells us where the pivot element has ended up – `pivotElementIterator`. We also know that the elements have been partitioned – we have two partitions, each with all the right elements, but in the wrong order. The boundary between those two partitions is the location of the pivot element.

We’ve used std::partial_sort a couple of times already, we can use it again to sort the bottom section of the display:

```std::partial_sort(
pivotElementIterator,
displayEnd,
std::end( files ),
comparator );
```

Of course we also want to sort the top section of the display. All we need is a version of std::partial_sort that will sort the end of a list, not the beginning. The standard library doesn’t supply us with that algorithm, but it does give us a way of reversing the list. If we reverse the list above the pivot element we can use std::partition. We do this using reverse iterators:

```std::partial_sort(
ReverseIter( pivotElementIterator ),
ReverseIter( displayBegin ),
ReverseIter( std::begin( files ) ),
std::bind( comparator, _2, _1 ) );
```

Reverse iterators are easily constructed from the forward iterators that we already have, and they plug right into algorithms just like regular iterators do. The beginning of our reversed list is at the pivot element, the end is at `std::begin( files )` and the element we are sorting to is the top of the display. Notice that we had to reverse our comparator as well (and notice that reversing the comparator does not involve applying `operator !` to its output, we actually need to reverse the order of the arguments).

Here’s the function in one block:

```void
sortAroundPivotElementBasic(
UInt nDisplayedElements,
UInt topElementIndex,
UInt pivotElementIndex,
Comparator const& comparator,
UInt& newTopElementIndex,
UInt& newPivotElementIndex,
FMDVector& files )
{
FileMetaData const pivotElement(
files[ pivotElementIndex ] );

Iter pivotElementIterator(
std::partition(
std::begin( files ),
std::end( files ),
std::bind( comparator, _1, pivotElement ) ) );

UInt const pivotOffset(
pivotElementIndex - topElementIndex );

Iter displayBegin( pivotElementIterator - pivotOffset );
Iter displayEnd( displayBegin + nDisplayedElements );

newTopElementIndex = displayBegin - std::begin( files );
newPivotElementIndex =
pivotElementIterator - std::begin( files );

std::partial_sort(
pivotElementIterator,
displayEnd,
std::end( files ),
comparator );

std::partial_sort(
ReverseIter( pivotElementIterator ),
ReverseIter( displayBegin ),
ReverseIter( std::begin( files ) ),
std::bind( comparator, _2, _1 ) );
}
```

And the performance?

# elements sort all sort initial sort range sort around pivot
1,000 0.000s 0.000s 0.000s 0.000s
10,000 0.000s 0.000s 0.016s 0.000s
100,000 0.187s 0.000s 0.016s 0.016s
1,000,000 2.480s 0.047s 0.203s 0.094s
10,000,000 33.134s 0.406s 2.340s 1.061s

Pretty darn good, in fact better than sorting a given range. Again, once we get up to ten million elements we lose responsiveness, I think the lesson here is that once we get over one million elements we need to find some other techniques.

I want to repeat my warning from above. The code I have just presented for the pivot sort fails in some cases (and fails in an “illegal memory access” way, not just a “gives the wrong answer” way). I will write a follow up post that fixes these problems.

## Wrap up

We have seen that with a little work, and some standard library algorithms, we can do distinctly better than sorting the entire list, we can increase the number of elements by 2 orders of magnitude and still get reasonable performance. Extremely large numbers of elements still give us problems though.

Is this the best we can do? It’s the best I’ve been able to come up with – if you have something better please post it in the comments, or send me a link to where you describe it.

One last thought. Earlier on I dismissed option #2 – “Use previous knowledge of the ordering to avoid having to do a complete re-sort.” by saying that I wanted algorithms that would work without prior knowledge. We now have those algorithms, and once we have applied any of them we will have some knowledge of the ordering. For example, once we have sorted a given range we can divide the data set into 3 – the first block of data has all the right elements, just in the wrong order, the second block has all of the right elements in the right order and the third block has all of the right elements in the wrong order. We can use this information as we’re scrolling through the list to make updates quicker.

# 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.