Namespaces
Variants
Views
Actions

Difference between revisions of "cpp/named req/Compare"

From cppreference.com
< cpp‎ | named req
m (added Spanish link)
m (fmt.)
 
(13 intermediate revisions by 6 users not shown)
Line 4: Line 4:
 
{{named req|Compare}} is a set of requirements expected by some of the standard library facilities from the user-provided function object types.
 
{{named req|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 {{named req/core|Compare}}, when [[cpp/language/implicit_cast|contextually converted]] to {{c|bool}}, yields {{c|true}} if the first argument of the call appears before the second in the ''strict weak ordering relation'' induced by this type, and {{c|false}} otherwise.
+
The return value of the function call operation applied to an object of a type satisfying {{named req/core|Compare}}, when [[cpp/language/implicit conversion|converted]] to {{c/core|bool}}, yields {{c|true}} if the first argument of the call appears before the second in the {{enwiki|Strict weak ordering|strict weak ordering relation}} induced by this type, and {{c|false}} otherwise.
  
−
As with any {{named req|BinaryPredicate}}, evaluation of that expression is not allowed to call non-const functions through the dereferenced iterators. <!-- see also LWG 3031 -->
+
As with any {{named req|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 {{c/core|const}} object arguments, with the same behavior regardless of whether the arguments are {{c/core|const}} or non-{{c/core|const}}.
  
 
===Requirements===
 
===Requirements===
Line 14: Line 14:
  
 
Given
 
Given
−
* {{tt|comp}}, an object of type {{tt|T}}
+
* {{tt|comp}}, an object of type {{tt|T}},
−
* {{tt|equiv(a, b)}}, an expression equivalent to {{tt|!comp(a, b) && !comp(b, a)}}
+
* {{c|equiv(a, b)}}, an [[cpp/language/expressions#Expression-equivalence|expression-equivalent]] to {{c|!comp(a, b) && !comp(b, a)}}.
  
−
The following expressions must be valid and have their specified effects
+
The following expressions must be valid and have their specified effects:
  
 
{|table class=wikitable
 
{|table class=wikitable
Line 23: Line 23:
 
!Expression||Return type||Requirements
 
!Expression||Return type||Requirements
 
|-
 
|-
−
| {{c|comp(a, b)}}
+
|{{c|comp(a, b)}}
−
| [[cpp/language/implicit_cast|implicitly convertible]] to {{c|bool}}
+
|{{rrev multi|noborder=true
−
| Establishes [[enwiki:Strict_weak_ordering|strict weak ordering]] relation with the following properties
+
|rev1=meets {{named req|BooleanTestable}}
−
* For all {{tt|a}}, {{c|comp(a,a){{==}}false}}
+
|since2=c++20|rev2=models ''{{ltt|cpp/concepts/boolean-testable}}''
−
* If {{c|comp(a,b){{==}}true}} then {{c|comp(b,a){{==}}false}}
+
}}
−
* if {{c|comp(a,b){{==}}true}} and {{c|comp(b,c){{==}}true}} then {{c|comp(a,c){{==}}true}}
+
|Establishes {{enwiki|strict weak ordering}} relation with the following properties:
 +
* For all {{tt|a}}, {{c|1=comp(a, a) == false}}.
 +
* If {{c|1=comp(a, b) == true}} then {{c|1=comp(b, a) == false}}.
 +
* if {{c|1=comp(a, b) == true}} and {{c|1=comp(b, c) == true}} then {{c|1=comp(a, c) == true}}.
 
|-
 
|-
−
| {{c|equiv(a, b)}}
+
|{{c|equiv(a, b)}}
−
| {{c|bool}}
+
|{{c/core|bool}}
−
| Establishes equivalence relationship with the following properties
+
|Establishes {{enwiki|equivalence relation}}ship with the following properties:
−
* For all {{tt|a}}, {{c|equiv(a,a){{==}}true}}
+
* For all {{tt|a}}, {{c|1=equiv(a, a) == true}}.
−
* If {{c|equiv(a,b){{==}}true}}, then {{c|equiv(b,a){{==}}true}}
+
* If {{c|1=equiv(a, b) == true}}, then {{c|1=equiv(b, a) == true}}.
−
* If {{c|equiv(a,b){{==}}true}} and {{c|equiv(b,c){{==}}true}}, then {{c|equiv(a,c){{==}}true}}
+
* If {{c|1=equiv(a, b) == true}} and {{c|1=equiv(b, c) == true}}, then {{c|1=equiv(a, c) == true}}.
 
|}
 
|}
  
−
Note: {{tt|comp}} induces a ''strict total ordering'' on the equivalence classes determined by {{tt|equiv}}
+
Note: {{tt|comp}} induces a {{enwiki|Total order#Strict and non-strict total orders|strict total ordering}} on the equivalence classes determined by {{tt|equiv}}.
  
 
===Standard library===
 
===Standard library===
 
The following standard library facilities expect a {{named req/core|Compare}} type.
 
The following standard library facilities expect a {{named req/core|Compare}} type.
 
{{dsc begin}}
 
{{dsc begin}}
−
{{dsc inc | cpp/container/dsc set}}
+
{{dsc inc|cpp/container/dsc set}}
−
{{dsc inc | cpp/container/dsc map}}
+
{{dsc inc|cpp/container/dsc map}}
−
{{dsc inc | cpp/container/dsc multiset}}
+
{{dsc inc|cpp/container/dsc multiset}}
−
{{dsc inc | cpp/container/dsc multimap}}
+
{{dsc inc|cpp/container/dsc multimap}}
−
{{dsc inc | cpp/container/dsc priority_queue}}
+
{{dsc inc|cpp/container/dsc priority_queue}}
−
{{dsc inc | cpp/algorithm/dsc sort}}
+
{{dsc inc|cpp/algorithm/dsc sort}}
−
{{dsc inc | cpp/container/dsc sort | forward_list}}
+
{{dsc inc|cpp/container/dsc sort|forward_list}}
−
{{dsc inc | cpp/container/dsc sort | list}}
+
{{dsc inc|cpp/container/dsc sort|list}}
−
{{dsc inc | cpp/algorithm/dsc stable_sort}}
+
{{dsc inc|cpp/algorithm/dsc stable_sort}}
−
{{dsc inc | cpp/algorithm/dsc partial_sort}}
+
{{dsc inc|cpp/algorithm/dsc partial_sort}}
−
{{dsc inc | cpp/algorithm/dsc partial_sort_copy}}
+
{{dsc inc|cpp/algorithm/dsc partial_sort_copy}}
−
{{dsc inc | cpp/algorithm/dsc is_sorted}}
+
{{dsc inc|cpp/algorithm/dsc is_sorted}}
−
{{dsc inc | cpp/algorithm/dsc is_sorted_until}}
+
{{dsc inc|cpp/algorithm/dsc is_sorted_until}}
−
{{dsc inc | cpp/algorithm/dsc nth_element}}
+
{{dsc inc|cpp/algorithm/dsc nth_element}}
−
{{dsc inc | cpp/algorithm/dsc lower_bound}}
+
{{dsc inc|cpp/algorithm/dsc lower_bound}}
−
{{dsc inc | cpp/algorithm/dsc upper_bound}}
+
{{dsc inc|cpp/algorithm/dsc upper_bound}}
−
{{dsc inc | cpp/algorithm/dsc binary_search}}
+
{{dsc inc|cpp/algorithm/dsc binary_search}}
−
{{dsc inc | cpp/algorithm/dsc equal_range}}
+
{{dsc inc|cpp/algorithm/dsc equal_range}}
−
{{dsc inc | cpp/algorithm/dsc merge}}
+
{{dsc inc|cpp/algorithm/dsc merge}}
−
{{dsc inc | cpp/container/dsc merge | forward_list}}
+
{{dsc inc|cpp/container/dsc merge|forward_list}}
−
{{dsc inc | cpp/container/dsc merge | list}}
+
{{dsc inc|cpp/container/dsc merge|list}}
−
{{dsc inc | cpp/algorithm/dsc inplace_merge}}
+
{{dsc inc|cpp/algorithm/dsc inplace_merge}}
−
{{dsc inc | cpp/algorithm/dsc includes}}
+
{{dsc inc|cpp/algorithm/dsc includes}}
−
{{dsc inc | cpp/algorithm/dsc set_difference}}
+
{{dsc inc|cpp/algorithm/dsc set_difference}}
−
{{dsc inc | cpp/algorithm/dsc set_intersection}}
+
{{dsc inc|cpp/algorithm/dsc set_intersection}}
−
{{dsc inc | cpp/algorithm/dsc set_symmetric_difference}}
+
{{dsc inc|cpp/algorithm/dsc set_symmetric_difference}}
−
{{dsc inc | cpp/algorithm/dsc set_union}}
+
{{dsc inc|cpp/algorithm/dsc set_union}}
−
{{dsc inc | cpp/algorithm/dsc push_heap}}
+
{{dsc inc|cpp/algorithm/dsc push_heap}}
−
{{dsc inc | cpp/algorithm/dsc pop_heap}}
+
{{dsc inc|cpp/algorithm/dsc pop_heap}}
−
{{dsc inc | cpp/algorithm/dsc make_heap}}
+
{{dsc inc|cpp/algorithm/dsc make_heap}}
−
{{dsc inc | cpp/algorithm/dsc sort_heap}}
+
{{dsc inc|cpp/algorithm/dsc sort_heap}}
−
{{dsc inc | cpp/algorithm/dsc is_heap}}
+
{{dsc inc|cpp/algorithm/dsc is_heap}}
−
{{dsc inc | cpp/algorithm/dsc is_heap_until}}
+
{{dsc inc|cpp/algorithm/dsc is_heap_until}}
−
{{dsc inc | cpp/algorithm/dsc max}}
+
{{dsc inc|cpp/algorithm/dsc max}}
−
{{dsc inc | cpp/algorithm/dsc max_element}}
+
{{dsc inc|cpp/algorithm/dsc max_element}}
−
{{dsc inc | cpp/algorithm/dsc min}}
+
{{dsc inc|cpp/algorithm/dsc min}}
−
{{dsc inc | cpp/algorithm/dsc min_element}}
+
{{dsc inc|cpp/algorithm/dsc min_element}}
−
{{dsc inc | cpp/algorithm/dsc minmax}}
+
{{dsc inc|cpp/algorithm/dsc minmax}}
−
{{dsc inc | cpp/algorithm/dsc minmax_element}}
+
{{dsc inc|cpp/algorithm/dsc minmax_element}}
−
{{dsc inc | cpp/algorithm/dsc lexicographical_compare}}
+
{{dsc inc|cpp/algorithm/dsc lexicographical_compare}}
−
{{dsc inc | cpp/algorithm/dsc next_permutation}}
+
{{dsc inc|cpp/algorithm/dsc next_permutation}}
−
{{dsc inc | cpp/algorithm/dsc prev_permutation}}
+
{{dsc inc|cpp/algorithm/dsc prev_permutation}}
 +
{{dsc end}}
 +
 
 +
===Defect reports===
 +
{{dr list begin}}
 +
{{dr list item|wg=lwg|dr=2114|paper=P2167R3|std=C++98|before=contextual convertibility of return types to {{c/core|bool}} did not<br>reflect the practice of implementations|after=requirements corrected}}
 +
{{dr list item|wg=lwg|dr=3031|std=C++98|before=requirements on {{c/core|const}} values were insufficent|after=requirements strengthened}}
 +
{{dr list end}}
 +
 
 +
===See also===
 +
{{dsc begin}}
 +
{{dsc inc|cpp/concepts/dsc strict_weak_order}}
 +
{{dsc|[[cpp/language/operator comparison|'''Comparison operators''']]|{{tt|<}}, {{tt|1=<=}}, {{tt|1= >}}, {{tt|1= >=}}, {{tt|1= ==}}, {{tt|1= !=}}, and {{tt|1= <=>}} {{mark c++20}}, compare the arguments}}
 
{{dsc end}}
 
{{dsc end}}
  
 
{{langlinks|es|ja|zh}}
 
{{langlinks|es|ja|zh}}

Latest revision as of 07:54, 9 September 2024

 
C++
 
C++ named requirements
 

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.

Contents

[edit] Requirements

The type T satisfies Compare if

Given

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.

[edit] Standard library

The following standard library facilities expect a Compare type.

collection of unique keys, sorted by keys
(class template) [edit]
collection of key-value pairs, sorted by keys, keys are unique
(class template) [edit]
collection of keys, sorted by keys
(class template) [edit]
collection of key-value pairs, sorted by keys
(class template) [edit]
adapts a container to provide priority queue
(class template) [edit]
sorts a range into ascending order
(function template) [edit]
sorts the elements
(public member function of std::forward_list<T,Allocator>) [edit]
sorts the elements
(public member function of std::list<T,Allocator>) [edit]
sorts a range of elements while preserving order between equal elements
(function template) [edit]
sorts the first N elements of a range
(function template) [edit]
copies and partially sorts a range of elements
(function template) [edit]
(C++11)
 checks whether a range is sorted into ascending order
(function template) [edit]
(C++11)
 finds the largest sorted subrange
(function template) [edit]
partially sorts the given range making sure that it is partitioned by the given element
(function template) [edit]
returns an iterator to the first element not less than the given value
(function template) [edit]
returns an iterator to the first element greater than a certain value
(function template) [edit]
determines if an element exists in a partially-ordered range
(function template) [edit]
returns range of elements matching a specific key
(function template) [edit]
merges two sorted ranges
(function template) [edit]
merges two sorted lists
(public member function of std::forward_list<T,Allocator>) [edit]
merges two sorted lists
(public member function of std::list<T,Allocator>) [edit]
merges two ordered ranges in-place
(function template) [edit]
returns true if one sequence is a subsequence of another
(function template) [edit]
computes the difference between two sets
(function template) [edit]
computes the intersection of two sets
(function template) [edit]
computes the symmetric difference between two sets
(function template) [edit]
computes the union of two sets
(function template) [edit]
adds an element to a max heap
(function template) [edit]
removes the largest element from a max heap
(function template) [edit]
creates a max heap out of a range of elements
(function template) [edit]
turns a max heap into a range of elements sorted in ascending order
(function template) [edit]
(C++11)
 checks if the given range is a max heap
(function template) [edit]
(C++11)
 finds the largest subrange that is a max heap
(function template) [edit]
returns the greater of the given values
(function template) [edit]
returns the largest element in a range
(function template) [edit]
returns the smaller of the given values
(function template) [edit]
returns the smallest element in a range
(function template) [edit]
(C++11)
 returns the smaller and larger of two elements
(function template) [edit]
(C++11)
 returns the smallest and the largest elements in a range
(function template) [edit]
returns true if one range is lexicographically less than another
(function template) [edit]
generates the next greater lexicographic permutation of a range of elements
(function template) [edit]
generates the next smaller lexicographic permutation of a range of elements
(function template) [edit]

[edit] 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

[edit] See also

(C++20)
 specifies that a relation imposes a strict weak ordering
(concept) [edit]
Comparison operators <, <=, >, >=, ==, !=, and <=> (C++20), compare the arguments
Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/named_req/Compare&oldid=175974"