From Jason Turner

[alg.binary.search]

C++17 → C++20 10.4 KB 169 lines
Current Draft | LaTeX Source
Archived: C++17 | C++20
Markdown: C++17 | C++20
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpth4v6kqj/{from.md → to.md} +112 -54
tmp/tmpth4v6kqj/{from.md → to.md} RENAMED
@@ -1,122 +1,180 @@
1
  ### Binary search <a id="alg.binary.search">[[alg.binary.search]]</a>
2
 
3
- All of the algorithms in this section are versions of binary search and
4
- assume that the sequence being searched is partitioned with respect to
5
- an expression formed by binding the search key to an argument of the
6
- implied or explicit comparison function. They work on non-random access
7
- iterators minimizing the number of comparisons, which will be
8
- logarithmic for all types of iterators. They are especially appropriate
9
- for random access iterators, because these algorithms do a logarithmic
10
- number of steps through the data structure. For non-random access
11
- iterators they execute a linear number of steps.
12
 
13
  #### `lower_bound` <a id="lower.bound">[[lower.bound]]</a>
14
 
15
  ``` cpp
16
  template<class ForwardIterator, class T>
17
- ForwardIterator
18
  lower_bound(ForwardIterator first, ForwardIterator last,
19
  const T& value);
20
 
21
  template<class ForwardIterator, class T, class Compare>
22
- ForwardIterator
23
  lower_bound(ForwardIterator first, ForwardIterator last,
24
  const T& value, Compare comp);
 
 
 
 
 
 
 
 
 
 
25
  ```
26
 
27
- *Requires:* The elements `e` of \[`first`, `last`) shall be partitioned
28
- with respect to the expression `e < value` or `comp(e, value)`.
 
 
 
 
29
 
30
  *Returns:* The furthermost iterator `i` in the range \[`first`, `last`\]
31
- such that for every iterator `j` in the range \[`first`, `i`) the
32
- following corresponding conditions hold: `*j < value` or
33
- `comp(*j, value) != false`.
34
 
35
- *Complexity:* At most log₂(`last - first`) + 𝑂(1) comparisons.
 
36
 
37
  #### `upper_bound` <a id="upper.bound">[[upper.bound]]</a>
38
 
39
  ``` cpp
40
  template<class ForwardIterator, class T>
41
- ForwardIterator
42
  upper_bound(ForwardIterator first, ForwardIterator last,
43
  const T& value);
44
 
45
  template<class ForwardIterator, class T, class Compare>
46
- ForwardIterator
47
  upper_bound(ForwardIterator first, ForwardIterator last,
48
  const T& value, Compare comp);
 
 
 
 
 
 
 
 
 
49
  ```
50
 
51
- *Requires:* The elements `e` of \[`first`, `last`) shall be partitioned
52
- with respect to the expression `!(value < e)` or `!comp(value, e)`.
 
 
 
 
53
 
54
  *Returns:* The furthermost iterator `i` in the range \[`first`, `last`\]
55
- such that for every iterator `j` in the range \[`first`, `i`) the
56
- following corresponding conditions hold: `!(value < *j)` or
57
- `comp(value, *j) == false`.
58
 
59
- *Complexity:* At most log₂(`last - first`) + 𝑂(1) comparisons.
 
60
 
61
  #### `equal_range` <a id="equal.range">[[equal.range]]</a>
62
 
63
  ``` cpp
64
  template<class ForwardIterator, class T>
65
- pair<ForwardIterator, ForwardIterator>
66
  equal_range(ForwardIterator first,
67
  ForwardIterator last, const T& value);
68
 
69
  template<class ForwardIterator, class T, class Compare>
70
- pair<ForwardIterator, ForwardIterator>
71
  equal_range(ForwardIterator first,
72
  ForwardIterator last, const T& value,
73
  Compare comp);
 
 
 
 
 
 
 
 
 
 
74
  ```
75
 
76
- *Requires:* The elements `e` of \[`first`, `last`) shall be partitioned
77
- with respect to the expressions `e < value` and `!(value < e)` or
78
- `comp(e, value)` and `!comp(value, e)`. Also, for all elements `e` of
79
- `[first, last)`, `e < value` shall imply `!(value < e)` or
80
- `comp(e, value)` shall imply `!comp(value, e)`.
 
 
 
 
81
 
82
  *Returns:*
83
 
 
84
  ``` cpp
85
- make_pair(lower_bound(first, last, value),
86
- upper_bound(first, last, value))
87
  ```
88
-
89
- or
90
-
91
  ``` cpp
92
- make_pair(lower_bound(first, last, value, comp),
93
- upper_bound(first, last, value, comp))
94
  ```
95
 
96
- *Complexity:* At most 2 * log₂(`last - first`) + 𝑂(1) comparisons.
 
