In this talk, Alex Stepanov states “Science is about classification”.

This series is going to look at different ways we can classify the standard algorithms. Classification involves finding patterns, and with any luck the patterns will reveal things that we didn’t previously know.

I’ll start by listing all of the algorithms – 144 in total:

The standard already classifies the algorithms in various ways – e.g. those included in the header <algorithm> vs. the header <numeric> or mutating vs. non-mutating algorithms. I am sure that we can find some more classifications that are interesting.

Our first classification will be a simple one – algorithms that guarantee that the input elements will be operated on in a particular order vs. algorithms that do not make that guarantee. Actually, this ended up not being as simple as I thought which makes it even more instructive.

All we need to do is search the standard for the phrases “and proceeding to” and “in order”. It turns out that there are 13 algorithms that guarantee their order of operation:

[ Edit: I should have included std::iota in this list. See my follow-up post. ]

No other algorithms guarantee the operation order. Of course there are some algorithms where we wouldn’t expect a guaranteed order – we want std::lower_bound to use whatever order is most efficient. What about an algorithm like std::find though? Since that returns the first occurrence of a value surely it must access its input range from beginning to end. The standard does not guarantee it. I can’t think of a sensible algorithm that would do anything other than go from begin to end (unless we get into parallelism which opens up another can of worms), but the standard does not specifically make that guarantee.

Here’s another example that does not guarantee the operation order – std::transform. At first glance, that seems to make sense. Take this example:

std::vector< int > v0( { 1, 2, 3, 4, 5 } );
std::vector< int > v1( 5 );

std::transform( 
    std::begin( v0 ), 
    std::end( v0 ), 
    std::begin( v1 ), 
    []( int i )
{
    return i + 1;
} );

There are five results, each of which is computed entirely independently of the others. We know that the operation supplied to std::transform should not have any side effects so it doesn’t matter what order the results are computed in, they might even be computed in parallel. It doesn’t matter whether the result in position [0] is written before or after the result in position [1] (the results have to be written to the correct position but they don’t have to be written in a particular order).

Now let’s change the problem slightly. In this case we won’t pre-allocate the output vector and we’ll use std::back_inserter:

std::vector< int > v0( { 1, 2, 3, 4, 5 } );
std::vector< int > v1;

std::transform( 
    std::begin( v0 ), 
    std::end( v0 ), 
    std::back_inserter( v1 ), 
    []( int i )
{
    return i + 1;
} );

Now it matters what order the results are written in – the order they are written in defines the position they are written to. Doesn’t this conflict with the lack of guarantee about the order of computation?

Given that std::back_inserter is a common idiom it’s obvious that the answer to the previous question is “no, there is no conflict”. It isn’t so obvious why there is no conflict.

Let’s go back to the first example I showed:

std::vector< int > v0( { 1, 2, 3, 4, 5 } );
std::vector< int > v1( 5 );

std::transform( 
    std::begin( v0 ), 
    std::end( v0 ), 
    std::begin( v1 ), 
    []( int i )
{
    return i + 1;
} );

and the declaration of the single input range version of std::transform:

My example is using std::vector – that gives us random access iterators that let us jump around all over the place. If you look at the declaration of std::transform though, it will work with input and output iterators. Input and output iterators do not allow random access – they don’t even allow you to iterate over the same range twice. Even though the algorithm will allow arbitrary access, the iterators don’t.

A quick look at the standard tells us that std::back_inserter returns std::back_insert_iterator which is an output iterator. If the destination of a std::transform call is an output iterator, the results must be written in the correct order. Internally they can still be calculated in any order (possible, even with input iterators, but unlikely to be efficient), but they must be written in the correct order.

So it is possible for a standard-conforming std::transform implementation to access the input elements in different orders depending on the type of iterators being used. There is definitely precedent for different algorithm implementations being used for different iterator types. Microsoft’s Stephan T. Lavavej demonstrates how template metaprogramnming can achieve this here.

However, in practice, I have never come across an implementation of std::transform that does anything other than iterate from beginning to end and I don’t expect to – at least not under the name std::transform. When I have been working with parallel code the parallelism has always been explicitly called out – I really don’t want the STL kicking off separate threads unless I tell it to. Intel’s TBB contains several explicitly parallel algorithms, but they all have the word “parallel” in their names.

In conclusion, I started off with what I though was going to be a simple classification. I went through a phase where I thought that it wasn’t so simple after all, then finally ended up at the simple place I started at – but perhaps a little wiser. I haven’t been able to find a lot of information about the access order of algorithms online, but I do recommend this 2001 DDJ article on the subject.