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 // template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2, 14 // class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity> 15 // requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2> 16 // constexpr bool ranges::equal(I1 first1, S1 last1, I2 first2, S2 last2, 17 // Pred pred = {}, 18 // Proj1 proj1 = {}, Proj2 proj2 = {}); 19 // template<input_range R1, input_range R2, class Pred = ranges::equal_to, 20 // class Proj1 = identity, class Proj2 = identity> 21 // requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2> 22 // constexpr bool ranges::equal(R1&& r1, R2&& r2, Pred pred = {}, 23 // Proj1 proj1 = {}, Proj2 proj2 = {}); 24 25 #include <algorithm> 26 #include <cassert> 27 #include <concepts> 28 #include <functional> 29 #include <ranges> 30 31 #include "almost_satisfies_types.h" 32 #include "test_iterators.h" 33 34 template <class Iter1, class Sent1 = sentinel_wrapper<Iter1>, 35 class Iter2 = Iter1, class Sent2 = sentinel_wrapper<Iter2>> 36 concept HasEqualIt = requires (Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) { 37 std::ranges::equal(first1, last1, first2, last2); 38 }; 39 40 static_assert(HasEqualIt<int*>); 41 static_assert(!HasEqualIt<InputIteratorNotDerivedFrom>); 42 static_assert(!HasEqualIt<InputIteratorNotIndirectlyReadable>); 43 static_assert(!HasEqualIt<InputIteratorNotInputOrOutputIterator>); 44 static_assert(!HasEqualIt<int*, int*, InputIteratorNotDerivedFrom>); 45 static_assert(!HasEqualIt<int*, int*, InputIteratorNotIndirectlyReadable>); 46 static_assert(!HasEqualIt<int*, int*, InputIteratorNotInputOrOutputIterator>); 47 static_assert(!HasEqualIt<int*, SentinelForNotSemiregular>); 48 static_assert(!HasEqualIt<int*, SentinelForNotWeaklyEqualityComparableWith>); 49 static_assert(!HasEqualIt<int*, int*, int*, SentinelForNotSemiregular>); 50 static_assert(!HasEqualIt<int*, int*, int*, SentinelForNotWeaklyEqualityComparableWith>); 51 static_assert(!HasEqualIt<int*, int*, int**>); 52 53 template <class Range1, class Range2> 54 concept HasEqualR = requires (Range1 range1, Range2 range2) { 55 std::ranges::equal(range1, range2); 56 }; 57 58 static_assert(HasEqualR<UncheckedRange<int*>, UncheckedRange<int*>>); 59 static_assert(!HasEqualR<InputRangeNotDerivedFrom, UncheckedRange<int*>>); 60 static_assert(!HasEqualR<InputRangeNotIndirectlyReadable, UncheckedRange<int*>>); 61 static_assert(!HasEqualR<InputRangeNotInputOrOutputIterator, UncheckedRange<int*>>); 62 static_assert(!HasEqualR<InputRangeNotSentinelSemiregular, UncheckedRange<int*>>); 63 static_assert(!HasEqualR<InputRangeNotSentinelEqualityComparableWith, UncheckedRange<int*>>); 64 static_assert(!HasEqualR<UncheckedRange<int*>, InputRangeNotDerivedFrom>); 65 static_assert(!HasEqualR<UncheckedRange<int*>, InputRangeNotIndirectlyReadable>); 66 static_assert(!HasEqualR<UncheckedRange<int*>, InputRangeNotInputOrOutputIterator>); 67 static_assert(!HasEqualR<UncheckedRange<int*>, InputRangeNotSentinelSemiregular>); 68 static_assert(!HasEqualR<UncheckedRange<int*>, InputRangeNotSentinelEqualityComparableWith>); 69 static_assert(!HasEqualR<UncheckedRange<int*>, UncheckedRange<int**>>); 70 71 template <class Iter1, class Sent1, class Iter2, class Sent2 = Iter2> 72 constexpr void test_iterators() { 73 { // simple test 74 { 75 int a[] = {1, 2, 3, 4}; 76 int b[] = {1, 2, 3, 4}; 77 std::same_as<bool> decltype(auto) ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), 78 Iter2(b), Sent2(Iter2(b + 4))); 79 assert(ret); 80 } 81 { 82 int a[] = {1, 2, 3, 4}; 83 int b[] = {1, 2, 3, 4}; 84 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4))); 85 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 4))); 86 std::same_as<bool> decltype(auto) ret = std::ranges::equal(range1, range2); 87 assert(ret); 88 } 89 } 90 91 { // check that false is returned for non-equal ranges 92 { 93 int a[] = {1, 2, 3, 4}; 94 int b[] = {1, 2, 4, 4}; 95 assert(!std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 4)))); 96 } 97 { 98 int a[] = {1, 2, 3, 4}; 99 int b[] = {1, 2, 4, 4}; 100 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4))); 101 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 4))); 102 assert(!std::ranges::equal(range1, range2)); 103 } 104 } 105 106 { // check that the predicate is used (return true) 107 { 108 int a[] = {1, 2, 3, 4}; 109 int b[] = {2, 3, 4, 5}; 110 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 4)), 111 [](int l, int r) { return l != r; }); 112 assert(ret); 113 } 114 { 115 int a[] = {1, 2, 3, 4}; 116 int b[] = {2, 3, 4, 5}; 117 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4))); 118 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 4))); 119 auto ret = std::ranges::equal(range1, range2, [](int l, int r) { return l != r; }); 120 assert(ret); 121 } 122 } 123 124 { // check that the predicate is used (return false) 125 { 126 int a[] = {1, 2, 3, 4}; 127 int b[] = {2, 3, 3, 5}; 128 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 4)), 129 [](int l, int r) { return l != r; }); 130 assert(!ret); 131 } 132 { 133 int a[] = {1, 2, 3, 4}; 134 int b[] = {2, 3, 3, 5}; 135 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4))); 136 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 4))); 137 auto ret = std::ranges::equal(range1, range2, [](int l, int r) { return l != r; }); 138 assert(!ret); 139 } 140 } 141 142 { // check that the projections are used 143 { 144 int a[] = {1, 2, 3, 4, 5}; 145 int b[] = {6, 10, 14, 18, 22}; 146 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 5)), 147 Iter2(b), Sent2(Iter2(b + 5)), 148 {}, 149 [](int i) { return i * 4; }, 150 [](int i) { return i - 2; }); 151 assert(ret); 152 } 153 { 154 int a[] = {1, 2, 3, 4, 5}; 155 int b[] = {6, 10, 14, 18, 22}; 156 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5))); 157 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 5))); 158 auto ret = std::ranges::equal(range1, 159 range2, 160 {}, 161 [](int i) { return i * 4; }, 162 [](int i) { return i - 2; }); 163 assert(ret); 164 } 165 } 166 167 { // check that different sized ranges work 168 { 169 int a[] = {4, 3, 2, 1}; 170 int b[] = {4, 3, 2, 1, 5, 6, 7}; 171 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 7))); 172 assert(!ret); 173 } 174 { 175 int a[] = {4, 3, 2, 1}; 176 int b[] = {4, 3, 2, 1, 5, 6, 7}; 177 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4))); 178 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 7))); 179 auto ret = std::ranges::equal(range1, range2); 180 assert(!ret); 181 } 182 } 183 184 { // check that two ranges with the same size but different values are different 185 { 186 int a[] = {4, 6, 34, 76, 5}; 187 int b[] = {4, 6, 34, 67, 5}; 188 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 5)), Iter2(b), Sent2(Iter2(b + 5))); 189 assert(!ret); 190 } 191 { 192 int a[] = {4, 6, 34, 76, 5}; 193 int b[] = {4, 6, 34, 67, 5}; 194 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5))); 195 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 5))); 196 auto ret = std::ranges::equal(range1, range2); 197 assert(!ret); 198 } 199 } 200 201 { // check that two empty ranges work 202 { 203 int a[] = {}; 204 int b[] = {}; 205 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a)), Iter2(b), Sent2(Iter2(b))); 206 assert(ret); 207 } 208 { 209 int a[] = {}; 210 int b[] = {}; 211 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a))); 212 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b))); 213 auto ret = std::ranges::equal(range1, range2); 214 assert(ret); 215 } 216 } 217 218 { // check that it works with the first range empty 219 { 220 int a[] = {}; 221 int b[] = {1, 2}; 222 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a)), Iter2(b), Sent2(Iter2(b + 2))); 223 assert(!ret); 224 } 225 { 226 int a[] = {}; 227 int b[] = {1, 2}; 228 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a))); 229 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 2))); 230 auto ret = std::ranges::equal(range1, range2); 231 assert(!ret); 232 } 233 } 234 235 { // check that it works with the second range empty 236 { 237 int a[] = {1, 2}; 238 int b[] = {}; 239 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 2)), Iter2(b), Sent2(Iter2(b))); 240 assert(!ret); 241 } 242 { 243 int a[] = {1, 2}; 244 int b[] = {}; 245 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 2))); 246 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b))); 247 auto ret = std::ranges::equal(range1, range2); 248 assert(!ret); 249 } 250 } 251 } 252 253 template<class Iter1, class Sent1 = Iter1> 254 constexpr void test_iterators2() { 255 test_iterators<Iter1, Sent1, cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>(); 256 test_iterators<Iter1, Sent1, cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>(); 257 test_iterators<Iter1, Sent1, forward_iterator<int*>>(); 258 test_iterators<Iter1, Sent1, bidirectional_iterator<int*>>(); 259 test_iterators<Iter1, Sent1, random_access_iterator<int*>>(); 260 test_iterators<Iter1, Sent1, contiguous_iterator<int*>>(); 261 test_iterators<Iter1, Sent1, int*>(); 262 test_iterators<Iter1, Sent1, const int*>(); 263 } 264 265 constexpr bool test() { 266 test_iterators2<cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>(); 267 test_iterators2<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>(); 268 test_iterators2<forward_iterator<int*>>(); 269 test_iterators2<bidirectional_iterator<int*>>(); 270 test_iterators2<random_access_iterator<int*>>(); 271 test_iterators2<contiguous_iterator<int*>>(); 272 test_iterators2<int*>(); 273 test_iterators2<const int*>(); 274 275 { // check that std::invoke is used 276 struct S { 277 constexpr S(int i_) : i(i_) {} 278 constexpr bool equal(int o) { return i == o; } 279 constexpr S& identity() { return *this; } 280 int i; 281 }; 282 { 283 S a[] = {7, 8, 9}; 284 S b[] = {7, 8, 9}; 285 auto ret = std::ranges::equal(a, a + 3, b, b + 3, &S::equal, &S::identity, &S::i); 286 assert(ret); 287 } 288 { 289 S a[] = {7, 8, 9}; 290 S b[] = {7, 8, 9}; 291 auto ret = std::ranges::equal(a, b, &S::equal, &S::identity, &S::i); 292 assert(ret); 293 } 294 } 295 296 { // check that the complexity requirements are met 297 { // different size 298 { 299 int a[] = {1, 2, 3}; 300 int b[] = {1, 2, 3, 4}; 301 int predCount = 0; 302 int projCount = 0; 303 auto pred = [&](int l, int r) { ++predCount; return l == r; }; 304 auto proj = [&](int i) { ++projCount; return i; }; 305 auto ret = std::ranges::equal(a, a + 3, b, b + 4, pred, proj, proj); 306 assert(!ret); 307 assert(predCount == 0); 308 assert(projCount == 0); 309 } 310 { 311 int a[] = {1, 2, 3}; 312 int b[] = {1, 2, 3, 4}; 313 int predCount = 0; 314 int projCount = 0; 315 auto pred = [&](int l, int r) { ++predCount; return l == r; }; 316 auto proj = [&](int i) { ++projCount; return i; }; 317 auto ret = std::ranges::equal(a, b, pred, proj, proj); 318 assert(!ret); 319 assert(predCount == 0); 320 assert(projCount == 0); 321 } 322 } 323 324 { // not a sized sentinel 325 { 326 int a[] = {1, 2, 3}; 327 int b[] = {1, 2, 3, 4}; 328 int predCount = 0; 329 int projCount = 0; 330 auto pred = [&](int l, int r) { ++predCount; return l == r; }; 331 auto proj = [&](int i) { ++projCount; return i; }; 332 auto ret = std::ranges::equal(a, sentinel_wrapper(a + 3), b, sentinel_wrapper(b + 4), pred, proj, proj); 333 assert(!ret); 334 assert(predCount <= 4); 335 assert(projCount <= 7); 336 } 337 { 338 int a[] = {1, 2, 3}; 339 int b[] = {1, 2, 3, 4}; 340 int predCount = 0; 341 int projCount = 0; 342 auto pred = [&](int l, int r) { ++predCount; return l == r; }; 343 auto proj = [&](int i) { ++projCount; return i; }; 344 auto range1 = std::ranges::subrange(a, sentinel_wrapper(a + 3)); 345 auto range2 = std::ranges::subrange(b, sentinel_wrapper(b + 4)); 346 auto ret = std::ranges::equal(range1, range2, pred, proj, proj); 347 assert(!ret); 348 assert(predCount <= 4); 349 assert(projCount <= 7); 350 } 351 } 352 353 { // same size 354 { 355 int a[] = {1, 2, 3}; 356 int b[] = {1, 2, 3}; 357 int predCount = 0; 358 int projCount = 0; 359 auto pred = [&](int l, int r) { ++predCount; return l == r; }; 360 auto proj = [&](int i) { ++projCount; return i; }; 361 auto ret = std::ranges::equal(a, a + 3, b, b + 3, pred, proj, proj); 362 assert(ret); 363 assert(predCount == 3); 364 assert(projCount == 6); 365 } 366 { 367 int a[] = {1, 2, 3}; 368 int b[] = {1, 2, 3}; 369 int predCount = 0; 370 int projCount = 0; 371 auto pred = [&](int l, int r) { ++predCount; return l == r; }; 372 auto proj = [&](int i) { ++projCount; return i; }; 373 auto ret = std::ranges::equal(a, b, pred, proj, proj); 374 assert(ret); 375 assert(predCount == 3); 376 assert(projCount == 6); 377 } 378 } 379 } 380 381 return true; 382 } 383 384 int main(int, char**) { 385 test(); 386 static_assert(test()); 387 388 return 0; 389 } 390