From Jason Turner

[alg.search]

C++17 → C++20 6.7 KB 95 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/tmpegxi7ipw/{from.md → to.md} +71 -20
tmp/tmpegxi7ipw/{from.md → to.md} RENAMED
@@ -1,21 +1,21 @@
1
  ### Search <a id="alg.search">[[alg.search]]</a>
2
 
3
  ``` cpp
4
  template<class ForwardIterator1, class ForwardIterator2>
5
- ForwardIterator1
6
  search(ForwardIterator1 first1, ForwardIterator1 last1,
7
  ForwardIterator2 first2, ForwardIterator2 last2);
8
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
9
  ForwardIterator1
10
  search(ExecutionPolicy&& exec,
11
  ForwardIterator1 first1, ForwardIterator1 last1,
12
  ForwardIterator2 first2, ForwardIterator2 last2);
13
 
14
  template<class ForwardIterator1, class ForwardIterator2,
15
  class BinaryPredicate>
16
- ForwardIterator1
17
  search(ForwardIterator1 first1, ForwardIterator1 last1,
18
  ForwardIterator2 first2, ForwardIterator2 last2,
19
  BinaryPredicate pred);
20
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
21
  class BinaryPredicate>
@@ -24,68 +24,119 @@ template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
24
  ForwardIterator1 first1, ForwardIterator1 last1,
25
  ForwardIterator2 first2, ForwardIterator2 last2,
26
  BinaryPredicate pred);
27
  ```
28
 
29
- *Effects:* Finds a subsequence of equal values in a sequence.
30
-
31
  *Returns:* The first iterator `i` in the range \[`first1`,
32
  `last1 - (last2-first2)`) such that for every non-negative integer `n`
33
  less than `last2 - first2` the following corresponding conditions hold:
34
  `*(i + n) == *(first2 + n), pred(*(i + n), *(first2 + n)) != false`.
35
  Returns `first1` if \[`first2`, `last2`) is empty, otherwise returns
36
  `last1` if no such iterator is found.
37
 
38
  *Complexity:* At most `(last1 - first1) * (last2 - first2)` applications
39
  of the corresponding predicate.
40
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
41
  ``` cpp
42
  template<class ForwardIterator, class Size, class T>
43
- ForwardIterator
44
- search_n(ForwardIterator first, ForwardIterator last, Size count,
45
- const T& value);
46
-
47
- template<class ForwardIterator, class Size, class T,
48
- class BinaryPredicate>
49
- ForwardIterator
50
- search_n(ForwardIterator first, ForwardIterator last, Size count,
51
- const T& value, BinaryPredicate pred);
52
-
53
  template<class ExecutionPolicy, class ForwardIterator, class Size, class T>
54
  ForwardIterator
55
  search_n(ExecutionPolicy&& exec,
56
  ForwardIterator first, ForwardIterator last,
57
  Size count, const T& value);
 
 
 
 
 
 
 
58
  template<class ExecutionPolicy, class ForwardIterator, class Size, class T,
59
  class BinaryPredicate>
60
  ForwardIterator
61
  search_n(ExecutionPolicy&& exec,
62
  ForwardIterator first, ForwardIterator last,
63
  Size count, const T& value,
64
  BinaryPredicate pred);
65
  ```
66
 
67
- *Requires:* The type `Size` shall be convertible to integral
68
  type ([[conv.integral]], [[class.conv]]).
69
 
70
- *Effects:* Finds a subsequence of equal values in a sequence.
71
-
72
  *Returns:* The first iterator `i` in the range \[`first`, `last-count`)
73
  such that for every non-negative integer `n` less than `count` the
74
  following corresponding conditions hold:
75
  `*(i + n) == value, pred(*(i + n),value) != false`. Returns `last` if no
76
  such iterator is found.
77
 
78
  *Complexity:* At most `last - first` applications of the corresponding
79
  predicate.
80
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
81
  ``` cpp
82
  template<class ForwardIterator, class Searcher>
83
- ForwardIterator search(ForwardIterator first, ForwardIterator last,
84
- const Searcher& searcher);
85
  ```
86
 
87
  *Effects:* Equivalent to: `return searcher(first, last).first;`
88
 
89
- *Remarks:* `Searcher` need not meet the `CopyConstructible`
90
  requirements.
91
 
 
1
  ### Search <a id="alg.search">[[alg.search]]</a>
2
 
3
  ``` cpp
4
  template<class ForwardIterator1, class ForwardIterator2>
5
+ constexpr ForwardIterator1
6
  search(ForwardIterator1 first1, ForwardIterator1 last1,
7
  ForwardIterator2 first2, ForwardIterator2 last2);
8
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
9
  ForwardIterator1
10
  search(ExecutionPolicy&& exec,
11
  ForwardIterator1 first1, ForwardIterator1 last1,
12
  ForwardIterator2 first2, ForwardIterator2 last2);
13
 
14
  template<class ForwardIterator1, class ForwardIterator2,
15
  class BinaryPredicate>
16
+ constexpr ForwardIterator1
17
  search(ForwardIterator1 first1, ForwardIterator1 last1,
18
  ForwardIterator2 first2, ForwardIterator2 last2,
19
  BinaryPredicate pred);
20
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
21
  class BinaryPredicate>
 
24
  ForwardIterator1 first1, ForwardIterator1 last1,
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
37
  of the corresponding predicate.
38
 
39
+ ``` cpp
40
+ template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2,
41
+ sentinel_for<I2> S2, class Pred = ranges::equal_to,
42
+ class Proj1 = identity, class Proj2 = identity>
43
+ requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
44
+ constexpr subrange<I1>
45
+ ranges::search(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
46
+ Proj1 proj1 = {}, Proj2 proj2 = {});
47
+ 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
+
64
+ is `true`.
65
+ - Returns `{last1, last1}` if no such iterator exists.
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,
93
  BinaryPredicate pred);
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 no
103
  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
130
+ predicate and projection.
131
+
132
  ``` cpp
133
  template<class ForwardIterator, class Searcher>
134
+ constexpr ForwardIterator
135
+ search(ForwardIterator first, ForwardIterator last, const Searcher& searcher);
136
  ```
137
 
138
  *Effects:* Equivalent to: `return searcher(first, last).first;`
139
 
140
+ *Remarks:* `Searcher` need not meet the *Cpp17CopyConstructible*
141
  requirements.
142