std::sort Comparison Function

Introduction

This article is a crash course on the STL’s std::sort comparison functions. I have an ex-colleague who used std::sort to sort a array of strings in ascending order and then copied the sorted array into another array in an reversal order, in order to achieve sorting in a descending order. His method is a waste of processor cycles and memory. He could have achieved sorting in a descending order by using the std::greater function object defined in the functional header or writing a comparison function for predicate version of std::sort. That incident prompted me to write this article. This article is a quick guide for programmers looking for information on how to write comparison function for std::sort. Without further ado, let us begin!

How to use std::sort

template <class RandomAccessIterator>
  void sort ( RandomAccessIterator first, RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>
  void sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );

Let’s do a quick refresh on how to use std::sort on arrays and containers like std::tr1::array, std::vector and std::deque. For sorting the array in ascending order, you need to specify the address of the first element of the array for the first parameter and the address of one past the last element of the array for the second parameter. Below is an example.

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

int main()
{
	int arr[5];
	arr[0] = 2;
	arr[1] = 3;
	arr[2] = 5;
	arr[3] = 1;
	arr[4] = 4;

	std::sort(arr,arr+5);

	std::cout<<arr[0]<<"n";
	std::cout<<arr[1]<<"n";
	std::cout<<arr[2]<<"n";
	std::cout<<arr[3]<<"n";
	std::cout<<arr[4]<<std::endl;

	return 0;
}

The output is as follows,

1
2
3
4
5

To achieve descending order, include the functional header and replace “std::sort(arr,arr+5);” line with “std::sort(arr,arr+5,std::greater());”

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

int main()
{
	int arr[5];
	arr[0] = 2;
	arr[1] = 3;
	arr[2] = 5;
	arr[3] = 1;
	arr[4] = 4;

	std::sort(arr,arr+5,std::greater());
	std::cout<<arr[0]<<"n";
	std::cout<<arr[1]<<"n";
	std::cout<<arr[2]<<"n";
	std::cout<<arr[3]<<"n";
	std::cout<<arr[4]<<std::endl;

	return 0;
}

The output is as follows,

5
4
3
2
1

For sorting std::tr1::array, std::vector or std::deque in ascending order, you specify the begin() method which returns the first iterator, as first parameter and end() method which returns the one iterator past the last iterator, as the second parameter. Below is an example of the std::vector.

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

int main()
{
	std::vector<int> vec;
	vec.push_back(2);
	vec.push_back(3);
	vec.push_back(5);
	vec.push_back(1);
	vec.push_back(4);

	std::sort(vec.begin(),vec.end());

	for(size_t i=0; i<vec.size(); ++i)
		std::cout<<vec[i]<<std::endl;

	return 0;
}

The output for the above code snippet is as follows,

1
2
3
4
5

Please take note that you cannot use std::sort to sort std::list which is a single-linked list because std::sort requires random access iterators, to work, which std::list does not have.

Global < Operator

std::sort calls std::less for its comparison and std::less, in turn, calls the < operator of the element type. For POD types, the < operator is already defined. For your own custom classes, you need to define our own < operator. There are two ways to go about defining your own < operator, you can define it as either a global < operator or member < operator function of the class. Below is an example of how to define a global < operator for the Person class.

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

class Person
{
public:
	// default constructor
	Person() : age(0) {}
	Person(int age, std::string name) {
		this->age = age; this->name = name;
	}
	int age;
	std::string name;
};

inline bool operator<(const Person& a, const Person& b)
{
	return a.age < b.age;
}

int main()
{
	std::vector<Person> vecPerson;
	vecPerson.push_back(Person(24,"Calvin"));
	vecPerson.push_back(Person(30,"Benny"));
	vecPerson.push_back(Person(28,"Alison"));

	std::sort(vecPerson.begin(),vecPerson.end());

	for(size_t i=0; i<vecPerson.size(); ++i)
		std::cout<<vecPerson[i].age<<", "<<vecPerson[i].name<<std::endl;

	return 0;
}

The output is as below,

24, Calvin
28, Alison
30, Benny

Member < Operator

Next is an example of how to define a member < operator for the Person class.

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

class Person
{
public:
	// default constructor
	Person() : age(0) {}
	Person(int age, std::string name) {
		this->age = age; this->name = name;
	}
	bool operator<(const Person& rhs)
	{
		return this->age < rhs.age;
	}
	int age;
	std::string name;
};

int main()
{
	std::vector<Person> vecPerson;
	vecPerson.push_back(Person(24,"Calvin"));
	vecPerson.push_back(Person(30,"Benny"));
	vecPerson.push_back(Person(28,"Alison"));

	std::sort(vecPerson.begin(),vecPerson.end());

	for(size_t i=0; i<vecPerson.size(); ++i)
		std::cout<<vecPerson[i].age<<", "<<vecPerson[i].name<<std::endl;

	return 0;
}

The output is the same as the global < operator example,

24, Calvin
28, Alison
30, Benny

You might ask if there is any advantages for the member operator function over the global operator function. Yes, there is! A member operator function can access the private and protected data members of the class whereas a global operator function cannot. If age in the Person class is a private member, global operator functions cannot access it without using a accessor function.

More by Author

Must Read