From Jason Turner

[alg.search]

C++23 → Trunk 7.3 KB 74 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/tmpcs0nz272/{from.md → to.md} +51 -17
tmp/tmpcs0nz272/{from.md → to.md} RENAMED
@@ -25,12 +25,13 @@ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
25
  ForwardIterator2 first2, ForwardIterator2 last2,
26
  BinaryPredicate pred);
27
  ```
28
 
29
  *Returns:* The first iterator `i` in the range \[`first1`,
30
- `last1 - (last2-first2)`) such that for every non-negative integer `n`
31
- less than `last2 - first2` the following corresponding conditions hold:
 
32
  `*(i + n) == *(first2 + n), pred(*(i + n), *(first2 + n)) != false`.
33
  Returns `first1` if \[`first2`, `last2`) is empty, otherwise returns
34
  `last1` if no such iterator is found.
35
 
36
  *Complexity:* At most `(last1 - first1) * (last2 - first2)` applications
@@ -48,16 +49,30 @@ template<forward_range R1, forward_range R2, class Pred = ranges::equal_to,
48
  class Proj1 = identity, class Proj2 = identity>
49
  requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
50
  constexpr borrowed_subrange_t<R1>
51
  ranges::search(R1&& r1, R2&& r2, Pred pred = {},
52
  Proj1 proj1 = {}, Proj2 proj2 = {});
 
 
 
 
 
 
 
 
 
 
 
 
 
 
53
  ```
54
 
55
  *Returns:*
56
 
57
  - `{i, i + (last2 - first2)}`, where `i` is the first iterator in the
58
- range \[`first1`, `last1 - (last2 - first2)`) such that for every
59
  non-negative integer `n` less than `last2 - first2` the condition
60
  ``` cpp
61
  bool(invoke(pred, invoke(proj1, *(i + n)), invoke(proj2, *(first2 + n))))
62
  ```
63
 
@@ -66,27 +81,29 @@ template<forward_range R1, forward_range R2, class Pred = ranges::equal_to,
66
 
67
  *Complexity:* At most `(last1 - first1) * (last2 - first2)` applications
68
  of the corresponding predicate and projections.
69
 
70
  ``` cpp
71
- template<class ForwardIterator, class Size, class T>
72
  constexpr ForwardIterator
73
  search_n(ForwardIterator first, ForwardIterator last,
74
  Size count, const T& value);
75
- template<class ExecutionPolicy, class ForwardIterator, class Size, class T>
 
76
  ForwardIterator
77
  search_n(ExecutionPolicy&& exec,
78
  ForwardIterator first, ForwardIterator last,
79
  Size count, const T& value);
80
 
81
- template<class ForwardIterator, class Size, class T,
82
  class BinaryPredicate>
83
  constexpr ForwardIterator
84
  search_n(ForwardIterator first, ForwardIterator last,
85
  Size count, const T& value,
86
  BinaryPredicate pred);
87
- template<class ExecutionPolicy, class ForwardIterator, class Size, class T,
 
88
  class BinaryPredicate>
89
  ForwardIterator
90
  search_n(ExecutionPolicy&& exec,
91
  ForwardIterator first, ForwardIterator last,
92
  Size count, const T& value,
@@ -94,36 +111,53 @@ template<class ExecutionPolicy, class ForwardIterator, class Size, class T,
94
  ```
95
 
96
  *Mandates:* The type `Size` is convertible to an integral
97
  type [[conv.integral]], [[class.conv]].
98
 
99
- *Returns:* The first iterator `i` in the range \[`first`, `last-count`)
100
- such that for every non-negative integer `n` less than `count` the
101
- following corresponding conditions hold:
102
- `*(i + n) == value, pred(*(i + n), value) != false`. Returns `last` if
103
- no such iterator is found.
 
 
104
 
105
  *Complexity:* At most `last - first` applications of the corresponding
106
  predicate.
107
 
