How to Reorder A Collection With the STL

The STL lets you do plenty of things on collections, and one of them is to reorder the elements inside of the collection. Or, said another way, to perform a permutation on the collection.

Inded, moving elements around a collection typically takes a fair amount of complex code to write, involving for loops and iterators. And it is perhaps the area where the STL generates the most spectacular improvements, by encapsulating those complex operations behing meaningful interfaces.

Let’s see what sorts of permutations the STL offers:

• Lexicographical permutations
• Cyclic permutations
• Random permutation
• Reverse
• Checking for permutations
• Other permutations

Thanks a lot to Stephan T. Lavavej for reviewing this article.

Lexicographical permutations

A given collection containing N elements can be reordered in several different ways (N! ways, to be accurate). Is it possible to iterate over all those permutations, and be sure not to forget any of them?

To achieve this, we can define an order on the set of permutations of a given collection. This way, we could start from one permutation, then go to the “next” one and to the “next” one and so on, until we’re back to our starting point.

But is there a natural way to order permutations?

It turns out there is: permutations of a given collection can be ordered by a lexicographical order. Imagine that each permutation of a collection is a “word”, and the elements of the collections are the “letters” that compose it.

Then we could sort those words by “alphabetical order” (I’m using quotes since we’re not talking about actual chars and strings here, it’s just to get the idea). For this to work, we need the elements of the collection to implement an operator< for comparing them.

To illustrate, here are 4 permutations of the collection {1, 2, 3, 4, 5} in increasing lexicographical order:

{1, 2, 3, 4, 5}
{1, 2, 3, 5, 4}
{1, 2, 4, 3, 5}
{1, 2, 4, 5, 3}
...

Now how to do this with the STL?

To go from one permutation to the next in lexicographical order, use std::next_permutation:

vector<int> v = {1, 2, 3, 4, 5 };

std::next_permutation(v.begin(), v.end()); // v now contains {1, 2, 3, 5, 4}

std::next_permutation returns a bool that is true if the permutation obtained is lexicographically bigger than the input permutation (in all cases but one), and false otherwise (in the unique case where the increase looped over and the range came back to the first (smallest) permutation).

And to go from one permutation to the previous one, use std::prev_permutation:

vector<int> v = {1, 2, 3, 5, 4};

std::prev_permutation(v.begin(), v.end()); // v now contains {1, 2, 3, 4, 5 }

Symmetrically, std::prev_permutation returns a bool that is true if the permutation obtained is lexicographically smaller than the input permutation (all cases but one), and false otherwise (in the unique case where the range was reset to the last (biggest) permutation).

std::next_permutation and std::prev_permutation operate directly on the range passed in argument, which makes it easy to apply them several times in a row:

std::vector<int> numbers = {1, 2, 3, 4};
do
{
    for (int n : numbers) std::cout << n << ' ';
    std::cout << '\n';
}
while (std::next_permutation(begin(numbers), end(numbers)));

The above code prints out:

1 2 3 4 
1 2 4 3 
1 3 2 4 
1 3 4 2 
1 4 2 3 
1 4 3 2 
2 1 3 4 
2 1 4 3 
2 3 1 4 
2 3 4 1 
2 4 1 3 
2 4 3 1 
3 1 2 4 
3 1 4 2 
3 2 1 4 
3 2 4 1 
3 4 1 2 
3 4 2 1 
4 1 2 3 
4 1 3 2 
4 2 1 3 
4 2 3 1 
4 3 1 2 
4 3 2 1

These are all the permutations of {1, 2, 3, 4} before it looped over to its inital position.

Cyclic permutations

A cyclic permutation moves down the elements in a collection and puts the elements at the end of the collection to its beginning. For instance the following permutations are cyclic permutations of {1, 2, 3, 4, 5}:

{1, 2, 3, 4, 5}
{5, 1, 2, 3, 4}
{4, 5, 1, 2, 3}
{3, 4, 5, 1, 2}
{2, 3, 4, 5, 1}

For a collection of N elements, there are N distinct cyclic permutations.

Basic usage

In C++, cyclic permutations are performed with std::rotate.

std::rotate takes 3 iterators:

• one pointing to the beginning of the range,
• one pointing to the element that you want std::rotate to bring up to the 1st position,
• one pointing to the end of the range.

In C++11, std::rotate returns an iterator pointing to the position where the first element has been brought. Here is its interface:

template<typename ForwardIterator>
ForwardIterator rotate(ForwardIterator begin, ForwardIterator new_begin, ForwardIterator end);

