From Jason Turner

[alg.min.max]

C++14 → C++17 8.1 KB 89 lines
Current Draft | LaTeX Source
Archived: C++14 | C++17
Markdown: C++14 | C++17
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmp_010lzvm/{from.md → to.md} +59 -26
tmp/tmp_010lzvm/{from.md → to.md} RENAMED
@@ -4,68 +4,76 @@
4
  template<class T> constexpr const T& min(const T& a, const T& b);
5
  template<class T, class Compare>
6
  constexpr const T& min(const T& a, const T& b, Compare comp);
7
  ```
8
 
9
- *Requires:* Type `T` is `LessThanComparable`
10
- (Table  [[lessthancomparable]]).
11
 
12
  *Returns:* The smaller value.
13
 
14
  *Remarks:* Returns the first argument when the arguments are equivalent.
15
 
 
 
16
  ``` cpp
17
  template<class T>
18
  constexpr T min(initializer_list<T> t);
19
  template<class T, class Compare>
20
  constexpr T min(initializer_list<T> t, Compare comp);
21
  ```
22
 
23
- *Requires:* `T` is `LessThanComparable` and `CopyConstructible` and
24
- `t.size() > 0`.
25
 
26
  *Returns:* The smallest value in the initializer_list.
27
 
28
  *Remarks:* Returns a copy of the leftmost argument when several
29
  arguments are equivalent to the smallest. 
30
 
 
 
31
  ``` cpp
32
  template<class T> constexpr const T& max(const T& a, const T& b);
33
  template<class T, class Compare>
34
  constexpr const T& max(const T& a, const T& b, Compare comp);
35
  ```
36
 
37
- *Requires:* Type `T` is `LessThanComparable`
38
- (Table  [[lessthancomparable]]).
39
 
40
  *Returns:* The larger value.
41
 
42
  *Remarks:* Returns the first argument when the arguments are equivalent.
43
 
 
 
44
  ``` cpp
45
  template<class T>
46
  constexpr T max(initializer_list<T> t);
47
  template<class T, class Compare>
48
  constexpr T max(initializer_list<T> t, Compare comp);
49
  ```
50
 
51
- *Requires:* `T` is `LessThanComparable` and `CopyConstructible` and
52
- `t.size() > 0`.
53
 
54
  *Returns:* The largest value in the initializer_list.
55
 
56
  *Remarks:* Returns a copy of the leftmost argument when several
57
  arguments are equivalent to the largest.
58
 
 
 
59
  ``` cpp
60
  template<class T> constexpr pair<const T&, const T&> minmax(const T& a, const T& b);
61
  template<class T, class Compare>
62
  constexpr pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp);
63
  ```
64
 
65
- *Requires:* Type `T` shall be `LessThanComparable`
66
- (Table  [[lessthancomparable]]).
67
 
68
  *Returns:* `pair<const T&, const T&>(b, a)` if `b` is smaller than `a`,
69
  and `pair<const T&, const T&>(a, b)` otherwise.
70
 
71
  *Remarks:* Returns `pair<const T&, const T&>(a, b)` when the arguments
@@ -78,70 +86,95 @@ template<class T>
78
  constexpr pair<T, T> minmax(initializer_list<T> t);
79
  template<class T, class Compare>
80
  constexpr pair<T, T> minmax(initializer_list<T> t, Compare comp);
81
  ```
82
 
83
- *Requires:* `T` is `LessThanComparable` and `CopyConstructible` and
84
- `t.size() > 0`.
85
 
86
  *Returns:* `pair<T, T>(x, y)`, where `x` has the smallest and `y` has
87
  the largest value in the initializer list.
88
 
89
  *Remarks:* `x` is a copy of the leftmost argument when several arguments
90
  are equivalent to the smallest. `y` is a copy of the rightmost argument
91
  when several arguments are equivalent to the largest.
92
 
93
- *Complexity:* At most `(3/2) * t.size()` applications of the
94
- corresponding predicate.
95
 
96
  ``` cpp
97
  template<class ForwardIterator>
98
- ForwardIterator min_element(ForwardIterator first, ForwardIterator last);
 
 
 
 
99
 
100
  template<class ForwardIterator, class Compare>
101
- ForwardIterator min_element(ForwardIterator first, ForwardIterator last,
 
 
 
 
102
  Compare comp);
103
  ```
104
 
105
  *Returns:* The first iterator `i` in the range \[`first`, `last`) such
106
  that for every iterator `j` in the range \[`first`, `last`) the
107
  following corresponding conditions hold: `!(*j < *i)` or
108
  `comp(*j, *i) == false`. Returns `last` if `first == last`.
109
 
110
- *Complexity:* Exactly `max((last - first) - 1, 0)` applications of the
111
  corresponding comparisons.
112
 