108
  ``` cpp
109
- template<forward_iterator I, sentinel_for<I> S, class T,
110
- class Pred = ranges::equal_to, class Proj = identity>
 
111
  requires indirectly_comparable<I, const T*, Pred, Proj>
112
  constexpr subrange<I>
113
  ranges::search_n(I first, S last, iter_difference_t<I> count,
114
  const T& value, Pred pred = {}, Proj proj = {});
115
- template<forward_range R, class T, class Pred = ranges::equal_to,
116
- class Proj = identity>
117
  requires indirectly_comparable<iterator_t<R>, const T*, Pred, Proj>
118
  constexpr borrowed_subrange_t<R>
119
  ranges::search_n(R&& r, range_difference_t<R> count,
120
  const T& value, Pred pred = {}, Proj proj = {});
 
 
 
 
 
 
 
 
 
 
 
 
 
 
121
  ```
122
 
123
  *Returns:* `{i, i + count}` where `i` is the first iterator in the range
124
- \[`first`, `last - count`) such that for every non-negative integer `n`
125
  less than `count`, the following condition holds:
126
  `invoke(pred, invoke(proj, *(i + n)), value)`. Returns `{last, last}` if
127
  no such iterator is found.
128
 
129
  *Complexity:* At most `last - first` applications of the corresponding
 
25
  ForwardIterator2 first2, ForwardIterator2 last2,
26
  BinaryPredicate pred);
27
  ```
28
 
29
  *Returns:* The first iterator `i` in the range \[`first1`,
30
+ `last1 - (last2 - first2)`\] such that for every non-negative integer
31
+ `n` less than `last2 - first2` the following corresponding conditions
32
+ hold:
33
  `*(i + n) == *(first2 + n), pred(*(i + n), *(first2 + n)) != false`.
34
  Returns `first1` if \[`first2`, `last2`) is empty, otherwise returns
35
  `last1` if no such iterator is found.
36
 
37
  *Complexity:* At most `(last1 - first1) * (last2 - first2)` applications
 
49
  class Proj1 = identity, class Proj2 = identity>
50
  requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
51
  constexpr borrowed_subrange_t<R1>
52
  ranges::search(R1&& r1, R2&& r2, Pred pred = {},
53
  Proj1 proj1 = {}, Proj2 proj2 = {});
54
+
55
+ template<execution-policy Ep, random_access_iterator I1, sized_sentinel_for<I1> S1,
56
+ random_access_iterator I2, sized_sentinel_for<I2> S2,
57
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
58
+ requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
59
+ subrange<I1>
60
+ ranges::search(Ep&& exec, I1 first1, S1 last1, I2 first2, S2 last2,
61
+ Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
62
+ template<execution-policy Ep, sized-random-access-range R1, sized-random-access-range R2,
63
+ class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
64
+ requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
65
+ borrowed_subrange_t<R1>
66
+ ranges::search(Ep&& exec, R1&& r1, R2&& r2,
67
+ Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
68
  ```
69
 
70
  *Returns:*
71
 
72
  - `{i, i + (last2 - first2)}`, where `i` is the first iterator in the
73
+ range \[`first1`, `last1 - (last2 - first2)`\] such that for every
74
  non-negative integer `n` less than `last2 - first2` the condition
75
  ``` cpp
76
  bool(invoke(pred, invoke(proj1, *(i + n)), invoke(proj2, *(first2 + n))))
77
  ```
78
 
 
81
 
82
  *Complexity:* At most `(last1 - first1) * (last2 - first2)` applications
83
  of the corresponding predicate and projections.
84
 
