The sort method of std accepts two iterators, begin and end, and abstracts access to the elements through the iterators, hiding the internal implementation.

This is a simple example:

1
2
3
4
5
6
7
8
9

std::list<int> list {
    0,
    4,
    2,
    1,
    3,
};

std::sort(list.begin(), list.end());

The result is that the list is sorted, and we don’t need to care about what sorting algorithm is used. In fact, the standard library decides what algorithm to use by the number of elements, based on Introspective Sorting. It is a hybrid sorting algorithm that.

  • Normal fast sort is used when the amount of data is large, when the efficiency is O(logN).
  • Once the amount of data after segmentation is less than a certain threshold, insertion sort is used instead, because this segmentation is basically ordered at this time, and the efficiency is up to O(N) at this time.
  • During recursion, if the recursion level is too deep and the segmentation behavior tends to deteriorate, it can automatically detect it and use heap sort to handle it, in this case keeping its efficiency at O(N logN) of heap sort, but this is again better than using heap sort at the beginning.

By default the sort is ascending, both the result is from smallest to largest, and we can control the sort by using std::equal_to, std::not_equal_to, std::greater, std::less, std::greater_equal, and std::less_equal.

These are some of the ways to control sorting that are built into the standard library and are applicable when the element has implemented a custom Compare requirement.

Compare is a set of requirements expected by some standard library facilities for user-supplied function object types.

The return value of a function call applied to an object of a type satisfying Compare, when contextually converted to bool, generates true if the first real parameter of the call precedes the second real parameter in the strict weak-order relationship introduced by the type, and false otherwise.

As with any BinaryPredicate, the evaluation of this expression is not allowed to call a non-const function via a dereferenced iterator.

In human terms, Compare must provide a comparison result.

See an example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

struct Test {
    int i;
}

std::list<Test> list {
    new Test(2),
    new Test(1),
    new Test(4),
    new Test(3),
    new Test(5),
};

std::sort(list.begin(), list.end(), [=] (const Test& test1, const Test& test2) -> bool {
    return test1.i < test2.i;
});

This example provides a Compare to provide a custom comparison function via lambda. The return value must be bool, otherwise the comparison function will not be satisfied.

As you can see from the above three approaches, the standard library sort function can easily provide users with both standard and custom comparisons. If the elements themselves have been implemented operator<, you only need to use the comparison function built into the standard library, but most of the cases actually do not involve the sorting of elements, and only in temporary cases need the list to be ordered, so I personally tend to provide the Compare function through lambda to complete the sorting of the list.