Skip to content
Tutorials Center
My learning

Topics

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.

C++
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

C++ Sorting with comparators

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.

C++ Ordered containers and custom order

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

C++
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

  • sort is not stable. Equal elements may change their relative order. Use std::stable_sort (slightly slower, may allocate) when order among equals matters.
  • Complexity. sort is O(n log n) comparisons; partial_sort for the smallest k is about O(n log k); nth_element finds the k-th element in O(n) average.
  • std::list and std::forward_list have member sort, because std::sort needs 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 returns a <= 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, and std::less uses it. See Three-way comparison.
  • Check first. std::is_sorted tells whether a range is already ordered, which is required before binary-search algorithms.