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// ADDITIONAL_COMPILE_FLAGS(gcc): -Wno-bool-compare
10// ADDITIONAL_COMPILE_FLAGS(gcc-style-warnings): -Wno-sign-compare
11// ADDITIONAL_COMPILE_FLAGS(character-conversion-warnings): -Wno-character-conversion
12// MSVC warning C4245: conversion from 'int' to 'wchar_t', signed/unsigned mismatch
13// MSVC warning C4305: truncation from 'int' to 'bool'
14// MSVC warning C4310: cast truncates constant value
15// MSVC warning C4389: '==': signed/unsigned mismatch
16// MSVC warning C4805: '==': unsafe mix of type 'char' and type 'bool' in operation
17// ADDITIONAL_COMPILE_FLAGS(cl-style-warnings): /wd4245 /wd4305 /wd4310 /wd4389 /wd4805
18// ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-steps): -fconstexpr-steps=20000000
19// ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-ops-limit): -fconstexpr-ops-limit=80000000
20// XFAIL: FROZEN-CXX03-HEADERS-FIXME
21
22// <algorithm>
23
24// template<InputIterator Iter, class T>
25// requires HasEqualTo<Iter::value_type, T>
26// constexpr Iter // constexpr after C++17
27// find(Iter first, Iter last, const T& value);
28
29#include <algorithm>
30#include <cassert>
31#include <cstddef>
32#include <deque>
33#include <vector>
34#include <type_traits>
35
36#include "sized_allocator.h"
37#include "test_macros.h"
38#include "test_iterators.h"
39#include "type_algorithms.h"
40
41static std::vector<int> comparable_data;
42
43template <class ArrayT, class CompareT>
44struct Test {
45 template <class Iter>
46 TEST_CONSTEXPR_CXX20 void operator()() {
47 ArrayT arr[] = {
48 ArrayT(1), ArrayT(2), ArrayT(3), ArrayT(4), ArrayT(5), ArrayT(6), ArrayT(7), ArrayT(8), ArrayT(9), ArrayT(10)};
49
50 static_assert(std::is_same<decltype(std::find(Iter(arr), Iter(arr), 0)), Iter>::value, "");
51
52 { // first element matches
53 Iter iter = std::find(Iter(arr), Iter(arr + 10), CompareT(1));
54 assert(*iter == ArrayT(1));
55 assert(base(iter) == arr);
56 }
57
58 { // range is empty; return last
59 Iter iter = std::find(Iter(arr), Iter(arr), CompareT(1));
60 assert(base(iter) == arr);
61 }
62
63 { // if multiple elements match, return the first match
64 ArrayT data[] = {
65 ArrayT(1), ArrayT(2), ArrayT(3), ArrayT(4), ArrayT(5), ArrayT(6), ArrayT(7), ArrayT(5), ArrayT(4)};
66 Iter iter = std::find(Iter(std::begin(data)), Iter(std::end(data)), CompareT(5));
67 assert(*iter == ArrayT(5));
68 assert(base(iter) == data + 4);
69 }
70
71 { // some element matches
72 Iter iter = std::find(Iter(arr), Iter(arr + 10), CompareT(6));
73 assert(*iter == ArrayT(6));
74 assert(base(iter) == arr + 5);
75 }
76
77 { // last element matches
78 Iter iter = std::find(Iter(arr), Iter(arr + 10), CompareT(10));
79 assert(*iter == ArrayT(10));
80 assert(base(iter) == arr + 9);
81 }
82
83 { // if no element matches, last is returned
84 Iter iter = std::find(Iter(arr), Iter(arr + 10), CompareT(20));
85 assert(base(iter) == arr + 10);
86 }
87
88 if (!TEST_IS_CONSTANT_EVALUATED)
89 comparable_data.clear();
90 }
91};
92
93template <class IndexT>
94class Comparable {
95 IndexT index_;
96
97 static IndexT init_index(IndexT i) {
98 IndexT size = static_cast<IndexT>(comparable_data.size());
99 comparable_data.push_back(i);
100 return size;
101 }
102
103public:
104 Comparable(IndexT i) : index_(init_index(i)) {}
105
106 friend bool operator==(const Comparable& lhs, const Comparable& rhs) {
107 return comparable_data[lhs.index_] == comparable_data[rhs.index_];
108 }
109};
110
111#if TEST_STD_VER >= 20
112template <class ElementT>
113class TriviallyComparable {
114 ElementT el_;
115
116public:
117 explicit constexpr TriviallyComparable(ElementT el) : el_(el) {}
118 bool operator==(const TriviallyComparable&) const = default;
119};
120#endif
121
122template <class CompareT>
123struct TestTypes {
124 template <class T>
125 TEST_CONSTEXPR_CXX20 void operator()() {
126 types::for_each(types::cpp17_input_iterator_list<T*>(), Test<T, CompareT>());
127 }
128};
129
130void test_deque() {
131 { // empty deque
132 std::deque<int> data;
133 assert(std::find(data.begin(), data.end(), 4) == data.end());
134 }
135
136 { // single element - match
137 std::deque<int> data;
138 data.push_back(x: 4);
139 assert(std::find(data.begin(), data.end(), 4) == data.begin());
140 }
141
142 { // single element - no match
143 std::deque<int> data;
144 data.push_back(x: 3);
145 assert(std::find(data.begin(), data.end(), 4) == data.end());
146 }
147
148 // many elements
149 int sizes[] = {2, 3, 1023, 1024, 1025, 2047, 2048, 2049};
150 for (auto size : sizes) {
151 { // last element match
152 std::deque<int> data;
153 data.resize(new_size: size);
154 std::fill(first: data.begin(), last: data.end(), value: 3);
155 data[size - 1] = 4;
156 assert(std::find(data.begin(), data.end(), 4) == data.end() - 1);
157 }
158
159 { // second-last element match
160 std::deque<int> data;
161 data.resize(new_size: size);
162 std::fill(first: data.begin(), last: data.end(), value: 3);
163 data[size - 2] = 4;
164 assert(std::find(data.begin(), data.end(), 4) == data.end() - 2);
165 }
166
167 { // no match
168 std::deque<int> data;
169 data.resize(new_size: size);
170 std::fill(first: data.begin(), last: data.end(), value: 3);
171 assert(std::find(data.begin(), data.end(), 4) == data.end());
172 }
173 }
174}
175
176template <class T>
177struct TestIntegerPromotions1 {
178 template <class U>
179 TEST_CONSTEXPR_CXX20 void test(T val, U to_find) {
180 bool expect_match = val == to_find;
181 assert(std::find(&val, &val + 1, to_find) == (expect_match ? &val : &val + 1));
182 }
183
184 template <class U>
185 TEST_CONSTEXPR_CXX20 void operator()() {
186 test<U>(0, 0);
187 test<U>(0, 1);
188 test<U>(1, 1);
189 test<U>(0, -1);
190 test<U>(-1, -1);
191 test<U>(0, U(-127));
192 test<U>(T(-127), U(-127));
193 test<U>(T(-128), U(-128));
194 test<U>(T(-129), U(-129));
195 test<U>(T(255), U(255));
196 test<U>(T(256), U(256));
197 test<U>(T(257), U(257));
198 test<U>(0, std::numeric_limits<U>::min());
199 test<U>(T(std::numeric_limits<U>::min()), std::numeric_limits<U>::min());
200 test<U>(0, std::numeric_limits<U>::min() + 1);
201 test<U>(T(std::numeric_limits<U>::min() + 1), std::numeric_limits<U>::min() + 1);
202 test<U>(0, std::numeric_limits<U>::max());
203 test<U>(T(std::numeric_limits<U>::max()), std::numeric_limits<U>::max());
204 test<U>(T(std::numeric_limits<U>::max() - 1), std::numeric_limits<U>::max() - 1);
205 }
206};
207
208struct TestIntegerPromotions {
209 template <class T>
210 TEST_CONSTEXPR_CXX20 void operator()() {
211 types::for_each(types::integral_types(), TestIntegerPromotions1<T>());
212 }
213};
214
215TEST_CONSTEXPR_CXX20 bool test() {
216 types::for_each(types::integer_types(), TestTypes<char>());
217 types::for_each(types::integer_types(), TestTypes<int>());
218 types::for_each(types::integer_types(), TestTypes<long long>());
219#if TEST_STD_VER >= 20
220 Test<TriviallyComparable<char>, TriviallyComparable<char>>().operator()<TriviallyComparable<char>*>();
221 Test<TriviallyComparable<wchar_t>, TriviallyComparable<wchar_t>>().operator()<TriviallyComparable<wchar_t>*>();
222#endif
223
224#if TEST_STD_VER >= 20
225 {
226 std::vector<std::vector<int>> vec = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
227 auto view = vec | std::views::join;
228 assert(std::find(view.begin(), view.end(), 4) == std::next(view.begin(), 3));
229 }
230#endif
231
232 types::for_each(types::integral_types(), TestIntegerPromotions());
233
234 {
235 // Test vector<bool>::iterator optimization
236 std::vector<bool> vec(256 + 8);
237 for (ptrdiff_t i = 8; i <= 256; i *= 2) {
238 for (size_t offset = 0; offset < 8; offset += 2) {
239 std::fill(first: vec.begin(), last: vec.end(), value: false);
240 std::fill(first: vec.begin() + offset, last: vec.begin() + i + offset, value: true);
241 assert(std::find(vec.begin(), vec.end(), true) == vec.begin() + offset);
242 assert(std::find(vec.begin() + offset, vec.end(), false) == vec.begin() + offset + i);
243 }
244 }
245
246 // Verify that the std::vector<bool>::iterator optimization works properly for allocators with custom size types
247 // Fix https://github.com/llvm/llvm-project/issues/122528
248 {
249 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
250 std::vector<bool, Alloc> in(100, false, Alloc(1));
251 in[in.size() - 2] = true;
252 assert(std::find(in.begin(), in.end(), true) == in.end() - 2);
253 }
254 {
255 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
256 std::vector<bool, Alloc> in(199, false, Alloc(1));
257 in[in.size() - 2] = true;
258 assert(std::find(in.begin(), in.end(), true) == in.end() - 2);
259 }
260 {
261 using Alloc = sized_allocator<bool, unsigned short, short>;
262 std::vector<bool, Alloc> in(200, false, Alloc(1));
263 in[in.size() - 2] = true;
264 assert(std::find(in.begin(), in.end(), true) == in.end() - 2);
265 }
266 {
267 using Alloc = sized_allocator<bool, std::uint32_t, std::int32_t>;
268 std::vector<bool, Alloc> in(205, false, Alloc(1));
269 in[in.size() - 2] = true;
270 assert(std::find(in.begin(), in.end(), true) == in.end() - 2);
271 }
272 {
273 using Alloc = sized_allocator<bool, std::uint64_t, std::int64_t>;
274 std::vector<bool, Alloc> in(257, false, Alloc(1));
275 in[in.size() - 2] = true;
276 assert(std::find(in.begin(), in.end(), true) == in.end() - 2);
277 }
278 }
279
280 return true;
281}
282
283int main(int, char**) {
284 test_deque();
285 test();
286#if TEST_STD_VER >= 20
287 static_assert(test());
288#endif
289
290 Test<Comparable<char>, Comparable<char> >().operator()<Comparable<char>*>();
291 Test<Comparable<wchar_t>, Comparable<wchar_t> >().operator()<Comparable<wchar_t>*>();
292
293 return 0;
294}
295

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