C++ named requirements: Compare

Compare is a set of requirements expected by some of the standard library facilities from the user-provided function object types.

The return value of the function call operation applied to an object of a type satisfying Compare, when converted to bool, yields true if the first argument of the call appears before the second in the strict weak ordering relation induced by this type, and false otherwise.

As with any BinaryPredicate, evaluation of that expression is not allowed to call non-const functions through the dereferenced iterators and, syntactically, the function call operation must accept const object arguments, with the same behavior regardless of whether the arguments are const or non-const.

Requirements

The type T satisfies Compare if

The type T satisfies BinaryPredicate, and

Given

comp, an object of type T,
equiv(a, b), an expression-equivalent to !comp(a, b) && !comp(b, a).

The following expressions must be valid and have their specified effects:

Expression Return type Requirements

comp(a, b)

meets BooleanTestable	(until C++20)
models `boolean-testable`	(since C++20)

Establishes strict weak ordering relation with the following properties:

For all a, comp(a, a) == false.
If comp(a, b) == true then comp(b, a) == false.
if comp(a, b) == true and comp(b, c) == true then comp(a, c) == true.

equiv(a, b)

bool

Establishes equivalence relationship with the following properties:

For all a, equiv(a, a) == true.
If equiv(a, b) == true, then equiv(b, a) == true.
If equiv(a, b) == true and equiv(b, c) == true, then equiv(a, c) == true.

Note: comp induces a strict total ordering on the equivalence classes determined by equiv.

Standard library

The following standard library facilities expect a Compare type.

set	collection of unique keys, sorted by keys (class template)
map	collection of key-value pairs, sorted by keys, keys are unique (class template)
multiset	collection of keys, sorted by keys (class template)
multimap	collection of key-value pairs, sorted by keys (class template)
priority_queue	adapts a container to provide priority queue (class template)
sort	sorts a range of elements (function template & algorithm function object)
ranges::sort (C++20)
sort	sorts the elements (public member function of `std::forward_list<T,Allocator>`)
sort	sorts the elements (public member function of `std::list<T,Allocator>`)
stable_sort	sorts a range of elements while preserving relative order between equivalent elements (function template & algorithm function object)
ranges::stable_sort (C++20)
partial_sort	sorts the first N elements of a range (function template & algorithm function object)
ranges::partial_sort (C++20)
partial_sort_copy	copies and partially sorts a range of elements (function template & algorithm function object)
ranges::partial_sort_copy (C++20)
is_sorted (C++11)	checks whether a range is sorted (function template & algorithm function object)
ranges::is_sorted (C++20)
is_sorted_until (C++11)	finds the largest sorted subrange (function template & algorithm function object)
ranges::is_sorted_until (C++20)
nth_element	finds the Nth element if the range were sorted (function template & algorithm function object)
ranges::nth_element (C++20)
lower_bound	finds the first element not less than the given value using binary search (function template & algorithm function object)
ranges::lower_bound (C++20)
upper_bound	finds the first element greater than the given value using binary search (function template & algorithm function object)
ranges::upper_bound (C++20)
binary_search	determines if an element exists in a range using binary search (function template & algorithm function object)
ranges::binary_search (C++20)
equal_range	finds the range of elements matching the given value using binary search (function template & algorithm function object)
ranges::equal_range (C++20)
merge	merges two sorted ranges (function template & algorithm function object)
ranges::merge (C++20)
merge	merges two sorted lists (public member function of `std::forward_list<T,Allocator>`)
merge	merges two sorted lists (public member function of `std::list<T,Allocator>`)
inplace_merge	merges two ordered ranges in-place (function template & algorithm function object)
ranges::inplace_merge (C++20)
includes	determines if one sequence is a subsequence of another (function template & algorithm function object)
ranges::includes (C++20)
set_difference	computes the difference between two sets (function template & algorithm function object)
ranges::set_difference (C++20)
set_intersection	computes the intersection of two sets (function template & algorithm function object)
ranges::set_intersection (C++20)
set_symmetric_difference	computes the symmetric difference between two sets (function template & algorithm function object)
ranges::set_symmetric_difference (C++20)
set_union	computes the union of two sets (function template & algorithm function object)
ranges::set_union (C++20)
push_heap	adds an element to a max heap (function template & algorithm function object)
ranges::push_heap (C++20)
pop_heap	removes the largest element from a max heap (function template & algorithm function object)
ranges::pop_heap (C++20)
make_heap	creates a max heap out of a range of elements (function template & algorithm function object)
ranges::make_heap (C++20)
sort_heap	turns a max heap into a range of elements sorted in ascending order (function template & algorithm function object)
ranges::sort_heap (C++20)
is_heap (C++11)	checks if the given range is a max heap (function template & algorithm function object)
ranges::is_heap (C++20)
is_heap_until (C++11)	finds the largest subrange that is a max heap (function template & algorithm function object)
ranges::is_heap_until (C++20)
max	returns the greater of the given values (function template & algorithm function object)
ranges::max (C++20)
max_element	returns the largest element in a range (function template & algorithm function object)
ranges::max_element (C++20)
min	returns the smaller of the given values (function template & algorithm function object)
ranges::min (C++20)
min_element	returns the smallest element in a range (function template & algorithm function object)
ranges::min_element (C++20)
minmax (C++11)	returns the smaller and larger of two elements (function template & algorithm function object)
ranges::minmax (C++20)
minmax_element (C++11)	returns the smallest and the largest elements in a range (function template & algorithm function object)
ranges::minmax_element (C++20)
lexicographical_compare	compares two ranges lexicographically (function template & algorithm function object)
ranges::lexicographical_compare (C++20)
next_permutation	generates the next greater lexicographic permutation of a range of elements (function template & algorithm function object)
ranges::next_permutation (C++20)
prev_permutation	generates the next smaller lexicographic permutation of a range of elements (function template & algorithm function object)
ranges::prev_permutation (C++20)

Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

DR	Applied to	Behavior as published	Correct behavior
LWG 2114 (P2167R3)	C++98	contextual convertibility of return types to bool did not reflect the practice of implementations	requirements corrected
LWG 3031	C++98	requirements on const values were insufficent	requirements strengthened

strict_weak_order (C++20)	specifies that a `relation` imposes a strict weak ordering (concept)
Comparison operators	`<`, `<=`, `>`, `>=`, `==`, `!=`, and `<=>` (C++20), compare the arguments

C++ named requirements: Compare

Requirements

Standard library

Defect reports

See also