How does comparator function of c++ STL sort work?

user_11752608 0
Viewed 5235
bool sortbysec(const pair<int,int> &a,const pair<int,int> &b) 
{ 
    return (a.second < b.second); 
} 
  

sort(vect.begin(), vect.end(), sortbysec);

vector< pair <int, int> > vect; 
  
int arr[] = {10, 17, 5, 70 }; 
int arr1[] = {30, 60, 20, 50}; 
int n = sizeof(arr)/sizeof(arr[0]); 
  
for (int i=0; i<n; i++) 
    vect.push_back( make_pair(arr[i],arr1[i]));

what does return(a.second<b.second) mean? how is it sorting by the second element?

sorting stl c++
1 Answers

The concept of a sorted sequence s, in abstract, is that for any pair of elements s[i] and s[j], s[i] is not greater than s[j] when i is less than j.

Sorting a sequence is simply rearranging the elements of the sequence to satisfy this definition. Therefore, in order to sort elements, we need to be able to ask if a particular value is less than or greater than some other value -- otherwise we cannot be sure that our arrangement of the sequence satisfies the definition of a "sorted sequence."

std::sort takes a comparison function as a means of answering this question. By default, it is std::less<T>() which simply uses the operator < to compare two elements. By applying this function to two elements, it can determine if they need to be rearranged. Looking at our definition of a sorted sequence, if s[j] < s[i] when i < j then the definition is not met. Swapping those two elements corrects the problem for that specific pair of elements.

By applying this comparison function along with a sorting algorithm, std::sort is able to determine the order that the elements should be in for the sequence to be sorted. That's all the sort function does: it applies this comparison function to pairs of elements and rearranges them until the sequence is sorted.

You can supply any comparison function fn that has strict weak ordering and std::sort will rearrange the elements as necessary to ensure that !fn(s[i], s[j]) is true for all valid index pairs i and j where i > j. This allows you to manipulate the sort function to get specific orders. For example:

  • If you supply a function that compares using the > operator instead of the < operator, then the sorted sequence will be in descending order.
  • You can supply a function that compares a specific attribute of the values. If you have a sequence of struct Person { std::string name; int age; } values, you could have a function that compares the ages only, which will sort the sequence by the age attribute.
    • You could even sort on multiple attributes. If you compare age first and then compare name if the ages are equal, the sequence will be sorted by age -- but within each subsequence where the age is equal, that subsequence is sorted by name.
user_5012500
Related