97
 
98
  #### `binary_search` <a id="binary.search">[[binary.search]]</a>
99
 
100
  ``` cpp
101
  template<class ForwardIterator, class T>
102
- bool binary_search(ForwardIterator first, ForwardIterator last,
 
103
  const T& value);
104
 
105
  template<class ForwardIterator, class T, class Compare>
106
- bool binary_search(ForwardIterator first, ForwardIterator last,
 
107
  const T& value, Compare comp);
 
 
 
 
 
 
 
 
 
 
108
  ```
109
 
110
- *Requires:* The elements `e` of \[`first`, `last`) are partitioned with
111
- respect to the expressions `e < value` and `!(value < e)` or
112
- `comp(e, value)` and `!comp(value, e)`. Also, for all elements `e` of
113
- `[first, last)`, `e < value` implies `!(value < e)` or `comp(e, value)`
114
- implies `!comp(value, e)`.
115
-
116
- *Returns:* `true` if there is an iterator `i` in the range \[`first`,
117
- `last`) that satisfies the corresponding conditions:
118
- `!(*i < value) && !(value < *i)` or
119
- `comp(*i, value) == false && comp(value, *i) == false`.
120
-
121
- *Complexity:* At most log₂(`last - first`) + 𝑂(1) comparisons.
 
 
 
 
 
122
 
 
1
  ### Binary search <a id="alg.binary.search">[[alg.binary.search]]</a>
2
 
3
+ All of the algorithms in this subclause are versions of binary search
4
+ and assume that the sequence being searched is partitioned with respect
5
+ to an expression formed by binding the search key to an argument of the
6
+ comparison function. They work on non-random access iterators minimizing
7
+ the number of comparisons, which will be logarithmic for all types of
8
+ iterators. They are especially appropriate for random access iterators,
9
+ because these algorithms do a logarithmic number of steps through the
10
+ data structure. For non-random access iterators they execute a linear
11
+ number of steps.
12
 
13
  #### `lower_bound` <a id="lower.bound">[[lower.bound]]</a>
14
 
15
  ``` cpp
16
  template<class ForwardIterator, class T>
17
+ constexpr ForwardIterator
18
  lower_bound(ForwardIterator first, ForwardIterator last,
19
  const T& value);
20
 
21
  template<class ForwardIterator, class T, class Compare>
22
+ constexpr ForwardIterator
23
  lower_bound(ForwardIterator first, ForwardIterator last,
24
  const T& value, Compare comp);
25
+
26
+ template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
27
+ indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
28
+ constexpr I ranges::lower_bound(I first, S last, const T& value, Comp comp = {},
29
+ Proj proj = {});
30
+ template<forward_range R, class T, class Proj = identity,
31
+ indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
32
+ ranges::less>
33
+ constexpr borrowed_iterator_t<R>
34
+ ranges::lower_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {});
35
  ```
36
 
37
+ Let `comp` be `less{}` and `proj` be `identity{}` for overloads with no
38
+ parameters by those names.
39
+
40
+ *Preconditions:* The elements `e` of \[`first`, `last`) are partitioned
41
+ with respect to the expression
42
+ `bool(invoke(comp, invoke(proj, e), value))`.
43
 
44
  *Returns:* The furthermost iterator `i` in the range \[`first`, `last`\]
45
+ such that for every iterator `j` in the range \[`first`, `i`),
46
+ `bool(invoke(comp, invoke(proj, *j), value))` is `true`.
 
47
 
48
+ *Complexity:* At most log₂(`last - first`) + 𝑂(1) comparisons and
49
+ projections.
50
 
51
  #### `upper_bound` <a id="upper.bound">[[upper.bound]]</a>
52
 
53
  ``` cpp
54
  template<class ForwardIterator, class T>
55
+ constexpr ForwardIterator
56
  upper_bound(ForwardIterator first, ForwardIterator last,
57
  const T& value);
58
 
59
  template<class ForwardIterator, class T, class Compare>
60
+ constexpr ForwardIterator
61
  upper_bound(ForwardIterator first, ForwardIterator last,
62
  const T& value, Compare comp);
63
+
64
+ template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
65
+ indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
66
+ constexpr I ranges::upper_bound(I first, S last, const T& value, Comp comp = {}, Proj proj = {});
67
+ template<forward_range R, class T, class Proj = identity,
68
+ indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
69
+ ranges::less>
70
+ constexpr borrowed_iterator_t<R>
71
+ ranges::upper_bound(R&& r, const T& value, Comp comp = {}, Proj proj = {});
72
  ```
73
 
