std::sort Comparison Function

Table of Contents

• Introduction
• How To Use std::sort
• Global < Operator
• Member < Operator
• A Function Pointer as Comparison Function
• A Function Object as Comparison Function
• Boost Lambda Library
• C++0x Lambda
• qsort
• stable_sort
• partial_sort
• partial_sort_copy
• Conclusion

Introduction

This article is a crash course on the STL's std::sort comparison functions. I have a 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<string> 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. Thus, 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 us do a quick refresh on how to use std::sort on arrays and ontainers like std::vector and std::deque. For sorting the array in ascending order, we 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<int>()); 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 in ascending order, we specify the std::vector::begin() which returns the first iterator, as first parameter and std::vector::end() which returns the one iterator past the last iterator, as the second parameter. Below is an example.

#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 our own custom classes, we need to define our own < operator. There is 2 ways to go about defining our own < operator, we can define it as either a global < operator or member < operator function of the class. Below is an example of how to define our own 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 our own 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 may ask if there is any advantages of member operator function over global operator function. Yes, there is. Member operator function can access the private and protected data members of the class whereas 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.

A function pointer as comparison function

What if we want to sort vector of Person by descending order? There are 2 ways to go about it: We can either define a comparison function and pass its function pointer to the prediate version of std::sort, or define a comparison function object(also known as functors) and pass it to the prediate version of std::sort as a comparison prediate.

If we are interesting to know who are the senior in age, we may sort by age descending and followed by name ascending. This is custom sorting, as opposed to sorting in descending order. Below is an example, using function pointer as a sorting prediate.

#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; }; bool Greater(const Person& a, const Person& b) { if(a.age == b.age) return a.name < b.name; 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(30,"Alice")); vecPerson.push_back(Person(28,"Alison")); std::sort(vecPerson.begin(),vecPerson.end(),Greater); 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 follows,

30, Alice
30, Benny
28, Alison
24, Calvin

A function object as comparison function

Below is an example of sorting, using function object (which is also known as functor) as a prediate. Any further discussion on how to write function objects is beyond the scope of this article; you may read this wikipedia on function object for more information.

#include <vector> #include <algorithm> #include <iostream> #include <string> #include <functional> 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; }; // function object struct GreaterAge : public std::binary_function<Person,Person,bool> { inline bool operator()(const Person& a, const Person& b) { if(a.age == b.age) return a.name < b.name; 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(30,"Alice")); vecPerson.push_back(Person(28,"Alison")); std::sort(vecPerson.begin(),vecPerson.end(),GreaterAge()); for(size_t i=0; i<vecPerson.size(); ++i) std::cout<<vecPerson[i].age<<", "<<vecPerson[i].name<<std::endl; return 0; }

This is the output

30, Alice
30, Benny
28, Alison
24, Calvin

Note: if we do not derived our function object from std::binary_function class, the above example would work just as well. Below is an example of the above function object not inheriting from any class.

// function object struct GreaterAge { inline bool operator()(const Person& a, const Person& b) { if(a.age == b.age) return a.name < b.name; return a.age > b.age; } }; 

You may ask, between function pointer and function object, which is preferred choice for writing comparison. The answer is function object because we can inline a function object for better performance whereas we cannot inline a function pointer. This is the reason why std::sort performs better than C's qsort. As C++ programmers, we should always use std::sort over qsort because qsort do not have type safety.

Boost Lambda Library

We can also specify the comparison function as an anonymous function, using Boost Lambda Library or C++0x Lambda. We shall see an example of using the Boost Lambda as an anonymous comparison function for the sorting an array of integers in descending order. We need to specify the return type of the lambda as boolean. _1 and _2 is the 2 integer arguments passed to the Lambda comparison function. Note: as seen in the earlier second code example in this article, we can achieve the same thing, using greater<int> prediate.

#include <algorithm> #include <iostream> #include <string> #include <cstdlib> #include <functional> #include <boost/lambda/lambda.hpp> int main() { int arr[5]; arr[0] = 2; arr[1] = 3; arr[2] = 5; arr[3] = 1; arr[4] = 4; using namespace boost::lambda; std::sort(arr,arr+5, ret<bool>(_1 > _2)); 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; }

This is the output as follows,

5
4
3
2
1

In the second Boost Lambda example, we are going to sort a vector of Person objects in ascending order.

#include <vector> #include <algorithm> #include <iostream> #include <string> #include <boost/lambda/lambda.hpp> #include <boost/lambda/casts.hpp> #include <boost/function/function_base.hpp> 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; }; int main() { std::vector<Person> vecPerson; vecPerson.push_back(Person(24,"Calvin")); vecPerson.push_back(Person(30,"Benny")); vecPerson.push_back(Person(28,"Alison")); using namespace boost::lambda; std::sort(vecPerson.begin(),vecPerson.end(), ret<bool>( (&_1 ->* &Person::age) < (&_2 ->* &Person::age) ) ); for(size_t i=0; i<vecPerson.size(); ++i) std::cout<<vecPerson[i].age<<", "<<vecPerson[i].name<<std::endl; return 0; }

This is the output as follows,

24, Calvin
28, Alison
30, Benny

