神刀安全网

STL Algorithm – std::sort Tutorial and Example

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 (<STARTOFRANGE> , <END OFRANGE>); 

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.

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

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » STL Algorithm – std::sort Tutorial and Example

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
分享按钮