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;
}