As we can see, this Boost Lambda syntax is more complex. The return type is specified first, followed by expression to compare the Person::age. To get the value of Person::age member, we need to put ampersand on left side of the arguments(_1 and _2) to convert it into an pointer so that we can use the overloaded pointer-to-member(->*) operator to access Person::age member. Ampersand is also put on the left of Person::age to get its address. If your vanilla comparison function is more complex than comparing class members, you will have a hard time in converting it to a Boost Lambda function because you have to use Boost Lambda's unnatural constructs to do if-else, switch-case, while-loop and so on. For more information on Boost Lambda, please refer to its documentation here. Next, let us look at the C++0x Lambda.

C++0x Lambda

Lambda is a language feature in the new upcoming C++ standard. To try out the C++0x Lambda examples listed below, you need to install Visual Studio 2010 Beta 1. You can download it here. You are advised to install Visual Studio 2010 Beta 1 in Virtual PC so as not to disrupt your current Visual Studio installation. You can download Virtual PC's OS images here. For more instructions on how to install Visual Studio 2010 Beta 1, you can refer to this website.

Let us look at the example of using the C++0x Lambda as an anonymous comparison function for the sorting an array of integers in descending order.

#include <algorithm> #include <iostream> #include <string> #include <cstdlib> 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, [](int x, int y){return x > y;}); 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; }

[] denotes the start of C++0x lambda. x and y are the arguments to the lambda. We are free to name this 2 arguments as we like, unlike in Boost Lambda, it has to be _1 and _2. We did not specify the return type of the lambda, it is automatically infer from the only return statement. We can get away without specifying the return type of lambda but we are only restricted to 1 expression which is the return statement.

This is the output as follows,

5
4
3
2
1

In the second C++0x Lambda example, we are going to sort a vector of Person objects with the age value in descending order and if the 2 age values are equal, then it is resolved by sorting the name in ascending order. Since this lambda has more than 1 statement, we need to specify its boolean return type, using this syntax, -> bool.

#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; }; int main() { std::vector<Person> vecPerson; vecPerson.push_back(Person(24,"Calvin")); vecPerson.push_back(Person(30,"Benny")); vecPerson.push_back(Person(30,"Alice")); vecPerson.push_back(Person(28,"Alison")); std::sort(vecPerson.begin(),vecPerson.end(), [](const Person& a, const Person& b) -> bool { if(a.age == b.age) return a.name < b.name; return a.age > b.age; }); for(size_t i=0; i<vecPerson.size(); ++i) std::cout<<vecPerson[i].age<<", "<<vecPerson[i].name<<std::endl; return 0; }

We can afford to do more with C++0x Lambda than Boost Lambda because the C++0x Lambda body syntax(refers to code enclosed in the curly parenthesis) is the same as pre-C++0x syntax, therefore is more natural and is easy to understand. For more information on C++0x Lambda syntax, please refer to this page.

This is the output as follows,

30, Alice
30, Benny
28, Alison
24, Calvin

Boost Lambda is implemented as a library while C++0x Lambda is implemented as a language feature. This explains why Boost Lambda syntax is convoluted, compared to C++0x Lambda syntax, due to workarounds to get over the C98 C++ language limitations.

qsort

Since we are on the topic of comparison function, let me show you briefly on how to write the comparison function for qsort. For sorting by ascending order, the comparison function has to return 0 if the 2 arguments are equal; It should return greater than zero if the first argument is greater than the second argument and return lesser than zero if the first argument is lesser than the second argument. Of course, you would reverse the return values if you want sorting by descending order. Below is an example of the qsort comparison function. For more information, please read this MSDN link

#include <iostream> #include <string> #include <cstdlib> int compare(const void* x, const void* y) { int* a = (int*)x; int* b = (int*)y; if(*a==*b) return 0; return *a > *b ? +1 : -1; } int main() { int arr[5]; arr[0] = 2; arr[1] = 3; arr[2] = 5; arr[3] = 1; arr[4] = 4; std::qsort(arr,5,sizeof(int),compare); 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

std::stable_sort

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

Since we are on the topic on std::sort, I'll touch briefly on std::stable_sort and other STL sort algorithms. The usage of std::stable_sort is the same as std::sort. The only difference is std::stable_sort will respect the original order of the elements which are equal whereas std::sort do not. std::stable_sort performs this trick at the expense of some performance because there are more comparisons made in order to determine if any 2 elements are equal. The strange thing is std::stable_sort does not require the element type to have the equality operator(==) defined; std::stable_sort determines if 2 elements are equal by using this expression !(xhere.

std::partial_sort

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

std::partial_sort rearranges elements in such a way that the subrange [first,middle) contains the smallest elements of the entire range sorted in ascending order, and the subrange [middle,end) contains the remaining elements without any specific order. The comparison function is the same as std::sort. For more information on std::partial_sort, you may read here.

std::partial_sort_copy

template <class InputIterator, class RandomAccessIterator> RandomAccessIterator partial_sort_copy ( InputIterator first,InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last ); template <class InputIterator, class RandomAccessIterator, class Compare> RandomAccessIterator partial_sort_copy ( InputIterator first,InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp ); 

std::partial_sort_copy sorts the same way as std::partial_sort except it would copy the results to [results_first,results_last). The comparison function is the same as std::sort. For more information on std::partial_sort_copy, you may read this link.

Conclusion

In this article, we have looked at how to use std::sort, how to define a < operators and the custom comparison function as either a function pointer or a function object. We have also looked briefly on qsort, std::stable_sort, std::partial_sort and std::partial_sort_copy. If you like this article and articles on STL, I may write more articles on useful STL algortihms. Thank you for reading!

Update history

License

This article, along with any associated source code and files, is licensed under The Intelliproject Open License (IPOL)

About the author