Quote of the week – make it easier

Here’s how you could have made it easier on yourselves.

Matt Smith

A couple of years ago I took a class in improvisational theater from Matt Smith. If you are looking for a way to push yourself out of your comfort zone I highly recommend improv., particularly since in our case we did two public performances at the end of the class. If you’re in Seattle, I highly recommend Matt’s classes – the man is a genius.

(If you have a fear of public speaking, improv. might not cure you of that fear, but at least it will demonstrate that there is something worse than getting up on stage with a speech already prepared. Getting up on stage with nothing prepared is in a whole different category of scary).

In 60 hours of class time over 4 weeks, Matt never once told us that we were doing something wrong. Instead he used the quote above – “here’s how you could have made it easier on yourselves” (there’s a whole series of blog posts waiting to be written about what a great way of giving feedback that phrase is).

I was reminded of Matt’s words when I read this list of techniques for robust software (the author is given as Nick P – I would love to be able to attribute this more precisely, if anyone knows who Nick P is, please post in the comments).

It’s a good list of techniques that have been known for many years (and yet I see many teams failing to implement them), but what struck me is how many of the techniques come down to “making it easier on yourselves”. It’s well worth reading the entire list, but here are a few highlights:

  • #2 “they used boring constructs that were easy to analyse”
  • #3 “each module must fit in your head”, “control graph that’s pretty predictable”
  • #6 “adopt languages that make robust development easier”
  • #11 “brilliant tooling that could reliably find race conditions, deadlocks, or livelocks”

Software development is hard, we need to take every opportunity to make it easier on ourselves.

(You should also check out Matt’s TEDx talk on The Failure Bow – a concept that came up over and over again in our class and would improve many workplace cultures).

Quote of the week – testing

Just in case the twitter links stop working:

Code that isn't tested == code that is broken.

Corollary. Multi-threaded code that is tested != code that works.

Wayne Wooten

Ah, the joys of parallel programming.

I did my undergraduate degree at Manchester University in the 1980s. In my “Parallel Computing” class we had a lecture about the Manchester Dataflow Machine – a parallel computing architecture that was going to take over the world.

I did my master’s degree at the University of Washington in the 2000s. In my “Parallel Computing” class we had a lecture about the Manchester Dataflow Machine, and why it didn’t take over the world.*

In 20 years it seems like we came up with a lot of ideas for parallel computing, without ever hitting on the single idea that ties everything together. For serial computing we have the Von Neumann architecture, and even though we now have caches and branch prediction and pipelining and more, we can still regard the basic machine as a Von Neumann machine.

The most practical approach I have seen is the use of parallel programming patterns. Depending on who you talk to, and how they group the patterns there are somewhere between 13 and 20 of these. I am partial to Dr. Michael McCool’s explanation of the patterns:

Parallel Programming Talk 82 – Michael McCool

Structured Parallel Programming with Deterministic Patterns


* I am being cruel for comic effect. It isn’t necessary for a machine (particularly not a research machine) to take over the world in order to be groundbreaking, useful and educational. The dataflow model is still a very relevant one – we used a dataflow architecture for hooking together graphs of image processing algorithms on the Adobe Image Foundation project. Search for “Photoshop oil paint filter” for examples produced by a dataflow graph of 13 image processing kernels.

C++ links

Bjarne Stroustrup and Herb Sutter are putting together a set of C++ core guidelines. The main document is here, and it’s worth looking round the rest of the repository for more links, and slides of talks.

I haven’t read all of the guidelines yet (it’s a big document), but what I have looked at so far is good.

There’s a discussion about the core guidelines on Hacker News. Sadly, one of the comments argues that:

drawline(int,int,int,int);

is superior to:

drawline(Point,Point);

I despair of this industry on a regular basis. We certainly don’t know everything about programming (and I hope in 20 years we’ll be looking back and laughing at our naivete), but we don’t know nothing either. Grouping data values into bundles is not a new idea, it has many demonstrated benefits and yet people still argue against it. Writing good code is hard, and we just make it harder by ignoring even the most basic of guidelines.

I laughed at another of the comments:

I agree, these are too opinionated to be unconditionally useful.

It’s a document by Bjarne Stroustrup and Herb Sutter. I’d be disappointed if it wasn’t opinionated.

Videos from the 2015 CppCon are starting to appear on the CppCon YouTube channel. There are also plenty of videos from previous years.

Notes from Herb Sutter’s talk Writing good C++14… by default are here

Juggling on the moon

Recently I tracked down an article I wrote in 1992 where I claimed (inaccurately) to be the first person to juggle on the moon. The piece was published in Kaskade – the European juggling magazine – and is here on page 14. Obviously I wasn’t on the moon, I was in a virtual reality juggling simulation which let me tweak gravity to whatever I wanted.

One point in the article bears some further discussion – objects on the moon don’t float gently to the ground. I programmed the simulation using Newton’s equations of motion. I ignored air resistance (for this problem it’s insignificant under earth gravity and non-existent on the moon anyway). I did A level* physics and maths – I’ve solved plenty of problems using these equations. If you asked me to do the calculation I could have told you that if you throw something up at x m/s in constant gravity it will come down past your hand at –x m/s.

Even knowing all of the theory, it still surprised me when I got into the simulation and tried it. My instinct was that everything fell at a constant speed on the moon. I knew that wasn’t true but I hadn’t experienced it. This might seem obvious to everyone else, but it wasn’t obvious to me. Perhaps I had been deceived by cartoon physics. Perhaps I was thinking that everything on the moon would be as light as a feather (not true), and since feathers float gently to the ground on earth (due to air resistance) objects would float to the ground on the moon.

There is a story (that I haven’t been able to find a good reference for so might be false) that NASA scientists were surprised the first time an astronaut tried turning a bolt in space on the outside of the capsule. The astronaut turned, not the bolt.

