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 ( Ι, ι ) 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

nelements. Add another element to the end of the sequence, then swap it with a randomly chosen element of the new (sizen + 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*