113
  ``` cpp
114
  template<class ForwardIterator>
115
- ForwardIterator max_element(ForwardIterator first, ForwardIterator last);
 
 
 
 
116
  template<class ForwardIterator, class Compare>
117
- ForwardIterator max_element(ForwardIterator first, ForwardIterator last,
 
 
 
 
118
  Compare comp);
119
  ```
120
 
121
  *Returns:* The first iterator `i` in the range \[`first`, `last`) such
122
  that for every iterator `j` in the range \[`first`, `last`) the
123
  following corresponding conditions hold: `!(*i < *j)` or
124
  `comp(*i, *j) == false`. Returns `last` if `first == last`.
125
 
126
- *Complexity:* Exactly `max((last - first) - 1, 0)` applications of the
127
  corresponding comparisons.
128
 
129
  ``` cpp
130
  template<class ForwardIterator>
131
- pair<ForwardIterator, ForwardIterator>
132
  minmax_element(ForwardIterator first, ForwardIterator last);
133
- template<class ForwardIterator, class Compare>
134
  pair<ForwardIterator, ForwardIterator>
 
 
 
 
 
135
  minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
 
 
 
 
136
  ```
137
 
138
  *Returns:* `make_pair(first, first)` if \[`first`, `last`) is empty,
139
  otherwise `make_pair(m, M)`, where `m` is the first iterator in
140
  \[`first`, `last`) such that no iterator in the range refers to a
141
- smaller element, and where `M` is the last iterator in \[`first`,
142
  `last`) such that no iterator in the range refers to a larger element.
143
 
144
- *Complexity:* At most $max(\lfloor{\frac{3}{2}} (N-1)\rfloor, 0)$
145
- applications of the corresponding predicate, where N is
146
- `distance(first, last)`.
147
 
 
4
  template<class T> constexpr const T& min(const T& a, const T& b);
5
  template<class T, class Compare>
6
  constexpr const T& min(const T& a, const T& b, Compare comp);
7
  ```
8
 
9
+ *Requires:* For the first form, type `T` shall be `LessThanComparable`
10
+ (Table  [[tab:lessthancomparable]]).
11
 
12
  *Returns:* The smaller value.
13
 
14
  *Remarks:* Returns the first argument when the arguments are equivalent.
15
 
16
+ *Complexity:* Exactly one comparison.
17
+
18
  ``` cpp
19
  template<class T>
20
  constexpr T min(initializer_list<T> t);
21
  template<class T, class Compare>
22
  constexpr T min(initializer_list<T> t, Compare comp);
23
  ```
24
 
25
+ *Requires:* `T` shall be `CopyConstructible` and `t.size() > 0`. For the
26
+ first form, type `T` shall be `LessThanComparable`.
27
 
28
  *Returns:* The smallest value in the initializer_list.
29
 
30
  *Remarks:* Returns a copy of the leftmost argument when several
31
  arguments are equivalent to the smallest. 
32
 
33
+ *Complexity:* Exactly `t.size() - 1` comparisons.
34
+
35
  ``` cpp
36
  template<class T> constexpr const T& max(const T& a, const T& b);
37
  template<class T, class Compare>
38
  constexpr const T& max(const T& a, const T& b, Compare comp);
39
  ```
40
 
41
+ *Requires:* For the first form, type `T` shall be `LessThanComparable`
42
+ (Table  [[tab:lessthancomparable]]).
43
 
44
  *Returns:* The larger value.
45
 
46
  *Remarks:* Returns the first argument when the arguments are equivalent.
47
 
48
+ *Complexity:* Exactly one comparison.
49
+
50
  ``` cpp
51
  template<class T>
52
  constexpr T max(initializer_list<T> t);
53
  template<class T, class Compare>
54
  constexpr T max(initializer_list<T> t, Compare comp);
55
  ```
56
 
57
+ *Requires:* `T` shall be `CopyConstructible` and `t.size() > 0`. For the
58
+ first form, type `T` shall be `LessThanComparable`.
59
 
60
  *Returns:* The largest value in the initializer_list.
61
 
62
  *Remarks:* Returns a copy of the leftmost argument when several
63
  arguments are equivalent to the largest.
64
 
65
+ *Complexity:* Exactly `t.size() - 1` comparisons.
66
+
67
  ``` cpp
68
  template<class T> constexpr pair<const T&, const T&> minmax(const T& a, const T& b);
69
  template<class T, class Compare>
70
  constexpr pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp);
71
  ```
72
 
73
+ *Requires:* For the first form, type `T` shall be `LessThanComparable`
74
+ (Table  [[tab:lessthancomparable]]).
75
 
76
  *Returns:* `pair<const T&, const T&>(b, a)` if `b` is smaller than `a`,
77
  and `pair<const T&, const T&>(a, b)` otherwise.
78
 
79
  *Remarks:* Returns `pair<const T&, const T&>(a, b)` when the arguments
 
86
  constexpr pair<T, T> minmax(initializer_list<T> t);
87
  template<class T, class Compare>
88
  constexpr pair<T, T> minmax(initializer_list<T> t, Compare comp);
89
  ```