This piece wouldn’t be complete without a link to the classic NASA video of dropping a hammer and a feather on the moon. Really on the moon this time. Notice that the hammer and the feather are both accelerating.

The conclusion? Theory is one thing, actually experiencing it is another.

 

* For those of you who are not Brits but are familiar with Harry Potter, A levels are equivalent to NEWTS**.

** For those of you not familiar with Harry Potter, NEWTS are the exams you do at age 18 having specialized in the subject for 2 years.

Algorithms and variations 2

One way of categorizing the algorithms is by the types of iterators that they take as arguments, or return as results.

Let’s start with a reminder of the hierarchy of iterators (I am deliberately ignoring some of the new iterator functionality being proposed for C++17):

Random access iterator
Bidirectional iterator
Forward iterator
Input iterator Output iterator


The key quality of an input iterator is that the input sequence can only be traversed once. We can make a copy of an input iterator, but the moment we increment one of the copies, the other becomes invalid. The input value is available once – a common example is reading in keys from a keyboard.

An output iterator will only let us write a value once. An example is writing a value to a stream that’s being sent over the network (this example ignores a bunch of details likely to apply in practice but that doesn’t stop it from being a useful reminder for me).

A forward iterator lets us read or write as many times as we want. We can make copies of the iterator and traverse the sequence as many times as we want but we can only traverse it in one direction – forward. The classic example is a singly linked list.

A bidirectional iterator has all of the qualities of a forward iterator but will let us traverse backwards as well as forwards – e.g. a doubly linked list.

Finally, a random access iterator will let us traverse forwards, backwards and additionally, jump to any point in the sequence. std::vector lets us do all of this.


Input iterator

There are lots of algorithms that take input iterators as arguments so I have subdivided them further by their return type. Let’s start off with the algorithms that do not return an iterator:

T accumulate (InputIterator, InputIterator, T)
T accumulate (InputIterator, InputIterator, T, BinaryOperation)
bool all_of (InputIterator, InputIterator, Predicate)
bool any_of (InputIterator, InputIterator, Predicate)
difference_type count (InputIterator, InputIterator, T)
difference_type count_if (InputIterator, InputIterator, Predicate)
bool equal (InputIterator1, InputIterator1, InputIterator2)
bool equal (InputIterator1, InputIterator1, InputIterator2, BinaryPredicate)
Function for_each (InputIterator, InputIterator, Function)
bool includes (InputIterator1, InputIterator1, InputIterator2, InputIterator2)
bool includes (InputIterator1, InputIterator1, InputIterator2, InputIterator2, Compare)
T inner_product (InputIterator1, InputIterator1, InputIterator2, T)
T inner_product (InputIterator1, InputIterator1, InputIterator2, T, BinaryOperation1, BinaryOperation2)
bool is_partitioned (InputIterator, InputIterator, Predicate)
bool lexicographical_compare (InputIterator1, InputIterator1, InputIterator2, InputIterator2)
bool lexicographical_compare (InputIterator1, InputIterator1, InputIterator2, InputIterator2, Compare)
bool none_of (InputIterator, InputIterator, Predicate)

We could subdivide this list even further. We have the algorithms that return bool – they are asking questions (all_of, any_of, equal, includes, is_partitioned, lexicographical_compare, none_of). We have the count and count_if algorithms – also asking questions and getting back an answer in the form of an integer. There are the algorithms that return a single value computed from the input range (accumulate and inner_product) and finally, for_each which, because it allows its function object to change state, returns the final version of the function object.

All of the algorithms can be run in a single pass over the input range – remember that input iterators do not allow us to iterate twice over a range. These algorithms can also be run over any pair of iterators above an input iterator in the hierarchy – i.e. all iterators except output iterators.

Next up, algorithms that take input iterators and return an output iterator:

OutputIterator adjacent_difference (InputIterator, InputIterator, OutputIterator)
OutputIterator adjacent_difference (InputIterator, InputIterator, OutputIterator, BinaryOperation)
OutputIterator copy (InputIterator, InputIterator, OutputIterator)
OutputIterator copy_if (InputIterator, InputIterator, OutputIterator, Predicate)
OutputIterator copy_n (InputIterator, Size, OutputIterator)
OutputIterator merge (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator)
OutputIterator merge (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator, Compare)
OutputIterator move (InputIterator, InputIterator, OutputIterator)
OutputIterator partial_sum (InputIterator, InputIterator, OutputIterator)
OutputIterator partial_sum (InputIterator, InputIterator, OutputIterator, BinaryOperation)
pair<OutputIterator1, OutputIterator2> partition_copy (InputIterator, InputIterator, OutputIterator1, OutputIterator2, Predicate)
OutputIterator remove_copy (InputIterator, InputIterator, OutputIterator, T)
OutputIterator remove_copy_if (InputIterator, InputIterator, OutputIterator, Predicate)
OutputIterator replace_copy (InputIterator, InputIterator, OutputIterator, T, T)
OutputIterator replace_copy_if (InputIterator, InputIterator, OutputIterator, Predicate, T)
OutputIterator set_difference (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator)
OutputIterator set_difference (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator, Compare)
OutputIterator set_intersection (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator)
OutputIterator set_intersection (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator, Compare)
OutputIterator set_symmetric_difference (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator)
OutputIterator set_symmetric_difference (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator, Compare)
OutputIterator set_union (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator)
OutputIterator set_union (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator, Compare)
OutputIterator transform (InputIterator, InputIterator, OutputIterator, UnaryOperation)
OutputIterator transform (InputIterator1, InputIterator1, InputIterator2, OutputIterator, UnaryOperation)
OutputIterator unique_copy (InputIterator, InputIterator, OutputIterator)
OutputIterator unique_copy (InputIterator, InputIterator, OutputIterator, BinaryPredicate)