85
  ``` cpp
86
+ template<class ForwardIterator, class Size, class T = iterator_traits<ForwardIterator>::value_type>
87
  constexpr ForwardIterator
88
  search_n(ForwardIterator first, ForwardIterator last,
89
  Size count, const T& value);
90
+ template<class ExecutionPolicy, class ForwardIterator, class Size,
91
+ class T = iterator_traits<ForwardIterator>::value_type>
92
  ForwardIterator
93
  search_n(ExecutionPolicy&& exec,
94
  ForwardIterator first, ForwardIterator last,
95
  Size count, const T& value);
96
 
97
+ template<class ForwardIterator, class Size, class T = iterator_traits<ForwardIterator>::value_type,
98
  class BinaryPredicate>
99
  constexpr ForwardIterator
100
  search_n(ForwardIterator first, ForwardIterator last,
101
  Size count, const T& value,
102
  BinaryPredicate pred);
103
+ template<class ExecutionPolicy, class ForwardIterator, class Size,
104
+ class T = iterator_traits<ForwardIterator>::value_type,
105
  class BinaryPredicate>
106
  ForwardIterator
107
  search_n(ExecutionPolicy&& exec,
108
  ForwardIterator first, ForwardIterator last,
109
  Size count, const T& value,
 
111
  ```
112
 
113
  *Mandates:* The type `Size` is convertible to an integral
114
  type [[conv.integral]], [[class.conv]].
115
 
116
+ Let E be `pred(*(i + n), value) != false` for the overloads with a
117
+ parameter `pred`, and `*(i + n) == value` otherwise.
118
+
119
+ *Returns:* The first iterator `i` in the range \[`first`,
120
+ `last - count`\] such that for every non-negative integer `n` less than
121
+ `count` the condition E is `true`. Returns `last` if no such iterator is
122
+ found.
123
 
124
  *Complexity:* At most `last - first` applications of the corresponding
125
  predicate.
126
 
127
  ``` cpp
128
+ template<forward_iterator I, sentinel_for<I> S,
129
+ class Pred = ranges::equal_to, class Proj = identity,
130
+ class T = projected_value_t<I, Proj>>
131
  requires indirectly_comparable<I, const T*, Pred, Proj>
132
  constexpr subrange<I>
133
  ranges::search_n(I first, S last, iter_difference_t<I> count,
134
  const T& value, Pred pred = {}, Proj proj = {});
135
+ template<forward_range R, class Pred = ranges::equal_to,
136
+ class Proj = identity, class T = projected_value_t<iterator_t<R>, Proj>>
137
  requires indirectly_comparable<iterator_t<R>, const T*, Pred, Proj>
138
  constexpr borrowed_subrange_t<R>
139
  ranges::search_n(R&& r, range_difference_t<R> count,
140
  const T& value, Pred pred = {}, Proj proj = {});
141
+
142
+ template<execution-policy Ep, random_access_iterator I, sized_sentinel_for<I> S,
143
+ class Pred = ranges::equal_to, class Proj = identity,
144
+ class T = projected_value_t<I, Proj>>
145
+ requires indirectly_comparable<I, const T*, Pred, Proj>
146
+ subrange<I>
147
+ ranges::search_n(Ep&& exec, I first, S last, iter_difference_t<I> count,
148
+ const T& value, Pred pred = {}, Proj proj = {});
149
+ template<execution-policy Ep, sized-random-access-range R, class Pred = ranges::equal_to,
150
+ class Proj = identity, class T = projected_value_t<iterator_t<R>, Proj>>
151
+ requires indirectly_comparable<iterator_t<R>, const T*, Pred, Proj>
152
+ borrowed_subrange_t<R>
153
+ ranges::search_n(Ep&& exec, R&& r, range_difference_t<R> count,
154
+ const T& value, Pred pred = {}, Proj proj = {});
155
  ```
156
 
157
  *Returns:* `{i, i + count}` where `i` is the first iterator in the range
158
+ \[`first`, `last - count`\] such that for every non-negative integer `n`
159
  less than `count`, the following condition holds:
160
  `invoke(pred, invoke(proj, *(i + n)), value)`. Returns `{last, last}` if
161
  no such iterator is found.
162
 
163
  *Complexity:* At most `last - first` applications of the corresponding