74
+ Let `comp` be `less{}` and `proj` be `identity{}` for overloads with no
75
+ parameters by those names.
76
+
77
+ *Preconditions:* The elements `e` of \[`first`, `last`) are partitioned
78
+ with respect to the expression
79
+ `!bool(invoke(comp, value, invoke(proj, e)))`.
80
 
81
  *Returns:* The furthermost iterator `i` in the range \[`first`, `last`\]
82
+ such that for every iterator `j` in the range \[`first`, `i`),
83
+ `!bool(invoke(comp, value, invoke(proj, *j)))` is `true`.
 
84
 
85
+ *Complexity:* At most log₂(`last - first`) + 𝑂(1) comparisons and
86
+ projections.
87
 
88
  #### `equal_range` <a id="equal.range">[[equal.range]]</a>
89
 
90
  ``` cpp
91
  template<class ForwardIterator, class T>
92
+ constexpr pair<ForwardIterator, ForwardIterator>
93
  equal_range(ForwardIterator first,
94
  ForwardIterator last, const T& value);
95
 
96
  template<class ForwardIterator, class T, class Compare>
97
+ constexpr pair<ForwardIterator, ForwardIterator>
98
  equal_range(ForwardIterator first,
99
  ForwardIterator last, const T& value,
100
  Compare comp);
101
+
102
+ template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
103
+ indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
104
+ constexpr subrange<I>
105
+ ranges::equal_range(I first, S last, const T& value, Comp comp = {}, Proj proj = {});
106
+ template<forward_range R, class T, class Proj = identity,
107
+ indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
108
+ ranges::less>
109
+ constexpr borrowed_subrange_t<R>
110
+ ranges::equal_range(R&& r, const T& value, Comp comp = {}, Proj proj = {});
111
  ```
112
 
113
+ Let `comp` be `less{}` and `proj` be `identity{}` for overloads with no
114
+ parameters by those names.
115
+
116
+ *Preconditions:* The elements `e` of \[`first`, `last`) are partitioned
117
+ with respect to the expressions
118
+ `bool(invoke(comp, invoke(proj, e), value))` and
119
+ `!bool(invoke(comp, value, invoke(proj, e)))`. Also, for all elements
120
+ `e` of `[first, last)`, `bool(comp(e, value))` implies
121
+ `!bool(comp(value, e))` for the overloads in namespace `std`.
122
 
123
  *Returns:*
124
 
125
+ - For the overloads in namespace `std`:
126
  ``` cpp
127
+ {lower_bound(first, last, value, comp),
128
+ upper_bound(first, last, value, comp)}
129
  ```
130
+ - For the overloads in namespace `ranges`:
 
 
131
  ``` cpp
132
+ {ranges::lower_bound(first, last, value, comp, proj),
133
+ ranges::upper_bound(first, last, value, comp, proj)}
134
  ```
135
 
136
+ *Complexity:* At most 2 * log₂(`last - first`) + 𝑂(1) comparisons and
137
+ projections.
138
 
139
  #### `binary_search` <a id="binary.search">[[binary.search]]</a>
140
 
141
  ``` cpp
142
  template<class ForwardIterator, class T>
143
+ constexpr bool
144
+ binary_search(ForwardIterator first, ForwardIterator last,
145
  const T& value);
146
 
147
  template<class ForwardIterator, class T, class Compare>
148
+ constexpr bool
149
+ binary_search(ForwardIterator first, ForwardIterator last,
150
  const T& value, Compare comp);
151
+
152
+ template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
153
+ indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
154
+ constexpr bool ranges::binary_search(I first, S last, const T& value, Comp comp = {},
155
+ Proj proj = {});
156
+ template<forward_range R, class T, class Proj = identity,
157
+ indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
158
+ ranges::less>
159
+ constexpr bool ranges::binary_search(R&& r, const T& value, Comp comp = {},
160
+ Proj proj = {});
161
  ```
162
 
163
+ Let `comp` be `less{}` and `proj` be `identity{}` for overloads with no
164
+ parameters by those names.
165
+
166
+ *Preconditions:* The elements `e` of \[`first`, `last`) are partitioned
167
+ with respect to the expressions
168
+ `bool(invoke(comp, invoke(proj, e), value))` and
169
+ `!bool(invoke(comp, value, invoke(proj, e)))`. Also, for all elements
170
+ `e` of `[first, last)`, `bool(comp(e, value))` implies
171
+ `!bool(comp(value, e))` for the overloads in namespace `std`.
172
+
173
+ *Returns:* `true` if and only if for some iterator `i` in the range
174
+ \[`first`, `last`),
175
+ `!bool(invoke(comp, invoke(proj, *i), value)) && !bool(invoke(comp, value, invoke(proj, *i)))`
176
+ is `true`.
177
+
178
+ *Complexity:* At most log₂(`last - first`) + 𝑂(1) comparisons and
179
+ projections.
180