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-style-warnings): -Wno-sign-compare 10 // MSVC warning C4389: '==': signed/unsigned mismatch 11 // ADDITIONAL_COMPILE_FLAGS(cl-style-warnings): /wd4389 12 13 // <algorithm> 14 15 // template<InputIterator Iter, class T> 16 // requires HasEqualTo<Iter::value_type, T> 17 // constexpr Iter // constexpr after C++17 18 // find(Iter first, Iter last, const T& value); 19 20 #include <algorithm> 21 #include <cassert> 22 #include <deque> 23 #include <vector> 24 #include <type_traits> 25 26 #include "test_macros.h" 27 #include "test_iterators.h" 28 #include "type_algorithms.h" 29 30 static std::vector<int> comparable_data; 31 32 template <class ArrayT, class CompareT> 33 struct Test { 34 template <class Iter> 35 TEST_CONSTEXPR_CXX20 void operator()() { 36 ArrayT arr[] = { 37 ArrayT(1), ArrayT(2), ArrayT(3), ArrayT(4), ArrayT(5), ArrayT(6), ArrayT(7), ArrayT(8), ArrayT(9), ArrayT(10)}; 38 39 static_assert(std::is_same<decltype(std::find(Iter(arr), Iter(arr), 0)), Iter>::value, ""); 40 41 { // first element matches 42 Iter iter = std::find(Iter(arr), Iter(arr + 10), CompareT(1)); 43 assert(*iter == ArrayT(1)); 44 assert(base(iter) == arr); 45 } 46 47 { // range is empty; return last 48 Iter iter = std::find(Iter(arr), Iter(arr), CompareT(1)); 49 assert(base(iter) == arr); 50 } 51 52 { // if multiple elements match, return the first match 53 ArrayT data[] = { 54 ArrayT(1), ArrayT(2), ArrayT(3), ArrayT(4), ArrayT(5), ArrayT(6), ArrayT(7), ArrayT(5), ArrayT(4)}; 55 Iter iter = std::find(Iter(std::begin(data)), Iter(std::end(data)), CompareT(5)); 56 assert(*iter == ArrayT(5)); 57 assert(base(iter) == data + 4); 58 } 59 60 { // some element matches 61 Iter iter = std::find(Iter(arr), Iter(arr + 10), CompareT(6)); 62 assert(*iter == ArrayT(6)); 63 assert(base(iter) == arr + 5); 64 } 65 66 { // last element matches 67 Iter iter = std::find(Iter(arr), Iter(arr + 10), CompareT(10)); 68 assert(*iter == ArrayT(10)); 69 assert(base(iter) == arr + 9); 70 } 71 72 { // if no element matches, last is returned 73 Iter iter = std::find(Iter(arr), Iter(arr + 10), CompareT(20)); 74 assert(base(iter) == arr + 10); 75 } 76 77 if (!TEST_IS_CONSTANT_EVALUATED) 78 comparable_data.clear(); 79 } 80 }; 81 82 template <class IndexT> 83 class Comparable { 84 IndexT index_; 85 86 static IndexT init_index(IndexT i) { 87 IndexT size = static_cast<IndexT>(comparable_data.size()); 88 comparable_data.push_back(i); 89 return size; 90 } 91 92 public: 93 Comparable(IndexT i) : index_(init_index(i)) {} 94 95 friend bool operator==(const Comparable& lhs, const Comparable& rhs) { 96 return comparable_data[lhs.index_] == comparable_data[rhs.index_]; 97 } 98 }; 99 100 #if TEST_STD_VER >= 20 101 template <class ElementT> 102 class TriviallyComparable { 103 ElementT el_; 104 105 public: 106 explicit constexpr TriviallyComparable(ElementT el) : el_(el) {} 107 bool operator==(const TriviallyComparable&) const = default; 108 }; 109 #endif 110 111 template <class CompareT> 112 struct TestTypes { 113 template <class T> 114 TEST_CONSTEXPR_CXX20 void operator()() { 115 types::for_each(types::cpp17_input_iterator_list<T*>(), Test<T, CompareT>()); 116 } 117 }; 118 119 void test_deque() { 120 { // empty deque 121 std::deque<int> data; 122 assert(std::find(data.begin(), data.end(), 4) == data.end()); 123 } 124 125 { // single element - match 126 std::deque<int> data; 127 data.push_back(4); 128 assert(std::find(data.begin(), data.end(), 4) == data.begin()); 129 } 130 131 { // single element - no match 132 std::deque<int> data; 133 data.push_back(3); 134 assert(std::find(data.begin(), data.end(), 4) == data.end()); 135 } 136 137 // many elements 138 int sizes[] = {2, 3, 1023, 1024, 1025, 2047, 2048, 2049}; 139 for (auto size : sizes) { 140 { // last element match 141 std::deque<int> data; 142 data.resize(size); 143 std::fill(data.begin(), data.end(), 3); 144 data[size - 1] = 4; 145 assert(std::find(data.begin(), data.end(), 4) == data.end() - 1); 146 } 147 148 { // second-last element match 149 std::deque<int> data; 150 data.resize(size); 151 std::fill(data.begin(), data.end(), 3); 152 data[size - 2] = 4; 153 assert(std::find(data.begin(), data.end(), 4) == data.end() - 2); 154 } 155 156 { // no match 157 std::deque<int> data; 158 data.resize(size); 159 std::fill(data.begin(), data.end(), 3); 160 assert(std::find(data.begin(), data.end(), 4) == data.end()); 161 } 162 } 163 } 164 165 TEST_CONSTEXPR_CXX20 bool test() { 166 types::for_each(types::integer_types(), TestTypes<char>()); 167 types::for_each(types::integer_types(), TestTypes<int>()); 168 types::for_each(types::integer_types(), TestTypes<long long>()); 169 #if TEST_STD_VER >= 20 170 Test<TriviallyComparable<char>, TriviallyComparable<char>>().operator()<TriviallyComparable<char>*>(); 171 Test<TriviallyComparable<wchar_t>, TriviallyComparable<wchar_t>>().operator()<TriviallyComparable<wchar_t>*>(); 172 #endif 173 174 // TODO: Remove the `_LIBCPP_ENABLE_EXPERIMENTAL` check once we have the FTM guarded or views::join isn't 175 // experimental anymore 176 #if TEST_STD_VER >= 20 && (!defined(_LIBCPP_VERSION) || defined(_LIBCPP_ENABLE_EXPERIMENTAL)) 177 { 178 std::vector<std::vector<int>> vec = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; 179 auto view = vec | std::views::join; 180 assert(std::find(view.begin(), view.end(), 4) == std::next(view.begin(), 3)); 181 } 182 #endif 183 184 return true; 185 } 186 187 int main(int, char**) { 188 test_deque(); 189 test(); 190 #if TEST_STD_VER >= 20 191 static_assert(test()); 192 #endif 193 194 Test<Comparable<char>, Comparable<char> >().operator()<Comparable<char>*>(); 195 Test<Comparable<wchar_t>, Comparable<wchar_t> >().operator()<Comparable<wchar_t>*>(); 196 197 return 0; 198 } 199