The algorithms that return an output iterator all take an output iterator as a parameter. The algorithms are taking an input range and converting it to an output range. The result is always the position after the last written element of the output range – i.e. the first element that was not overwritten.

Alex Stepanov had many design principles for the STL. One of them states that an algorithm that calculates a useful value should return that value even when the calculation of that value is not the main point of the algorithm. Take std::copy. The programmer already knows where the beginning and end of the input range are, and where the beginning of the output range is. What the programmer does not necessarily know is where the end of the output range is. Since the algorithm computes the end of the output range, and it is potentially useful information (I’ve used it several times), the algorithm returns the end of the output range.

As well as straightforward copying we also get variants on std::copy : std::copy, std::copy_if, std::copy_n, std::remove_copy, std::remove_copy_if, std::partition_copy (note that std::remove, std::remove_if and std::partition need more powerful iterators – it is the copying which lets them work with input iterators).

We also get std::merge – a building block for merge sort algorithms.

Finally for the input iterators, we have the algorithms that return an input iterator.

InputIterator find (InputIterator, InputIterator, T)
InputIterator find_first_of (InputIterator, InputIterator, ForwardIterator, ForwardIterator)
InputIterator find_first_of (InputIterator, InputIterator, ForwardIterator, ForwardIterator, BinaryPredicate)
InputIterator find_if (InputIterator, InputIterator, Predicate)
InputIterator find_if_not (InputIterator, InputIterator, Predicate)
pair<InputIterator1, InputIterator2> mismatch (InputIterator1, InputIterator1, InputIterator2)
pair<InputIterator1, InputIterator2> mismatch (InputIterator1, InputIterator1, InputIterator2, BinaryPredicate)

All of the algorithms return the position of something that was found, whether that was a given value or a mismatch.

Remember that an input iterator only gets to iterate over a range once. Once we have read a value and moved on that value is gone, however an algorithm like std::find only needs to read that value, it does not need to move on before returning the iterator.


Output iterator

There are only a couple of algorithms that take no iterators other than output iterators. Unsurprisingly, these are algorithms that generate some output:

OutputIterator fill_n (OutputIterator, Size, T)
OutputIterator generate_n (OutputIterator, Size, Generator)

There are other variants of std::fill and std::generate which we’ll look at later. These two algorithms write a sequence of n values. They are useful because we don’t always have the option of getting an “end” output iterator. Imagine appending data to a file, the end is wherever we decide to stop writing – there is no predetermined “end”.

In a previous blog post I mentioned the idea of adding iota_n. This is the category that iota_n would fit into. Incidentally, the boost algorithms library has boost::iota_n available, along with many other useful algorithms.


Forward iterator

ForwardIterator adjacent_find (ForwardIterator, ForwardIterator)
ForwardIterator adjacent_find (ForwardIterator, ForwardIterator, BinaryPredicate)
bool binary_search (ForwardIterator, ForwardIterator, T)
bool binary_search (ForwardIterator, ForwardIterator, T, Compare)
pair<ForwardIterator, ForwardIterator> equal_range (ForwardIterator, ForwardIterator, T)
pair<ForwardIterator, ForwardIterator> equal_range (ForwardIterator, ForwardIterator, T, Compare)
void fill (ForwardIterator, ForwardIterator, T)
ForwardIterator1 find_end (ForwardIterator1, ForwardIterator1, ForwardIterator2, ForwardIterator2)
ForwardIterator1 find_end (ForwardIterator1, ForwardIterator1, ForwardIterator2, ForwardIterator2, BinaryPredicate)
void generate (ForwardIterator, ForwardIterator, Generator)
void iota (ForwardIterator, ForwardIterator, T)
bool is_permutation (ForwardIterator1, ForwardIterator1, ForwardIterator2)
bool is_permutation (ForwardIterator1, ForwardIterator1, ForwardIterator2, BinaryPredicate)
bool is_sorted (ForwardIterator, ForwardIterator)
bool is_sorted (ForwardIterator, ForwardIterator, Compare)
bool is_sorted_until (ForwardIterator, ForwardIterator)
bool is_sorted_until (ForwardIterator, ForwardIterator, Compare)
void iter_swap (ForwardIterator1, ForwardIterator2)
ForwardIterator lower_bound (ForwardIterator, ForwardIterator, T)
ForwardIterator lower_bound (ForwardIterator, ForwardIterator, T, Compare)
ForwardIterator max_element (ForwardIterator, ForwardIterator)
ForwardIterator max_element (ForwardIterator, ForwardIterator, Compare)
ForwardIterator min_element (ForwardIterator, ForwardIterator)
ForwardIterator min_element (ForwardIterator, ForwardIterator, Compare)
pair<ForwardIterator, ForwardIterator> minmax_element (ForwardIterator, ForwardIterator)
pair<ForwardIterator, ForwardIterator> minmax_element (ForwardIterator, ForwardIterator, Compare)
ForwardIterator partition (ForwardIterator, ForwardIterator, Predicate)
ForwardIterator partition_point (ForwardIterator, ForwardIterator, Predicate)
ForwardIterator remove (ForwardIterator, ForwardIterator, T)
ForwardIterator remove_if (ForwardIterator, ForwardIterator, Predicate)
void replace (ForwardIterator, ForwardIterator, T, T)
void replace_if (ForwardIterator, ForwardIterator, Predicate, T)
ForwardIterator rotate (ForwardIterator, ForwardIterator, ForwardIterator)
OutputIterator rotate_copy (ForwardIterator, ForwardIterator, ForwardIterator, OutputIterator)
ForwardIterator1 search (ForwardIterator1, ForwardIterator1, ForwardIterator2, ForwardIterator2)
ForwardIterator1 search (ForwardIterator1, ForwardIterator1, ForwardIterator2, ForwardIterator2, BinaryPredicate)
ForwardIterator search_n (ForwardIterator, ForwardIterator, Size, T)
ForwardIterator search_n (ForwardIterator, ForwardIterator, Size, T, BinaryPredicate)
ForwardIterator2 swap_ranges (ForwardIterator1, ForwardIterator1, ForwardIterator2)
ForwardIterator unique (ForwardIterator, ForwardIterator)
ForwardIterator unique (ForwardIterator, ForwardIterator, BinaryPredicate)
ForwardIterator upper_bound (ForwardIterator, ForwardIterator, T)
ForwardIterator upper_bound (ForwardIterator, ForwardIterator, T, Compare)

