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 the predicate is used (return true) 92 { 93 int a[] = {1, 2, 3, 4}; 94 int b[] = {2, 3, 4, 5}; 95 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 4)), 96 [](int l, int r) { return l != r; }); 97 assert(ret); 98 } 99 { 100 int a[] = {1, 2, 3, 4}; 101 int b[] = {2, 3, 4, 5}; 102 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4))); 103 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 4))); 104 auto ret = std::ranges::equal(range1, range2, [](int l, int r) { return l != r; }); 105 assert(ret); 106 } 107 } 108 109 { // check that the predicate is used (return false) 110 { 111 int a[] = {1, 2, 3, 4}; 112 int b[] = {2, 3, 3, 5}; 113 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 4)), 114 [](int l, int r) { return l != r; }); 115 assert(!ret); 116 } 117 { 118 int a[] = {1, 2, 3, 4}; 119 int b[] = {2, 3, 3, 5}; 120 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4))); 121 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 4))); 122 auto ret = std::ranges::equal(range1, range2, [](int l, int r) { return l != r; }); 123 assert(!ret); 124 } 125 } 126 127 { // check that the projections are used 128 { 129 int a[] = {1, 2, 3, 4, 5}; 130 int b[] = {6, 10, 14, 18, 22}; 131 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 5)), 132 Iter2(b), Sent2(Iter2(b + 5)), 133 {}, 134 [](int i) { return i * 4; }, 135 [](int i) { return i - 2; }); 136 assert(ret); 137 } 138 { 139 int a[] = {1, 2, 3, 4, 5}; 140 int b[] = {6, 10, 14, 18, 22}; 141 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5))); 142 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 5))); 143 auto ret = std::ranges::equal(range1, 144 range2, 145 {}, 146 [](int i) { return i * 4; }, 147 [](int i) { return i - 2; }); 148 assert(ret); 149 } 150 } 151 152 { // check that different sized ranges work 153 { 154 int a[] = {4, 3, 2, 1}; 155 int b[] = {4, 3, 2, 1, 5, 6, 7}; 156 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 4)), Iter2(b), Sent2(Iter2(b + 7))); 157 assert(!ret); 158 } 159 { 160 int a[] = {4, 3, 2, 1}; 161 int b[] = {4, 3, 2, 1, 5, 6, 7}; 162 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 4))); 163 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 7))); 164 auto ret = std::ranges::equal(range1, range2); 165 assert(!ret); 166 } 167 } 168 169 { // check that two ranges with the same size but different values are different 170 { 171 int a[] = {4, 6, 34, 76, 5}; 172 int b[] = {4, 6, 34, 67, 5}; 173 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 5)), Iter2(b), Sent2(Iter2(b + 5))); 174 assert(!ret); 175 } 176 { 177 int a[] = {4, 6, 34, 76, 5}; 178 int b[] = {4, 6, 34, 67, 5}; 179 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 5))); 180 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 5))); 181 auto ret = std::ranges::equal(range1, range2); 182 assert(!ret); 183 } 184 } 185 186 { // check that two empty ranges work 187 { 188 int a[] = {}; 189 int b[] = {}; 190 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a)), Iter2(b), Sent2(Iter2(b))); 191 assert(ret); 192 } 193 { 194 int a[] = {}; 195 int b[] = {}; 196 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a))); 197 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b))); 198 auto ret = std::ranges::equal(range1, range2); 199 assert(ret); 200 } 201 } 202 203 { // check that it works with the first range empty 204 { 205 int a[] = {}; 206 int b[] = {1, 2}; 207 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a)), Iter2(b), Sent2(Iter2(b + 2))); 208 assert(!ret); 209 } 210 { 211 int a[] = {}; 212 int b[] = {1, 2}; 213 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a))); 214 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b + 2))); 215 auto ret = std::ranges::equal(range1, range2); 216 assert(!ret); 217 } 218 } 219 220 { // check that it works with the second range empty 221 { 222 int a[] = {1, 2}; 223 int b[] = {}; 224 auto ret = std::ranges::equal(Iter1(a), Sent1(Iter1(a + 2)), Iter2(b), Sent2(Iter2(b))); 225 assert(!ret); 226 } 227 { 228 int a[] = {1, 2}; 229 int b[] = {}; 230 auto range1 = std::ranges::subrange(Iter1(a), Sent1(Iter1(a + 2))); 231 auto range2 = std::ranges::subrange(Iter2(b), Sent2(Iter2(b))); 232 auto ret = std::ranges::equal(range1, range2); 233 assert(!ret); 234 } 235 } 236 } 237 238 template<class Iter1, class Sent1 = Iter1> 239 constexpr void test_iterators2() { 240 test_iterators<Iter1, Sent1, cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>(); 241 test_iterators<Iter1, Sent1, cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>(); 242 test_iterators<Iter1, Sent1, forward_iterator<int*>>(); 243 test_iterators<Iter1, Sent1, bidirectional_iterator<int*>>(); 244 test_iterators<Iter1, Sent1, random_access_iterator<int*>>(); 245 test_iterators<Iter1, Sent1, contiguous_iterator<int*>>(); 246 test_iterators<Iter1, Sent1, int*>(); 247 test_iterators<Iter1, Sent1, const int*>(); 248 } 249 250 constexpr bool test() { 251 test_iterators2<cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>(); 252 test_iterators2<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>(); 253 test_iterators2<forward_iterator<int*>>(); 254 test_iterators2<bidirectional_iterator<int*>>(); 255 test_iterators2<random_access_iterator<int*>>(); 256 test_iterators2<contiguous_iterator<int*>>(); 257 test_iterators2<int*>(); 258 test_iterators2<const int*>(); 259 260 { // check that std::invoke is used 261 struct S { 262 constexpr S(int i_) : i(i_) {} 263 constexpr bool equal(int o) { return i == o; } 264 constexpr S& identity() { return *this; } 265 int i; 266 }; 267 { 268 S a[] = {7, 8, 9}; 269 S b[] = {7, 8, 9}; 270 auto ret = std::ranges::equal(a, a + 3, b, b + 3, &S::equal, &S::identity, &S::i); 271 assert(ret); 272 } 273 { 274 S a[] = {7, 8, 9}; 275 S b[] = {7, 8, 9}; 276 auto ret = std::ranges::equal(a, b, &S::equal, &S::identity, &S::i); 277 assert(ret); 278 } 279 } 280 281 { // check that the complexity requirements are met 282 { // different size 283 { 284 int a[] = {1, 2, 3}; 285 int b[] = {1, 2, 3, 4}; 286 int predCount = 0; 287 int projCount = 0; 288 auto pred = [&](int l, int r) { ++predCount; return l == r; }; 289 auto proj = [&](int i) { ++projCount; return i; }; 290 auto ret = std::ranges::equal(a, a + 3, b, b + 4, pred, proj, proj); 291 assert(!ret); 292 assert(predCount == 0); 293 assert(projCount == 0); 294 } 295 { 296 int a[] = {1, 2, 3}; 297 int b[] = {1, 2, 3, 4}; 298 int predCount = 0; 299 int projCount = 0; 300 auto pred = [&](int l, int r) { ++predCount; return l == r; }; 301 auto proj = [&](int i) { ++projCount; return i; }; 302 auto ret = std::ranges::equal(a, b, pred, proj, proj); 303 assert(!ret); 304 assert(predCount == 0); 305 assert(projCount == 0); 306 } 307 } 308 309 { // not a sized sentinel 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, sentinel_wrapper(a + 3), b, sentinel_wrapper(b + 4), pred, proj, proj); 318 assert(!ret); 319 assert(predCount <= 4); 320 assert(projCount <= 7); 321 } 322 { 323 int a[] = {1, 2, 3}; 324 int b[] = {1, 2, 3, 4}; 325 int predCount = 0; 326 int projCount = 0; 327 auto pred = [&](int l, int r) { ++predCount; return l == r; }; 328 auto proj = [&](int i) { ++projCount; return i; }; 329 auto range1 = std::ranges::subrange(a, sentinel_wrapper(a + 3)); 330 auto range2 = std::ranges::subrange(b, sentinel_wrapper(b + 4)); 331 auto ret = std::ranges::equal(range1, range2, pred, proj, proj); 332 assert(!ret); 333 assert(predCount <= 4); 334 assert(projCount <= 7); 335 } 336 } 337 338 { // same size 339 { 340 int a[] = {1, 2, 3}; 341 int b[] = {1, 2, 3}; 342 int predCount = 0; 343 int projCount = 0; 344 auto pred = [&](int l, int r) { ++predCount; return l == r; }; 345 auto proj = [&](int i) { ++projCount; return i; }; 346 auto ret = std::ranges::equal(a, a + 3, b, b + 3, pred, proj, proj); 347 assert(ret); 348 assert(predCount == 3); 349 assert(projCount == 6); 350 } 351 { 352 int a[] = {1, 2, 3}; 353 int b[] = {1, 2, 3}; 354 int predCount = 0; 355 int projCount = 0; 356 auto pred = [&](int l, int r) { ++predCount; return l == r; }; 357 auto proj = [&](int i) { ++projCount; return i; }; 358 auto ret = std::ranges::equal(a, b, pred, proj, proj); 359 assert(ret); 360 assert(predCount == 3); 361 assert(projCount == 6); 362 } 363 } 364 } 365 366 return true; 367 } 368 369 int main(int, char**) { 370 test(); 371 static_assert(test()); 372 373 return 0; 374 } 375