By Kent Fagerjord, last updated July 7, 2016

Contents

- 1Sorting methods in C++
- 2Sorting "Hello World!"
- 3Sorting structs and classes
- 3.1Member operator < overload
- 3.2Non-member operator < overload
- 3.3Sort predicate examples
- 3.3.1Lambda as a sort predicate
- 3.3.2Free method (non-member method) sort predicate
- 3.3.3Member method sort predicate
- 3.3.4Sorting with template predicates
- 4Sorting std::list

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.

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.

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.

C++ std::sort predicate with templates was last modified: July 7th, 2016 by Kent Fagerjord

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