1885 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef SUPPORT_TEST_ITERATORS_H10#define SUPPORT_TEST_ITERATORS_H11 12#include <cassert>13#include <concepts>14#include <cstdint>15#include <iterator>16#include <ranges>17#include <stdexcept>18#include <type_traits>19#include <utility>20 21#include "double_move_tracker.h"22#include "test_macros.h"23#include "type_algorithms.h"24 25 26// This iterator meets C++20's Cpp17OutputIterator requirements, as described27// in Table 90 ([output.iterators]).28template <class It>29class cpp17_output_iterator30{31 It it_;32 support::double_move_tracker tracker_;33 34 template <class U> friend class cpp17_output_iterator;35public:36 typedef std::output_iterator_tag iterator_category;37 typedef void value_type;38 typedef typename std::iterator_traits<It>::difference_type difference_type;39 typedef It pointer;40 typedef typename std::iterator_traits<It>::reference reference;41 42 TEST_CONSTEXPR explicit cpp17_output_iterator(It it) : it_(std::move(it)) {}43 44 template <class U>45 TEST_CONSTEXPR cpp17_output_iterator(const cpp17_output_iterator<U>& u) : it_(u.it_), tracker_(u.tracker_) {}46 47 template <class U, class = typename std::enable_if<std::is_default_constructible<U>::value>::type>48 TEST_CONSTEXPR_CXX14 cpp17_output_iterator(cpp17_output_iterator<U>&& u)49 : it_(std::move(u.it_)), tracker_(std::move(u.tracker_)) {50 u.it_ = U();51 }52 53 TEST_CONSTEXPR reference operator*() const {return *it_;}54 55 TEST_CONSTEXPR_CXX14 cpp17_output_iterator& operator++() {++it_; return *this;}56 TEST_CONSTEXPR_CXX14 cpp17_output_iterator operator++(int) {return cpp17_output_iterator(it_++);}57 58 friend TEST_CONSTEXPR It base(const cpp17_output_iterator& i) { return i.it_; }59 60 template <class T>61 void operator,(T const &) = delete;62 63 template <class T>64 friend void operator,(const T&, const cpp17_output_iterator&) = delete;65};66#if TEST_STD_VER > 1467template <class It>68cpp17_output_iterator(It) -> cpp17_output_iterator<It>;69#endif70 71#if TEST_STD_VER > 1772 static_assert(std::output_iterator<cpp17_output_iterator<int*>, int>);73#endif74 75// This iterator meets C++20's Cpp17InputIterator requirements, as described76// in Table 89 ([input.iterators]).77template <class It, class ItTraits = It>78class cpp17_input_iterator79{80 typedef std::iterator_traits<ItTraits> Traits;81 It it_;82 support::double_move_tracker tracker_;83 84 template <class U, class T> friend class cpp17_input_iterator;85public:86 typedef std::input_iterator_tag iterator_category;87 typedef typename Traits::value_type value_type;88 typedef typename Traits::difference_type difference_type;89 typedef It pointer;90 typedef typename Traits::reference reference;91 92 TEST_CONSTEXPR explicit cpp17_input_iterator(It it) : it_(it) {}93 94 template <class U, class T>95 TEST_CONSTEXPR cpp17_input_iterator(const cpp17_input_iterator<U, T>& u) : it_(u.it_), tracker_(u.tracker_) {}96 97 template <class U, class T, class = typename std::enable_if<std::is_default_constructible<U>::value>::type>98 TEST_CONSTEXPR_CXX14 cpp17_input_iterator(cpp17_input_iterator<U, T>&& u)99 : it_(std::move(u.it_)), tracker_(std::move(u.tracker_)) {100 u.it_ = U();101 }102 103 TEST_CONSTEXPR reference operator*() const {return *it_;}104 105 TEST_CONSTEXPR_CXX14 cpp17_input_iterator& operator++() {++it_; return *this;}106 TEST_CONSTEXPR_CXX14 cpp17_input_iterator operator++(int) {return cpp17_input_iterator(it_++);}107 108 friend TEST_CONSTEXPR bool operator==(const cpp17_input_iterator& x, const cpp17_input_iterator& y) {return x.it_ == y.it_;}109 friend TEST_CONSTEXPR bool operator!=(const cpp17_input_iterator& x, const cpp17_input_iterator& y) {return x.it_ != y.it_;}110 111 friend TEST_CONSTEXPR It base(const cpp17_input_iterator& i) { return i.it_; }112 113 template <class T>114 void operator,(T const &) = delete;115 116 template <class T>117 friend void operator,(const T&, const cpp17_input_iterator&) = delete;118};119#if TEST_STD_VER > 14120template <class It>121cpp17_input_iterator(It) -> cpp17_input_iterator<It>;122#endif123 124#if TEST_STD_VER > 17125 static_assert(std::input_iterator<cpp17_input_iterator<int*>>);126#endif127 128template <class It>129class forward_iterator130{131 It it_;132 support::double_move_tracker tracker_;133 134 template <class U> friend class forward_iterator;135public:136 typedef std::forward_iterator_tag iterator_category;137 typedef typename std::iterator_traits<It>::value_type value_type;138 typedef typename std::iterator_traits<It>::difference_type difference_type;139 typedef It pointer;140 typedef typename std::iterator_traits<It>::reference reference;141 142 TEST_CONSTEXPR forward_iterator() : it_() {}143 TEST_CONSTEXPR explicit forward_iterator(It it) : it_(it) {}144 145 template <class U>146 TEST_CONSTEXPR forward_iterator(const forward_iterator<U>& u) : it_(u.it_), tracker_(u.tracker_) {}147 148 template <class U, class = typename std::enable_if<std::is_default_constructible<U>::value>::type>149 TEST_CONSTEXPR_CXX14 forward_iterator(forward_iterator<U>&& other)150 : it_(std::move(other.it_)), tracker_(std::move(other.tracker_)) {151 other.it_ = U();152 }153 154 TEST_CONSTEXPR reference operator*() const {return *it_;}155 156 TEST_CONSTEXPR_CXX14 forward_iterator& operator++() {++it_; return *this;}157 TEST_CONSTEXPR_CXX14 forward_iterator operator++(int) {return forward_iterator(it_++);}158 159 friend TEST_CONSTEXPR bool operator==(const forward_iterator& x, const forward_iterator& y) {return x.it_ == y.it_;}160 friend TEST_CONSTEXPR bool operator!=(const forward_iterator& x, const forward_iterator& y) {return x.it_ != y.it_;}161 162 friend TEST_CONSTEXPR It base(const forward_iterator& i) { return i.it_; }163 164 template <class T>165 void operator,(T const &) = delete;166 167 template <class T>168 friend void operator,(const T&, const forward_iterator&) = delete;169};170#if TEST_STD_VER > 14171template <class It>172forward_iterator(It) -> forward_iterator<It>;173#endif174 175template <class It>176class bidirectional_iterator177{178 It it_;179 support::double_move_tracker tracker_;180 181 template <class U> friend class bidirectional_iterator;182public:183 typedef std::bidirectional_iterator_tag iterator_category;184 typedef typename std::iterator_traits<It>::value_type value_type;185 typedef typename std::iterator_traits<It>::difference_type difference_type;186 typedef It pointer;187 typedef typename std::iterator_traits<It>::reference reference;188 189 TEST_CONSTEXPR bidirectional_iterator() : it_() {}190 TEST_CONSTEXPR explicit bidirectional_iterator(It it) : it_(it) {}191 192 template <class U>193 TEST_CONSTEXPR bidirectional_iterator(const bidirectional_iterator<U>& u) : it_(u.it_), tracker_(u.tracker_) {}194 195 template <class U, class = typename std::enable_if<std::is_default_constructible<U>::value>::type>196 TEST_CONSTEXPR_CXX14 bidirectional_iterator(bidirectional_iterator<U>&& u)197 : it_(std::move(u.it_)), tracker_(std::move(u.tracker_)) {198 u.it_ = U();199 }200 201 TEST_CONSTEXPR reference operator*() const {return *it_;}202 203 TEST_CONSTEXPR_CXX14 bidirectional_iterator& operator++() {++it_; return *this;}204 TEST_CONSTEXPR_CXX14 bidirectional_iterator& operator--() {--it_; return *this;}205 TEST_CONSTEXPR_CXX14 bidirectional_iterator operator++(int) {return bidirectional_iterator(it_++);}206 TEST_CONSTEXPR_CXX14 bidirectional_iterator operator--(int) {return bidirectional_iterator(it_--);}207 208 friend TEST_CONSTEXPR bool operator==(const bidirectional_iterator& x, const bidirectional_iterator& y) {return x.it_ == y.it_;}209 friend TEST_CONSTEXPR bool operator!=(const bidirectional_iterator& x, const bidirectional_iterator& y) {return x.it_ != y.it_;}210 211 friend TEST_CONSTEXPR It base(const bidirectional_iterator& i) { return i.it_; }212 213 template <class T>214 void operator,(T const &) = delete;215 216 template <class T>217 friend void operator,(const T&, const bidirectional_iterator&) = delete;218};219#if TEST_STD_VER > 14220template <class It>221bidirectional_iterator(It) -> bidirectional_iterator<It>;222#endif223 224template <class It>225class random_access_iterator226{227 It it_;228 support::double_move_tracker tracker_;229 230 template <class U> friend class random_access_iterator;231public:232 typedef std::random_access_iterator_tag iterator_category;233 typedef typename std::iterator_traits<It>::value_type value_type;234 typedef typename std::iterator_traits<It>::difference_type difference_type;235 typedef It pointer;236 typedef typename std::iterator_traits<It>::reference reference;237 238 TEST_CONSTEXPR random_access_iterator() : it_() {}239 TEST_CONSTEXPR explicit random_access_iterator(It it) : it_(it) {}240 241 template <class U>242 TEST_CONSTEXPR random_access_iterator(const random_access_iterator<U>& u) : it_(u.it_), tracker_(u.tracker_) {}243 244 template <class U, class = typename std::enable_if<std::is_default_constructible<U>::value>::type>245 TEST_CONSTEXPR_CXX14 random_access_iterator(random_access_iterator<U>&& u)246 : it_(std::move(u.it_)), tracker_(std::move(u.tracker_)) {247 u.it_ = U();248 }249 250 TEST_CONSTEXPR_CXX14 reference operator*() const {return *it_;}251 TEST_CONSTEXPR_CXX14 reference operator[](difference_type n) const {return it_[n];}252 253 TEST_CONSTEXPR_CXX14 random_access_iterator& operator++() {++it_; return *this;}254 TEST_CONSTEXPR_CXX14 random_access_iterator& operator--() {--it_; return *this;}255 TEST_CONSTEXPR_CXX14 random_access_iterator operator++(int) {return random_access_iterator(it_++);}256 TEST_CONSTEXPR_CXX14 random_access_iterator operator--(int) {return random_access_iterator(it_--);}257 258 TEST_CONSTEXPR_CXX14 random_access_iterator& operator+=(difference_type n) {it_ += n; return *this;}259 TEST_CONSTEXPR_CXX14 random_access_iterator& operator-=(difference_type n) {it_ -= n; return *this;}260 friend TEST_CONSTEXPR_CXX14 random_access_iterator operator+(random_access_iterator x, difference_type n) {x += n; return x;}261 friend TEST_CONSTEXPR_CXX14 random_access_iterator operator+(difference_type n, random_access_iterator x) {x += n; return x;}262 friend TEST_CONSTEXPR_CXX14 random_access_iterator operator-(random_access_iterator x, difference_type n) {x -= n; return x;}263 friend TEST_CONSTEXPR difference_type operator-(random_access_iterator x, random_access_iterator y) {return x.it_ - y.it_;}264 265 friend TEST_CONSTEXPR bool operator==(const random_access_iterator& x, const random_access_iterator& y) {return x.it_ == y.it_;}266 friend TEST_CONSTEXPR bool operator!=(const random_access_iterator& x, const random_access_iterator& y) {return x.it_ != y.it_;}267 friend TEST_CONSTEXPR bool operator< (const random_access_iterator& x, const random_access_iterator& y) {return x.it_ < y.it_;}268 friend TEST_CONSTEXPR bool operator<=(const random_access_iterator& x, const random_access_iterator& y) {return x.it_ <= y.it_;}269 friend TEST_CONSTEXPR bool operator> (const random_access_iterator& x, const random_access_iterator& y) {return x.it_ > y.it_;}270 friend TEST_CONSTEXPR bool operator>=(const random_access_iterator& x, const random_access_iterator& y) {return x.it_ >= y.it_;}271 272 friend TEST_CONSTEXPR It base(const random_access_iterator& i) { return i.it_; }273 274 template <class T>275 void operator,(T const &) = delete;276 277 template <class T>278 friend void operator,(const T&, const random_access_iterator&) = delete;279};280#if TEST_STD_VER > 14281template <class It>282random_access_iterator(It) -> random_access_iterator<It>;283#endif284 285// Since C++20, a container iterator type that is random access is also required to support three-way comparison.286// See C++20 [tab:container.req], C++23 [container.reqmts]/39 - /41.287template <class It>288class three_way_random_access_iterator {289 It it_;290 support::double_move_tracker tracker_;291 292 template <class U>293 friend class three_way_random_access_iterator;294 295public:296 typedef std::random_access_iterator_tag iterator_category;297 typedef typename std::iterator_traits<It>::value_type value_type;298 typedef typename std::iterator_traits<It>::difference_type difference_type;299 typedef It pointer;300 typedef typename std::iterator_traits<It>::reference reference;301 302 TEST_CONSTEXPR three_way_random_access_iterator() : it_() {}303 TEST_CONSTEXPR explicit three_way_random_access_iterator(It it) : it_(it) {}304 305 template <class U>306 TEST_CONSTEXPR three_way_random_access_iterator(const three_way_random_access_iterator<U>& u)307 : it_(u.it_), tracker_(u.tracker_) {}308 309 template <class U, class = typename std::enable_if<std::is_default_constructible<U>::value>::type>310 TEST_CONSTEXPR_CXX14 three_way_random_access_iterator(three_way_random_access_iterator<U>&& u)311 : it_(std::move(u.it_)), tracker_(std::move(u.tracker_)) {312 u.it_ = U();313 }314 315 TEST_CONSTEXPR_CXX14 reference operator*() const { return *it_; }316 TEST_CONSTEXPR_CXX14 reference operator[](difference_type n) const { return it_[n]; }317 318 TEST_CONSTEXPR_CXX14 three_way_random_access_iterator& operator++() {319 ++it_;320 return *this;321 }322 TEST_CONSTEXPR_CXX14 three_way_random_access_iterator& operator--() {323 --it_;324 return *this;325 }326 TEST_CONSTEXPR_CXX14 three_way_random_access_iterator operator++(int) {327 return three_way_random_access_iterator(it_++);328 }329 TEST_CONSTEXPR_CXX14 three_way_random_access_iterator operator--(int) {330 return three_way_random_access_iterator(it_--);331 }332 333 TEST_CONSTEXPR_CXX14 three_way_random_access_iterator& operator+=(difference_type n) {334 it_ += n;335 return *this;336 }337 TEST_CONSTEXPR_CXX14 three_way_random_access_iterator& operator-=(difference_type n) {338 it_ -= n;339 return *this;340 }341 friend TEST_CONSTEXPR_CXX14 three_way_random_access_iterator342 operator+(three_way_random_access_iterator x, difference_type n) {343 x += n;344 return x;345 }346 friend TEST_CONSTEXPR_CXX14 three_way_random_access_iterator347 operator+(difference_type n, three_way_random_access_iterator x) {348 x += n;349 return x;350 }351 friend TEST_CONSTEXPR_CXX14 three_way_random_access_iterator352 operator-(three_way_random_access_iterator x, difference_type n) {353 x -= n;354 return x;355 }356 friend TEST_CONSTEXPR difference_type357 operator-(three_way_random_access_iterator x, three_way_random_access_iterator y) {358 return x.it_ - y.it_;359 }360 361 friend TEST_CONSTEXPR bool362 operator==(const three_way_random_access_iterator& x, const three_way_random_access_iterator& y) {363 return x.it_ == y.it_;364 }365#if TEST_STD_VER < 20366 friend TEST_CONSTEXPR bool367 operator!=(const three_way_random_access_iterator& x, const three_way_random_access_iterator& y) {368 return x.it_ != y.it_;369 }370#endif371 friend TEST_CONSTEXPR bool372 operator<(const three_way_random_access_iterator& x, const three_way_random_access_iterator& y) {373 return x.it_ < y.it_;374 }375 friend TEST_CONSTEXPR bool376 operator<=(const three_way_random_access_iterator& x, const three_way_random_access_iterator& y) {377 return x.it_ <= y.it_;378 }379 friend TEST_CONSTEXPR bool380 operator>(const three_way_random_access_iterator& x, const three_way_random_access_iterator& y) {381 return x.it_ > y.it_;382 }383 friend TEST_CONSTEXPR bool384 operator>=(const three_way_random_access_iterator& x, const three_way_random_access_iterator& y) {385 return x.it_ >= y.it_;386 }387#if TEST_STD_VER >= 20388 friend constexpr std::strong_ordering389 operator<=>(const three_way_random_access_iterator& x, const three_way_random_access_iterator& y) {390 if constexpr (std::three_way_comparable<It>) {391 return x.it_ <=> y.it_;392 } else {393 if (x.it_ < y.it_) {394 return std::strong_ordering::less;395 } else if (y.it_ < x.it_) {396 return std::strong_ordering::greater;397 } else {398 return std::strong_ordering::equal;399 }400 }401 }402#endif403 404 friend TEST_CONSTEXPR It base(const three_way_random_access_iterator& i) { return i.it_; }405 406 template <class T>407 void operator,(T const&) = delete;408 409 template <class T>410 friend void operator,(const T&, const three_way_random_access_iterator&) = delete;411};412#if TEST_STD_VER > 14413template <class It>414three_way_random_access_iterator(It) -> three_way_random_access_iterator<It>;415#endif416 417#if TEST_STD_VER > 17418 419template <std::random_access_iterator It>420class cpp20_random_access_iterator {421 It it_;422 support::double_move_tracker tracker_;423 424 template <std::random_access_iterator>425 friend class cpp20_random_access_iterator;426 427public:428 using iterator_category = std::input_iterator_tag;429 using iterator_concept = std::random_access_iterator_tag;430 using value_type = typename std::iterator_traits<It>::value_type;431 using difference_type = typename std::iterator_traits<It>::difference_type;432 433 constexpr cpp20_random_access_iterator() : it_() {}434 constexpr explicit cpp20_random_access_iterator(It it) : it_(it) {}435 436 template <class U>437 constexpr cpp20_random_access_iterator(const cpp20_random_access_iterator<U>& u) : it_(u.it_), tracker_(u.tracker_) {}438 439 template <class U>440 constexpr cpp20_random_access_iterator(cpp20_random_access_iterator<U>&& u)441 : it_(std::move(u.it_)), tracker_(std::move(u.tracker_)) {442 u.it_ = U();443 }444 445 constexpr decltype(auto) operator*() const { return *it_; }446 constexpr decltype(auto) operator[](difference_type n) const { return it_[n]; }447 448 constexpr cpp20_random_access_iterator& operator++() {449 ++it_;450 return *this;451 }452 constexpr cpp20_random_access_iterator& operator--() {453 --it_;454 return *this;455 }456 constexpr cpp20_random_access_iterator operator++(int) { return cpp20_random_access_iterator(it_++); }457 constexpr cpp20_random_access_iterator operator--(int) { return cpp20_random_access_iterator(it_--); }458 459 constexpr cpp20_random_access_iterator& operator+=(difference_type n) {460 it_ += n;461 return *this;462 }463 constexpr cpp20_random_access_iterator& operator-=(difference_type n) {464 it_ -= n;465 return *this;466 }467 friend constexpr cpp20_random_access_iterator operator+(cpp20_random_access_iterator x, difference_type n) {468 x += n;469 return x;470 }471 friend constexpr cpp20_random_access_iterator operator+(difference_type n, cpp20_random_access_iterator x) {472 x += n;473 return x;474 }475 friend constexpr cpp20_random_access_iterator operator-(cpp20_random_access_iterator x, difference_type n) {476 x -= n;477 return x;478 }479 friend constexpr difference_type operator-(cpp20_random_access_iterator x, cpp20_random_access_iterator y) {480 return x.it_ - y.it_;481 }482 483 friend constexpr bool operator==(const cpp20_random_access_iterator& x, const cpp20_random_access_iterator& y) {484 return x.it_ == y.it_;485 }486 friend constexpr bool operator!=(const cpp20_random_access_iterator& x, const cpp20_random_access_iterator& y) {487 return x.it_ != y.it_;488 }489 friend constexpr bool operator<(const cpp20_random_access_iterator& x, const cpp20_random_access_iterator& y) {490 return x.it_ < y.it_;491 }492 friend constexpr bool operator<=(const cpp20_random_access_iterator& x, const cpp20_random_access_iterator& y) {493 return x.it_ <= y.it_;494 }495 friend constexpr bool operator>(const cpp20_random_access_iterator& x, const cpp20_random_access_iterator& y) {496 return x.it_ > y.it_;497 }498 friend constexpr bool operator>=(const cpp20_random_access_iterator& x, const cpp20_random_access_iterator& y) {499 return x.it_ >= y.it_;500 }501 502 friend constexpr It base(const cpp20_random_access_iterator& i) { return i.it_; }503 504 template <class T>505 void operator,(T const&) = delete;506 507 template <class T>508 friend void operator,(const T&, const cpp20_random_access_iterator&) = delete;509};510template <class It>511cpp20_random_access_iterator(It) -> cpp20_random_access_iterator<It>;512 513static_assert(std::random_access_iterator<cpp20_random_access_iterator<int*>>);514 515template <std::contiguous_iterator It>516class contiguous_iterator {517 It it_;518 support::double_move_tracker tracker_;519 520 template <std::contiguous_iterator U>521 friend class contiguous_iterator;522 523public:524 using iterator_category = std::contiguous_iterator_tag;525 using value_type = typename std::iterator_traits<It>::value_type;526 using difference_type = typename std::iterator_traits<It>::difference_type;527 using pointer = typename std::iterator_traits<It>::pointer;528 using reference = typename std::iterator_traits<It>::reference;529 using element_type = value_type;530 531 constexpr It base() const { return it_; }532 533 constexpr contiguous_iterator() : it_() {}534 constexpr explicit contiguous_iterator(It it) : it_(it) {}535 536 template <class U>537 constexpr contiguous_iterator(const contiguous_iterator<U>& u) : it_(u.it_), tracker_(u.tracker_) {}538 539 template <class U, class = typename std::enable_if<std::is_default_constructible<U>::value>::type>540 constexpr contiguous_iterator(contiguous_iterator<U>&& u) : it_(std::move(u.it_)), tracker_(std::move(u.tracker_)) {541 u.it_ = U();542 }543 544 constexpr reference operator*() const { return *it_; }545 constexpr pointer operator->() const { return it_; }546 constexpr reference operator[](difference_type n) const { return it_[n]; }547 548 constexpr contiguous_iterator& operator++() {549 ++it_;550 return *this;551 }552 constexpr contiguous_iterator& operator--() {553 --it_;554 return *this;555 }556 constexpr contiguous_iterator operator++(int) { return contiguous_iterator(it_++); }557 constexpr contiguous_iterator operator--(int) { return contiguous_iterator(it_--); }558 559 constexpr contiguous_iterator& operator+=(difference_type n) {560 it_ += n;561 return *this;562 }563 constexpr contiguous_iterator& operator-=(difference_type n) {564 it_ -= n;565 return *this;566 }567 friend constexpr contiguous_iterator operator+(contiguous_iterator x, difference_type n) {568 x += n;569 return x;570 }571 friend constexpr contiguous_iterator operator+(difference_type n, contiguous_iterator x) {572 x += n;573 return x;574 }575 friend constexpr contiguous_iterator operator-(contiguous_iterator x, difference_type n) {576 x -= n;577 return x;578 }579 friend constexpr difference_type operator-(contiguous_iterator x, contiguous_iterator y) { return x.it_ - y.it_; }580 581 friend constexpr bool operator==(const contiguous_iterator& x, const contiguous_iterator& y) {582 return x.it_ == y.it_;583 }584 friend constexpr bool operator!=(const contiguous_iterator& x, const contiguous_iterator& y) {585 return x.it_ != y.it_;586 }587 friend constexpr bool operator<(const contiguous_iterator& x, const contiguous_iterator& y) { return x.it_ < y.it_; }588 friend constexpr bool operator<=(const contiguous_iterator& x, const contiguous_iterator& y) {589 return x.it_ <= y.it_;590 }591 friend constexpr bool operator>(const contiguous_iterator& x, const contiguous_iterator& y) { return x.it_ > y.it_; }592 friend constexpr bool operator>=(const contiguous_iterator& x, const contiguous_iterator& y) {593 return x.it_ >= y.it_;594 }595 596 // Note no operator<=>, use three_way_contiguous_iterator for testing operator<=>597 598 friend constexpr It base(const contiguous_iterator& i) { return i.it_; }599 600 template <class T>601 void operator,(T const&) = delete;602 603 template <class T>604 friend void operator,(const T&, const contiguous_iterator&) = delete;605};606template <class It>607contiguous_iterator(It) -> contiguous_iterator<It>;608 609template <class It>610class three_way_contiguous_iterator611{612 static_assert(std::is_pointer_v<It>, "Things probably break in this case");613 614 It it_;615 support::double_move_tracker tracker_;616 617 template <class U> friend class three_way_contiguous_iterator;618public:619 typedef std::contiguous_iterator_tag iterator_category;620 typedef typename std::iterator_traits<It>::value_type value_type;621 typedef typename std::iterator_traits<It>::difference_type difference_type;622 typedef It pointer;623 typedef typename std::iterator_traits<It>::reference reference;624 typedef typename std::remove_pointer<It>::type element_type;625 626 constexpr It base() const {return it_;}627 628 constexpr three_way_contiguous_iterator() : it_() {}629 constexpr explicit three_way_contiguous_iterator(It it) : it_(it) {}630 631 template <class U>632 constexpr three_way_contiguous_iterator(const three_way_contiguous_iterator<U>& u)633 : it_(u.it_), tracker_(u.tracker_) {}634 635 template <class U, class = typename std::enable_if<std::is_default_constructible<U>::value>::type>636 constexpr three_way_contiguous_iterator(three_way_contiguous_iterator<U>&& u)637 : it_(std::move(u.it_)), tracker_(std::move(u.tracker_)) {638 u.it_ = U();639 }640 641 constexpr reference operator*() const {return *it_;}642 constexpr pointer operator->() const {return it_;}643 constexpr reference operator[](difference_type n) const {return it_[n];}644 645 constexpr three_way_contiguous_iterator& operator++() {++it_; return *this;}646 constexpr three_way_contiguous_iterator& operator--() {--it_; return *this;}647 constexpr three_way_contiguous_iterator operator++(int) {return three_way_contiguous_iterator(it_++);}648 constexpr three_way_contiguous_iterator operator--(int) {return three_way_contiguous_iterator(it_--);}649 650 constexpr three_way_contiguous_iterator& operator+=(difference_type n) {it_ += n; return *this;}651 constexpr three_way_contiguous_iterator& operator-=(difference_type n) {it_ -= n; return *this;}652 friend constexpr three_way_contiguous_iterator operator+(three_way_contiguous_iterator x, difference_type n) {x += n; return x;}653 friend constexpr three_way_contiguous_iterator operator+(difference_type n, three_way_contiguous_iterator x) {x += n; return x;}654 friend constexpr three_way_contiguous_iterator operator-(three_way_contiguous_iterator x, difference_type n) {x -= n; return x;}655 friend constexpr difference_type operator-(three_way_contiguous_iterator x, three_way_contiguous_iterator y) {return x.it_ - y.it_;}656 657 friend constexpr auto operator<=>(const three_way_contiguous_iterator& x, const three_way_contiguous_iterator& y) {return x.it_ <=> y.it_;}658 friend constexpr bool operator==(const three_way_contiguous_iterator& x, const three_way_contiguous_iterator& y) {return x.it_ == y.it_;}659 660 template <class T>661 void operator,(T const &) = delete;662 663 template <class T>664 friend void operator,(const T&, const three_way_contiguous_iterator&) = delete;665};666template <class It>667three_way_contiguous_iterator(It) -> three_way_contiguous_iterator<It>;668#endif // TEST_STD_VER > 17669 670template <class Iter> // ADL base() for everything else (including pointers)671TEST_CONSTEXPR Iter base(Iter i) { return i; }672 673template <typename T>674struct ThrowingIterator {675 typedef std::bidirectional_iterator_tag iterator_category;676 typedef std::ptrdiff_t difference_type;677 typedef const T value_type;678 typedef const T * pointer;679 typedef const T & reference;680 681 enum ThrowingAction { TAIncrement, TADecrement, TADereference, TAAssignment, TAComparison };682 683 TEST_CONSTEXPR ThrowingIterator()684 : begin_(nullptr), end_(nullptr), current_(nullptr), action_(TADereference), index_(0) {}685 TEST_CONSTEXPR explicit ThrowingIterator(const T* first, const T* last, int index = 0,686 ThrowingAction action = TADereference)687 : begin_(first), end_(last), current_(first), action_(action), index_(index) {}688 TEST_CONSTEXPR ThrowingIterator(const ThrowingIterator &rhs)689 : begin_(rhs.begin_), end_(rhs.end_), current_(rhs.current_), action_(rhs.action_), index_(rhs.index_) {}690 691 TEST_CONSTEXPR_CXX14 ThrowingIterator& operator=(const ThrowingIterator& rhs) {692 if (action_ == TAAssignment && --index_ < 0) {693#ifndef TEST_HAS_NO_EXCEPTIONS694 throw std::runtime_error("throw from iterator assignment");695#else696 assert(false);697#endif698 }699 begin_ = rhs.begin_;700 end_ = rhs.end_;701 current_ = rhs.current_;702 action_ = rhs.action_;703 index_ = rhs.index_;704 return *this;705 }706 707 TEST_CONSTEXPR_CXX14 reference operator*() const {708 if (action_ == TADereference && --index_ < 0) {709#ifndef TEST_HAS_NO_EXCEPTIONS710 throw std::runtime_error("throw from iterator dereference");711#else712 assert(false);713#endif714 }715 return *current_;716 }717 718 TEST_CONSTEXPR_CXX14 ThrowingIterator& operator++() {719 if (action_ == TAIncrement && --index_ < 0) {720#ifndef TEST_HAS_NO_EXCEPTIONS721 throw std::runtime_error("throw from iterator increment");722#else723 assert(false);724#endif725 }726 ++current_;727 return *this;728 }729 730 TEST_CONSTEXPR_CXX14 ThrowingIterator operator++(int) {731 ThrowingIterator temp = *this;732 ++(*this);733 return temp;734 }735 736 TEST_CONSTEXPR_CXX14 ThrowingIterator& operator--() {737 if (action_ == TADecrement && --index_ < 0) {738#ifndef TEST_HAS_NO_EXCEPTIONS739 throw std::runtime_error("throw from iterator decrement");740#else741 assert(false);742#endif743 }744 --current_;745 return *this;746 }747 748 TEST_CONSTEXPR_CXX14 ThrowingIterator operator--(int) {749 ThrowingIterator temp = *this;750 --(*this);751 return temp;752 }753 754 TEST_CONSTEXPR_CXX14 friend bool operator==(const ThrowingIterator& a, const ThrowingIterator& b) {755 if (a.action_ == TAComparison && --a.index_ < 0) {756#ifndef TEST_HAS_NO_EXCEPTIONS757 throw std::runtime_error("throw from iterator comparison");758#else759 assert(false);760#endif761 }762 bool atEndL = a.current_ == a.end_;763 bool atEndR = b.current_ == b.end_;764 if (atEndL != atEndR) return false; // one is at the end (or empty), the other is not.765 if (atEndL) return true; // both are at the end (or empty)766 return a.current_ == b.current_;767 }768 769 TEST_CONSTEXPR friend bool operator!=(const ThrowingIterator& a, const ThrowingIterator& b) {770 return !(a == b);771 }772 773 template <class T2>774 void operator,(T2 const &) = delete;775 776 template <class T2>777 friend void operator,(const T2&, const ThrowingIterator&) = delete;778 779 private:780 const T* begin_;781 const T* end_;782 const T* current_;783 ThrowingAction action_;784 mutable int index_;785};786 787template <typename T>788struct NonThrowingIterator {789 typedef std::bidirectional_iterator_tag iterator_category;790 typedef std::ptrdiff_t difference_type;791 typedef const T value_type;792 typedef const T * pointer;793 typedef const T & reference;794 795 NonThrowingIterator()796 : begin_(nullptr), end_(nullptr), current_(nullptr) {}797 explicit NonThrowingIterator(const T *first, const T *last)798 : begin_(first), end_(last), current_(first) {}799 NonThrowingIterator(const NonThrowingIterator& rhs)800 : begin_(rhs.begin_), end_(rhs.end_), current_(rhs.current_) {}801 802 NonThrowingIterator& operator=(const NonThrowingIterator& rhs) TEST_NOEXCEPT {803 begin_ = rhs.begin_;804 end_ = rhs.end_;805 current_ = rhs.current_;806 return *this;807 }808 809 reference operator*() const TEST_NOEXCEPT {810 return *current_;811 }812 813 NonThrowingIterator& operator++() TEST_NOEXCEPT {814 ++current_;815 return *this;816 }817 818 NonThrowingIterator operator++(int) TEST_NOEXCEPT {819 NonThrowingIterator temp = *this;820 ++(*this);821 return temp;822 }823 824 NonThrowingIterator & operator--() TEST_NOEXCEPT {825 --current_;826 return *this;827 }828 829 NonThrowingIterator operator--(int) TEST_NOEXCEPT {830 NonThrowingIterator temp = *this;831 --(*this);832 return temp;833 }834 835 friend bool operator==(const NonThrowingIterator& a, const NonThrowingIterator& b) TEST_NOEXCEPT {836 bool atEndL = a.current_ == a.end_;837 bool atEndR = b.current_ == b.end_;838 if (atEndL != atEndR) return false; // one is at the end (or empty), the other is not.839 if (atEndL) return true; // both are at the end (or empty)840 return a.current_ == b.current_;841 }842 843 friend bool operator!=(const NonThrowingIterator& a, const NonThrowingIterator& b) TEST_NOEXCEPT {844 return !(a == b);845 }846 847 template <class T2>848 void operator,(T2 const &) = delete;849 850 template <class T2>851 friend void operator,(const T2&, const NonThrowingIterator&) = delete;852 853 private:854 const T *begin_;855 const T *end_;856 const T *current_;857};858 859#if TEST_STD_VER > 17860 861template <class It>862class cpp20_input_iterator863{864 It it_;865 support::double_move_tracker tracker_;866 867public:868 using value_type = std::iter_value_t<It>;869 using difference_type = std::iter_difference_t<It>;870 using iterator_concept = std::input_iterator_tag;871 872 constexpr explicit cpp20_input_iterator(It it) : it_(it) {}873 cpp20_input_iterator(cpp20_input_iterator&&) = default;874 cpp20_input_iterator& operator=(cpp20_input_iterator&&) = default;875 constexpr decltype(auto) operator*() const { return *it_; }876 constexpr cpp20_input_iterator& operator++() { ++it_; return *this; }877 constexpr void operator++(int) { ++it_; }878 879 friend constexpr It base(const cpp20_input_iterator& i) { return i.it_; }880 881 template <class T>882 void operator,(T const &) = delete;883 884 template <class T>885 friend void operator,(const T&, const cpp20_input_iterator&) = delete;886};887template <class It>888cpp20_input_iterator(It) -> cpp20_input_iterator<It>;889 890static_assert(std::input_iterator<cpp20_input_iterator<int*>>);891 892template<std::input_or_output_iterator>893struct iter_value_or_void { using type = void; };894 895template<std::input_iterator I>896struct iter_value_or_void<I> {897 using type = std::iter_value_t<I>;898};899 900template <class It>901class cpp20_output_iterator {902 It it_;903 support::double_move_tracker tracker_;904 905public:906 using difference_type = std::iter_difference_t<It>;907 908 constexpr explicit cpp20_output_iterator(It it) : it_(it) {}909 cpp20_output_iterator(cpp20_output_iterator&&) = default;910 cpp20_output_iterator& operator=(cpp20_output_iterator&&) = default;911 912 constexpr decltype(auto) operator*() const { return *it_; }913 constexpr cpp20_output_iterator& operator++() {914 ++it_;915 return *this;916 }917 constexpr cpp20_output_iterator operator++(int) { return cpp20_output_iterator(it_++); }918 919 friend constexpr It base(const cpp20_output_iterator& i) { return i.it_; }920 921 template <class T>922 void operator,(T const&) = delete;923 924 template <class T>925 friend void operator,(const T&, const cpp20_output_iterator&) = delete;926};927template <class It>928cpp20_output_iterator(It) -> cpp20_output_iterator<It>;929 930static_assert(std::output_iterator<cpp20_output_iterator<int*>, int>);931 932# if TEST_STD_VER >= 20933 934// An `input_iterator` that can be used in a `std::ranges::common_range`935template <class Base>936struct common_input_iterator {937 Base it_;938 939 using value_type = std::iter_value_t<Base>;940 using difference_type = std::intptr_t;941 using iterator_concept = std::input_iterator_tag;942 943 constexpr common_input_iterator() = default;944 constexpr explicit common_input_iterator(Base it) : it_(it) {}945 946 constexpr common_input_iterator& operator++() {947 ++it_;948 return *this;949 }950 constexpr void operator++(int) { ++it_; }951 952 constexpr decltype(auto) operator*() const { return *it_; }953 954 friend constexpr bool operator==(common_input_iterator const&, common_input_iterator const&) = default;955};956 957# endif // TEST_STD_VER >= 20958 959struct IteratorOpCounts {960 std::size_t increments = 0; ///< Number of times the iterator moved forward (++it, it++, it+=positive, it-=negative).961 std::size_t decrements = 0; ///< Number of times the iterator moved backward (--it, it--, it-=positive, it+=negative).962 std::size_t zero_moves = 0; ///< Number of times a call was made to move the iterator by 0 positions (it+=0, it-=0).963 std::size_t equal_cmps = 0; ///< Total number of calls to op== or op!=. If compared against a sentinel object, that964 /// sentinel object must call the `record_equality_comparison` function so that the965 /// comparison is counted correctly.966};967 968// Iterator adaptor that records its operation counts in a IteratorOpCounts969template <class It>970class operation_counting_iterator {971public:972 using value_type = typename iter_value_or_void<It>::type;973 using difference_type = std::iter_difference_t<It>;974 using iterator_concept =975 std::conditional_t<std::contiguous_iterator<It>, std::contiguous_iterator_tag,976 std::conditional_t<std::random_access_iterator<It>, std::random_access_iterator_tag,977 std::conditional_t<std::bidirectional_iterator<It>, std::bidirectional_iterator_tag,978 std::conditional_t<std::forward_iterator<It>, std::forward_iterator_tag,979 std::conditional_t<std::input_iterator<It>, std::input_iterator_tag,980 /* else */ std::output_iterator_tag981 >>>>>;982 using iterator_category = iterator_concept;983 984 operation_counting_iterator()985 requires std::default_initializable<It>986 = default;987 988 constexpr explicit operation_counting_iterator(It const& it, IteratorOpCounts* counts = nullptr)989 : base_(base(it)), counts_(counts) {}990 991 constexpr operation_counting_iterator(const operation_counting_iterator& o) { *this = o; }992 constexpr operation_counting_iterator(operation_counting_iterator&& o) { *this = o; }993 994 constexpr operation_counting_iterator& operator=(const operation_counting_iterator& o) = default;995 constexpr operation_counting_iterator& operator=(operation_counting_iterator&& o) { return *this = o; }996 997 friend constexpr It base(operation_counting_iterator const& it) { return It(it.base_); }998 999 constexpr decltype(auto) operator*() const { return *It(base_); }1000 1001 constexpr decltype(auto) operator[](difference_type n) const { return It(base_)[n]; }1002 1003 constexpr operation_counting_iterator& operator++() {1004 It tmp(base_);1005 base_ = base(++tmp);1006 moved_by(1);1007 return *this;1008 }1009 1010 constexpr void operator++(int) { ++*this; }1011 1012 constexpr operation_counting_iterator operator++(int)1013 requires std::forward_iterator<It>1014 {1015 auto temp = *this;1016 ++*this;1017 return temp;1018 }1019 1020 constexpr operation_counting_iterator& operator--()1021 requires std::bidirectional_iterator<It>1022 {1023 It tmp(base_);1024 base_ = base(--tmp);1025 moved_by(-1);1026 return *this;1027 }1028 1029 constexpr operation_counting_iterator operator--(int)1030 requires std::bidirectional_iterator<It>1031 {1032 auto temp = *this;1033 --*this;1034 return temp;1035 }1036 1037 constexpr operation_counting_iterator& operator+=(difference_type const n)1038 requires std::random_access_iterator<It>1039 {1040 It tmp(base_);1041 base_ = base(tmp += n);1042 moved_by(n);1043 return *this;1044 }1045 1046 constexpr operation_counting_iterator& operator-=(difference_type const n)1047 requires std::random_access_iterator<It>1048 {1049 It tmp(base_);1050 base_ = base(tmp -= n);1051 moved_by(-n);1052 return *this;1053 }1054 1055 friend constexpr operation_counting_iterator operator+(operation_counting_iterator it, difference_type n)1056 requires std::random_access_iterator<It>1057 {1058 return it += n;1059 }1060 1061 friend constexpr operation_counting_iterator operator+(difference_type n, operation_counting_iterator it)1062 requires std::random_access_iterator<It>1063 {1064 return it += n;1065 }1066 1067 friend constexpr operation_counting_iterator operator-(operation_counting_iterator it, difference_type n)1068 requires std::random_access_iterator<It>1069 {1070 return it -= n;1071 }1072 1073 friend constexpr difference_type1074 operator-(operation_counting_iterator const& x, operation_counting_iterator const& y)1075 requires std::sized_sentinel_for<It, It>1076 {1077 return base(x) - base(y);1078 }1079 1080 constexpr void record_equality_comparison() const {1081 if (counts_ != nullptr)1082 ++counts_->equal_cmps;1083 }1084 1085 constexpr bool operator==(operation_counting_iterator const& other) const1086 requires std::sentinel_for<It, It>1087 {1088 record_equality_comparison();1089 return It(base_) == It(other.base_);1090 }1091 1092 friend constexpr bool operator<(operation_counting_iterator const& x, operation_counting_iterator const& y)1093 requires std::random_access_iterator<It>1094 {1095 return It(x.base_) < It(y.base_);1096 }1097 1098 friend constexpr bool operator>(operation_counting_iterator const& x, operation_counting_iterator const& y)1099 requires std::random_access_iterator<It>1100 {1101 return It(x.base_) > It(y.base_);1102 }1103 1104 friend constexpr bool operator<=(operation_counting_iterator const& x, operation_counting_iterator const& y)1105 requires std::random_access_iterator<It>1106 {1107 return It(x.base_) <= It(y.base_);1108 }1109 1110 friend constexpr bool operator>=(operation_counting_iterator const& x, operation_counting_iterator const& y)1111 requires std::random_access_iterator<It>1112 {1113 return It(x.base_) >= It(y.base_);1114 }1115 1116 template <class T>1117 void operator,(T const &) = delete;1118 1119 template <class T>1120 friend void operator,(const T&, const operation_counting_iterator&) = delete;1121 1122 private:1123 constexpr void moved_by(difference_type n) {1124 if (counts_ == nullptr)1125 return;1126 if (n > 0)1127 ++counts_->increments;1128 else if (n < 0)1129 ++counts_->decrements;1130 else1131 ++counts_->zero_moves;1132 }1133 1134 decltype(base(std::declval<It>())) base_;1135 IteratorOpCounts* counts_ = nullptr;1136};1137template <class It>1138operation_counting_iterator(It) -> operation_counting_iterator<It>;1139 1140#endif // TEST_STD_VER > 171141 1142#if TEST_STD_VER > 171143template <class It>1144class sentinel_wrapper {1145public:1146 explicit sentinel_wrapper() = default;1147 constexpr explicit sentinel_wrapper(const It& it) : base_(base(it)) {}1148 constexpr bool operator==(const It& other) const {1149 // If supported, record statistics about the equality operator call1150 // inside `other`.1151 if constexpr (requires { other.record_equality_comparison(); }) {1152 other.record_equality_comparison();1153 }1154 return base_ == base(other);1155 }1156 friend constexpr It base(const sentinel_wrapper& s) { return It(s.base_); }1157private:1158 decltype(base(std::declval<It>())) base_;1159};1160template <class It>1161sentinel_wrapper(It) -> sentinel_wrapper<It>;1162 1163template <class It>1164class sized_sentinel {1165public:1166 explicit sized_sentinel() = default;1167 constexpr explicit sized_sentinel(const It& it) : base_(base(it)) {}1168 constexpr bool operator==(const It& other) const { return base_ == base(other); }1169 friend constexpr auto operator-(const sized_sentinel& s, const It& i) { return s.base_ - base(i); }1170 friend constexpr auto operator-(const It& i, const sized_sentinel& s) { return base(i) - s.base_; }1171 friend constexpr It base(const sized_sentinel& s) { return It(s.base_); }1172private:1173 decltype(base(std::declval<It>())) base_;1174};1175template <class It>1176sized_sentinel(It) -> sized_sentinel<It>;1177 1178namespace adl {1179 1180class Iterator {1181 public:1182 using value_type = int;1183 using reference = int&;1184 using difference_type = std::ptrdiff_t;1185 1186 private:1187 value_type* ptr_ = nullptr;1188 int* iter_moves_ = nullptr;1189 int* iter_swaps_ = nullptr;1190 1191 constexpr Iterator(int* p, int* iter_moves, int* iter_swaps)1192 : ptr_(p)1193 , iter_moves_(iter_moves)1194 , iter_swaps_(iter_swaps) {}1195 1196 public:1197 constexpr Iterator() = default;1198 static constexpr Iterator TrackMoves(int* p, int& iter_moves) {1199 return Iterator(p, &iter_moves, /*iter_swaps=*/nullptr);1200 }1201 static constexpr Iterator TrackSwaps(int& iter_swaps) {1202 return Iterator(/*p=*/nullptr, /*iter_moves=*/nullptr, &iter_swaps);1203 }1204 static constexpr Iterator TrackSwaps(int* p, int& iter_swaps) {1205 return Iterator(p, /*iter_moves=*/nullptr, &iter_swaps);1206 }1207 1208 constexpr int iter_moves() const { assert(iter_moves_); return *iter_moves_; }1209 constexpr int iter_swaps() const { assert(iter_swaps_); return *iter_swaps_; }1210 1211 constexpr value_type& operator*() const { return *ptr_; }1212 constexpr reference operator[](difference_type n) const { return ptr_[n]; }1213 1214 friend constexpr Iterator operator+(Iterator i, difference_type n) {1215 return Iterator(i.ptr_ + n, i.iter_moves_, i.iter_swaps_);1216 }1217 friend constexpr Iterator operator+(difference_type n, Iterator i) {1218 return i + n;1219 }1220 constexpr Iterator operator-(difference_type n) const {1221 return Iterator(ptr_ - n, iter_moves_, iter_swaps_);1222 }1223 constexpr difference_type operator-(Iterator rhs) const {1224 return ptr_ - rhs.ptr_;1225 }1226 constexpr Iterator& operator+=(difference_type n) {1227 ptr_ += n;1228 return *this;1229 }1230 constexpr Iterator& operator-=(difference_type n) {1231 ptr_ -= n;1232 return *this;1233 }1234 1235 constexpr Iterator& operator++() { ++ptr_; return *this; }1236 constexpr Iterator operator++(int) {1237 Iterator prev = *this;1238 ++ptr_;1239 return prev;1240 }1241 1242 constexpr Iterator& operator--() { --ptr_; return *this; }1243 constexpr Iterator operator--(int) {1244 Iterator prev = *this;1245 --ptr_;1246 return prev;1247 }1248 1249 constexpr friend void iter_swap(Iterator a, Iterator b) {1250 std::swap(a.ptr_, b.ptr_);1251 if (a.iter_swaps_) {1252 ++(*a.iter_swaps_);1253 }1254 }1255 1256 constexpr friend value_type&& iter_move(Iterator iter) {1257 if (iter.iter_moves_) {1258 ++(*iter.iter_moves_);1259 }1260 return std::move(*iter);1261 }1262 1263 constexpr friend bool operator==(const Iterator& lhs, const Iterator& rhs) {1264 return lhs.ptr_ == rhs.ptr_;1265 }1266 constexpr friend auto operator<=>(const Iterator& lhs, const Iterator& rhs) {1267 return lhs.ptr_ <=> rhs.ptr_;1268 }1269};1270 1271} // namespace adl1272 1273template <class T>1274class rvalue_iterator {1275public:1276 using iterator_category = std::input_iterator_tag;1277 using iterator_concept = std::random_access_iterator_tag;1278 using difference_type = std::ptrdiff_t;1279 using reference = T&&;1280 using value_type = T;1281 1282 rvalue_iterator() = default;1283 constexpr rvalue_iterator(T* it) : it_(it) {}1284 1285 constexpr reference operator*() const { return std::move(*it_); }1286 1287 constexpr rvalue_iterator& operator++() {1288 ++it_;1289 return *this;1290 }1291 1292 constexpr rvalue_iterator operator++(int) {1293 auto tmp = *this;1294 ++it_;1295 return tmp;1296 }1297 1298 constexpr rvalue_iterator& operator--() {1299 --it_;1300 return *this;1301 }1302 1303 constexpr rvalue_iterator operator--(int) {1304 auto tmp = *this;1305 --it_;1306 return tmp;1307 }1308 1309 constexpr rvalue_iterator operator+(difference_type n) const {1310 auto tmp = *this;1311 tmp.it += n;1312 return tmp;1313 }1314 1315 constexpr friend rvalue_iterator operator+(difference_type n, rvalue_iterator iter) {1316 iter += n;1317 return iter;1318 }1319 1320 constexpr rvalue_iterator operator-(difference_type n) const {1321 auto tmp = *this;1322 tmp.it -= n;1323 return tmp;1324 }1325 1326 constexpr difference_type operator-(const rvalue_iterator& other) const { return it_ - other.it_; }1327 1328 constexpr rvalue_iterator& operator+=(difference_type n) {1329 it_ += n;1330 return *this;1331 }1332 1333 constexpr rvalue_iterator& operator-=(difference_type n) {1334 it_ -= n;1335 return *this;1336 }1337 1338 constexpr reference operator[](difference_type n) const { return std::move(it_[n]); }1339 1340 auto operator<=>(const rvalue_iterator&) const noexcept = default;1341 1342private:1343 T* it_;1344};1345 1346template <class T>1347rvalue_iterator(T*) -> rvalue_iterator<T>;1348 1349static_assert(std::random_access_iterator<rvalue_iterator<int*>>);1350 1351// The ProxyDiffTBase allows us to conditionally specify Proxy<T>::difference_type1352// which we need in certain situations. For example when we want1353// std::weakly_incrementable<Proxy<T>> to be true.1354template <class T>1355struct ProxyDiffTBase {1356 // Add default `operator<=>` so that the derived type, Proxy, can also use the default `operator<=>`1357 friend constexpr auto operator<=>(const ProxyDiffTBase&, const ProxyDiffTBase&) = default;1358};1359 1360template <class T>1361 requires requires { std::iter_difference_t<T>{}; }1362struct ProxyDiffTBase<T> {1363 using difference_type = std::iter_difference_t<T>;1364 // Add default `operator<=>` so that the derived type, Proxy, can also use the default `operator<=>`1365 friend constexpr auto operator<=>(const ProxyDiffTBase&, const ProxyDiffTBase&) = default;1366};1367 1368// Proxy1369// ======================================================================1370// Proxy that can wrap a value or a reference. It simulates C++23's tuple1371// but simplified to just hold one argument.1372// Note that unlike tuple, this class deliberately doesn't have special handling1373// of swap to cause a compilation error if it's used in an algorithm that relies1374// on plain swap instead of ranges::iter_swap.1375// This class is useful for testing that if algorithms support proxy iterator1376// properly, i.e. calling ranges::iter_swap and ranges::iter_move instead of1377// plain swap and std::move.1378 1379template <class T>1380struct Proxy;1381 1382template <class T>1383inline constexpr bool IsProxy = false;1384 1385template <class T>1386inline constexpr bool IsProxy<Proxy<T>> = true;1387 1388template <class T>1389struct Proxy : ProxyDiffTBase<T> {1390 T data;1391 1392 constexpr T& getData() & { return data; }1393 1394 constexpr const T& getData() const& { return data; }1395 1396 constexpr T&& getData() && { return static_cast<T&&>(data); }1397 1398 constexpr const T&& getData() const&& { return static_cast<const T&&>(data); }1399 1400 // Explicitly declare the copy constructor as defaulted to avoid deprecation of the implicitly declared one1401 // because of the user-provided copy assignment operator.1402 Proxy(const Proxy&) = default;1403 1404 template <class U>1405 requires std::constructible_from<T, U&&>1406 constexpr Proxy(U&& u) : data{std::forward<U>(u)} {}1407 1408 // This constructor covers conversion from cvref of Proxy<U>, including non-const/const versions of copy/move constructor1409 template <class Other>1410 requires(IsProxy<std::decay_t<Other>> && std::constructible_from<T, decltype(std::declval<Other>().getData())>)1411 constexpr Proxy(Other&& other) : data{std::forward<Other>(other).getData()} {}1412 1413 template <class Other>1414 requires(IsProxy<std::decay_t<Other>> && std::assignable_from<T&, decltype(std::declval<Other>().getData())>)1415 constexpr Proxy& operator=(Other&& other) {1416 data = std::forward<Other>(other).getData();1417 return *this;1418 }1419 1420 // const assignment required to make ProxyIterator model std::indirectly_writable1421 template <class Other>1422 requires(IsProxy<std::decay_t<Other>> && std::assignable_from<const T&, decltype(std::declval<Other>().getData())>)1423 constexpr const Proxy& operator=(Other&& other) const {1424 data = std::forward<Other>(other).getData();1425 return *this;1426 }1427 1428 // If `T` is a reference type, the implicitly-generated assignment operator will be deleted (and would take precedence1429 // over the templated `operator=` above because it's a better match).1430 constexpr Proxy& operator=(const Proxy& rhs) {1431 data = rhs.data;1432 return *this;1433 }1434 1435 // no specialised swap function that takes const Proxy& and no specialised const member swap1436 // Calling swap(Proxy<T>{}, Proxy<T>{}) would fail (pass prvalues)1437 1438 // Compare operators are defined for the convenience of the tests1439 friend constexpr bool operator==(const Proxy&, const Proxy&)1440 requires(std::equality_comparable<T> && !std::is_reference_v<T>)1441 = default;1442 1443 // Helps compare e.g. `Proxy<int>` and `Proxy<int&>`. Note that the default equality comparison operator is deleted1444 // when `T` is a reference type.1445 template <class U>1446 friend constexpr bool operator==(const Proxy& lhs, const Proxy<U>& rhs)1447 requires std::equality_comparable_with<std::decay_t<T>, std::decay_t<U>> {1448 return lhs.data == rhs.data;1449 }1450 1451 friend constexpr auto operator<=>(const Proxy&, const Proxy&)1452 requires(std::three_way_comparable<T> && !std::is_reference_v<T>)1453 = default;1454 1455 // Helps compare e.g. `Proxy<int>` and `Proxy<int&>`. Note that the default 3-way comparison operator is deleted when1456 // `T` is a reference type.1457 template <class U>1458 friend constexpr auto operator<=>(const Proxy& lhs, const Proxy<U>& rhs)1459 requires std::three_way_comparable_with<std::decay_t<T>, std::decay_t<U>> {1460 return lhs.data <=> rhs.data;1461 }1462 1463 // Needed to allow certain types to be weakly_incrementable1464 constexpr Proxy& operator++()1465 requires(std::weakly_incrementable<std::remove_reference_t<T>>)1466 {1467 ++data;1468 return *this;1469 }1470 1471 constexpr Proxy operator++(int)1472 requires(std::incrementable<std::remove_reference_t<T>>)1473 {1474 Proxy tmp = *this;1475 operator++();1476 return tmp;1477 }1478};1479 1480// This is to make ProxyIterator model `std::indirectly_readable`1481template <class T, class U, template <class> class TQual, template <class> class UQual>1482 requires requires { typename std::common_reference_t<TQual<T>, UQual<U>>; }1483struct std::basic_common_reference<Proxy<T>, Proxy<U>, TQual, UQual> {1484 using type = Proxy<std::common_reference_t<TQual<T>, UQual<U>>>;1485};1486 1487template <class T, class U>1488 requires requires { typename std::common_type_t<T, U>; }1489struct std::common_type<Proxy<T>, Proxy<U>> {1490 using type = Proxy<std::common_type_t<T, U>>;1491};1492 1493// ProxyIterator1494// ======================================================================1495// It wraps `Base` iterator and when dereferenced it returns a Proxy<ref>1496// It simulates C++23's zip_view::iterator but simplified to just wrap1497// one base iterator.1498// Note it forwards value_type, iter_move, iter_swap. e.g if the base1499// iterator is int*,1500// operator* -> Proxy<int&>1501// iter_value_t -> Proxy<int>1502// iter_move -> Proxy<int&&>1503template <class Base>1504struct ProxyIteratorBase {};1505 1506template <class Base>1507 requires std::derived_from<1508 typename std::iterator_traits<Base>::iterator_category,1509 std::input_iterator_tag>1510struct ProxyIteratorBase<Base> {1511 using iterator_category = std::input_iterator_tag;1512};1513 1514template <std::input_iterator Base>1515consteval auto get_iterator_concept() {1516 if constexpr (std::random_access_iterator<Base>) {1517 return std::random_access_iterator_tag{};1518 } else if constexpr (std::bidirectional_iterator<Base>) {1519 return std::bidirectional_iterator_tag{};1520 } else if constexpr (std::forward_iterator<Base>) {1521 return std::forward_iterator_tag{};1522 } else {1523 return std::input_iterator_tag{};1524 }1525}1526 1527template <std::input_iterator Base>1528struct ProxyIterator : ProxyIteratorBase<Base> {1529 Base base_;1530 1531 using iterator_concept = decltype(get_iterator_concept<Base>());1532 using value_type = Proxy<std::iter_value_t<Base>>;1533 using difference_type = std::iter_difference_t<Base>;1534 1535 ProxyIterator()1536 requires std::default_initializable<Base>1537 = default;1538 1539 constexpr ProxyIterator(Base base) : base_{std::move(base)} {}1540 1541 template <class T>1542 requires std::constructible_from<Base, T&&>1543 constexpr ProxyIterator(T&& t) : base_{std::forward<T>(t)} {}1544 1545 friend constexpr decltype(auto) base(const ProxyIterator& p) { return base(p.base_); }1546 1547 // Specialization of iter_move1548 // If operator* returns Proxy<Foo&>, iter_move will return Proxy<Foo&&>1549 // Note std::move(*it) returns Proxy<Foo&>&&, which is not what we want as1550 // it will likely result in a copy rather than a move1551 friend constexpr Proxy<std::iter_rvalue_reference_t<Base>> iter_move(const ProxyIterator& p) noexcept {1552 return {std::ranges::iter_move(p.base_)};1553 }1554 1555 // Specialization of iter_swap1556 // Note std::swap(*x, *y) would fail to compile as operator* returns prvalues1557 // and std::swap takes non-const lvalue references1558 friend constexpr void iter_swap(const ProxyIterator& x, const ProxyIterator& y) noexcept {1559 std::ranges::iter_swap(x.base_, y.base_);1560 }1561 1562 // to satisfy input_iterator1563 constexpr Proxy<std::iter_reference_t<Base>> operator*() const { return {*base_}; }1564 1565 constexpr ProxyIterator& operator++() {1566 ++base_;1567 return *this;1568 }1569 1570 constexpr void operator++(int) { ++*this; }1571 1572 friend constexpr bool operator==(const ProxyIterator& x, const ProxyIterator& y)1573 requires std::equality_comparable<Base> {1574 return x.base_ == y.base_;1575 }1576 1577 // to satisfy forward_iterator1578 constexpr ProxyIterator operator++(int)1579 requires std::forward_iterator<Base> {1580 auto tmp = *this;1581 ++*this;1582 return tmp;1583 }1584 1585 // to satisfy bidirectional_iterator1586 constexpr ProxyIterator& operator--()1587 requires std::bidirectional_iterator<Base> {1588 --base_;1589 return *this;1590 }1591 1592 constexpr ProxyIterator operator--(int)1593 requires std::bidirectional_iterator<Base> {1594 auto tmp = *this;1595 --*this;1596 return tmp;1597 }1598 1599 // to satisfy random_access_iterator1600 constexpr ProxyIterator& operator+=(difference_type n)1601 requires std::random_access_iterator<Base> {1602 base_ += n;1603 return *this;1604 }1605 1606 constexpr ProxyIterator& operator-=(difference_type n)1607 requires std::random_access_iterator<Base> {1608 base_ -= n;1609 return *this;1610 }1611 1612 constexpr Proxy<std::iter_reference_t<Base>> operator[](difference_type n) const1613 requires std::random_access_iterator<Base> {1614 return {base_[n]};1615 }1616 1617 friend constexpr bool operator<(const ProxyIterator& x, const ProxyIterator& y)1618 requires std::random_access_iterator<Base> {1619 return x.base_ < y.base_;1620 }1621 1622 friend constexpr bool operator>(const ProxyIterator& x, const ProxyIterator& y)1623 requires std::random_access_iterator<Base> {1624 return x.base_ > y.base_;1625 }1626 1627 friend constexpr bool operator<=(const ProxyIterator& x, const ProxyIterator& y)1628 requires std::random_access_iterator<Base> {1629 return x.base_ <= y.base_;1630 }1631 1632 friend constexpr bool operator>=(const ProxyIterator& x, const ProxyIterator& y)1633 requires std::random_access_iterator<Base> {1634 return x.base_ >= y.base_;1635 }1636 1637 friend constexpr auto operator<=>(const ProxyIterator& x, const ProxyIterator& y)1638 requires(std::random_access_iterator<Base> && std::three_way_comparable<Base>) {1639 return x.base_ <=> y.base_;1640 }1641 1642 friend constexpr ProxyIterator operator+(const ProxyIterator& x, difference_type n)1643 requires std::random_access_iterator<Base> {1644 return ProxyIterator{x.base_ + n};1645 }1646 1647 friend constexpr ProxyIterator operator+(difference_type n, const ProxyIterator& x)1648 requires std::random_access_iterator<Base> {1649 return ProxyIterator{n + x.base_};1650 }1651 1652 friend constexpr ProxyIterator operator-(const ProxyIterator& x, difference_type n)1653 requires std::random_access_iterator<Base> {1654 return ProxyIterator{x.base_ - n};1655 }1656 1657 friend constexpr difference_type operator-(const ProxyIterator& x, const ProxyIterator& y)1658 requires std::random_access_iterator<Base> {1659 return x.base_ - y.base_;1660 }1661};1662template <class Base>1663ProxyIterator(Base) -> ProxyIterator<Base>;1664 1665static_assert(std::indirectly_readable<ProxyIterator<int*>>);1666static_assert(std::indirectly_writable<ProxyIterator<int*>, Proxy<int>>);1667static_assert(std::indirectly_writable<ProxyIterator<int*>, Proxy<int&>>);1668 1669template <class Iter>1670using Cpp20InputProxyIterator = ProxyIterator<cpp20_input_iterator<Iter>>;1671 1672template <class Iter>1673using ForwardProxyIterator = ProxyIterator<forward_iterator<Iter>>;1674 1675template <class Iter>1676using BidirectionalProxyIterator = ProxyIterator<bidirectional_iterator<Iter>>;1677 1678template <class Iter>1679using RandomAccessProxyIterator = ProxyIterator<random_access_iterator<Iter>>;1680 1681template <class Iter>1682using ContiguousProxyIterator = ProxyIterator<contiguous_iterator<Iter>>;1683 1684template <class BaseSent>1685struct ProxySentinel {1686 BaseSent base_;1687 1688 ProxySentinel() = default;1689 constexpr ProxySentinel(BaseSent base) : base_{std::move(base)} {}1690 1691 template <class Base>1692 requires std::equality_comparable_with<Base, BaseSent>1693 friend constexpr bool operator==(const ProxyIterator<Base>& p, const ProxySentinel& sent) {1694 return p.base_ == sent.base_;1695 }1696};1697template <class BaseSent>1698ProxySentinel(BaseSent) -> ProxySentinel<BaseSent>;1699 1700template <std::ranges::input_range Base>1701 requires std::ranges::view<Base>1702struct ProxyRange {1703 Base base_;1704 1705 constexpr auto begin() { return ProxyIterator{std::ranges::begin(base_)}; }1706 1707 constexpr auto end() { return ProxySentinel{std::ranges::end(base_)}; }1708 1709 constexpr auto begin() const1710 requires std::ranges::input_range<const Base> {1711 return ProxyIterator{std::ranges::begin(base_)};1712 }1713 1714 constexpr auto end() const1715 requires std::ranges::input_range<const Base> {1716 return ProxySentinel{std::ranges::end(base_)};1717 }1718};1719 1720template <std::ranges::input_range R>1721 requires std::ranges::viewable_range<R&&>1722ProxyRange(R&&) -> ProxyRange<std::views::all_t<R&&>>;1723 1724#endif // TEST_STD_VER > 171725 1726#if TEST_STD_VER >= 171727 1728namespace util {1729template <class Derived, class Iter>1730class iterator_wrapper {1731 Iter iter_;1732 1733 using iter_traits = std::iterator_traits<Iter>;1734 1735public:1736 using iterator_category = typename iter_traits::iterator_category;1737 using value_type = typename iter_traits::value_type;1738 using difference_type = typename iter_traits::difference_type;1739 using pointer = typename iter_traits::pointer;1740 using reference = typename iter_traits::reference;1741 1742 constexpr iterator_wrapper() : iter_() {}1743 constexpr explicit iterator_wrapper(Iter iter) : iter_(iter) {}1744 1745 decltype(*iter_) operator*() { return *iter_; }1746 decltype(*iter_) operator*() const { return *iter_; }1747 1748 decltype(iter_[0]) operator[](difference_type v) const {1749 return iter_[v];1750 }1751 1752 Derived& operator++() {1753 ++iter_;1754 return static_cast<Derived&>(*this);1755 }1756 1757 Derived operator++(int) {1758 auto tmp = static_cast<Derived&>(*this);1759 ++(*this);1760 return tmp;1761 }1762 1763 Derived& operator--() {1764 --iter_;1765 return static_cast<Derived&>(*this);1766 }1767 1768 Derived operator--(int) {1769 auto tmp = static_cast<Derived&>(*this);1770 --(*this);1771 return tmp;1772 }1773 1774 Derived& operator+=(difference_type i) {1775 iter_ += i;1776 return static_cast<Derived&>(*this);1777 }1778 1779 Derived& operator-=(difference_type i) {1780 iter_ -= i;1781 return static_cast<Derived&>(*this);1782 }1783 1784 friend decltype(iter_ - iter_) operator-(const iterator_wrapper& lhs, const iterator_wrapper& rhs) {1785 return lhs.iter_ - rhs.iter_;1786 }1787 1788 friend Derived operator-(Derived iter, difference_type i) {1789 iter.iter_ -= i;1790 return iter;1791 }1792 1793 friend Derived operator+(Derived iter, difference_type i) {1794 iter.iter_ += i;1795 return iter;1796 }1797 1798 friend Derived operator+(difference_type i, Derived iter) { return iter + i; }1799 1800 friend bool operator==(const iterator_wrapper& lhs, const iterator_wrapper& rhs) { return lhs.iter_ == rhs.iter_; }1801 friend bool operator!=(const iterator_wrapper& lhs, const iterator_wrapper& rhs) { return lhs.iter_ != rhs.iter_; }1802 1803 friend bool operator>(const iterator_wrapper& lhs, const iterator_wrapper& rhs) { return lhs.iter_ > rhs.iter_; }1804 friend bool operator<(const iterator_wrapper& lhs, const iterator_wrapper& rhs) { return lhs.iter_ < rhs.iter_; }1805 friend bool operator<=(const iterator_wrapper& lhs, const iterator_wrapper& rhs) { return lhs.iter_ <= rhs.iter_; }1806 friend bool operator>=(const iterator_wrapper& lhs, const iterator_wrapper& rhs) { return lhs.iter_ >= rhs.iter_; }1807};1808 1809class iterator_error : std::runtime_error {1810public:1811 iterator_error(const char* what) : std::runtime_error(what) {}1812};1813 1814#ifndef TEST_HAS_NO_EXCEPTIONS1815template <class Iter>1816class throw_on_move_iterator : public iterator_wrapper<throw_on_move_iterator<Iter>, Iter> {1817 using base = iterator_wrapper<throw_on_move_iterator<Iter>, Iter>;1818 1819 int moves_until_throw_ = 0;1820 1821public:1822 using difference_type = typename base::difference_type;1823 using value_type = typename base::value_type;1824 using iterator_category = typename base::iterator_category;1825 1826 throw_on_move_iterator() = default;1827 throw_on_move_iterator(Iter iter, int moves_until_throw)1828 : base(std::move(iter)), moves_until_throw_(moves_until_throw) {}1829 1830 throw_on_move_iterator(const throw_on_move_iterator& other) : base(other) {}1831 throw_on_move_iterator& operator=(const throw_on_move_iterator& other) {1832 static_cast<base&>(*this) = other;1833 return *this;1834 }1835 1836 throw_on_move_iterator(throw_on_move_iterator&& other)1837 : base(std::move(other)), moves_until_throw_(other.moves_until_throw_ - 1) {1838 if (moves_until_throw_ == -1)1839 throw iterator_error("throw_on_move_iterator");1840 }1841 1842 throw_on_move_iterator& operator=(throw_on_move_iterator&& other) {1843 moves_until_throw_ = other.moves_until_throw_ - 1;1844 if (moves_until_throw_ == -1)1845 throw iterator_error("throw_on_move_iterator");1846 return *this;1847 }1848};1849 1850template <class Iter>1851throw_on_move_iterator(Iter) -> throw_on_move_iterator<Iter>;1852#endif // TEST_HAS_NO_EXCEPTIONS1853} // namespace util1854 1855#endif // TEST_STD_VER >= 171856 1857namespace types {1858template <class Ptr>1859using random_access_iterator_list =1860 type_list<Ptr,1861#if TEST_STD_VER >= 201862 contiguous_iterator<Ptr>,1863#endif1864 random_access_iterator<Ptr> >;1865 1866template <class Ptr>1867using bidirectional_iterator_list =1868 concatenate_t<random_access_iterator_list<Ptr>, type_list<bidirectional_iterator<Ptr> > >;1869 1870template <class Ptr>1871using forward_iterator_list = concatenate_t<bidirectional_iterator_list<Ptr>, type_list<forward_iterator<Ptr> > >;1872 1873template <class Ptr>1874using cpp17_input_iterator_list = concatenate_t<forward_iterator_list<Ptr>, type_list<cpp17_input_iterator<Ptr> > >;1875 1876#if TEST_STD_VER >= 201877template <class Ptr>1878using cpp20_input_iterator_list =1879 concatenate_t<forward_iterator_list<Ptr>, type_list<cpp20_input_iterator<Ptr>, cpp17_input_iterator<Ptr>>>;1880#endif1881} // namespace types1882 1883 1884#endif // SUPPORT_TEST_ITERATORS_H1885