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, c++20 12 13 // template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity> 14 // requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*> 15 // constexpr bool ranges::contains(I first, S last, const T& value, Proj proj = {}); // since C++23 16 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 bool ranges::contains(R&& r, const T& value, Proj proj = {}); // since C++23 20 21 #include <algorithm> 22 #include <array> 23 #include <cassert> 24 #include <list> 25 #include <ranges> 26 #include <string> 27 #include <vector> 28 29 #include "almost_satisfies_types.h" 30 #include "boolean_testable.h" 31 #include "test_iterators.h" 32 33 struct NotEqualityComparable {}; 34 35 template <class Iter, class Sent = Iter> 36 concept HasContainsIt = requires(Iter iter, Sent sent) { std::ranges::contains(iter, sent, *iter); }; 37 38 static_assert(HasContainsIt<int*>); 39 static_assert(HasContainsIt<int*, int*>); 40 static_assert(!HasContainsIt<NotEqualityComparable*>); 41 static_assert(!HasContainsIt<InputIteratorNotDerivedFrom>); 42 static_assert(!HasContainsIt<InputIteratorNotIndirectlyReadable>); 43 static_assert(!HasContainsIt<InputIteratorNotInputOrOutputIterator>); 44 static_assert(!HasContainsIt<cpp20_input_iterator<int*>, SentinelForNotSemiregular>); 45 static_assert(!HasContainsIt<cpp20_input_iterator<int*>, InputRangeNotSentinelEqualityComparableWith>); 46 static_assert(!HasContainsIt<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>); 47 48 static_assert(!HasContainsIt<int*, int>); 49 static_assert(!HasContainsIt<int, int*>); 50 51 template <class Range, class ValT> 52 concept HasContainsR = requires(Range&& range) { std::ranges::contains(std::forward<Range>(range), ValT{}); }; 53 54 static_assert(!HasContainsR<int, int>); 55 static_assert(HasContainsR<int[1], int>); 56 static_assert(!HasContainsR<NotEqualityComparable[1], NotEqualityComparable>); 57 static_assert(!HasContainsR<InputRangeNotDerivedFrom, int>); 58 static_assert(!HasContainsR<InputRangeNotIndirectlyReadable, int>); 59 static_assert(!HasContainsR<InputRangeNotInputOrOutputIterator, int>); 60 static_assert(!HasContainsR<InputRangeNotSentinelSemiregular, int>); 61 static_assert(!HasContainsR<InputRangeNotSentinelEqualityComparableWith, int>); 62 63 template <class Iter, class Sent = Iter> 64 constexpr void test_iterators() { 65 using ValueT = std::iter_value_t<Iter>; 66 { // simple tests 67 ValueT a[] = {1, 2, 3, 4, 5, 6}; 68 { 69 std::same_as<bool> decltype(auto) ret = std::ranges::contains(Iter(a), Sent(Iter(a + 6)), 3); 70 assert(ret); 71 } 72 { 73 auto whole = std::ranges::subrange(Iter(a), Sent(Iter(a + 6))); 74 std::same_as<bool> decltype(auto) ret = std::ranges::contains(whole, 3); 75 assert(ret); 76 } 77 } 78 79 { // check that a range with a single element works 80 ValueT a[] = {32}; 81 { 82 bool ret = std::ranges::contains(Iter(a), Sent(Iter(a + 1)), 32); 83 assert(ret); 84 } 85 { 86 auto whole = std::ranges::subrange(Iter(a), Sent(Iter(a + 1))); 87 bool ret = std::ranges::contains(whole, 32); 88 assert(ret); 89 } 90 } 91 92 { // check that an empty range works 93 std::array<ValueT, 0> a = {}; 94 { 95 bool ret = std::ranges::contains(Iter(a.data()), Sent(Iter(a.data())), 1); 96 assert(!ret); 97 } 98 { 99 auto whole = std::ranges::subrange(Iter(a.data()), Sent(Iter(a.data()))); 100 bool ret = std::ranges::contains(whole, 1); 101 assert(!ret); 102 } 103 } 104 105 { // check that the first element matches 106 ValueT a[] = {32, 3, 2, 1, 0, 23, 21, 9, 40, 100}; 107 { 108 bool ret = std::ranges::contains(Iter(a), Sent(Iter(a + 10)), 32); 109 assert(ret); 110 } 111 { 112 auto whole = std::ranges::subrange(Iter(a), Sent(Iter(a + 10))); 113 bool ret = std::ranges::contains(whole, 32); 114 assert(ret); 115 } 116 } 117 118 { // check that the last element matches 119 ValueT a[] = {3, 22, 1, 43, 99, 0, 56, 100, 32}; 120 { 121 bool ret = std::ranges::contains(Iter(a), Sent(Iter(a + 9)), 32); 122 assert(ret); 123 } 124 { 125 auto whole = std::ranges::subrange(Iter(a), Sent(Iter(a + 9))); 126 bool ret = std::ranges::contains(whole, 32); 127 assert(ret); 128 } 129 } 130 131 { // no match 132 ValueT a[] = {13, 1, 21, 4, 5}; 133 { 134 bool ret = std::ranges::contains(Iter(a), Sent(Iter(a + 5)), 10); 135 assert(!ret); 136 } 137 { 138 auto whole = std::ranges::subrange(Iter(a), Sent(Iter(a + 5))); 139 bool ret = std::ranges::contains(whole, 10); 140 assert(!ret); 141 } 142 } 143 144 { // check that the projections are used 145 int a[] = {1, 9, 0, 13, 25}; 146 { 147 bool ret = std::ranges::contains(a, a + 5, -13, [&](int i) { return i * -1; }); 148 assert(ret); 149 } 150 { 151 auto range = std::ranges::subrange(a, a + 5); 152 bool ret = std::ranges::contains(range, -13, [&](int i) { return i * -1; }); 153 assert(ret); 154 } 155 } 156 } 157 158 constexpr bool test() { 159 types::for_each(types::type_list<char, long long>{}, []<class T> { 160 types::for_each(types::cpp20_input_iterator_list<T*>{}, []<class Iter> { 161 if constexpr (std::forward_iterator<Iter>) 162 test_iterators<Iter>(); 163 test_iterators<Iter, sentinel_wrapper<Iter>>(); 164 test_iterators<Iter, sized_sentinel<Iter>>(); 165 }); 166 }); 167 168 { // count invocations of the projection for contiguous iterators 169 int a[] = {1, 9, 0, 13, 25}; 170 int projection_count = 0; 171 { 172 bool ret = std::ranges::contains(a, a + 5, 0, [&](int i) { 173 ++projection_count; 174 return i; 175 }); 176 assert(ret); 177 assert(projection_count == 3); 178 projection_count = 0; 179 } 180 { 181 bool ret = std::ranges::contains(a, 0, [&](int i) { 182 ++projection_count; 183 return i; 184 }); 185 assert(ret); 186 assert(projection_count == 3); 187 } 188 } 189 190 { // check invocations of the projection for std::string 191 const std::string str{"hello world"}; 192 const std::string str1{"hi world"}; 193 int projection_count = 0; 194 { 195 std::string a[] = {str1, str1, str, str1, str1}; 196 auto whole = 197 std::ranges::subrange(forward_iterator(std::move_iterator(a)), forward_iterator(std::move_iterator(a + 5))); 198 bool ret = std::ranges::contains(whole.begin(), whole.end(), "hello world", [&](const std::string i) { 199 ++projection_count; 200 return i; 201 }); 202 assert(ret); 203 assert(projection_count == 3); 204 projection_count = 0; 205 } 206 { 207 std::string a[] = {str1, str1, str, str1, str1}; 208 auto whole = 209 std::ranges::subrange(forward_iterator(std::move_iterator(a)), forward_iterator(std::move_iterator(a + 5))); 210 bool ret = std::ranges::contains(whole, "hello world", [&](const std::string i) { 211 ++projection_count; 212 return i; 213 }); 214 assert(ret); 215 assert(projection_count == 3); 216 } 217 } 218 219 { // check invocations of the projection for non-contiguous iterators 220 std::vector<bool> whole{false, false, true, false}; 221 int projection_count = 0; 222 { 223 bool ret = std::ranges::contains(whole.begin(), whole.end(), true, [&](bool b) { 224 ++projection_count; 225 return b; 226 }); 227 assert(ret); 228 assert(projection_count == 3); 229 projection_count = 0; 230 } 231 { 232 bool ret = std::ranges::contains(whole, true, [&](bool b) { 233 ++projection_count; 234 return b; 235 }); 236 assert(ret); 237 assert(projection_count == 3); 238 } 239 } 240 241 { // check invocations of the projection for views::transform 242 int a[] = {1, 2, 3, 4, 5}; 243 int projection_count = 0; 244 auto square_number = a | std::views::transform([](int x) { return x * x; }); 245 { 246 bool ret = std::ranges::contains(square_number.begin(), square_number.end(), 16, [&](int i) { 247 ++projection_count; 248 return i; 249 }); 250 assert(ret); 251 assert(projection_count == 4); 252 projection_count = 0; 253 } 254 { 255 bool ret = std::ranges::contains(square_number, 16, [&](int i) { 256 ++projection_count; 257 return i; 258 }); 259 assert(ret); 260 assert(projection_count == 4); 261 } 262 } 263 264 return true; 265 } 266 267 // test for non-contiguous containers 268 bool test_nonconstexpr() { 269 std::list<int> a = {7, 5, 0, 16, 8}; 270 int projection_count = 0; 271 { 272 bool ret = std::ranges::contains(a.begin(), a.end(), 0, [&](int i) { 273 ++projection_count; 274 return i; 275 }); 276 assert(ret); 277 assert(projection_count == 3); 278 projection_count = 0; 279 } 280 { 281 bool ret = std::ranges::contains(a, 0, [&](int i) { 282 ++projection_count; 283 return i; 284 }); 285 assert(ret); 286 assert(projection_count == 3); 287 } 288 289 return true; 290 } 291 292 int main(int, char**) { 293 test(); 294 static_assert(test()); 295 296 assert(test_nonconstexpr()); 297 298 return 0; 299 } 300