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 // UNSUPPORTED: libcpp-has-no-incomplete-ranges 13 14 // template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity> 15 // requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*> 16 // constexpr I ranges::find(I first, S last, const T& value, Proj proj = {}); 17 // template<input_range R, class T, class Proj = identity> 18 // requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*> 19 // constexpr borrowed_iterator_t<R> 20 // ranges::find(R&& r, const T& value, Proj proj = {}); 21 22 #include <algorithm> 23 #include <array> 24 #include <cassert> 25 #include <ranges> 26 27 #include "almost_satisfies_types.h" 28 #include "test_iterators.h" 29 30 struct NotEqualityComparable {}; 31 32 template <class It, class Sent = It> 33 concept HasFindIt = requires(It it, Sent sent) { std::ranges::find(it, sent, *it); }; 34 static_assert(HasFindIt<int*>); 35 static_assert(!HasFindIt<NotEqualityComparable*>); 36 static_assert(!HasFindIt<InputIteratorNotDerivedFrom>); 37 static_assert(!HasFindIt<InputIteratorNotIndirectlyReadable>); 38 static_assert(!HasFindIt<InputIteratorNotInputOrOutputIterator>); 39 static_assert(!HasFindIt<cpp20_input_iterator<int*>, SentinelForNotSemiregular>); 40 static_assert(!HasFindIt<cpp20_input_iterator<int*>, InputRangeNotSentinelEqualityComparableWith>); 41 42 static_assert(!HasFindIt<int*, int>); 43 static_assert(!HasFindIt<int, int*>); 44 45 template <class Range, class ValT> 46 concept HasFindR = requires(Range r) { std::ranges::find(r, ValT{}); }; 47 static_assert(HasFindR<std::array<int, 1>, int>); 48 static_assert(!HasFindR<int, int>); 49 static_assert(!HasFindR<std::array<NotEqualityComparable, 1>, NotEqualityComparable>); 50 static_assert(!HasFindR<InputRangeNotDerivedFrom, int>); 51 static_assert(!HasFindR<InputRangeNotIndirectlyReadable, int>); 52 static_assert(!HasFindR<InputRangeNotInputOrOutputIterator, int>); 53 static_assert(!HasFindR<InputRangeNotSentinelSemiregular, int>); 54 static_assert(!HasFindR<InputRangeNotSentinelEqualityComparableWith, int>); 55 56 template <class It, class Sent = It> 57 constexpr void test_iterators() { 58 { 59 int a[] = {1, 2, 3, 4}; 60 std::same_as<It> auto ret = std::ranges::find(It(a), Sent(It(a + 4)), 4); 61 assert(base(ret) == a + 3); 62 assert(*ret == 4); 63 } 64 { 65 int a[] = {1, 2, 3, 4}; 66 auto range = std::ranges::subrange(It(a), Sent(It(a + 4))); 67 std::same_as<It> auto ret = std::ranges::find(range, 4); 68 assert(base(ret) == a + 3); 69 assert(*ret == 4); 70 } 71 } 72 73 struct OneWayComparable { 74 bool isLeft; 75 friend constexpr bool operator==(OneWayComparable l, OneWayComparable) { return l.isLeft; } 76 }; 77 78 struct NonConstComparableLValue { 79 friend constexpr bool operator==(const NonConstComparableLValue&, const NonConstComparableLValue&) { return false; } 80 friend constexpr bool operator==(NonConstComparableLValue&, NonConstComparableLValue&) { return false; } 81 friend constexpr bool operator==(const NonConstComparableLValue&, NonConstComparableLValue&) { return false; } 82 friend constexpr bool operator==(NonConstComparableLValue&, const NonConstComparableLValue&) { return true; } 83 }; 84 85 struct NonConstComparableRValue { 86 friend constexpr bool operator==(const NonConstComparableRValue&, const NonConstComparableRValue&) { return false; } 87 friend constexpr bool operator==(const NonConstComparableRValue&&, const NonConstComparableRValue&&) { return false; } 88 friend constexpr bool operator==(NonConstComparableRValue&&, NonConstComparableRValue&&) { return false; } 89 friend constexpr bool operator==(NonConstComparableRValue&&, const NonConstComparableRValue&) { return true; } 90 }; 91 92 constexpr bool test() { 93 test_iterators<int*>(); 94 test_iterators<const int*>(); 95 test_iterators<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>(); 96 test_iterators<bidirectional_iterator<int*>>(); 97 test_iterators<forward_iterator<int*>>(); 98 test_iterators<random_access_iterator<int*>>(); 99 test_iterators<contiguous_iterator<int*>>(); 100 101 { 102 // check that projections are used properly and that they are called with the iterator directly 103 { 104 int a[] = {1, 2, 3, 4}; 105 auto ret = std::ranges::find(a, a + 4, a + 3, [](int& i) { return &i; }); 106 assert(ret == a + 3); 107 } 108 { 109 int a[] = {1, 2, 3, 4}; 110 auto ret = std::ranges::find(a, a + 3, [](int& i) { return &i; }); 111 assert(ret == a + 3); 112 } 113 } 114 115 { // check that the first element is returned 116 { 117 struct S { 118 int comp; 119 int other; 120 }; 121 S a[] = { {0, 0}, {0, 2}, {0, 1} }; 122 auto ret = std::ranges::find(a, 0, &S::comp); 123 assert(ret == a); 124 assert(ret->comp == 0); 125 assert(ret->other == 0); 126 } 127 { 128 struct S { 129 int comp; 130 int other; 131 }; 132 S a[] = { {0, 0}, {0, 2}, {0, 1} }; 133 auto ret = std::ranges::find(a, a + 3, 0, &S::comp); 134 assert(ret == a); 135 assert(ret->comp == 0); 136 assert(ret->other == 0); 137 } 138 } 139 140 { // check that end + 1 iterator is returned with no match 141 { 142 int a[] = {1, 1, 1}; 143 auto ret = std::ranges::find(a, a + 3, 0); 144 assert(ret == a + 3); 145 } 146 { 147 int a[] = {1, 1, 1}; 148 auto ret = std::ranges::find(a, 0); 149 assert(ret == a + 3); 150 } 151 } 152 153 { 154 // check that ranges::dangling is returned 155 [[maybe_unused]] std::same_as<std::ranges::dangling> auto ret = 156 std::ranges::find(std::array{1, 2}, 3); 157 } 158 159 { 160 // check that an iterator is returned with a borrowing range 161 int a[] = {1, 2, 3, 4}; 162 std::same_as<int*> auto ret = std::ranges::find(std::views::all(a), 1); 163 assert(ret == a); 164 assert(*ret == 1); 165 } 166 167 { 168 // check that std::invoke is used 169 struct S { int i; }; 170 S a[] = { S{1}, S{3}, S{2} }; 171 std::same_as<S*> auto ret = std::ranges::find(a, 4, &S::i); 172 assert(ret == a + 3); 173 } 174 175 { 176 // count invocations of the projection 177 { 178 int a[] = {1, 2, 3, 4}; 179 int projection_count = 0; 180 auto ret = std::ranges::find(a, a + 4, 2, [&](int i) { ++projection_count; return i; }); 181 assert(ret == a + 1); 182 assert(*ret == 2); 183 assert(projection_count == 2); 184 } 185 { 186 int a[] = {1, 2, 3, 4}; 187 int projection_count = 0; 188 auto ret = std::ranges::find(a, 2, [&](int i) { ++projection_count; return i; }); 189 assert(ret == a + 1); 190 assert(*ret == 2); 191 assert(projection_count == 2); 192 } 193 } 194 195 { 196 // check comparison order 197 { 198 OneWayComparable a[] = { OneWayComparable{true} }; 199 auto ret = std::ranges::find(a, a + 1, OneWayComparable{false}); 200 assert(ret == a); 201 } 202 { 203 OneWayComparable a[] = { OneWayComparable{true} }; 204 auto ret = std::ranges::find(a, OneWayComparable{false}); 205 assert(ret == a); 206 } 207 } 208 209 { 210 // check that the return type of `iter::operator*` doesn't change 211 { 212 NonConstComparableLValue a[] = { NonConstComparableLValue{} }; 213 auto ret = std::ranges::find(a, a + 1, NonConstComparableLValue{}); 214 assert(ret == a); 215 } 216 { 217 using It = std::move_iterator<NonConstComparableRValue*>; 218 NonConstComparableRValue a[] = { NonConstComparableRValue{} }; 219 auto ret = std::ranges::find(It(a), It(a + 1), NonConstComparableRValue{}); 220 assert(ret.base() == a); 221 } 222 { 223 NonConstComparableLValue a[] = { NonConstComparableLValue{} }; 224 auto ret = std::ranges::find(a, NonConstComparableLValue{}); 225 assert(ret == a); 226 } 227 { 228 using It = std::move_iterator<NonConstComparableRValue*>; 229 NonConstComparableRValue a[] = { NonConstComparableRValue{} }; 230 auto range = std::ranges::subrange(It(a), It(a + 1)); 231 auto ret = std::ranges::find(range, NonConstComparableRValue{}); 232 assert(ret.base() == a); 233 } 234 } 235 236 { 237 // check that an empty range works 238 { 239 std::array<int ,0> a = {}; 240 auto ret = std::ranges::find(a.begin(), a.end(), 1); 241 assert(ret == a.begin()); 242 } 243 { 244 std::array<int, 0> a = {}; 245 auto ret = std::ranges::find(a, 1); 246 assert(ret == a.begin()); 247 } 248 } 249 250 return true; 251 } 252 253 int main(int, char**) { 254 test(); 255 static_assert(test()); 256 257 return 0; 258 } 259