1// -*- C++ -*- 2//===-------------------------- iterator ----------------------------------===// 3// 4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5// See https://llvm.org/LICENSE.txt for license information. 6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7// 8//===----------------------------------------------------------------------===// 9 10#ifndef _LIBCPP_ITERATOR 11#define _LIBCPP_ITERATOR 12 13/* 14 iterator synopsis 15 16#include <concepts> 17 18namespace std 19{ 20template<class> struct incrementable_traits; // since C++20 21template<class T> 22 using iter_difference_t = see below; // since C++20 23 24template<class> struct indirectly_readable_traits; // since C++20 25template<class T> 26 using iter_value_t = see below; // since C++20 27 28template<class Iterator> 29struct iterator_traits; 30 31template<class T> 32 requires is_object_v<T> // since C++20 33struct iterator_traits<T*>; 34 35template<dereferenceable T> 36 using iter_reference_t = decltype(*declval<T&>()); 37 38namespace ranges::inline unspecified { 39 inline constexpr unspecified iter_move = unspecified; // since C++20, nodiscard as an extension 40}} 41 42template<dereferenceable T> 43 requires ... 44using iter_rvalue_reference_t = decltype(ranges::iter_move(declval<T&>())); // since C++20 45 46// [iterator.concepts], iterator concepts 47// [iterator.concept.readable], concept indirectly_readable 48template<class In> 49 concept indirectly_readable = see below; // since C++20 50 51template<indirectly_readable T> 52 using iter_common_reference_t = 53 common_reference_t<iter_reference_t<T>, iter_value_t<T>&>; // since C++20 54 55// [iterator.concept.writable], concept indirectly_writable 56template<class Out, class T> 57 concept indirectly_writable = see below; // since C++20 58 59// [iterator.concept.winc], concept weakly_incrementable 60template<class I> 61 concept weakly_incrementable = see below; // since C++20 62 63// [iterator.concept.inc], concept incrementable 64template<class I> 65 concept incrementable = see below; // since C++20 66 67// [iterator.concept.iterator], concept input_or_output_iterator 68 template<class I> 69 concept input_or_output_iterator = see below; // since C++20 70 71// [iterator.concept.sentinel], concept sentinel_for 72template<class S, class I> 73 concept sentinel_for = see below; // since C++20 74 75// [iterator.concept.sizedsentinel], concept sized_sentinel_for 76template<class S, class I> 77 inline constexpr bool disable_sized_sentinel_for = false; 78 79template<class S, class I> 80 concept sized_sentinel_for = see below; 81 82// [iterator.concept.input], concept input_iterator 83template<class I> 84 concept input_iterator = see below; // since C++20 85 86// [iterator.concept.forward], concept forward_iterator 87template<class I> 88 concept forward_iterator = see below; // since C++20 89 90// [iterator.concept.bidir], concept bidirectional_iterator 91template<class I> 92 concept bidirectional_iterator = see below; // since C++20 93 94// [iterator.concept.random.access], concept random_access_iterator 95template<class I> 96 concept random_access_iterator = see below; // since C++20 97 98// [indirectcallable] 99// [indirectcallable.indirectinvocable] 100template<class F, class I> 101 concept indirectly_unary_invocable = see below; // since C++20 102 103template<class F, class I> 104 concept indirectly_regular_unary_invocable = see below; // since C++20 105 106template<class F, class I> 107 concept indirect_unary_predicate = see below; // since C++20 108 109template<class F, class I1, class I2> 110 concept indirect_binary_predicate = see below; // since C++20 111 112template<class F, class I1, class I2 = I1> 113 concept indirect_equivalence_relation = see below; // since C++20 114 115template<class F, class I1, class I2 = I1> 116 concept indirect_strict_weak_order = see below; // since C++20 117 118template<class F, class... Is> 119 using indirect_result_t = see below; // since C++20 120 121// [projected], projected 122template<indirectly_readable I, indirectly_regular_unary_invocable<I> Proj> 123 struct projected; // since C++20 124 125template<weakly_incrementable I, indirectly_regular_unary_invocable<I> Proj> 126 struct incrementable_traits<projected<I, Proj>>; // since C++20 127 128// [alg.req.ind.move], concept indirectly_movable 129template<class In, class Out> 130 concept indirectly_movable = see below; // since C++20 131 132template<class In, class Out> 133 concept indirectly_movable_storable = see below; // since C++20 134 135// [alg.req.ind.swap], concept indirectly_swappable 136template<class I1, class I2 = I1> 137 concept indirectly_swappable = see below; // since C++20 138 139template<class Category, class T, class Distance = ptrdiff_t, 140 class Pointer = T*, class Reference = T&> 141struct iterator // deprecated in C++17 142{ 143 typedef T value_type; 144 typedef Distance difference_type; 145 typedef Pointer pointer; 146 typedef Reference reference; 147 typedef Category iterator_category; 148}; 149 150struct input_iterator_tag {}; 151struct output_iterator_tag {}; 152struct forward_iterator_tag : public input_iterator_tag {}; 153struct bidirectional_iterator_tag : public forward_iterator_tag {}; 154struct random_access_iterator_tag : public bidirectional_iterator_tag {}; 155 156// 27.4.3, iterator operations 157template <class InputIterator, class Distance> // constexpr in C++17 158 constexpr void advance(InputIterator& i, Distance n); 159 160template <class InputIterator> // constexpr in C++17 161 constexpr typename iterator_traits<InputIterator>::difference_type 162 distance(InputIterator first, InputIterator last); 163 164template <class InputIterator> // constexpr in C++17 165 constexpr InputIterator next(InputIterator x, 166typename iterator_traits<InputIterator>::difference_type n = 1); 167 168template <class BidirectionalIterator> // constexpr in C++17 169 constexpr BidirectionalIterator prev(BidirectionalIterator x, 170 typename iterator_traits<BidirectionalIterator>::difference_type n = 1); 171 172// [range.iter.ops], range iterator operations 173namespace ranges { 174 // [range.iter.op.advance], ranges::advance 175 template<input_or_output_iterator I> 176 constexpr void advance(I& i, iter_difference_t<I> n); // since C++20 177 template<input_or_output_iterator I, sentinel_for<I> S> 178 constexpr void advance(I& i, S bound); // since C++20 179 template<input_or_output_iterator I, sentinel_for<I> S> 180 constexpr iter_difference_t<I> advance(I& i, iter_difference_t<I> n, S bound); // since C++20 181} 182 183template <class Iterator> 184class reverse_iterator 185 : public iterator<typename iterator_traits<Iterator>::iterator_category, // until C++17 186 typename iterator_traits<Iterator>::value_type, 187 typename iterator_traits<Iterator>::difference_type, 188 typename iterator_traits<Iterator>::pointer, 189 typename iterator_traits<Iterator>::reference> 190{ 191protected: 192 Iterator current; 193public: 194 typedef Iterator iterator_type; 195 typedef typename iterator_traits<Iterator>::difference_type difference_type; 196 typedef typename iterator_traits<Iterator>::reference reference; 197 typedef typename iterator_traits<Iterator>::pointer pointer; 198 199 constexpr reverse_iterator(); 200 constexpr explicit reverse_iterator(Iterator x); 201 template <class U> constexpr reverse_iterator(const reverse_iterator<U>& u); 202 template <class U> constexpr reverse_iterator& operator=(const reverse_iterator<U>& u); 203 constexpr Iterator base() const; 204 constexpr reference operator*() const; 205 constexpr pointer operator->() const; 206 constexpr reverse_iterator& operator++(); 207 constexpr reverse_iterator operator++(int); 208 constexpr reverse_iterator& operator--(); 209 constexpr reverse_iterator operator--(int); 210 constexpr reverse_iterator operator+ (difference_type n) const; 211 constexpr reverse_iterator& operator+=(difference_type n); 212 constexpr reverse_iterator operator- (difference_type n) const; 213 constexpr reverse_iterator& operator-=(difference_type n); 214 constexpr reference operator[](difference_type n) const; 215}; 216 217template <class Iterator1, class Iterator2> 218constexpr bool // constexpr in C++17 219operator==(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 220 221template <class Iterator1, class Iterator2> 222constexpr bool // constexpr in C++17 223operator<(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 224 225template <class Iterator1, class Iterator2> 226constexpr bool // constexpr in C++17 227operator!=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 228 229template <class Iterator1, class Iterator2> 230constexpr bool // constexpr in C++17 231operator>(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 232 233template <class Iterator1, class Iterator2> 234constexpr bool // constexpr in C++17 235operator>=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 236 237template <class Iterator1, class Iterator2> 238constexpr bool // constexpr in C++17 239operator<=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 240 241template <class Iterator1, class Iterator2> 242constexpr auto 243operator-(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y) 244-> decltype(__y.base() - __x.base()); // constexpr in C++17 245 246template <class Iterator> 247constexpr reverse_iterator<Iterator> 248operator+(typename reverse_iterator<Iterator>::difference_type n, 249 const reverse_iterator<Iterator>& x); // constexpr in C++17 250 251template <class Iterator> 252constexpr reverse_iterator<Iterator> make_reverse_iterator(Iterator i); // C++14, constexpr in C++17 253 254template <class Container> 255class back_insert_iterator 256 : public iterator<output_iterator_tag, void, void, void, void> // until C++17 257{ 258protected: 259 Container* container; 260public: 261 typedef Container container_type; 262 typedef void value_type; 263 typedef void difference_type; // until C++20 264 typedef ptrdiff_t difference_type; // since C++20 265 typedef void reference; 266 typedef void pointer; 267 268 explicit back_insert_iterator(Container& x); // constexpr in C++20 269 back_insert_iterator& operator=(const typename Container::value_type& value); // constexpr in C++20 270 back_insert_iterator& operator*(); // constexpr in C++20 271 back_insert_iterator& operator++(); // constexpr in C++20 272 back_insert_iterator operator++(int); // constexpr in C++20 273}; 274 275template <class Container> back_insert_iterator<Container> back_inserter(Container& x); // constexpr in C++20 276 277template <class Container> 278class front_insert_iterator 279 : public iterator<output_iterator_tag, void, void, void, void> // until C++17 280{ 281protected: 282 Container* container; 283public: 284 typedef Container container_type; 285 typedef void value_type; 286 typedef void difference_type; // until C++20 287 typedef ptrdiff_t difference_type; // since C++20 288 typedef void reference; 289 typedef void pointer; 290 291 explicit front_insert_iterator(Container& x); // constexpr in C++20 292 front_insert_iterator& operator=(const typename Container::value_type& value); // constexpr in C++20 293 front_insert_iterator& operator*(); // constexpr in C++20 294 front_insert_iterator& operator++(); // constexpr in C++20 295 front_insert_iterator operator++(int); // constexpr in C++20 296}; 297 298template <class Container> front_insert_iterator<Container> front_inserter(Container& x); // constexpr in C++20 299 300template <class Container> 301class insert_iterator 302 : public iterator<output_iterator_tag, void, void, void, void> // until C++17 303{ 304protected: 305 Container* container; 306 typename Container::iterator iter; 307public: 308 typedef Container container_type; 309 typedef void value_type; 310 typedef void difference_type; // until C++20 311 typedef ptrdiff_t difference_type; // since C++20 312 typedef void reference; 313 typedef void pointer; 314 315 insert_iterator(Container& x, typename Container::iterator i); // constexpr in C++20 316 insert_iterator& operator=(const typename Container::value_type& value); // constexpr in C++20 317 insert_iterator& operator*(); // constexpr in C++20 318 insert_iterator& operator++(); // constexpr in C++20 319 insert_iterator& operator++(int); // constexpr in C++20 320}; 321 322template <class Container, class Iterator> 323insert_iterator<Container> inserter(Container& x, Iterator i); // constexpr in C++20 324 325template <class Iterator> 326class move_iterator { 327public: 328 typedef Iterator iterator_type; 329 typedef typename iterator_traits<Iterator>::difference_type difference_type; 330 typedef Iterator pointer; 331 typedef typename iterator_traits<Iterator>::value_type value_type; 332 typedef typename iterator_traits<Iterator>::iterator_category iterator_category; 333 typedef value_type&& reference; 334 335 constexpr move_iterator(); // all the constexprs are in C++17 336 constexpr explicit move_iterator(Iterator i); 337 template <class U> 338 constexpr move_iterator(const move_iterator<U>& u); 339 template <class U> 340 constexpr move_iterator& operator=(const move_iterator<U>& u); 341 constexpr iterator_type base() const; 342 constexpr reference operator*() const; 343 constexpr pointer operator->() const; 344 constexpr move_iterator& operator++(); 345 constexpr move_iterator operator++(int); 346 constexpr move_iterator& operator--(); 347 constexpr move_iterator operator--(int); 348 constexpr move_iterator operator+(difference_type n) const; 349 constexpr move_iterator& operator+=(difference_type n); 350 constexpr move_iterator operator-(difference_type n) const; 351 constexpr move_iterator& operator-=(difference_type n); 352 constexpr unspecified operator[](difference_type n) const; 353private: 354 Iterator current; // exposition only 355}; 356 357template <class Iterator1, class Iterator2> 358constexpr bool // constexpr in C++17 359operator==(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y); 360 361template <class Iterator1, class Iterator2> 362constexpr bool // constexpr in C++17 363operator!=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y); 364 365template <class Iterator1, class Iterator2> 366constexpr bool // constexpr in C++17 367operator<(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y); 368 369template <class Iterator1, class Iterator2> 370constexpr bool // constexpr in C++17 371operator<=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y); 372 373template <class Iterator1, class Iterator2> 374constexpr bool // constexpr in C++17 375operator>(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y); 376 377template <class Iterator1, class Iterator2> 378constexpr bool // constexpr in C++17 379operator>=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y); 380 381template <class Iterator1, class Iterator2> 382constexpr auto // constexpr in C++17 383operator-(const move_iterator<Iterator1>& x, 384 const move_iterator<Iterator2>& y) -> decltype(x.base() - y.base()); 385 386template <class Iterator> 387constexpr move_iterator<Iterator> operator+( // constexpr in C++17 388 typename move_iterator<Iterator>::difference_type n, 389 const move_iterator<Iterator>& x); 390 391template <class Iterator> // constexpr in C++17 392constexpr move_iterator<Iterator> make_move_iterator(const Iterator& i); 393 394// [default.sentinel], default sentinel 395struct default_sentinel_t; 396inline constexpr default_sentinel_t default_sentinel{}; 397 398template <class T, class charT = char, class traits = char_traits<charT>, class Distance = ptrdiff_t> 399class istream_iterator 400 : public iterator<input_iterator_tag, T, Distance, const T*, const T&> // until C++17 401{ 402public: 403 typedef input_iterator_tag iterator_category; 404 typedef T value_type; 405 typedef Distance difference_type; 406 typedef const T* pointer; 407 typedef const T& reference; 408 409 typedef charT char_type; 410 typedef traits traits_type; 411 typedef basic_istream<charT, traits> istream_type; 412 413 constexpr istream_iterator(); 414 istream_iterator(istream_type& s); 415 istream_iterator(const istream_iterator& x); 416 ~istream_iterator(); 417 418 const T& operator*() const; 419 const T* operator->() const; 420 istream_iterator& operator++(); 421 istream_iterator operator++(int); 422}; 423 424template <class T, class charT, class traits, class Distance> 425bool operator==(const istream_iterator<T,charT,traits,Distance>& x, 426 const istream_iterator<T,charT,traits,Distance>& y); 427template <class T, class charT, class traits, class Distance> 428bool operator!=(const istream_iterator<T,charT,traits,Distance>& x, 429 const istream_iterator<T,charT,traits,Distance>& y); 430 431template <class T, class charT = char, class traits = char_traits<charT> > 432class ostream_iterator 433 : public iterator<output_iterator_tag, void, void, void, void> // until C++17 434{ 435public: 436 typedef output_iterator_tag iterator_category; 437 typedef void value_type; 438 typedef void difference_type; // until C++20 439 typedef ptrdiff_t difference_type; // since C++20 440 typedef void pointer; 441 typedef void reference; 442 443 typedef charT char_type; 444 typedef traits traits_type; 445 typedef basic_ostream<charT,traits> ostream_type; 446 447 ostream_iterator(ostream_type& s); 448 ostream_iterator(ostream_type& s, const charT* delimiter); 449 ostream_iterator(const ostream_iterator& x); 450 ~ostream_iterator(); 451 ostream_iterator& operator=(const T& value); 452 453 ostream_iterator& operator*(); 454 ostream_iterator& operator++(); 455 ostream_iterator& operator++(int); 456}; 457 458template<class charT, class traits = char_traits<charT> > 459class istreambuf_iterator 460 : public iterator<input_iterator_tag, charT, traits::off_type, unspecified, charT> // until C++17 461{ 462public: 463 typedef input_iterator_tag iterator_category; 464 typedef charT value_type; 465 typedef traits::off_type difference_type; 466 typedef unspecified pointer; 467 typedef charT reference; 468 469 typedef charT char_type; 470 typedef traits traits_type; 471 typedef traits::int_type int_type; 472 typedef basic_streambuf<charT, traits> streambuf_type; 473 typedef basic_istream<charT, traits> istream_type; 474 475 istreambuf_iterator() noexcept; 476 istreambuf_iterator(istream_type& s) noexcept; 477 istreambuf_iterator(streambuf_type* s) noexcept; 478 istreambuf_iterator(a-private-type) noexcept; 479 480 charT operator*() const; 481 pointer operator->() const; 482 istreambuf_iterator& operator++(); 483 a-private-type operator++(int); 484 485 bool equal(const istreambuf_iterator& b) const; 486}; 487 488template <class charT, class traits> 489bool operator==(const istreambuf_iterator<charT,traits>& a, 490 const istreambuf_iterator<charT,traits>& b); 491template <class charT, class traits> 492bool operator!=(const istreambuf_iterator<charT,traits>& a, 493 const istreambuf_iterator<charT,traits>& b); 494 495template <class charT, class traits = char_traits<charT> > 496class ostreambuf_iterator 497 : public iterator<output_iterator_tag, void, void, void, void> // until C++17 498{ 499public: 500 typedef output_iterator_tag iterator_category; 501 typedef void value_type; 502 typedef void difference_type; // until C++20 503 typedef ptrdiff_t difference_type; // since C++20 504 typedef void pointer; 505 typedef void reference; 506 507 typedef charT char_type; 508 typedef traits traits_type; 509 typedef basic_streambuf<charT, traits> streambuf_type; 510 typedef basic_ostream<charT, traits> ostream_type; 511 512 ostreambuf_iterator(ostream_type& s) noexcept; 513 ostreambuf_iterator(streambuf_type* s) noexcept; 514 ostreambuf_iterator& operator=(charT c); 515 ostreambuf_iterator& operator*(); 516 ostreambuf_iterator& operator++(); 517 ostreambuf_iterator& operator++(int); 518 bool failed() const noexcept; 519}; 520 521template <class C> constexpr auto begin(C& c) -> decltype(c.begin()); 522template <class C> constexpr auto begin(const C& c) -> decltype(c.begin()); 523template <class C> constexpr auto end(C& c) -> decltype(c.end()); 524template <class C> constexpr auto end(const C& c) -> decltype(c.end()); 525template <class T, size_t N> constexpr T* begin(T (&array)[N]); 526template <class T, size_t N> constexpr T* end(T (&array)[N]); 527 528template <class C> auto constexpr cbegin(const C& c) -> decltype(std::begin(c)); // C++14 529template <class C> auto constexpr cend(const C& c) -> decltype(std::end(c)); // C++14 530template <class C> auto constexpr rbegin(C& c) -> decltype(c.rbegin()); // C++14 531template <class C> auto constexpr rbegin(const C& c) -> decltype(c.rbegin()); // C++14 532template <class C> auto constexpr rend(C& c) -> decltype(c.rend()); // C++14 533template <class C> constexpr auto rend(const C& c) -> decltype(c.rend()); // C++14 534template <class E> reverse_iterator<const E*> constexpr rbegin(initializer_list<E> il); // C++14 535template <class E> reverse_iterator<const E*> constexpr rend(initializer_list<E> il); // C++14 536template <class T, size_t N> reverse_iterator<T*> constexpr rbegin(T (&array)[N]); // C++14 537template <class T, size_t N> reverse_iterator<T*> constexpr rend(T (&array)[N]); // C++14 538template <class C> constexpr auto crbegin(const C& c) -> decltype(std::rbegin(c)); // C++14 539template <class C> constexpr auto crend(const C& c) -> decltype(std::rend(c)); // C++14 540 541// 24.8, container access: 542template <class C> constexpr auto size(const C& c) -> decltype(c.size()); // C++17 543template <class T, size_t N> constexpr size_t size(const T (&array)[N]) noexcept; // C++17 544 545template <class C> constexpr auto ssize(const C& c) 546 -> common_type_t<ptrdiff_t, make_signed_t<decltype(c.size())>>; // C++20 547template <class T, ptrdiff_t> constexpr ptrdiff_t ssize(const T (&array)[N]) noexcept; // C++20 548 549template <class C> constexpr auto empty(const C& c) -> decltype(c.empty()); // C++17 550template <class T, size_t N> constexpr bool empty(const T (&array)[N]) noexcept; // C++17 551template <class E> constexpr bool empty(initializer_list<E> il) noexcept; // C++17 552template <class C> constexpr auto data(C& c) -> decltype(c.data()); // C++17 553template <class C> constexpr auto data(const C& c) -> decltype(c.data()); // C++17 554template <class T, size_t N> constexpr T* data(T (&array)[N]) noexcept; // C++17 555template <class E> constexpr const E* data(initializer_list<E> il) noexcept; // C++17 556 557} // std 558 559*/ 560 561#include <__config> 562#include <__debug> 563#include <__functional_base> 564#include <__iterator/access.h> 565#include <__iterator/advance.h> 566#include <__iterator/back_insert_iterator.h> 567#include <__iterator/concepts.h> 568#include <__iterator/data.h> 569#include <__iterator/default_sentinel.h> 570#include <__iterator/distance.h> 571#include <__iterator/empty.h> 572#include <__iterator/erase_if_container.h> 573#include <__iterator/front_insert_iterator.h> 574#include <__iterator/incrementable_traits.h> 575#include <__iterator/insert_iterator.h> 576#include <__iterator/istreambuf_iterator.h> 577#include <__iterator/istream_iterator.h> 578#include <__iterator/iterator.h> 579#include <__iterator/iterator_traits.h> 580#include <__iterator/iter_move.h> 581#include <__iterator/iter_swap.h> 582#include <__iterator/move_iterator.h> 583#include <__iterator/next.h> 584#include <__iterator/ostreambuf_iterator.h> 585#include <__iterator/ostream_iterator.h> 586#include <__iterator/prev.h> 587#include <__iterator/projected.h> 588#include <__iterator/readable_traits.h> 589#include <__iterator/reverse_access.h> 590#include <__iterator/reverse_iterator.h> 591#include <__iterator/size.h> 592#include <__iterator/wrap_iter.h> 593#include <__memory/addressof.h> 594#include <__memory/pointer_traits.h> 595#include <__utility/forward.h> 596#include <compare> 597#include <concepts> // Mandated by the Standard. 598#include <cstddef> 599#include <initializer_list> 600#include <type_traits> 601#include <version> 602 603#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 604#pragma GCC system_header 605#endif 606 607#endif // _LIBCPP_ITERATOR 608