90
 
91
+ *Requires:* `T` shall be `CopyConstructible` and `t.size() > 0`. For the
92
+ first form, type `T` shall be `LessThanComparable`.
93
 
94
  *Returns:* `pair<T, T>(x, y)`, where `x` has the smallest and `y` has
95
  the largest value in the initializer list.
96
 
97
  *Remarks:* `x` is a copy of the leftmost argument when several arguments
98
  are equivalent to the smallest. `y` is a copy of the rightmost argument
99
  when several arguments are equivalent to the largest.
100
 
101
+ *Complexity:* At most (3/2)`t.size()` applications of the corresponding
102
+ predicate.
103
 
104
  ``` cpp
105
  template<class ForwardIterator>
106
+ constexpr ForwardIterator min_element(ForwardIterator first, ForwardIterator last);
107
+
108
+ template<class ExecutionPolicy, class ForwardIterator>
109
+ ForwardIterator min_element(ExecutionPolicy&& exec,
110
+ ForwardIterator first, ForwardIterator last);
111
 
112
  template<class ForwardIterator, class Compare>
113
+ constexpr ForwardIterator min_element(ForwardIterator first, ForwardIterator last,
114
+ Compare comp);
115
+ template<class ExecutionPolicy, class ForwardIterator, class Compare>
116
+ ForwardIterator min_element(ExecutionPolicy&& exec,
117
+ ForwardIterator first, ForwardIterator last,
118
  Compare comp);
119
  ```
120
 
121
  *Returns:* The first iterator `i` in the range \[`first`, `last`) such
122
  that for every iterator `j` in the range \[`first`, `last`) the
123
  following corresponding conditions hold: `!(*j < *i)` or
124
  `comp(*j, *i) == false`. Returns `last` if `first == last`.
125
 
126
+ *Complexity:* Exactly max(`last - first - 1`, 0) applications of the
127
  corresponding comparisons.
128
 
129
  ``` cpp
130
  template<class ForwardIterator>
131
+ constexpr ForwardIterator max_element(ForwardIterator first, ForwardIterator last);
132
+ template<class ExecutionPolicy, class ForwardIterator>
133
+ ForwardIterator max_element(ExecutionPolicy&& exec,
134
+ ForwardIterator first, ForwardIterator last);
135
+
136
  template<class ForwardIterator, class Compare>
137
+ constexpr ForwardIterator max_element(ForwardIterator first, ForwardIterator last,
138
+ Compare comp);
139
+ template<class ExecutionPolicy, class ForwardIterator, class Compare>
140
+ ForwardIterator max_element(ExecutionPolicy&& exec,
141
+ ForwardIterator first, ForwardIterator last,
142
  Compare comp);
143
  ```
144
 
145
  *Returns:* The first iterator `i` in the range \[`first`, `last`) such
146
  that for every iterator `j` in the range \[`first`, `last`) the
147
  following corresponding conditions hold: `!(*i < *j)` or
148
  `comp(*i, *j) == false`. Returns `last` if `first == last`.
149
 
150
+ *Complexity:* Exactly max(`last - first - 1`, 0) applications of the
151
  corresponding comparisons.
152
 
153
  ``` cpp
154
  template<class ForwardIterator>
155
+ constexpr pair<ForwardIterator, ForwardIterator>
156
  minmax_element(ForwardIterator first, ForwardIterator last);
157
+ template<class ExecutionPolicy, class ForwardIterator>
158
  pair<ForwardIterator, ForwardIterator>
159
+ minmax_element(ExecutionPolicy&& exec,
160
+ ForwardIterator first, ForwardIterator last);
161
+
162
+ template<class ForwardIterator, class Compare>
163
+ constexpr pair<ForwardIterator, ForwardIterator>
164
  minmax_element(ForwardIterator first, ForwardIterator last, Compare comp);
165
+ template<class ExecutionPolicy, class ForwardIterator, class Compare>
166
+ pair<ForwardIterator, ForwardIterator>
167
+ minmax_element(ExecutionPolicy&& exec,
168
+ ForwardIterator first, ForwardIterator last, Compare comp);
169
  ```
170
 
171
  *Returns:* `make_pair(first, first)` if \[`first`, `last`) is empty,
172
  otherwise `make_pair(m, M)`, where `m` is the first iterator in
173
  \[`first`, `last`) such that no iterator in the range refers to a
174
+ smaller element, and where `M` is the last iterator[^5] in \[`first`,
175
  `last`) such that no iterator in the range refers to a larger element.
176
 
177
+ *Complexity:* At most
178
+ $\max(\bigl\lfloor{\frac{3}{2}} (N-1)\bigr\rfloor, 0)$ applications of
179
+ the corresponding predicate, where N is `last - first`.
180