From Jason Turner

[alg.binary.search]

C++23 → Trunk 7.5 KB 56 lines
Current Draft | LaTeX Source
Archived: C++23
Markdown: C++23 | Trunk
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmp9wzrg98i/{from.md → to.md} +30 -18
tmp/tmp9wzrg98i/{from.md → to.md} RENAMED
@@ -13,25 +13,28 @@ through the data structure. For non-random access iterators they execute
13
  a linear number of steps.
14
 
15
  #### `lower_bound` <a id="lower.bound">[[lower.bound]]</a>
16
 
17
  ``` cpp
18
- template<class ForwardIterator, class T>
19
  constexpr ForwardIterator
20
  lower_bound(ForwardIterator first, ForwardIterator last,
21
  const T& value);
22
 
23
- template<class ForwardIterator, class T, class Compare>
 
24
  constexpr ForwardIterator
25
  lower_bound(ForwardIterator first, ForwardIterator last,
26
  const T& value, Compare comp);
27
 
28
- template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
 
29
  indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
30
  constexpr I ranges::lower_bound(I first, S last, const T& value, Comp comp = {},
31
  Proj proj = {});
32
- template<forward_range R, class T, class Proj = identity,
 
33
  indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
34
  ranges::less>
35
  constexpr borrowed_iterator_t<R>
36
  ranges::lower_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {});
37
  ```
@@ -51,24 +54,27 @@ such that for every iterator `j` in the range \[`first`, `i`),
51
  projections.
52
 
53
  #### `upper_bound` <a id="upper.bound">[[upper.bound]]</a>
54
 
55
  ``` cpp
56
- template<class ForwardIterator, class T>
57
  constexpr ForwardIterator
58
  upper_bound(ForwardIterator first, ForwardIterator last,
59
  const T& value);
60
 
61
- template<class ForwardIterator, class T, class Compare>
 
62
  constexpr ForwardIterator
63
  upper_bound(ForwardIterator first, ForwardIterator last,
64
  const T& value, Compare comp);
65
 
66
- template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
 
67
  indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
68
  constexpr I ranges::upper_bound(I first, S last, const T& value, Comp comp = {}, Proj proj = {});
69
- template<forward_range R, class T, class Proj = identity,
 
70
  indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
71
  ranges::less>
72
  constexpr borrowed_iterator_t<R>
73
  ranges::upper_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {});
74
  ```
@@ -88,26 +94,29 @@ such that for every iterator `j` in the range \[`first`, `i`),
88
  projections.
89
 
90
  #### `equal_range` <a id="equal.range">[[equal.range]]</a>
91
 
92
  ``` cpp
93
- template<class ForwardIterator, class T>
94
  constexpr pair<ForwardIterator, ForwardIterator>
95
  equal_range(ForwardIterator first,
96
  ForwardIterator last, const T& value);
97
 
98
- template<class ForwardIterator, class T, class Compare>
 
99
  constexpr pair<ForwardIterator, ForwardIterator>
100
  equal_range(ForwardIterator first,
101
  ForwardIterator last, const T& value,
102
  Compare comp);
103
 
104
- template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
 
105
  indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
106
  constexpr subrange<I>
107
  ranges::equal_range(I first, S last, const T& value, Comp comp = {}, Proj proj = {});
108
- template<forward_range R, class T, class Proj = identity,
 
109
  indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
110
  ranges::less>
111
  constexpr borrowed_subrange_t<R>
112
  ranges::equal_range(R&& r, const T& value, Comp comp = {}, Proj proj = {});
113
  ```
@@ -117,11 +126,11 @@ parameters by those names.
117
 
118
  *Preconditions:* The elements `e` of \[`first`, `last`) are partitioned
119
  with respect to the expressions
120
  `bool(invoke(comp, invoke(proj, e), value))` and
121
  `!bool(invoke(comp, value, invoke(proj, e)))`. Also, for all elements
122
- `e` of `[first, last)`, `bool(comp(e, value))` implies
123
  `!bool(comp(value, e))` for the overloads in namespace `std`.
124
 
125
  *Returns:*
126
 
127
  - For the overloads in namespace `std`:
@@ -139,25 +148,28 @@ with respect to the expressions
139
  projections.
140
 
141
  #### `binary_search` <a id="binary.search">[[binary.search]]</a>
142
 
143
  ``` cpp
144
- template<class ForwardIterator, class T>
145
  constexpr bool
146
  binary_search(ForwardIterator first, ForwardIterator last,
147
  const T& value);
148
 
149
- template<class ForwardIterator, class T, class Compare>
 
150
  constexpr bool
151
  binary_search(ForwardIterator first, ForwardIterator last,
152
  const T& value, Compare comp);
153
 
154
- template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
 
155
  indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
156
  constexpr bool ranges::binary_search(I first, S last, const T& value, Comp comp = {},
157
  Proj proj = {});
158
- template<forward_range R, class T, class Proj = identity,
 
159
  indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
160
  ranges::less>
161
  constexpr bool ranges::binary_search(R&& r, const T& value, Comp comp = {},
162
  Proj proj = {});
163
  ```
@@ -167,11 +179,11 @@ parameters by those names.
167
 
168
  *Preconditions:* The elements `e` of \[`first`, `last`) are partitioned
169
  with respect to the expressions
170
  `bool(invoke(comp, invoke(proj, e), value))` and
171
  `!bool(invoke(comp, value, invoke(proj, e)))`. Also, for all elements
172
- `e` of `[first, last)`, `bool(comp(e, value))` implies
173
  `!bool(comp(value, e))` for the overloads in namespace `std`.
174
 
175
  *Returns:* `true` if and only if for some iterator `i` in the range
