C++ Reference ยท Containers
Sorting and ordering in C++ containers
How C++ orders elements: std::sort, stable_sort, std::less and std::greater, custom comparators, strict weak ordering rules and ordered containers.
Sorting and ordered containers share one idea: a comparator, a callable that answers "does a come before b?". The default is std::less, which uses operator<. Algorithms such as std::sort and containers such as std::set and std::map accept a comparator so you can order by another field, in reverse, or case-insensitively.
A comparator must define a strict weak ordering: it returns false for equal elements (never <=), it is transitive, and equivalence ("neither is less than the other") is transitive too. Breaking these rules is undefined behavior and can crash std::sort.
std::sort(v.begin(), v.end()); // ascending std::sort(v.begin(), v.end(), std::greater<>{}); // descending std::set<int, std::greater<>> s; // ordered container, descending
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Syntax
template<class It, class Compare> void sort(It first, It last, Compare comp); // <algorithm> template<class It, class Compare> void stable_sort(It first, It last, Compare comp); template<class It, class Compare> void partial_sort(It first, It middle, It last, Compare comp); template<class It, class Compare> void nth_element(It first, It nth, It last, Compare comp); template<class T, class Compare = std::less<T>, class Alloc> class set; // <set>
| Name | Description |
|---|---|
first, last |
Random-access iterators for sort, stable_sort, partial_sort and nth_element. |
comp |
Callable taking two elements and returning something convertible to bool: true if the first must come before the second. |
Returns: nothing; the range is rearranged. std::ranges::sort returns an iterator to the end.
Undefined behavior: a comparator that is not a strict weak ordering (for example <=), or that changes the elements while comparing.
Usage notes
sortis not stable. Equal elements may change their relative order. Usestd::stable_sort(slightly slower, may allocate) when order among equals matters.- Complexity.
sortis O(n log n) comparisons;partial_sortfor the smallest k is about O(n log k);nth_elementfinds the k-th element in O(n) average. std::listandstd::forward_listhave membersort, becausestd::sortneeds random access.- Ordered containers (
set,map,multiset,multimap) keep elements sorted at all times, so you pay O(log n) per insert but never sort. Two keys are treated as the same when neither is less than the other. - Descending order is
std::greater<>, not a comparator that returnsa <= b. - Comparator state. A stateful comparator is copied, so keep it cheap or use
std::ref. - Three-way comparison. With
operator<=>(C++20) a type gets all comparison operators, andstd::lessuses it. See Three-way comparison. - Check first.
std::is_sortedtells whether a range is already ordered, which is required before binary-search algorithms.