Forward iterators give us a lot more options. Since forward iterators can iterate over a range more than once we can handle algorithms such as std::adjacent_find which require us to iterate over each value twice.

As I promised earlier, we have the other variants of std::generate and std::fill here, and we also get std::iota. Now we have moved into forward iterators we can start dealing with output ranges.

One suprise is that std::binary_search, std::equal_range, std::lower_bound and std::upper_bound are present in this list. We normally think of these algorithms as being O(log n) algorithms. Surely we cannot have a O(log n) algorithm working with forward iterators since the algorithm might have to iterate over the entire sequence making it O(n). The reason they are available for forward iterators is because the standard defines their complexity requirements as O(log n) on the number of comparisons, not the number of elements iterated over. We might regard this as cheating.

We are not stuck with one implementation of an algorithm though. There is also a great talk by Stephan T. Lavavej here where he explains how an implementation can select different algorithms for different iterator types so (for example) std::binary_search can use one implementation for forward iterators but a more efficient implementation for random access iterators.

Another surprise for me is that std::min_element, std::max_element and std::minmax_element all require forward iterators. Surely it is possible to find the maximum element of a sequence using input iterators? Well, it is possible to find the maximum element of a sequence using input iterators, however there are two problems:

  1. std::max_element and friends actually return the position of the desired element(s), not just the value of the desired element. The position is a more general piece of information
  2. If we had a version of std::max_element that ran on input iterators it would have to make a copy of the element – both for the comparison and to return the value of the element. Making a copy could be expensive, undesirable or impossible. Having said that, there is a Stack Overflow post here where making a copy increases the performance of the algorithm, probably due to a cache effect.

Working out how to implement some of these algorithms to achieve the required complexity guarantees is an interesting exercise.


Bidirectional iterator

BidirectionalIterator2 copy_backward (BidirectionalIterator1, BidirectionalIterator1, BidirectionalIterator2)
void inplace_merge (BidirectionalIterator, BidirectionalIterator, BidirectionalIterator)
void inplace_merge (BidirectionalIterator, BidirectionalIterator, BidirectionalIterator, Compare)
BidirectionalIterator2 move_backward (BidirectionalIterator1, BidirectionalIterator1, BidirectionalIterator2)
bool next_permutation (BidirectionalIterator, BidirectionalIterator)
bool next_permutation (BidirectionalIterator, BidirectionalIterator, Compare)
bool prev_permutation (BidirectionalIterator, BidirectionalIterator)
bool prev_permutation (BidirectionalIterator, BidirectionalIterator, Compare)
void reverse (BidirectionalIterator, BidirectionalIterator)
OutputIterator reverse_copy (BidirectionalIterator, BidirectionalIterator, OutputIterator)
BidirectionalIterator stable_partition (BidirectionalIterator, BidirectionalIterator, Predicate)

The bidirectional iterator algorithms are an interesting bunch. The algorithms need more functionality than provided by forward iterators, but don’t require the full power of random access iterators.

We get std::copy_backward. As we saw in part 1a, std::copy and std::copy_backward handle overlapping ranges (std::reverse_copy requires non-overlapping ranges). If you’re looking from some additional amusement, look into how using reverse iterators affects the overlapping range guarantees of std::copy and std::copy_backward (we can make similar arguments for the std::move set of algorithms).

We get std::inplace_merge, an algorithm that will make use of extra memory if it can get it. The standard does not specify where the extra memory comes from – usually C++ allows you to handle all memory via custom allocators, that does not appear to be the case here.


Random access iterator

bool is_heap (RandomAccessIterator, RandomAccessIterator)
bool is_heap (RandomAccessIterator, RandomAccessIterator, Compare)
RandomAccessIterator is_heap_until (RandomAccessIterator, RandomAccessIterator)
RandomAccessIterator is_heap_until (RandomAccessIterator, RandomAccessIterator, Compare)
void make_heap (RandomAccessIterator, RandomAccessIterator)
void make_heap (RandomAccessIterator, RandomAccessIterator, Compare)
void nth_element (RandomAccessIterator, RandomAccessIterator, RandomAccessIterator)
void nth_element (RandomAccessIterator, RandomAccessIterator, RandomAccessIterator, Compare)
void partial_sort (RandomAccessIterator, RandomAccessIterator, RandomAccessIterator)
void partial_sort (RandomAccessIterator, RandomAccessIterator, RandomAccessIterator, Compare)
void pop_heap (RandomAccessIterator, RandomAccessIterator)
void pop_heap (RandomAccessIterator, RandomAccessIterator, Compare)
void push_heap (RandomAccessIterator, RandomAccessIterator)
void push_heap (RandomAccessIterator, RandomAccessIterator, Compare)
void random_shuffle (RandomAccessIterator, RandomAccessIterator)
void random_shuffle (RandomAccessIterator, RandomAccessIterator, RandomNumberGenerator)
void shuffle (RandomAccessIterator, RandomAccessIterator, URandomNumberGenerator)
void sort (RandomAccessIterator, RandomAccessIterator)
void sort (RandomAccessIterator, RandomAccessIterator, Compare)
void sort_heap (RandomAccessIterator, RandomAccessIterator)
void sort_heap (RandomAccessIterator, RandomAccessIterator, Compare)
void stable_sort (RandomAccessIterator, RandomAccessIterator)
void stable_sort (RandomAccessIterator, RandomAccessIterator, Compare)