176
  \[`first`, `last`),
177
  `!bool(invoke(comp, invoke(proj, *i), value)) && !bool(invoke(comp, value, invoke(proj, *i)))`
 
13
  a linear number of steps.
14
 
15
  #### `lower_bound` <a id="lower.bound">[[lower.bound]]</a>
16
 
17
  ``` cpp
18
+ template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type>
19
  constexpr ForwardIterator
20
  lower_bound(ForwardIterator first, ForwardIterator last,
21
  const T& value);
22
 
23
+ template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type,
24
+ class Compare>
25
  constexpr ForwardIterator
26
  lower_bound(ForwardIterator first, ForwardIterator last,
27
  const T& value, Compare comp);
28
 
29
+ template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
30
+ class T = projected_value_t<I, Proj>,
31
  indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
32
  constexpr I ranges::lower_bound(I first, S last, const T& value, Comp comp = {},
33
  Proj proj = {});
34
+ template<forward_range R, class Proj = identity,
35
+ class T = projected_value_t<iterator_t<R>, Proj>,
36
  indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
37
  ranges::less>
38
  constexpr borrowed_iterator_t<R>
39
  ranges::lower_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {});
40
  ```
 
54
  projections.
55
 
56
  #### `upper_bound` <a id="upper.bound">[[upper.bound]]</a>
57
 
58
  ``` cpp
59
+ template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type>
60
  constexpr ForwardIterator
61
  upper_bound(ForwardIterator first, ForwardIterator last,
62
  const T& value);
63
 
64
+ template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type,
65
+ class Compare>
66
  constexpr ForwardIterator
67
  upper_bound(ForwardIterator first, ForwardIterator last,
68
  const T& value, Compare comp);
69
 
70
+ template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
71
+ class T = projected_value_t<I, Proj>,
72
  indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
73
  constexpr I ranges::upper_bound(I first, S last, const T& value, Comp comp = {}, Proj proj = {});
74
+ template<forward_range R, class Proj = identity,
75
+ class T = projected_value_t<iterator_t<R>, Proj>,
76
  indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
77
  ranges::less>
78
  constexpr borrowed_iterator_t<R>
79
  ranges::upper_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {});
80
  ```
 
94
  projections.
95
 
96
  #### `equal_range` <a id="equal.range">[[equal.range]]</a>
97
 
98
  ``` cpp
99
+ template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type>
100
  constexpr pair<ForwardIterator, ForwardIterator>
101
  equal_range(ForwardIterator first,
102
  ForwardIterator last, const T& value);
103
 
104
+ template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type,
105
+ class Compare>
106
  constexpr pair<ForwardIterator, ForwardIterator>
107
  equal_range(ForwardIterator first,
108
  ForwardIterator last, const T& value,
109
  Compare comp);
110
 
111
+ template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
112
+ class T = projected_value_t<I, Proj>,
113
  indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
114
  constexpr subrange<I>
115
  ranges::equal_range(I first, S last, const T& value, Comp comp = {}, Proj proj = {});
116
+ template<forward_range R, class Proj = identity,
117
+ class T = projected_value_t<iterator_t<R>, Proj>,
118
  indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
119
  ranges::less>
120
  constexpr borrowed_subrange_t<R>
121
  ranges::equal_range(R&& r, const T& value, Comp comp = {}, Proj proj = {});
122
  ```
 
126
 
127
  *Preconditions:* The elements `e` of \[`first`, `last`) are partitioned
128
  with respect to the expressions
129
  `bool(invoke(comp, invoke(proj, e), value))` and
130
  `!bool(invoke(comp, value, invoke(proj, e)))`. Also, for all elements
131
+ `e` of \[`first`, `last`), `bool(comp(e, value))` implies
132
  `!bool(comp(value, e))` for the overloads in namespace `std`.
133
 
134
  *Returns:*
135
 
136
  - For the overloads in namespace `std`:
 
148
  projections.
149
 
150
  #### `binary_search` <a id="binary.search">[[binary.search]]</a>
151
 
152
  ``` cpp
153
+ template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type>
154
  constexpr bool
155
  binary_search(ForwardIterator first, ForwardIterator last,
156
  const T& value);
157
 
158
+ template<class ForwardIterator, class T = iterator_traits<ForwardIterator>::value_type,
159
+ class Compare>
160
  constexpr bool
161
  binary_search(ForwardIterator first, ForwardIterator last,
162
  const T& value, Compare comp);
163
 
164
+ template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
165
+ class T = projected_value_t<I, Proj>,
166
  indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
167
  constexpr bool ranges::binary_search(I first, S last, const T& value, Comp comp = {},
168
  Proj proj = {});
169
+ template<forward_range R, class Proj = identity,
170
+ class T = projected_value_t<iterator_t<R>, Proj>,
171
  indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
172
  ranges::less>
173
  constexpr bool ranges::binary_search(R&& r, const T& value, Comp comp = {},
174
  Proj proj = {});
175
  ```
 
179
 
180
  *Preconditions:* The elements `e` of \[`first`, `last`) are partitioned
181
  with respect to the expressions
182
  `bool(invoke(comp, invoke(proj, e), value))` and
183
  `!bool(invoke(comp, value, invoke(proj, e)))`. Also, for all elements
184
+ `e` of \[`first`, `last`), `bool(comp(e, value))` implies
185
  `!bool(comp(value, e))` for the overloads in namespace `std`.
186
 
187
  *Returns:* `true` if and only if for some iterator `i` in the range
188
  \[`first`, `last`),
189
  `!bool(invoke(comp, invoke(proj, *i), value)) && !bool(invoke(comp, value, invoke(proj, *i)))`