1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9// <algorithm>
10
11// UNSUPPORTED: c++03, c++11, c++14, c++17
12
13// ADDITIONAL_COMPILE_FLAGS(gcc-style-warnings): -Wno-sign-compare
14// MSVC warning C4242: 'argument': conversion from 'const _Ty' to 'ElementT', possible loss of data
15// MSVC warning C4244: 'argument': conversion from 'const _Ty' to 'ElementT', possible loss of data
16// ADDITIONAL_COMPILE_FLAGS(cl-style-warnings): /wd4242 /wd4244
17// ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-steps): -fconstexpr-steps=20000000
18// ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-ops-limit): -fconstexpr-ops-limit=80000000
19
20// template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity>
21// requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
22// constexpr I ranges::find(I first, S last, const T& value, Proj proj = {});
23// template<input_range R, class T, class Proj = identity>
24// requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
25// constexpr borrowed_iterator_t<R>
26// ranges::find(R&& r, const T& value, Proj proj = {});
27
28#include <algorithm>
29#include <array>
30#include <cassert>
31#include <cstddef>
32#include <deque>
33#include <ranges>
34#include <vector>
35
36#include "almost_satisfies_types.h"
37#include "sized_allocator.h"
38#include "test_iterators.h"
39
40struct NotEqualityComparable {};
41
42template <class It, class Sent = It>
43concept HasFindIt = requires(It it, Sent sent) { std::ranges::find(it, sent, *it); };
44static_assert(HasFindIt<int*>);
45static_assert(!HasFindIt<NotEqualityComparable*>);
46static_assert(!HasFindIt<InputIteratorNotDerivedFrom>);
47static_assert(!HasFindIt<InputIteratorNotIndirectlyReadable>);
48static_assert(!HasFindIt<InputIteratorNotInputOrOutputIterator>);
49static_assert(!HasFindIt<cpp20_input_iterator<int*>, SentinelForNotSemiregular>);
50static_assert(!HasFindIt<cpp20_input_iterator<int*>, InputRangeNotSentinelEqualityComparableWith>);
51
52static_assert(!HasFindIt<int*, int>);
53static_assert(!HasFindIt<int, int*>);
54
55template <class Range, class ValT>
56concept HasFindR = requires(Range r) { std::ranges::find(r, ValT{}); };
57static_assert(HasFindR<std::array<int, 1>, int>);
58static_assert(!HasFindR<int, int>);
59static_assert(!HasFindR<std::array<NotEqualityComparable, 1>, NotEqualityComparable>);
60static_assert(!HasFindR<InputRangeNotDerivedFrom, int>);
61static_assert(!HasFindR<InputRangeNotIndirectlyReadable, int>);
62static_assert(!HasFindR<InputRangeNotInputOrOutputIterator, int>);
63static_assert(!HasFindR<InputRangeNotSentinelSemiregular, int>);
64static_assert(!HasFindR<InputRangeNotSentinelEqualityComparableWith, int>);
65
66static std::vector<int> comparable_data;
67
68template <class It, class Sent = It>
69constexpr void test_iterators() {
70 using ValueT = std::iter_value_t<It>;
71 { // simple test
72 {
73 ValueT a[] = {1, 2, 3, 4};
74 std::same_as<It> auto ret = std::ranges::find(It(a), Sent(It(a + 4)), 4);
75 assert(base(ret) == a + 3);
76 assert(*ret == 4);
77 }
78 {
79 ValueT a[] = {1, 2, 3, 4};
80 auto range = std::ranges::subrange(It(a), Sent(It(a + 4)));
81 std::same_as<It> auto ret = std::ranges::find(range, 4);
82 assert(base(ret) == a + 3);
83 assert(*ret == 4);
84 }
85 }
86
87 { // check that an empty range works
88 {
89 std::array<ValueT, 0> a = {};
90 auto ret = std::ranges::find(It(a.data()), Sent(It(a.data())), 1);
91 assert(base(ret) == a.data());
92 }
93 {
94 std::array<ValueT, 0> a = {};
95 auto range = std::ranges::subrange(It(a.data()), Sent(It(a.data())));
96 auto ret = std::ranges::find(range, 1);
97 assert(base(ret) == a.data());
98 }
99 }
100
101 { // check that last is returned with no match
102 {
103 ValueT a[] = {1, 1, 1};
104 auto ret = std::ranges::find(a, a + 3, 0);
105 assert(ret == a + 3);
106 }
107 {
108 ValueT a[] = {1, 1, 1};
109 auto ret = std::ranges::find(a, 0);
110 assert(ret == a + 3);
111 }
112 }
113
114 if (!std::is_constant_evaluated())
115 comparable_data.clear();
116}
117
118template <class ElementT>
119class TriviallyComparable {
120 ElementT el_;
121
122public:
123 TEST_CONSTEXPR TriviallyComparable(ElementT el) : el_(el) {}
124 bool operator==(const TriviallyComparable&) const = default;
125};
126
127constexpr bool test() {
128 types::for_each(types::type_list<char, wchar_t, int, long, TriviallyComparable<char>, TriviallyComparable<wchar_t>>{},
129 []<class T> {
130 types::for_each(types::cpp20_input_iterator_list<T*>{}, []<class Iter> {
131 if constexpr (std::forward_iterator<Iter>)
132 test_iterators<Iter>();
133 test_iterators<Iter, sentinel_wrapper<Iter>>();
134 test_iterators<Iter, sized_sentinel<Iter>>();
135 });
136 });
137
138#if TEST_STD_VER >= 20
139 {
140 std::vector<std::vector<int>> vec = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
141 auto view = vec | std::views::join;
142 assert(std::ranges::find(view.begin(), view.end(), 4) == std::next(view.begin(), 3));
143 assert(std::ranges::find(view, 4) == std::next(view.begin(), 3));
144 }
145#endif
146
147 { // check that the first element is returned
148 {
149 struct S {
150 int comp;
151 int other;
152 };
153 S a[] = {{.comp: 0, .other: 0}, {.comp: 0, .other: 2}, {.comp: 0, .other: 1}};
154 auto ret = std::ranges::find(a, 0, &S::comp);
155 assert(ret == a);
156 assert(ret->comp == 0);
157 assert(ret->other == 0);
158 }
159 {
160 struct S {
161 int comp;
162 int other;
163 };
164 S a[] = {{.comp: 0, .other: 0}, {.comp: 0, .other: 2}, {.comp: 0, .other: 1}};
165 auto ret = std::ranges::find(a, a + 3, 0, &S::comp);
166 assert(ret == a);
167 assert(ret->comp == 0);
168 assert(ret->other == 0);
169 }
170 }
171
172 {
173 // check that an iterator is returned with a borrowing range
174 int a[] = {1, 2, 3, 4};
175 std::same_as<int*> auto ret = std::ranges::find(std::views::all(a), 1);
176 assert(ret == a);
177 assert(*ret == 1);
178 }
179
180 {
181 // count invocations of the projection
182 {
183 int a[] = {1, 2, 3, 4};
184 int projection_count = 0;
185 auto ret = std::ranges::find(a, a + 4, 2, [&](int i) {
186 ++projection_count;
187 return i;
188 });
189 assert(ret == a + 1);
190 assert(*ret == 2);
191 assert(projection_count == 2);
192 }
193 {
194 int a[] = {1, 2, 3, 4};
195 int projection_count = 0;
196 auto ret = std::ranges::find(a, 2, [&](int i) {
197 ++projection_count;
198 return i;
199 });
200 assert(ret == a + 1);
201 assert(*ret == 2);
202 assert(projection_count == 2);
203 }
204 }
205
206 {
207 // Test vector<bool>::iterator optimization
208 std::vector<bool> vec(256 + 8);
209 for (ptrdiff_t i = 8; i <= 256; i *= 2) {
210 for (size_t offset = 0; offset < 8; offset += 2) {
211 std::fill(first: vec.begin(), last: vec.end(), value: false);
212 std::fill(first: vec.begin() + offset, last: vec.begin() + i + offset, value: true);
213
214 // check both range and iterator-sentinel overloads
215 assert(std::ranges::find(vec, true) == std::ranges::begin(vec) + offset);
216 assert(std::ranges::find(std::ranges::begin(vec) + offset, std::ranges::end(vec), false) ==
217 std::ranges::begin(vec) + offset + i);
218 }
219 }
220
221 // Verify that the std::vector<bool>::iterator optimization works properly for allocators with custom size types
222 // See https://github.com/llvm/llvm-project/issues/122528
223 {
224 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
225 std::vector<bool, Alloc> in(100, false, Alloc(1));
226 in[in.size() - 2] = true;
227 assert(std::ranges::find(in, true) == in.end() - 2);
228 }
229 {
230 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
231 std::vector<bool, Alloc> in(199, false, Alloc(1));
232 in[in.size() - 2] = true;
233 assert(std::ranges::find(in, true) == in.end() - 2);
234 }
235 {
236 using Alloc = sized_allocator<bool, unsigned short, short>;
237 std::vector<bool, Alloc> in(200, false, Alloc(1));
238 in[in.size() - 2] = true;
239 assert(std::ranges::find(in, true) == in.end() - 2);
240 }
241 {
242 using Alloc = sized_allocator<bool, std::uint32_t, std::int32_t>;
243 std::vector<bool, Alloc> in(205, false, Alloc(1));
244 in[in.size() - 2] = true;
245 assert(std::ranges::find(in, true) == in.end() - 2);
246 }
247 {
248 using Alloc = sized_allocator<bool, std::uint64_t, std::int64_t>;
249 std::vector<bool, Alloc> in(257, false, Alloc(1));
250 in[in.size() - 2] = true;
251 assert(std::ranges::find(in, true) == in.end() - 2);
252 }
253 }
254
255 return true;
256}
257
258template <class IndexT>
259class Comparable {
260 IndexT index_;
261
262public:
263 Comparable(IndexT i)
264 : index_([&]() {
265 IndexT size = static_cast<IndexT>(comparable_data.size());
266 comparable_data.push_back(i);
267 return size;
268 }()) {}
269
270 bool operator==(const Comparable& other) const { return comparable_data[other.index_] == comparable_data[index_]; }
271
272 friend bool operator==(const Comparable& lhs, long long rhs) { return comparable_data[lhs.index_] == rhs; }
273};
274
275void test_deque() {
276 { // empty deque
277 std::deque<int> data;
278 assert(std::ranges::find(data, 4) == data.end());
279 assert(std::ranges::find(data.begin(), data.end(), 4) == data.end());
280 }
281
282 { // single element - match
283 std::deque<int> data = {4};
284 assert(std::ranges::find(data, 4) == data.begin());
285 assert(std::ranges::find(data.begin(), data.end(), 4) == data.begin());
286 }
287
288 { // single element - no match
289 std::deque<int> data = {3};
290 assert(std::ranges::find(data, 4) == data.end());
291 assert(std::ranges::find(data.begin(), data.end(), 4) == data.end());
292 }
293
294 // many elements
295 for (auto size : {2, 3, 1023, 1024, 1025, 2047, 2048, 2049}) {
296 { // last element match
297 std::deque<int> data;
298 data.resize(new_size: size);
299 std::fill(first: data.begin(), last: data.end(), value: 3);
300 data[size - 1] = 4;
301 assert(std::ranges::find(data, 4) == data.end() - 1);
302 assert(std::ranges::find(data.begin(), data.end(), 4) == data.end() - 1);
303 }
304
305 { // second-last element match
306 std::deque<int> data;
307 data.resize(new_size: size);
308 std::fill(first: data.begin(), last: data.end(), value: 3);
309 data[size - 2] = 4;
310 assert(std::ranges::find(data, 4) == data.end() - 2);
311 assert(std::ranges::find(data.begin(), data.end(), 4) == data.end() - 2);
312 }
313
314 { // no match
315 std::deque<int> data;
316 data.resize(new_size: size);
317 std::fill(first: data.begin(), last: data.end(), value: 3);
318 assert(std::ranges::find(data, 4) == data.end());
319 assert(std::ranges::find(data.begin(), data.end(), 4) == data.end());
320 }
321 }
322}
323
324int main(int, char**) {
325 test_deque();
326 test();
327 static_assert(test());
328
329 types::for_each(types::cpp20_input_iterator_list<Comparable<char>*>{}, []<class Iter> {
330 if constexpr (std::forward_iterator<Iter>)
331 test_iterators<Iter>();
332 test_iterators<Iter, sentinel_wrapper<Iter>>();
333 test_iterators<Iter, sized_sentinel<Iter>>();
334 });
335
336 types::for_each(types::cpp20_input_iterator_list<Comparable<wchar_t>*>{}, []<class Iter> {
337 if constexpr (std::forward_iterator<Iter>)
338 test_iterators<Iter>();
339 test_iterators<Iter, sentinel_wrapper<Iter>>();
340 test_iterators<Iter, sized_sentinel<Iter>>();
341 });
342
343 return 0;
344}
345

source code of libcxx/test/std/algorithms/alg.nonmodifying/alg.find/ranges.find.pass.cpp