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 contextually 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 (since C++20).
Requirements
The type T satisfies Compare if
- The type T satisfies BinaryPredicate, and
Given
comp, an object of typeTequiv(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) | implicitly convertible to bool | 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.
| pub | set | collection of unique keys, sorted by keys |
| pub | map | collection of key-value pairs, sorted by keys, keys are unique |
| pub | multiset | collection of keys, sorted by keys |
| pub | multimap | collection of key-value pairs, sorted by keys |
| pub | priority_queue | adapts a container to provide priority queue |
| pub | sort | sorts a range into ascending order (function template) |
| pub | sort(C++11) | sorts the elements (public member function of std::forward_list<T,Allocator>) |
| pub | sort | sorts the elements (public member function of std::list<T,Allocator>) |
| pub | stable_sort | sorts a range of elements while preserving order between equal elements |
| pub | partial_sort | sorts the first N elements of a range |
| pub | partial_sort_copy | copies and partially sorts a range of elements |
| pub | is_sorted(C++11) | checks whether a range is sorted into ascending order |
| pub | is_sorted_until(C++11) | finds the largest sorted subrange |
| pub | nth_element | partially sorts the given range making sure that it is partitioned by the given element |
| pub | lower_bound | returns an iterator to the first element not less than the given value |
| pub | upper_bound | returns an iterator to the first element greater than a certain value |
| pub | binary_search | determines if an element exists in a partially-ordered range |
| pub | equal_range | returns range of elements matching a specific key |
| pub | merge | merges two sorted ranges (function template) |
| pub | merge(C++11) | merges two sorted lists (public member function of std::forward_list<T,Allocator>) |
| pub | merge | merges two sorted lists (public member function of std::list<T,Allocator>) |
| pub | inplace_merge | merges two ordered ranges in-place |
| pub | includes | returns true if one sequence is a subsequence of another |
| pub | set_difference | computes the difference between two sets |
| pub | set_intersection | computes the intersection of two sets |
| pub | set_symetric_difference | computes the symmetric difference between two sets |
| pub | set_union | computes the union of two sets |
| pub | push_heap | adds an element to a max heap |
| pub | pop_heap | removes the largest element from a max heap |
| pub | make_heap | creates a max heap out of a range of elements |
| pub | sort_heap | turns a max heap into a range of elements sorted in ascending order |
| pub | is_heap(C++11) | checks if the given range is a max heap |
| pub | is_heap_until(C++11) | finds the largest subrange that is a max heap |
| pub | max | returns the greater of the given values |
| pub | max_element | returns the largest element in a range |
| pub | min | returns the smaller of the given values |
| pub | min_element | returns the smallest element in a range |
| pub | minmax(C++11) | returns the smaller and larger of two elements |
| pub | minmax_element(C++11) | returns the smallest and the largest elements in a range |
| pub | lexicographical_compare | returns true if one range is lexicographically less than another |
| pub | next_permutation | generates the next greater lexicographic permutation of a range of elements |
| pub | prev_permutation | generates the next smaller lexicographic permutation of a range of elements |