C++ Tutorial – Sorting STL Containers

C++ Tutorial – Sorting STL Containers

Welcome to the first C++ tutorial ever written in here. Our tutorials are typically centered around C# and Flex, however lots of people in the world (including me) program in C++ every day – and the standard template library is an integral part of any modern C++ project. This tutorial is going to demonstrate how to use the built-in algorithms to perform custom sorting on standard template library collections.

The STL object I’m going to be using as my example will be a vector, which is one of several containers offered by the library. To use a vector, you’ll have to include <vector>. All of the algorithms, like sort, are located in <algorithm>. And of course, everything inside the standard template library is located in the std namespace.

Let’s start by using the simplest form of sort.

using namespace std;

//create a vector
vector<int> v;

//populate the vector
v.push_back(2);
v.push_back(3);
v.push_back(1);
v.push_back(5);
v.push_back(4);

//sort the vector
sort(v.begin(), v.end());

//v = {1, 2, 3, 4, 5}

This use of the sort function will sort the elements by applying the < operator on each element. So if you were populating this vector with your custom objects, you’d have to define the < operator to sort them. The sort function takes two iterators, which are essentially pointers to objects inside the collection. The begin() and end() functions return iterators that point to the first element and the last element respectively. Since sort will sort the elements between these two iterators, you could sort just a portion of the vector if you wanted:

using namespace std;
 
 //create a vector
 vector<int> v;
 
 //populate the vector
 v.push_back(2);
 v.push_back(3);
 v.push_back(1);
 v.push_back(5);
 v.push_back(4);
 
 //sort the last two elements
 sort(v.begin() + 3, v.end());
 
 //v = {2, 3, 1, 4, 5}

All right, enough with iterators. Let’s look at another version of the sort function. One that takes a functor instead of using the < operator.

Using namespace std;
 
 //create a vector
 vector<int> v;
 
 //populate the vector
 v.push_back(2);
 v.push_back(3);
 v.push_back(1);
 v.push_back(5);
 v.push_back(4);
 
 struct reverseSort
 {
  bool operator()(int a, int b) { return b < a; }
 };
 
 //sort the elements using custom functor
 sort(v.begin(), v.end(), reverseSort());
 
 //v = {5, 4, 3, 2, 1}

Functors are typically just functions or function pointers, but they are also objects that define the () operator. Here I created a struct that defines the () operator and takes two integers as arguments. The sort function will now use this functor to compare objects in my collection. In my example, I reversed the default comparer, which will sort the vector in the reverse order – largest to smallest.

The functor object passed into sort must be a Binary Predicate – that is a function that takes two arguments and returns a boolean. The sort function is also not stable, meaning if two objects resolve to the same value, their orders in the list are not guaranteed to be the same as they were before sort was called. If stability is required, stable_sort will get the job done.

That’s pretty much it for sorting standard template library containers. The sort function uses the introsort algorithm, which has a complexity of O(N log(N)) and is a hybrid of QuickSort and HeapSort.

Share this post

Post Comment