The random access algorithms are all about sorting and shuffling. I have rarely used the heap algorithms directly but they are useful building blocks for algorithms such as std::nth_element (previously discussed here), std::partial_sort_copy and std::partial_sort.


Input iterator and random access iterator

RandomAccessIterator partial_sort_copy (InputIterator, InputIterator, RandomAccessIterator, RandomAccessIterator)
RandomAccessIterator partial_sort_copy (InputIterator, InputIterator, RandomAccessIterator, RandomAccessIterator, Compare)

std::partial_sort_copy uses an interesting combination of input iterators and random access iterators.


No iterator

const T& max (T, T)
const T& max (T, T, Compare)
T max (InitializerList)
T max (InitializerList, Compare)
const T& min (T, T)
const T& min (T, T, Compare)
T min (InitializerList)
T min (InitializerList, Compare)
pair<const T&, const T&> minmax (T, T)
pair<const T&, const T&> minmax (T, T, Compare)
pair<T, T> minmax (InitializerList)
pair<T, T> minmax (InitializerList, Compare)

Finally, there are the core min and max algorithms that don’t use iterators at all.


Conclusion

I don’t have a conclusion for this post. I found it interesting to see which algorithms required which iterators – there were a couple that surprised me. The general rule is to write algorithms that use the weakest iterators possible to make the algorithms as widely useful as possible.

C++ samples – “A repository of modern C++ code samples”

A link to a cool website. C++ samples describes itself as:

A repository of modern C++ code samples curated by the community.

There’s a Github repo so that anyone can fork, add a new sample and make a pull request. There are some interesting samples up there already, and I look forward to seeing what gets added in the future.

Joseph Mansfield is the programmer behind C++ samples and his own blog has plenty of interesting posts.

Algorithms and Variations 1a

In the first part of this series we looked at algorithms which guaranteed their order of operations vs. algorithms that don’t. On further reflection, there are two things missing from that article.

First of all, I should have included std::iota in the list of “order guaranteed” algorithms. I overlooked this partly because std::iota doesn’t take an input range, but also because the language used in the standard isn’t entirely clear. I am reasonably confident though that operator++ must be applied starting with the first value output, and continuing in sequence. (As always, if someone has some evidence I am wrong about this please tell me).

This raises the number of algorithms that guarantee ordering to 14.

Secondly, we didn’t look at “why”. Why should some algorithms guarantee their operation order while others don’t? Let’s look at the 14 algorithms in groups, starting with std::copy and std::move:

OutputIterator copy (InputIterator, InputIterator, OutputIterator)
BidirectionalIterator2 copy_backward (BidirectionalIterator1, BidirectionalIterator1, BidirectionalIterator2)
OutputIterator move (InputIterator, InputIterator, OutputIterator)
BidirectionalIterator2 move_backward (BidirectionalIterator1, BidirectionalIterator1, BidirectionalIterator2)

Copy and move have specific forward and backward versions. This is to handle overlapping input and output ranges. In order for copying or moving between overlapping ranges to work as expected, the order must be specified. The order will be different depending on whether the destination range overlaps the beginning or the end of the source range – hence the forward and backward versions.

(There was an issue raised in 1995 about the direction of std::copy. Read it here.)

Moving on, the next algorithm is std::for_each:

Function for_each (InputIterator, InputIterator, Function)

As Kreft and Langer point out here, std::for_each was unusual among the algorithms because it allows its function object to have side effects. I say was because the C++98 standard includes the phrase – op and binary_op shall not have any side effects – in the description of std::transform. The C++11 standard weakens that requirement.

Regardless of the changes to the wording of std::transform, once your function object can have side effects, it is possible for those side effects to vary depending on the order in which the range is processed. To get deterministic results you need a deterministic processing order, hence (at least historically) the order requirement for std::for_each.

That leaves us with 9 algorithms to explain:

T accumulate (InputIterator, InputIterator, T)
T accumulate (InputIterator, InputIterator, T, BinaryOperation)
OutputIterator adjacent_difference (InputIterator, InputIterator, OutputIterator)
OutputIterator adjacent_difference (InputIterator, InputIterator, OutputIterator, BinaryOperation)
T inner_product (InputIterator1, InputIterator1, InputIterator2, T)
T inner_product (InputIterator1, InputIterator1, InputIterator2, T, BinaryOperation1, BinaryOperation2)
void iota (ForwardIterator, ForwardIterator, T)
OutputIterator partial_sum (InputIterator, InputIterator, OutputIterator)
OutputIterator partial_sum (InputIterator, InputIterator, OutputIterator, BinaryOperation)

What do these algorithms have in common?

  1. They are all in the header numeric. In fact, they are the entire contents of the header numeric.
  2. They all involve combining elements of the input range in some way (or the output range for std::iota).

So we have “in order”, “numeric”, and “combining”. “Numeric” leads us to think of floating point values, and the combination of “in order” and “floating point” leads us to the fact that floating point arithmetic is neither associative nor commutative. [Edit: See John Payson’s comment where he points out that IEEE-754 floating point is commutative for addition and multiplication.] Running std::accumulate from front to back does not necessarily give us the same answer as running it from back to front. Once again, if we want a deterministic answer we need a deterministic processing order, hence the “in order” requirement for these algorithms.

As usual, if the standard algorithms do not supply us with what we want, we can write our own.

The C++11 standard also makes it clear that the compiler is limited in its rearrangement of operators:

[ Note: Operators can be regrouped according to the usual mathematical rules only where the operators really are associative or commutative.

C++11 standard 1.9


In case anyone thinks that floating point commutativity [Edit: I should have said associative here] only matters for very large, very small or very accurate calculations, it doesn’t. One of my home projects is a music typesetting program. It lays out music onto a typical sheet of paper (A4 or 8.5 x 11) and it doesn’t need micron accuracy, however I still got caught by floating point operations.

At one point I had two functions (A and B) that computed what was nominally the same value, but in two different ways. I sorted a vector using a comparison operator that called function A. I then attempted to do a binary search on the vector using a comparison operator that called function B. Fortunately the debug version of the STL I was using detected attempts to use a binary search on a vector that was not sorted – the vector was sorted according to A, it was not sorted according to B. Yet another reason why “don’t repeat yourself” is such a good rule.


In part 1 I mentioned the possibility of having some of the algorithms perform their calculations in parallel. The C++11 standard has this to say:

Unless otherwise specified, C++ standard library functions shall perform all operations solely within the current thread if those operations have effects that are visible (1.10) to users.
[ Note: This allows implementations to parallelize operations if there are no visible side effects. —end note ]

C++11 standard 17.6.5.9

I.e. no parallelism unless it’s invisible to the user.

There are some interesting proposals for explicitly parallel algorithms. For example, see section 6.6 Associativity/Commutativity of Binary Operators (p66) of A Parallel Algorithms Library which points out that some parallel algorithms will require associative and commutative operators.

Parallelizing the Standard Algorithms Library also looks at the topic of parallelization. For example, see section 5.2 std::accumulate versus thrust::reduce for a discussion of the need for associative and commutative operators.


Several of my references in this post came from this website which contains many papers from the C++ standards committee. If you have far too much time to kill, the site contains fascinating information – current and historical.

Quote of the week – shortcuts

… too tight a schedule will inevitably lead to the temptation to take shortcuts. These shortcuts might succeed in getting the system working on time – but only if everything goes right, which it rarely does.

Gerald Weinberg The Psychology of Computer Programming Silver Anniversary Edition p68

The Psychology of Computer Programming was originally published in 1971 but remains a great read and very relevant even in a very different computing world. I have the silver anniversary edition which reprints the original with additional commentary at the end of each chapter – what Weinberg calls “wisdom of hindsight remarks”. Weinberg’s comments – 25 years on – about the above quote state:

The wisdom of age has made me ashamed of this statement. “Rarely” is pussy footing; something always goes wrong. Shilly-shallying like this by authors like me has perpetuated the myth of the “optimistic” estimate – how long a project would take if everything went right. Such “estimating” might just as well be based on the assumption that the Laws of Thermodynamics will be repealed during the project.

Gerald Weinberg The Psychology of Computer Programming Silver Anniversary Edition 5.i

Quote of the week – 6 tools

I imposed on [Jack] Real the requirement that he try to design the helicopter so that it could be serviced with six simple tools – any six of his choice. This was more a challenge than an arbitrary decision. I think most good designers want to keep things simple, but sometimes, for the sheer engineering delight of creating, things become unnecessarily complex and cumbersome.

Clarence L. “Kelly” Johnson Kelly: More than My Share of It All

Kelly Johnson was the head of Lockheed’s Skunk Works and a renowned aeronautical engineer. His Wikipedia article contains many more details, including his 14 Rules of Management.

Kelly: More than My Share of It All is also worth reading. It includes stories of Amelia Earhart, the SR-71 Blackbird and a 400lb lion chasing Althea Johnson (Kelly Johnson’s wife) around a factory.

I am not going to search for a software equivalent of “six simple tools” – that would be an analogy too far, and as Johnson goes on to say, the “six tools” are less of a requirement than they are about setting up an attitude. Maintenance matters. Simplicity matters. What use is the best helicopter in the world if you can’t keep it running?

I think there is a software parallel in this comment from Chris Jaynes (commenting on Tim Bray’s post On Duct Tape, itself a response to Joel Spolsky’s post The Duct Tape Programmer that in turn was inspired by a chapter in the book Coders at Work profiling Jamie Zawinski):

Yes, shipping version 1 is a feature, but shipping version 2 is ALSO a feature!

To that I would add:

Being able to fix bugs is a feature.
Being able to maintain code is a feature.
Being able to add features is itself a feature.

Algorithms and Variations 1

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:

T accumulate (InputIterator, InputIterator, T)
T accumulate (InputIterator, InputIterator, T, BinaryOperation)
OutputIterator adjacent_difference (InputIterator, InputIterator, OutputIterator)
OutputIterator adjacent_difference (InputIterator, InputIterator, OutputIterator, BinaryOperation)
ForwardIterator adjacent_find (ForwardIterator, ForwardIterator)
ForwardIterator adjacent_find (ForwardIterator, ForwardIterator, BinaryPredicate)
bool all_of (InputIterator, InputIterator, Predicate)
bool any_of (InputIterator, InputIterator, Predicate)
bool binary_search (ForwardIterator, ForwardIterator, T)
bool binary_search (ForwardIterator, ForwardIterator, T, Compare)
OutputIterator copy (InputIterator, InputIterator, OutputIterator)
BidirectionalIterator2 copy_backward (BidirectionalIterator1, BidirectionalIterator1, BidirectionalIterator2)
OutputIterator copy_if (InputIterator, InputIterator, OutputIterator, Predicate)
OutputIterator copy_n (InputIterator, Size, OutputIterator)
difference_type count (InputIterator, InputIterator, T)
difference_type count_if (InputIterator, InputIterator, Predicate)
bool equal (InputIterator1, InputIterator1, InputIterator2)
bool equal (InputIterator1, InputIterator1, InputIterator2, BinaryPredicate)
pair<ForwardIterator, ForwardIterator> equal_range (ForwardIterator, ForwardIterator, T)
pair<ForwardIterator, ForwardIterator> equal_range (ForwardIterator, ForwardIterator, T, Compare)
void fill (ForwardIterator, ForwardIterator, T)
OutputIterator fill_n (OutputIterator, Size, T)
InputIterator find (InputIterator, InputIterator, T)
ForwardIterator1 find_end (ForwardIterator1, ForwardIterator1, ForwardIterator2, ForwardIterator2)
ForwardIterator1 find_end (ForwardIterator1, ForwardIterator1, ForwardIterator2, ForwardIterator2, BinaryPredicate)
InputIterator find_first_of (InputIterator, InputIterator, ForwardIterator, ForwardIterator)
InputIterator find_first_of (InputIterator, InputIterator, ForwardIterator, ForwardIterator, BinaryPredicate)
InputIterator find_if (InputIterator, InputIterator, Predicate)
InputIterator find_if_not (InputIterator, InputIterator, Predicate)
Function for_each (InputIterator, InputIterator, Function)
void generate (ForwardIterator, ForwardIterator, Generator)
OutputIterator generate_n (OutputIterator, Size, Generator)
bool includes (InputIterator1, InputIterator1, InputIterator2, InputIterator2)
bool includes (InputIterator1, InputIterator1, InputIterator2, InputIterator2, Compare)
T inner_product (InputIterator1, InputIterator1, InputIterator2, T)
T inner_product (InputIterator1, InputIterator1, InputIterator2, T, BinaryOperation1, BinaryOperation2)
void inplace_merge (BidirectionalIterator, BidirectionalIterator, BidirectionalIterator)
void inplace_merge (BidirectionalIterator, BidirectionalIterator, BidirectionalIterator, Compare)
void iota (ForwardIterator, ForwardIterator, T)
bool is_heap (RandomAccessIterator, RandomAccessIterator)
bool is_heap (RandomAccessIterator, RandomAccessIterator, Compare)
RandomAccessIterator is_heap_until (RandomAccessIterator, RandomAccessIterator)
RandomAccessIterator is_heap_until (RandomAccessIterator, RandomAccessIterator, Compare)
bool is_partitioned (InputIterator, InputIterator, Predicate)
bool is_permutation (ForwardIterator1, ForwardIterator1, ForwardIterator2)
bool is_permutation (ForwardIterator1, ForwardIterator1, ForwardIterator2, BinaryPredicate)
bool is_sorted (ForwardIterator, ForwardIterator)
bool is_sorted (ForwardIterator, ForwardIterator, Compare)
bool is_sorted_until (ForwardIterator, ForwardIterator)
bool is_sorted_until (ForwardIterator, ForwardIterator, Compare)
void iter_swap (ForwardIterator1, ForwardIterator2)
bool lexicographical_compare (InputIterator1, InputIterator1, InputIterator2, InputIterator2)
bool lexicographical_compare (InputIterator1, InputIterator1, InputIterator2, InputIterator2, Compare)
ForwardIterator lower_bound (ForwardIterator, ForwardIterator, T)
ForwardIterator lower_bound (ForwardIterator, ForwardIterator, T, Compare)
void make_heap (RandomAccessIterator, RandomAccessIterator)
void make_heap (RandomAccessIterator, RandomAccessIterator, Compare)
const T& max (T, T)
const T& max (T, T, Compare)
T max (InitializerList)
T max (InitializerList, Compare)
ForwardIterator max_element (ForwardIterator, ForwardIterator)
ForwardIterator max_element (ForwardIterator, ForwardIterator, Compare)
OutputIterator merge (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator)
OutputIterator merge (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator, Compare)
const T& min (T, T)
const T& min (T, T, Compare)
T min (InitializerList)
T min (InitializerList, Compare)
ForwardIterator min_element (ForwardIterator, ForwardIterator)
ForwardIterator min_element (ForwardIterator, ForwardIterator, Compare)
pair<const T&, const T&> minmax (T, T)
pair<const T&, const T&> minmax (T, T, Compare)
pair<T, T> minmax (InitializerList)
pair<T, T> minmax (InitializerList, Compare)
pair<ForwardIterator, ForwardIterator> minmax_element (ForwardIterator, ForwardIterator)
pair<ForwardIterator, ForwardIterator> minmax_element (ForwardIterator, ForwardIterator, Compare)
pair<InputIterator1, InputIterator2> mismatch (InputIterator1, InputIterator1, InputIterator2)
pair<InputIterator1, InputIterator2> mismatch (InputIterator1, InputIterator1, InputIterator2, BinaryPredicate)
OutputIterator move (InputIterator, InputIterator, OutputIterator)
BidirectionalIterator2 move_backward (BidirectionalIterator1, BidirectionalIterator1, BidirectionalIterator2)
bool next_permutation (BidirectionalIterator, BidirectionalIterator)
bool next_permutation (BidirectionalIterator, BidirectionalIterator, Compare)
bool none_of (InputIterator, InputIterator, Predicate)
void nth_element (RandomAccessIterator, RandomAccessIterator, RandomAccessIterator)
void nth_element (RandomAccessIterator, RandomAccessIterator, RandomAccessIterator, Compare)
void partial_sort (RandomAccessIterator, RandomAccessIterator, RandomAccessIterator)
void partial_sort (RandomAccessIterator, RandomAccessIterator, RandomAccessIterator, Compare)
RandomAccessIterator partial_sort_copy (InputIterator, InputIterator, RandomAccessIterator, RandomAccessIterator)
RandomAccessIterator partial_sort_copy (InputIterator, InputIterator, RandomAccessIterator, RandomAccessIterator, Compare)
OutputIterator partial_sum (InputIterator, InputIterator, OutputIterator)
OutputIterator partial_sum (InputIterator, InputIterator, OutputIterator, BinaryOperation)
ForwardIterator partition (ForwardIterator, ForwardIterator, Predicate)
pair<OutputIterator1, OutputIterator2> partition_copy (InputIterator, InputIterator, OutputIterator1, OutputIterator2, Predicate)
ForwardIterator partition_point (ForwardIterator, ForwardIterator, Predicate)
void pop_heap (RandomAccessIterator, RandomAccessIterator)
void pop_heap (RandomAccessIterator, RandomAccessIterator, Compare)
bool prev_permutation (BidirectionalIterator, BidirectionalIterator)
bool prev_permutation (BidirectionalIterator, BidirectionalIterator, Compare)
void push_heap (RandomAccessIterator, RandomAccessIterator)
void push_heap (RandomAccessIterator, RandomAccessIterator, Compare)
void random_shuffle (RandomAccessIterator, RandomAccessIterator)
void random_shuffle (RandomAccessIterator, RandomAccessIterator, RandomNumberGeneratorenerator)
ForwardIterator remove (ForwardIterator, ForwardIterator, T)
OutputIterator remove_copy (InputIterator, InputIterator, OutputIterator, T)
OutputIterator remove_copy_if (InputIterator, InputIterator, OutputIterator, Predicate)
ForwardIterator remove_if (ForwardIterator, ForwardIterator, Predicate)
void replace (ForwardIterator, ForwardIterator, T, T)
OutputIterator replace_copy (InputIterator, InputIterator, OutputIterator, T, T)
OutputIterator replace_copy_if (InputIterator, InputIterator, OutputIterator, Predicate, T)
void replace_if (ForwardIterator, ForwardIterator, Predicate, T)
void reverse (BidirectionalIterator, BidirectionalIterator)
OutputIterator reverse_copy (BidirectionalIterator, BidirectionalIterator, OutputIterator)
ForwardIterator rotate (ForwardIterator, ForwardIterator, ForwardIterator)
OutputIterator rotate_copy (ForwardIterator, ForwardIterator, ForwardIterator, OutputIterator)
ForwardIterator1 search (ForwardIterator1, ForwardIterator1, ForwardIterator2, ForwardIterator2)
ForwardIterator1 search (ForwardIterator1, ForwardIterator1, ForwardIterator2, ForwardIterator2, BinaryPredicate)
ForwardIterator search_n (ForwardIterator, ForwardIterator, Size, T)
ForwardIterator search_n (ForwardIterator, ForwardIterator, Size, T, BinaryPredicate)
OutputIterator set_difference (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator)
OutputIterator set_difference (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator, Compare)
OutputIterator set_intersection (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator)
OutputIterator set_intersection (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator, Compare)
OutputIterator set_symmetric_difference (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator)
OutputIterator set_symmetric_difference (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator, Compare)
OutputIterator set_union (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator)
OutputIterator set_union (InputIterator1, InputIterator1, InputIterator2, InputIterator2, OutputIterator, Compare)
void shuffle (RandomAccessIterator, RandomAccessIterator, URandomNumberGeneratorenerator)
void sort (RandomAccessIterator, RandomAccessIterator)
void sort (RandomAccessIterator, RandomAccessIterator, Compare)
void sort_heap (RandomAccessIterator, RandomAccessIterator)
void sort_heap (RandomAccessIterator, RandomAccessIterator, Compare)
BidirectionalIterator stable_partition (BidirectionalIterator, BidirectionalIterator, Predicate)
void stable_sort (RandomAccessIterator, RandomAccessIterator)
void stable_sort (RandomAccessIterator, RandomAccessIterator, Compare)
ForwardIterator2 swap_ranges (ForwardIterator1, ForwardIterator1, ForwardIterator2)
OutputIterator transform (InputIterator, InputIterator, OutputIterator, UnaryOperation)
OutputIterator transform (InputIterator1, InputIterator1, InputIterator2, OutputIterator, UnaryOperation)
ForwardIterator unique (ForwardIterator, ForwardIterator)
ForwardIterator unique (ForwardIterator, ForwardIterator, BinaryPredicate)
OutputIterator unique_copy (InputIterator, InputIterator, OutputIterator)
OutputIterator unique_copy (InputIterator, InputIterator, OutputIterator, BinaryPredicate)
ForwardIterator upper_bound (ForwardIterator, ForwardIterator, T)
ForwardIterator upper_bound (ForwardIterator, ForwardIterator, T, Compare)

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:

T accumulate (InputIterator, InputIterator, T)
T accumulate (InputIterator, InputIterator, T, BinaryOperation)
OutputIterator adjacent_difference (InputIterator, InputIterator, OutputIterator)
OutputIterator adjacent_difference (InputIterator, InputIterator, OutputIterator, BinaryOperation)
OutputIterator copy (InputIterator, InputIterator, OutputIterator)
BidirectionalIterator2 copy_backward (BidirectionalIterator1, BidirectionalIterator1, BidirectionalIterator2)
Function for_each (InputIterator, InputIterator, Function)
T inner_product (InputIterator1, InputIterator1, InputIterator2, T)
T inner_product (InputIterator1, InputIterator1, InputIterator2, T, BinaryOperation1, BinaryOperation2)
OutputIterator move (InputIterator, InputIterator, OutputIterator)
BidirectionalIterator2 move_backward (BidirectionalIterator1, BidirectionalIterator1, BidirectionalIterator2)
OutputIterator partial_sum (InputIterator, InputIterator, OutputIterator)
OutputIterator partial_sum (InputIterator, InputIterator, OutputIterator, BinaryOperation)

[ 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:

OutputIterator transform (InputIterator, InputIterator, OutputIterator, UnaryOperation)

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.