Przejdź do głównej zawartości

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 (od C++20).

Requirements

The type T satisfies Compare if

Given

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

ExpressionReturn typeRequirements
comp(a, b)implicitly convertible to boolEstablishes 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)boolEstablishes 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.

pubsetcollection of unique keys, sorted by keys
pubmapcollection of key-value pairs, sorted by keys, keys are unique
pubmultisetcollection of keys, sorted by keys
pubmultimapcollection of key-value pairs, sorted by keys
pubpriority_queueadapts a container to provide priority queue
pubsortsorts a range into ascending order
(function template)
pubsort(C++11)sorts the elements
(public member function of std::forward_list<T,Allocator>)
pubsortsorts the elements
(public member function of std::list<T,Allocator>)
pubstable_sortsorts a range of elements while preserving order between equal elements
pubpartial_sortsorts the first N elements of a range
pubpartial_sort_copycopies and partially sorts a range of elements
pubis_sorted(C++11)checks whether a range is sorted into ascending order
pubis_sorted_until(C++11)finds the largest sorted subrange
pubnth_elementpartially sorts the given range making sure that it is partitioned by the given element
publower_boundreturns an iterator to the first element not less than the given value
pubupper_boundreturns an iterator to the first element greater than a certain value
pubbinary_searchdetermines if an element exists in a partially-ordered range
pubequal_rangereturns range of elements matching a specific key
pubmergemerges two sorted ranges
(function template)
pubmerge(C++11)merges two sorted lists
(public member function of std::forward_list<T,Allocator>)
pubmergemerges two sorted lists
(public member function of std::list<T,Allocator>)
pubinplace_mergemerges two ordered ranges in-place
pubincludesreturns true if one sequence is a subsequence of another
pubset_differencecomputes the difference between two sets
pubset_intersectioncomputes the intersection of two sets
pubset_symetric_differencecomputes the symmetric difference between two sets
pubset_unioncomputes the union of two sets
pubpush_heapadds an element to a max heap
pubpop_heapremoves the largest element from a max heap
pubmake_heapcreates a max heap out of a range of elements
pubsort_heapturns a max heap into a range of elements sorted in ascending order
pubis_heap(C++11)checks if the given range is a max heap
pubis_heap_until(C++11)finds the largest subrange that is a max heap
pubmaxreturns the greater of the given values
pubmax_elementreturns the largest element in a range
pubminreturns the smaller of the given values
pubmin_elementreturns the smallest element in a range
pubminmax(C++11)returns the smaller and larger of two elements
pubminmax_element(C++11)returns the smallest and the largest elements in a range
publexicographical_comparereturns true if one range is lexicographically less than another
pubnext_permutationgenerates the next greater lexicographic permutation of a range of elements
pubprev_permutationgenerates the next smaller lexicographic permutation of a range of elements

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 (od C++20).

Requirements

The type T satisfies Compare if

Given

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

ExpressionReturn typeRequirements
comp(a, b)implicitly convertible to boolEstablishes 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)boolEstablishes 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.

pubsetcollection of unique keys, sorted by keys
pubmapcollection of key-value pairs, sorted by keys, keys are unique
pubmultisetcollection of keys, sorted by keys
pubmultimapcollection of key-value pairs, sorted by keys
pubpriority_queueadapts a container to provide priority queue
pubsortsorts a range into ascending order
(function template)
pubsort(C++11)sorts the elements
(public member function of std::forward_list<T,Allocator>)
pubsortsorts the elements
(public member function of std::list<T,Allocator>)
pubstable_sortsorts a range of elements while preserving order between equal elements
pubpartial_sortsorts the first N elements of a range
pubpartial_sort_copycopies and partially sorts a range of elements
pubis_sorted(C++11)checks whether a range is sorted into ascending order
pubis_sorted_until(C++11)finds the largest sorted subrange
pubnth_elementpartially sorts the given range making sure that it is partitioned by the given element
publower_boundreturns an iterator to the first element not less than the given value
pubupper_boundreturns an iterator to the first element greater than a certain value
pubbinary_searchdetermines if an element exists in a partially-ordered range
pubequal_rangereturns range of elements matching a specific key
pubmergemerges two sorted ranges
(function template)
pubmerge(C++11)merges two sorted lists
(public member function of std::forward_list<T,Allocator>)
pubmergemerges two sorted lists
(public member function of std::list<T,Allocator>)
pubinplace_mergemerges two ordered ranges in-place
pubincludesreturns true if one sequence is a subsequence of another
pubset_differencecomputes the difference between two sets
pubset_intersectioncomputes the intersection of two sets
pubset_symetric_differencecomputes the symmetric difference between two sets
pubset_unioncomputes the union of two sets
pubpush_heapadds an element to a max heap
pubpop_heapremoves the largest element from a max heap
pubmake_heapcreates a max heap out of a range of elements
pubsort_heapturns a max heap into a range of elements sorted in ascending order
pubis_heap(C++11)checks if the given range is a max heap
pubis_heap_until(C++11)finds the largest subrange that is a max heap
pubmaxreturns the greater of the given values
pubmax_elementreturns the largest element in a range
pubminreturns the smaller of the given values
pubmin_elementreturns the smallest element in a range
pubminmax(C++11)returns the smaller and larger of two elements
pubminmax_element(C++11)returns the smallest and the largest elements in a range
publexicographical_comparereturns true if one range is lexicographically less than another
pubnext_permutationgenerates the next greater lexicographic permutation of a range of elements
pubprev_permutationgenerates the next smaller lexicographic permutation of a range of elements