The interface in C++98 is slightly different as it returns void:

template<typename ForwardIterator>
void rotate(ForwardIterator begin, ForwardIterator new_begin, ForwardIterator end);

std::rotate operates directly on the range it is passed. If you want to leave this range unchanged, use std::rotate_copy to write the output into another collection.

An interesting usage of std::rotate

std::rotate can be built upon to create new algorithms, as shown by Sean Parent’s in its famous talk C++ Seasoning he gave at GoingNative 2013. Let’s see the example Sean demonstrated, as it is revealing of the power of using STL algorithms.

The example is this: given a range, how to implement an algorithm that “slides” a subset of contiguous elements over to a given position in the range ?

Just think a minute about how you would have implemented it, just to get a grasp of the complexity of the problem.

In fact, sliding the elements from first to last over to pos is equivalent to performing a cyclic permutation on the range first to pos, putting last at the beginning. This is precisely what std::rotate does:

std::rotate(first, last, pos);

Now this works only if last < pos, meaning that the elements are slided forward. How to slide them backwards, to a position pos < first ?

Sliding elements backwards also comes down to performing a cyclic permutation, on the range from pos to last, but this time putting first at the beginning. So the implementation is:

std::rotate(pos, first, last);

Now if pos is between first and last, it means that elements need to be slided to where they already are, so no need to do anything.

Putting this all together, the implementation is:

if (pos < first) std::rotate(pos, first, last);
if (last < pos) std::rotate(first, last, pos);

Based on the C++11 interface that returns the new position the elements that was at the beginning of the range before applying std::rotate, we can even return the range where the elements are located after the sliding has occurred:

• If pos < first, the slided elements are located between pos and the new position of the first element of the rotated range (not the slided range), which is the return value of std::rotate(pos, first, last).
• If last < pos, the slided elements are located between the new position of the first element, and pos.

In summary the implementation of slide would be:

template <typename RandomAccessIterator>
std::pair<RandomAccessIterator, RandomAccessIterator> slide(RandomAccessIterator first, RandomAccessIterator last, RandomAccessIterator pos)
{
    if (pos < first) return { pos, std::rotate(pos, first, last) };
    if (last < pos) return { std::rotate(first, last, pos), pos };
    return { first, last };
}

Even if it is not related to the permutation on the collection itself, we can note that returning a pair of iterators in this case is questionable. Indeed, what we mean to return is really a range, represented by its beginning and end.

For this reason we can consider raising the level of abstraction of this interface and returning a type that better expresses this intention, in the spirit of boost::iterator_range or the iterator_range class of range-v3. Note that we had already encountered this need when looking at the interface of std::equal_range to find something efficiently with the STL.

Random permutation

One simple way to reorder the elements of a collection is to shuffle them at random!

For this, you can use std::shuffle which does exactly that:

#include <random>
#include <algorithm>
#include <vector>

std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
 
std::random_device randomDevice;
std::mt19937 generator(randomDevice());
 
std::shuffle(begin(numbers), end(numbers), generator);

for (int n : numbers) std::cout << n << ' ';

The above code prints the new ordering of numbers:

8 10 5 1 7 2 3 6 4 9

The doomed std::random_shuffle

Here is an important note: before C++11 it was std::random_shuffle that allowed to achieve this feature. But its source of randomness (rand()) was less than ideal (although it had another overload that allowed to provide another generator but it was very obnoxious to use). So it was deprecated in C++14 and removed in C++17. So you should not use it.

On the other hand, its replacement std::shuffle has been introduced in C++11. So if you’re in C++98 how do you do to shuffle a collection without introducing technical debt?

If you have encountered that case personnally (I haven’t), it would be great if you could share it, as there are quite a few people in the C++ community still in the process of migrating to C++11 as I’m writing those lines.

Reverse

An even simpler permutation is reversing the elements of a collection, which you can do with… std::reverse!

std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
 
std::reverse(begin(numbers), end(numbers));

Printing the contents of numbers gives:

10 9 8 7 6 5 4 3 2 1

Checking for permutations

To check if a collection is a permutation of another one, you can use is_permutation that is described in detail in this part of the article on predicates on ranges.

Other permutations

Did we cover all the ways the STL lets us change the order of the elements of a collection here?

Not yet! There are other types of permutations, and that have enough depth to deserve their own articles:

• Partitioning with the STL algorithms
• Sorting with the STL algorithms
• Operating on Heaps with the STL algorithms

Don't want to miss out ? Follow:   
Share this post!