In this article we will discuss STL Algorithm std::sort algorithm.
std::sort is a STL Algorithm which provides the functionality of sorting a given range of elements. To use std::sort we need to pass start and end of range in it as an argument i.e.
std::sort (<START OF RANGE> , <END OF RANGE>);
For example, we have an array of integers and we want to sort them using std::sort . Let’s see how to do this,
int arr[] = { 1, 3, 2, 8, 6, 7, 5 }; int len = sizeof(arr) / sizeof(int); std::sort(arr, arr + len);
We can use std::sort with array and containers too. But only with containers that provides random access functionality like std::vector etc.
It can not be used with std::list and associative containers because they don’t have random access iterators.
This sorting function compares the elements in given range using operator <.
How to sort a vector of Strings using std::sort
std::vector<std::string> vecOfStrings; vecOfStrings.push_back("bbb"); vecOfStrings.push_back("fff"); vecOfStrings.push_back("aaa"); vecOfStrings.push_back("ccc"); vecOfStrings.push_back("abc"); std::sort(vecOfStrings.begin(), vecOfStrings.end()); std::for_each(vecOfStrings.begin(), vecOfStrings.end(), [](std::string str) { std::cout<<str<< " , "; });
std::sort will use the < operator for sorting provided range of strings, therefore given string elements will be sorted in lexicographical order i.e
aaa , abc , bbb , ccc , fff
Till now we have seen how to sort primitive data types with std::sort. Now lets see,
Sorting User Defined Objects with std::sort
Suppose we have a class Person with name and id as member variables. Now we want to sort a vector of class Person objects on the basis of id.
[showads ad=inside_post]
To that wee need to to overload < operator in class Person because std::sort algorithm uses this < operator for comparision while sorting.
Lets see the code of class Person,
class Person { public: std::string m_name; int m_id; Person(std::string name, int id) : m_name(name), m_id(id) { } bool operator <(const Person & obj) { if (m_id < obj.m_id) return true; else return false; } };
Now lets sort a vector of class Person objects based on its id using its internal < operator i.e.
std::vector<Person> vecOfPersons = { Person("aaa", 7), Person("kkk", 3), Person("ddd", 5), Person("abc", 2) }; std::sort(vecOfPersons.begin(), vecOfPersons.end()); std::cout << "Sorted Persons List based on ID\n"; std::for_each(vecOfPersons.begin(), vecOfPersons.end(), [](Person & obj) { std::cout<<obj.m_id<< " :: "<<obj.m_name<<std::endl; });
Output will be like this,
2 :: abc
3 :: kkk
5 :: ddd
7 :: aaa
Now suppose a new requirement comes and we want to sort sort a vector of class Person objects based on its name instead of id.
Also we don’t can not change the current implementation of < operator in class.
In such scenario we will use overloaded version of std::sort that accepts a comparator (Function Pointer/ Object) as an argument and uses that for comparisons instead of < operator.
Lets see how to define a Function Object for this scenario
struct PersonCompartor { bool operator()(const Person & first, const Person & sec) { if (first.m_name < sec.m_name) return true; else return false; } };
Now lets use this comparator in std::sort for sorting Person Objects based on name i.e.
std::sort(vecOfPersons.begin(), vecOfPersons.end(), PersonCompartor()); std::cout << "Sorted Persons List based on Name using Func Object\n"; std::for_each(vecOfPersons.begin(), vecOfPersons.end(), [](Person & obj) { std::cout<<obj.m_id<< " :: "<<obj.m_name<<std::endl; });
Output:
7 :: aaa
2 :: abc
5 :: ddd
3 :: kkk
Same can be achieved using lambda function instead of comparators in std::sort i.e.
std::sort(vecOfPersons.begin(), vecOfPersons.end(), [](const Person & first, const Person & sec) { if (first.m_name < sec.m_name) return true; else return false; });
Complete Code is as follows,
#include <iostream> #include <algorithm> #include <vector> #include <string> class Person { public: std::string m_name; int m_id; Person(std::string name, int id) : m_name(name), m_id(id) { } bool operator <(const Person & obj) { if (m_id < obj.m_id) return true; else return false; } }; struct PersonCompartor { bool operator()(const Person & first, const Person & sec) { if (first.m_name < sec.m_name) return true; else return false; } }; int main() { int arr[] = { 1, 3, 2, 8, 6, 7, 5 }; int len = sizeof(arr) / sizeof(int); std::sort(arr, arr + len); for (int i = 0; i < len; i++) std::cout << arr[i] << " , "; std::cout << std::endl; std::vector<std::string> vecOfStrings; vecOfStrings.push_back("bbb"); vecOfStrings.push_back("fff"); vecOfStrings.push_back("aaa"); vecOfStrings.push_back("ccc"); vecOfStrings.push_back("abc"); std::sort(vecOfStrings.begin(), vecOfStrings.end()); std::for_each(vecOfStrings.begin(), vecOfStrings.end(), [](std::string str) { std::cout<<str<< " , "; }); std::cout << std::endl; std::vector<Person> vecOfPersons = { Person("aaa", 7), Person("kkk", 3), Person("ddd", 5), Person("abc", 2) }; std::sort(vecOfPersons.begin(), vecOfPersons.end()); std::cout << "Sorted Persons List based on ID\n"; std::for_each(vecOfPersons.begin(), vecOfPersons.end(), [](Person & obj) { std::cout<<obj.m_id<< " :: "<<obj.m_name<<std::endl; }); std::sort(vecOfPersons.begin(), vecOfPersons.end(), PersonCompartor()); std::cout << "Sorted Persons List based on Name using Func Object\n"; std::for_each(vecOfPersons.begin(), vecOfPersons.end(), [](Person & obj) { std::cout<<obj.m_id<< " :: "<<obj.m_name<<std::endl; }); std::cout << "Sorted Persons List based on Name using Lamba\n"; std::sort(vecOfPersons.begin(), vecOfPersons.end(), [](const Person & first, const Person & sec) { if (first.m_name < sec.m_name) return true; else return false; }); std::cout << "Sorted Persons List based on Name\n"; std::for_each(vecOfPersons.begin(), vecOfPersons.end(), [](Person & obj) { std::cout<<obj.m_id<< " :: "<<obj.m_name<<std::endl; }); return 0; }