C++ std::sort predicate with templates

By , last updated July 7, 2016

There are a couple of sorting algorithms in C++, each tailored to different use cases. As a programmer, you may or may not want to delve into the depths of sort algorithms. That’s a domain left for experts. Luckily, it’s quite easy to get started with sorting data.

Sorting methods in C++

With C++, there is a standardized sort method readily available. It’s called std::sort and works by calling it with a range it should sort, usually a begin-iterator and an end-iterator. Normal use cases are sorting a vector or an array, but any container which implements the RandomAccess-iterator can be sorted. Containers like std::list can’t be sorted with std::sort. std::sort is available in the <algorithm> header.

If you try to sort std::list with std::sort, you’ll get a compile error. The error will be a variation of not being able to use operator - on the std::list iterator type. If you want to sort a list, you’ll have to use std::list::sort.

Using qsort to sort structs or classes will not be covered.

What algorithm std::sort will use, is left to the implementation, but the complexity should not exceed O(N log N) where N is number of elements to sort. Implementations are usually implementing std::sort by combining different sort algorithms with different strengths and weaknesses. One such algorithm is IntroSort.

IntroSort is a hybrid sort algorithm, invented in 1997 by David Musser. The goal of IntroSort is to provide a sorting algorithm, which has a fast average performance and an optimal worst case performance. It combines Quicksort and Heapsort, and combines the good parts from both algorithms. Due to this, IntroSort has an average performance and a worst case performance of O(n log n), where N is number of elements.

In theory, sorting numbers and sorting any data is not different. They use the same algorithm, the same range, and the same method. The only difference is the comparison between elements. But that’s standardized too. The real difference is the method comparing the elements.

To sort a collection of any data (also known as POD, Plain Old Data) with STL we need to tell it how to sort these objects. This chapter will go through many of those methods.

Sorting "Hello World!"

Most tutorials about sorting starts with sorting some numbers. But any container with RandomIterator can be sorted with std::sort. And as it happens to be, std::string implements RandomIterator.

#include <algorithm>
#include <string>
#include <iostream>

std::string hello{ "Hello World!" };
std::sort(hello.begin(), hello.end());
std::cout << hello << "\n";

Output will be !HWdellloor. Notice the space in front, which is the first character.

Professional Software Developer, doing mostly C++. Connect with Kent on Twitter.