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 128template<class Category, class T, class Distance = ptrdiff_t, 129 class Pointer = T*, class Reference = T&> 130struct iterator // deprecated in C++17 131{ 132 typedef T value_type; 133 typedef Distance difference_type; 134 typedef Pointer pointer; 135 typedef Reference reference; 136 typedef Category iterator_category; 137}; 138 139struct input_iterator_tag {}; 140struct output_iterator_tag {}; 141struct forward_iterator_tag : public input_iterator_tag {}; 142struct bidirectional_iterator_tag : public forward_iterator_tag {}; 143struct random_access_iterator_tag : public bidirectional_iterator_tag {}; 144 145// 27.4.3, iterator operations 146template <class InputIterator, class Distance> // constexpr in C++17 147 constexpr void advance(InputIterator& i, Distance n); 148 149template <class InputIterator> // constexpr in C++17 150 constexpr typename iterator_traits<InputIterator>::difference_type 151 distance(InputIterator first, InputIterator last); 152 153template <class InputIterator> // constexpr in C++17 154 constexpr InputIterator next(InputIterator x, 155typename iterator_traits<InputIterator>::difference_type n = 1); 156 157template <class BidirectionalIterator> // constexpr in C++17 158 constexpr BidirectionalIterator prev(BidirectionalIterator x, 159 typename iterator_traits<BidirectionalIterator>::difference_type n = 1); 160 161// [range.iter.ops], range iterator operations 162namespace ranges { 163 // [range.iter.op.advance], ranges::advance 164 template<input_or_output_iterator I> 165 constexpr void advance(I& i, iter_difference_t<I> n); // since C++20 166 template<input_or_output_iterator I, sentinel_for<I> S> 167 constexpr void advance(I& i, S bound); // since C++20 168 template<input_or_output_iterator I, sentinel_for<I> S> 169 constexpr iter_difference_t<I> advance(I& i, iter_difference_t<I> n, S bound); // since C++20 170} 171 172template <class Iterator> 173class reverse_iterator 174 : public iterator<typename iterator_traits<Iterator>::iterator_category, // until C++17 175 typename iterator_traits<Iterator>::value_type, 176 typename iterator_traits<Iterator>::difference_type, 177 typename iterator_traits<Iterator>::pointer, 178 typename iterator_traits<Iterator>::reference> 179{ 180protected: 181 Iterator current; 182public: 183 typedef Iterator iterator_type; 184 typedef typename iterator_traits<Iterator>::difference_type difference_type; 185 typedef typename iterator_traits<Iterator>::reference reference; 186 typedef typename iterator_traits<Iterator>::pointer pointer; 187 188 constexpr reverse_iterator(); 189 constexpr explicit reverse_iterator(Iterator x); 190 template <class U> constexpr reverse_iterator(const reverse_iterator<U>& u); 191 template <class U> constexpr reverse_iterator& operator=(const reverse_iterator<U>& u); 192 constexpr Iterator base() const; 193 constexpr reference operator*() const; 194 constexpr pointer operator->() const; 195 constexpr reverse_iterator& operator++(); 196 constexpr reverse_iterator operator++(int); 197 constexpr reverse_iterator& operator--(); 198 constexpr reverse_iterator operator--(int); 199 constexpr reverse_iterator operator+ (difference_type n) const; 200 constexpr reverse_iterator& operator+=(difference_type n); 201 constexpr reverse_iterator operator- (difference_type n) const; 202 constexpr reverse_iterator& operator-=(difference_type n); 203 constexpr reference operator[](difference_type n) const; 204}; 205 206template <class Iterator1, class Iterator2> 207constexpr bool // constexpr in C++17 208operator==(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 209 210template <class Iterator1, class Iterator2> 211constexpr bool // constexpr in C++17 212operator<(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 213 214template <class Iterator1, class Iterator2> 215constexpr bool // constexpr in C++17 216operator!=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 217 218template <class Iterator1, class Iterator2> 219constexpr bool // constexpr in C++17 220operator>(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 221 222template <class Iterator1, class Iterator2> 223constexpr bool // constexpr in C++17 224operator>=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 225 226template <class Iterator1, class Iterator2> 227constexpr bool // constexpr in C++17 228operator<=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 229 230template <class Iterator1, class Iterator2> 231constexpr auto 232operator-(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y) 233-> decltype(__y.base() - __x.base()); // constexpr in C++17 234 235template <class Iterator> 236constexpr reverse_iterator<Iterator> 237operator+(typename reverse_iterator<Iterator>::difference_type n, 238 const reverse_iterator<Iterator>& x); // constexpr in C++17 239 240template <class Iterator> 241constexpr reverse_iterator<Iterator> make_reverse_iterator(Iterator i); // C++14, constexpr in C++17 242 243template <class Container> 244class back_insert_iterator 245 : public iterator<output_iterator_tag, void, void, void, void> // until C++17 246{ 247protected: 248 Container* container; 249public: 250 typedef Container container_type; 251 typedef void value_type; 252 typedef void difference_type; // until C++20 253 typedef ptrdiff_t difference_type; // since C++20 254 typedef void reference; 255 typedef void pointer; 256 257 constexpr back_insert_iterator() noexcept = default; // since C++20 258 explicit back_insert_iterator(Container& x); // constexpr in C++20 259 back_insert_iterator& operator=(const typename Container::value_type& value); // constexpr in C++20 260 back_insert_iterator& operator*(); // constexpr in C++20 261 back_insert_iterator& operator++(); // constexpr in C++20 262 back_insert_iterator operator++(int); // constexpr in C++20 263}; 264 265template <class Container> back_insert_iterator<Container> back_inserter(Container& x); // constexpr in C++20 266 267template <class Container> 268class front_insert_iterator 269 : public iterator<output_iterator_tag, void, void, void, void> // until C++17 270{ 271protected: 272 Container* container; 273public: 274 typedef Container container_type; 275 typedef void value_type; 276 typedef void difference_type; // until C++20 277 typedef ptrdiff_t difference_type; // since C++20 278 typedef void reference; 279 typedef void pointer; 280 281 constexpr front_insert_iterator() noexcept = default; // since C++20 282 explicit front_insert_iterator(Container& x); // constexpr in C++20 283 front_insert_iterator& operator=(const typename Container::value_type& value); // constexpr in C++20 284 front_insert_iterator& operator*(); // constexpr in C++20 285 front_insert_iterator& operator++(); // constexpr in C++20 286 front_insert_iterator operator++(int); // constexpr in C++20 287}; 288 289template <class Container> front_insert_iterator<Container> front_inserter(Container& x); // constexpr in C++20 290 291template <class Container> 292class insert_iterator 293 : public iterator<output_iterator_tag, void, void, void, void> // until C++17 294{ 295protected: 296 Container* container; 297 typename Container::iterator iter; 298public: 299 typedef Container container_type; 300 typedef void value_type; 301 typedef void difference_type; // until C++20 302 typedef ptrdiff_t difference_type; // since C++20 303 typedef void reference; 304 typedef void pointer; 305 306 insert_iterator() = default; // since C++20 307 insert_iterator(Container& x, typename Container::iterator i); // constexpr in C++20 308 insert_iterator& operator=(const typename Container::value_type& value); // constexpr in C++20 309 insert_iterator& operator*(); // constexpr in C++20 310 insert_iterator& operator++(); // constexpr in C++20 311 insert_iterator& operator++(int); // constexpr in C++20 312}; 313 314template <class Container, class Iterator> 315insert_iterator<Container> inserter(Container& x, Iterator i); // constexpr in C++20 316 317template <class Iterator> 318class move_iterator { 319public: 320 typedef Iterator iterator_type; 321 typedef typename iterator_traits<Iterator>::difference_type difference_type; 322 typedef Iterator pointer; 323 typedef typename iterator_traits<Iterator>::value_type value_type; 324 typedef typename iterator_traits<Iterator>::iterator_category iterator_category; 325 typedef value_type&& reference; 326 327 constexpr move_iterator(); // all the constexprs are in C++17 328 constexpr explicit move_iterator(Iterator i); 329 template <class U> 330 constexpr move_iterator(const move_iterator<U>& u); 331 template <class U> 332 constexpr move_iterator& operator=(const move_iterator<U>& u); 333 constexpr iterator_type base() const; 334 constexpr reference operator*() const; 335 constexpr pointer operator->() const; 336 constexpr move_iterator& operator++(); 337 constexpr move_iterator operator++(int); 338 constexpr move_iterator& operator--(); 339 constexpr move_iterator operator--(int); 340 constexpr move_iterator operator+(difference_type n) const; 341 constexpr move_iterator& operator+=(difference_type n); 342 constexpr move_iterator operator-(difference_type n) const; 343 constexpr move_iterator& operator-=(difference_type n); 344 constexpr unspecified operator[](difference_type n) const; 345private: 346 Iterator current; // exposition only 347}; 348 349template <class Iterator1, class Iterator2> 350constexpr bool // constexpr in C++17 351operator==(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y); 352 353template <class Iterator1, class Iterator2> 354constexpr bool // constexpr in C++17 355operator!=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y); 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 auto // constexpr in C++17 375operator-(const move_iterator<Iterator1>& x, 376 const move_iterator<Iterator2>& y) -> decltype(x.base() - y.base()); 377 378template <class Iterator> 379constexpr move_iterator<Iterator> operator+( // constexpr in C++17 380 typename move_iterator<Iterator>::difference_type n, 381 const move_iterator<Iterator>& x); 382 383template <class Iterator> // constexpr in C++17 384constexpr move_iterator<Iterator> make_move_iterator(const Iterator& i); 385 386 387template <class T, class charT = char, class traits = char_traits<charT>, class Distance = ptrdiff_t> 388class istream_iterator 389 : public iterator<input_iterator_tag, T, Distance, const T*, const T&> // until C++17 390{ 391public: 392 typedef input_iterator_tag iterator_category; 393 typedef T value_type; 394 typedef Distance difference_type; 395 typedef const T* pointer; 396 typedef const T& reference; 397 398 typedef charT char_type; 399 typedef traits traits_type; 400 typedef basic_istream<charT, traits> istream_type; 401 402 constexpr istream_iterator(); 403 istream_iterator(istream_type& s); 404 istream_iterator(const istream_iterator& x); 405 ~istream_iterator(); 406 407 const T& operator*() const; 408 const T* operator->() const; 409 istream_iterator& operator++(); 410 istream_iterator operator++(int); 411}; 412 413template <class T, class charT, class traits, class Distance> 414bool operator==(const istream_iterator<T,charT,traits,Distance>& x, 415 const istream_iterator<T,charT,traits,Distance>& y); 416template <class T, class charT, class traits, class Distance> 417bool operator!=(const istream_iterator<T,charT,traits,Distance>& x, 418 const istream_iterator<T,charT,traits,Distance>& y); 419 420template <class T, class charT = char, class traits = char_traits<charT> > 421class ostream_iterator 422 : public iterator<output_iterator_tag, void, void, void, void> // until C++17 423{ 424public: 425 typedef output_iterator_tag iterator_category; 426 typedef void value_type; 427 typedef void difference_type; // until C++20 428 typedef ptrdiff_t difference_type; // since C++20 429 typedef void pointer; 430 typedef void reference; 431 432 typedef charT char_type; 433 typedef traits traits_type; 434 typedef basic_ostream<charT,traits> ostream_type; 435 436 constexpr ostream_iterator() noexcept = default; // since C++20 437 ostream_iterator(ostream_type& s); 438 ostream_iterator(ostream_type& s, const charT* delimiter); 439 ostream_iterator(const ostream_iterator& x); 440 ~ostream_iterator(); 441 ostream_iterator& operator=(const T& value); 442 443 ostream_iterator& operator*(); 444 ostream_iterator& operator++(); 445 ostream_iterator& operator++(int); 446}; 447 448template<class charT, class traits = char_traits<charT> > 449class istreambuf_iterator 450 : public iterator<input_iterator_tag, charT, traits::off_type, unspecified, charT> // until C++17 451{ 452public: 453 typedef input_iterator_tag iterator_category; 454 typedef charT value_type; 455 typedef traits::off_type difference_type; 456 typedef unspecified pointer; 457 typedef charT reference; 458 459 typedef charT char_type; 460 typedef traits traits_type; 461 typedef traits::int_type int_type; 462 typedef basic_streambuf<charT, traits> streambuf_type; 463 typedef basic_istream<charT, traits> istream_type; 464 465 istreambuf_iterator() noexcept; 466 istreambuf_iterator(istream_type& s) noexcept; 467 istreambuf_iterator(streambuf_type* s) noexcept; 468 istreambuf_iterator(a-private-type) noexcept; 469 470 charT operator*() const; 471 pointer operator->() const; 472 istreambuf_iterator& operator++(); 473 a-private-type operator++(int); 474 475 bool equal(const istreambuf_iterator& b) const; 476}; 477 478template <class charT, class traits> 479bool operator==(const istreambuf_iterator<charT,traits>& a, 480 const istreambuf_iterator<charT,traits>& b); 481template <class charT, class traits> 482bool operator!=(const istreambuf_iterator<charT,traits>& a, 483 const istreambuf_iterator<charT,traits>& b); 484 485template <class charT, class traits = char_traits<charT> > 486class ostreambuf_iterator 487 : public iterator<output_iterator_tag, void, void, void, void> // until C++17 488{ 489public: 490 typedef output_iterator_tag iterator_category; 491 typedef void value_type; 492 typedef void difference_type; // until C++20 493 typedef ptrdiff_t difference_type; // since C++20 494 typedef void pointer; 495 typedef void reference; 496 497 typedef charT char_type; 498 typedef traits traits_type; 499 typedef basic_streambuf<charT, traits> streambuf_type; 500 typedef basic_ostream<charT, traits> ostream_type; 501 502 constexpr ostreambuf_iterator() noexcept = default; // since C++20 503 ostreambuf_iterator(ostream_type& s) noexcept; 504 ostreambuf_iterator(streambuf_type* s) noexcept; 505 ostreambuf_iterator& operator=(charT c); 506 ostreambuf_iterator& operator*(); 507 ostreambuf_iterator& operator++(); 508 ostreambuf_iterator& operator++(int); 509 bool failed() const noexcept; 510}; 511 512template <class C> constexpr auto begin(C& c) -> decltype(c.begin()); 513template <class C> constexpr auto begin(const C& c) -> decltype(c.begin()); 514template <class C> constexpr auto end(C& c) -> decltype(c.end()); 515template <class C> constexpr auto end(const C& c) -> decltype(c.end()); 516template <class T, size_t N> constexpr T* begin(T (&array)[N]); 517template <class T, size_t N> constexpr T* end(T (&array)[N]); 518 519template <class C> auto constexpr cbegin(const C& c) -> decltype(std::begin(c)); // C++14 520template <class C> auto constexpr cend(const C& c) -> decltype(std::end(c)); // C++14 521template <class C> auto constexpr rbegin(C& c) -> decltype(c.rbegin()); // C++14 522template <class C> auto constexpr rbegin(const C& c) -> decltype(c.rbegin()); // C++14 523template <class C> auto constexpr rend(C& c) -> decltype(c.rend()); // C++14 524template <class C> constexpr auto rend(const C& c) -> decltype(c.rend()); // C++14 525template <class E> reverse_iterator<const E*> constexpr rbegin(initializer_list<E> il); // C++14 526template <class E> reverse_iterator<const E*> constexpr rend(initializer_list<E> il); // C++14 527template <class T, size_t N> reverse_iterator<T*> constexpr rbegin(T (&array)[N]); // C++14 528template <class T, size_t N> reverse_iterator<T*> constexpr rend(T (&array)[N]); // C++14 529template <class C> constexpr auto crbegin(const C& c) -> decltype(std::rbegin(c)); // C++14 530template <class C> constexpr auto crend(const C& c) -> decltype(std::rend(c)); // C++14 531 532// 24.8, container access: 533template <class C> constexpr auto size(const C& c) -> decltype(c.size()); // C++17 534template <class T, size_t N> constexpr size_t size(const T (&array)[N]) noexcept; // C++17 535 536template <class C> constexpr auto ssize(const C& c) 537 -> common_type_t<ptrdiff_t, make_signed_t<decltype(c.size())>>; // C++20 538template <class T, ptrdiff_t> constexpr ptrdiff_t ssize(const T (&array)[N]) noexcept; // C++20 539 540template <class C> constexpr auto empty(const C& c) -> decltype(c.empty()); // C++17 541template <class T, size_t N> constexpr bool empty(const T (&array)[N]) noexcept; // C++17 542template <class E> constexpr bool empty(initializer_list<E> il) noexcept; // C++17 543template <class C> constexpr auto data(C& c) -> decltype(c.data()); // C++17 544template <class C> constexpr auto data(const C& c) -> decltype(c.data()); // C++17 545template <class T, size_t N> constexpr T* data(T (&array)[N]) noexcept; // C++17 546template <class E> constexpr const E* data(initializer_list<E> il) noexcept; // C++17 547 548} // std 549 550*/ 551 552#include <__config> 553#include <__debug> 554#include <__functional_base> 555#include <__iterator/advance.h> 556#include <__iterator/concepts.h> 557#include <__iterator/incrementable_traits.h> 558#include <__iterator/indirect_concepts.h> 559#include <__iterator/iter_move.h> 560#include <__iterator/iterator_traits.h> 561#include <__iterator/next.h> 562#include <__iterator/prev.h> 563#include <__iterator/projected.h> 564#include <__iterator/readable_traits.h> 565#include <__memory/addressof.h> 566#include <__memory/pointer_traits.h> 567#include <compare> 568#include <concepts> // Mandated by the Standard. 569#include <cstddef> 570#include <initializer_list> 571#include <iosfwd> // for forward declarations of vector and string 572#include <type_traits> 573#include <version> 574 575#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 576#pragma GCC system_header 577#endif 578 579_LIBCPP_BEGIN_NAMESPACE_STD 580 581template<class _Category, class _Tp, class _Distance = ptrdiff_t, 582 class _Pointer = _Tp*, class _Reference = _Tp&> 583struct _LIBCPP_TEMPLATE_VIS _LIBCPP_DEPRECATED_IN_CXX17 iterator 584{ 585 typedef _Tp value_type; 586 typedef _Distance difference_type; 587 typedef _Pointer pointer; 588 typedef _Reference reference; 589 typedef _Category iterator_category; 590}; 591 592template <class _InputIter> 593inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 594void __advance(_InputIter& __i, 595 typename iterator_traits<_InputIter>::difference_type __n, input_iterator_tag) 596{ 597 for (; __n > 0; --__n) 598 ++__i; 599} 600 601template <class _BiDirIter> 602inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 603void __advance(_BiDirIter& __i, 604 typename iterator_traits<_BiDirIter>::difference_type __n, bidirectional_iterator_tag) 605{ 606 if (__n >= 0) 607 for (; __n > 0; --__n) 608 ++__i; 609 else 610 for (; __n < 0; ++__n) 611 --__i; 612} 613 614template <class _RandIter> 615inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 616void __advance(_RandIter& __i, 617 typename iterator_traits<_RandIter>::difference_type __n, random_access_iterator_tag) 618{ 619 __i += __n; 620} 621 622template <class _InputIter, class _Distance, 623 class = typename enable_if<is_integral<decltype(_VSTD::__convert_to_integral(declval<_Distance>()))>::value>::type> 624inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 625void advance(_InputIter& __i, _Distance __orig_n) 626{ 627 typedef decltype(_VSTD::__convert_to_integral(__orig_n)) _IntegralSize; 628 _IntegralSize __n = __orig_n; 629 _LIBCPP_ASSERT(__n >= 0 || __is_cpp17_bidirectional_iterator<_InputIter>::value, 630 "Attempt to advance(it, n) with negative n on a non-bidirectional iterator"); 631 _VSTD::__advance(__i, __n, typename iterator_traits<_InputIter>::iterator_category()); 632} 633 634template <class _InputIter> 635inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 636typename iterator_traits<_InputIter>::difference_type 637__distance(_InputIter __first, _InputIter __last, input_iterator_tag) 638{ 639 typename iterator_traits<_InputIter>::difference_type __r(0); 640 for (; __first != __last; ++__first) 641 ++__r; 642 return __r; 643} 644 645template <class _RandIter> 646inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 647typename iterator_traits<_RandIter>::difference_type 648__distance(_RandIter __first, _RandIter __last, random_access_iterator_tag) 649{ 650 return __last - __first; 651} 652 653template <class _InputIter> 654inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 655typename iterator_traits<_InputIter>::difference_type 656distance(_InputIter __first, _InputIter __last) 657{ 658 return _VSTD::__distance(__first, __last, typename iterator_traits<_InputIter>::iterator_category()); 659} 660 661template <class _InputIter> 662inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 663typename enable_if 664< 665 __is_cpp17_input_iterator<_InputIter>::value, 666 _InputIter 667>::type 668next(_InputIter __x, 669 typename iterator_traits<_InputIter>::difference_type __n = 1) 670{ 671 _LIBCPP_ASSERT(__n >= 0 || __is_cpp17_bidirectional_iterator<_InputIter>::value, 672 "Attempt to next(it, n) with negative n on a non-bidirectional iterator"); 673 674 _VSTD::advance(__x, __n); 675 return __x; 676} 677 678template <class _InputIter> 679inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 680typename enable_if 681< 682 __is_cpp17_input_iterator<_InputIter>::value, 683 _InputIter 684>::type 685prev(_InputIter __x, 686 typename iterator_traits<_InputIter>::difference_type __n = 1) 687{ 688 _LIBCPP_ASSERT(__n <= 0 || __is_cpp17_bidirectional_iterator<_InputIter>::value, 689 "Attempt to prev(it, n) with a positive n on a non-bidirectional iterator"); 690 _VSTD::advance(__x, -__n); 691 return __x; 692} 693 694 695template <class _Tp, class = void> 696struct __is_stashing_iterator : false_type {}; 697 698template <class _Tp> 699struct __is_stashing_iterator<_Tp, typename __void_t<typename _Tp::__stashing_iterator_tag>::type> 700 : true_type {}; 701 702_LIBCPP_SUPPRESS_DEPRECATED_PUSH 703template <class _Iter> 704class _LIBCPP_TEMPLATE_VIS reverse_iterator 705#if _LIBCPP_STD_VER <= 14 || !defined(_LIBCPP_ABI_NO_ITERATOR_BASES) 706 : public iterator<typename iterator_traits<_Iter>::iterator_category, 707 typename iterator_traits<_Iter>::value_type, 708 typename iterator_traits<_Iter>::difference_type, 709 typename iterator_traits<_Iter>::pointer, 710 typename iterator_traits<_Iter>::reference> 711#endif 712{ 713_LIBCPP_SUPPRESS_DEPRECATED_POP 714private: 715#ifndef _LIBCPP_ABI_NO_ITERATOR_BASES 716 _Iter __t; // no longer used as of LWG #2360, not removed due to ABI break 717#endif 718 719 static_assert(!__is_stashing_iterator<_Iter>::value, 720 "The specified iterator type cannot be used with reverse_iterator; " 721 "Using stashing iterators with reverse_iterator causes undefined behavior"); 722 723protected: 724 _Iter current; 725public: 726 typedef _Iter iterator_type; 727 typedef typename iterator_traits<_Iter>::difference_type difference_type; 728 typedef typename iterator_traits<_Iter>::reference reference; 729 typedef typename iterator_traits<_Iter>::pointer pointer; 730 typedef _If<__is_cpp17_random_access_iterator<_Iter>::value, 731 random_access_iterator_tag, 732 typename iterator_traits<_Iter>::iterator_category> iterator_category; 733 typedef typename iterator_traits<_Iter>::value_type value_type; 734 735#if _LIBCPP_STD_VER > 17 736 typedef _If<__is_cpp17_random_access_iterator<_Iter>::value, 737 random_access_iterator_tag, 738 bidirectional_iterator_tag> iterator_concept; 739#endif 740 741#ifndef _LIBCPP_ABI_NO_ITERATOR_BASES 742 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 743 reverse_iterator() : __t(), current() {} 744 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 745 explicit reverse_iterator(_Iter __x) : __t(__x), current(__x) {} 746 template <class _Up> 747 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 748 reverse_iterator(const reverse_iterator<_Up>& __u) : __t(__u.base()), current(__u.base()) {} 749 template <class _Up> 750 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 751 reverse_iterator& operator=(const reverse_iterator<_Up>& __u) 752 { __t = current = __u.base(); return *this; } 753#else 754 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 755 reverse_iterator() : current() {} 756 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 757 explicit reverse_iterator(_Iter __x) : current(__x) {} 758 template <class _Up> 759 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 760 reverse_iterator(const reverse_iterator<_Up>& __u) : current(__u.base()) {} 761 template <class _Up> 762 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 763 reverse_iterator& operator=(const reverse_iterator<_Up>& __u) 764 { current = __u.base(); return *this; } 765#endif 766 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 767 _Iter base() const {return current;} 768 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 769 reference operator*() const {_Iter __tmp = current; return *--__tmp;} 770 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 771 pointer operator->() const {return _VSTD::addressof(operator*());} 772 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 773 reverse_iterator& operator++() {--current; return *this;} 774 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 775 reverse_iterator operator++(int) {reverse_iterator __tmp(*this); --current; return __tmp;} 776 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 777 reverse_iterator& operator--() {++current; return *this;} 778 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 779 reverse_iterator operator--(int) {reverse_iterator __tmp(*this); ++current; return __tmp;} 780 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 781 reverse_iterator operator+ (difference_type __n) const {return reverse_iterator(current - __n);} 782 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 783 reverse_iterator& operator+=(difference_type __n) {current -= __n; return *this;} 784 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 785 reverse_iterator operator- (difference_type __n) const {return reverse_iterator(current + __n);} 786 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 787 reverse_iterator& operator-=(difference_type __n) {current += __n; return *this;} 788 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 789 reference operator[](difference_type __n) const {return *(*this + __n);} 790}; 791 792template <class _Iter1, class _Iter2> 793inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 794bool 795operator==(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) 796{ 797 return __x.base() == __y.base(); 798} 799 800template <class _Iter1, class _Iter2> 801inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 802bool 803operator<(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) 804{ 805 return __x.base() > __y.base(); 806} 807 808template <class _Iter1, class _Iter2> 809inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 810bool 811operator!=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) 812{ 813 return __x.base() != __y.base(); 814} 815 816template <class _Iter1, class _Iter2> 817inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 818bool 819operator>(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) 820{ 821 return __x.base() < __y.base(); 822} 823 824template <class _Iter1, class _Iter2> 825inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 826bool 827operator>=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) 828{ 829 return __x.base() <= __y.base(); 830} 831 832template <class _Iter1, class _Iter2> 833inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 834bool 835operator<=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) 836{ 837 return __x.base() >= __y.base(); 838} 839 840#ifndef _LIBCPP_CXX03_LANG 841template <class _Iter1, class _Iter2> 842inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 843auto 844operator-(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) 845-> decltype(__y.base() - __x.base()) 846{ 847 return __y.base() - __x.base(); 848} 849#else 850template <class _Iter1, class _Iter2> 851inline _LIBCPP_INLINE_VISIBILITY 852typename reverse_iterator<_Iter1>::difference_type 853operator-(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) 854{ 855 return __y.base() - __x.base(); 856} 857#endif 858 859template <class _Iter> 860inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 861reverse_iterator<_Iter> 862operator+(typename reverse_iterator<_Iter>::difference_type __n, const reverse_iterator<_Iter>& __x) 863{ 864 return reverse_iterator<_Iter>(__x.base() - __n); 865} 866 867#if _LIBCPP_STD_VER > 11 868template <class _Iter> 869inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 870reverse_iterator<_Iter> make_reverse_iterator(_Iter __i) 871{ 872 return reverse_iterator<_Iter>(__i); 873} 874#endif 875 876_LIBCPP_SUPPRESS_DEPRECATED_PUSH 877template <class _Container> 878class _LIBCPP_TEMPLATE_VIS back_insert_iterator 879#if _LIBCPP_STD_VER <= 14 || !defined(_LIBCPP_ABI_NO_ITERATOR_BASES) 880 : public iterator<output_iterator_tag, void, void, void, void> 881#endif 882{ 883_LIBCPP_SUPPRESS_DEPRECATED_POP 884protected: 885 _Container* container; 886public: 887 typedef output_iterator_tag iterator_category; 888 typedef void value_type; 889#if _LIBCPP_STD_VER > 17 890 typedef ptrdiff_t difference_type; 891#else 892 typedef void difference_type; 893#endif 894 typedef void pointer; 895 typedef void reference; 896 typedef _Container container_type; 897 898#if _LIBCPP_STD_VER > 17 899 _LIBCPP_INLINE_VISIBILITY constexpr back_insert_iterator() noexcept = default; 900#endif 901 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 explicit back_insert_iterator(_Container& __x) : container(_VSTD::addressof(__x)) {} 902 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 back_insert_iterator& operator=(const typename _Container::value_type& __value_) 903 {container->push_back(__value_); return *this;} 904#ifndef _LIBCPP_CXX03_LANG 905 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 back_insert_iterator& operator=(typename _Container::value_type&& __value_) 906 {container->push_back(_VSTD::move(__value_)); return *this;} 907#endif // _LIBCPP_CXX03_LANG 908 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 back_insert_iterator& operator*() {return *this;} 909 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 back_insert_iterator& operator++() {return *this;} 910 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 back_insert_iterator operator++(int) {return *this;} 911}; 912 913template <class _Container> 914inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 915back_insert_iterator<_Container> 916back_inserter(_Container& __x) 917{ 918 return back_insert_iterator<_Container>(__x); 919} 920 921_LIBCPP_SUPPRESS_DEPRECATED_PUSH 922template <class _Container> 923class _LIBCPP_TEMPLATE_VIS front_insert_iterator 924#if _LIBCPP_STD_VER <= 14 || !defined(_LIBCPP_ABI_NO_ITERATOR_BASES) 925 : public iterator<output_iterator_tag, void, void, void, void> 926#endif 927{ 928_LIBCPP_SUPPRESS_DEPRECATED_POP 929protected: 930 _Container* container; 931public: 932 typedef output_iterator_tag iterator_category; 933 typedef void value_type; 934#if _LIBCPP_STD_VER > 17 935 typedef ptrdiff_t difference_type; 936#else 937 typedef void difference_type; 938#endif 939 typedef void pointer; 940 typedef void reference; 941 typedef _Container container_type; 942 943#if _LIBCPP_STD_VER > 17 944 _LIBCPP_INLINE_VISIBILITY constexpr front_insert_iterator() noexcept = default; 945#endif 946 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 explicit front_insert_iterator(_Container& __x) : container(_VSTD::addressof(__x)) {} 947 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 front_insert_iterator& operator=(const typename _Container::value_type& __value_) 948 {container->push_front(__value_); return *this;} 949#ifndef _LIBCPP_CXX03_LANG 950 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 front_insert_iterator& operator=(typename _Container::value_type&& __value_) 951 {container->push_front(_VSTD::move(__value_)); return *this;} 952#endif // _LIBCPP_CXX03_LANG 953 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 front_insert_iterator& operator*() {return *this;} 954 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 front_insert_iterator& operator++() {return *this;} 955 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 front_insert_iterator operator++(int) {return *this;} 956}; 957 958template <class _Container> 959inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 960front_insert_iterator<_Container> 961front_inserter(_Container& __x) 962{ 963 return front_insert_iterator<_Container>(__x); 964} 965 966_LIBCPP_SUPPRESS_DEPRECATED_PUSH 967template <class _Container> 968class _LIBCPP_TEMPLATE_VIS insert_iterator 969#if _LIBCPP_STD_VER <= 14 || !defined(_LIBCPP_ABI_NO_ITERATOR_BASES) 970 : public iterator<output_iterator_tag, void, void, void, void> 971#endif 972{ 973_LIBCPP_SUPPRESS_DEPRECATED_POP 974protected: 975 _Container* container; 976 typename _Container::iterator iter; 977public: 978 typedef output_iterator_tag iterator_category; 979 typedef void value_type; 980#if _LIBCPP_STD_VER > 17 981 typedef ptrdiff_t difference_type; 982#else 983 typedef void difference_type; 984#endif 985 typedef void pointer; 986 typedef void reference; 987 typedef _Container container_type; 988 989#if _LIBCPP_STD_VER > 17 990 _LIBCPP_INLINE_VISIBILITY insert_iterator() = default; 991#endif 992 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 insert_iterator(_Container& __x, typename _Container::iterator __i) 993 : container(_VSTD::addressof(__x)), iter(__i) {} 994 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 insert_iterator& operator=(const typename _Container::value_type& __value_) 995 {iter = container->insert(iter, __value_); ++iter; return *this;} 996#ifndef _LIBCPP_CXX03_LANG 997 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 insert_iterator& operator=(typename _Container::value_type&& __value_) 998 {iter = container->insert(iter, _VSTD::move(__value_)); ++iter; return *this;} 999#endif // _LIBCPP_CXX03_LANG 1000 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 insert_iterator& operator*() {return *this;} 1001 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 insert_iterator& operator++() {return *this;} 1002 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 insert_iterator& operator++(int) {return *this;} 1003}; 1004 1005template <class _Container> 1006inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 1007insert_iterator<_Container> 1008inserter(_Container& __x, typename _Container::iterator __i) 1009{ 1010 return insert_iterator<_Container>(__x, __i); 1011} 1012 1013_LIBCPP_SUPPRESS_DEPRECATED_PUSH 1014template <class _Tp, class _CharT = char, 1015 class _Traits = char_traits<_CharT>, class _Distance = ptrdiff_t> 1016class _LIBCPP_TEMPLATE_VIS istream_iterator 1017#if _LIBCPP_STD_VER <= 14 || !defined(_LIBCPP_ABI_NO_ITERATOR_BASES) 1018 : public iterator<input_iterator_tag, _Tp, _Distance, const _Tp*, const _Tp&> 1019#endif 1020{ 1021_LIBCPP_SUPPRESS_DEPRECATED_POP 1022public: 1023 typedef input_iterator_tag iterator_category; 1024 typedef _Tp value_type; 1025 typedef _Distance difference_type; 1026 typedef const _Tp* pointer; 1027 typedef const _Tp& reference; 1028 typedef _CharT char_type; 1029 typedef _Traits traits_type; 1030 typedef basic_istream<_CharT,_Traits> istream_type; 1031private: 1032 istream_type* __in_stream_; 1033 _Tp __value_; 1034public: 1035 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR istream_iterator() : __in_stream_(nullptr), __value_() {} 1036 _LIBCPP_INLINE_VISIBILITY istream_iterator(istream_type& __s) : __in_stream_(_VSTD::addressof(__s)) 1037 { 1038 if (!(*__in_stream_ >> __value_)) 1039 __in_stream_ = nullptr; 1040 } 1041 1042 _LIBCPP_INLINE_VISIBILITY const _Tp& operator*() const {return __value_;} 1043 _LIBCPP_INLINE_VISIBILITY const _Tp* operator->() const {return _VSTD::addressof((operator*()));} 1044 _LIBCPP_INLINE_VISIBILITY istream_iterator& operator++() 1045 { 1046 if (!(*__in_stream_ >> __value_)) 1047 __in_stream_ = nullptr; 1048 return *this; 1049 } 1050 _LIBCPP_INLINE_VISIBILITY istream_iterator operator++(int) 1051 {istream_iterator __t(*this); ++(*this); return __t;} 1052 1053 template <class _Up, class _CharU, class _TraitsU, class _DistanceU> 1054 friend _LIBCPP_INLINE_VISIBILITY 1055 bool 1056 operator==(const istream_iterator<_Up, _CharU, _TraitsU, _DistanceU>& __x, 1057 const istream_iterator<_Up, _CharU, _TraitsU, _DistanceU>& __y); 1058 1059 template <class _Up, class _CharU, class _TraitsU, class _DistanceU> 1060 friend _LIBCPP_INLINE_VISIBILITY 1061 bool 1062 operator==(const istream_iterator<_Up, _CharU, _TraitsU, _DistanceU>& __x, 1063 const istream_iterator<_Up, _CharU, _TraitsU, _DistanceU>& __y); 1064}; 1065 1066template <class _Tp, class _CharT, class _Traits, class _Distance> 1067inline _LIBCPP_INLINE_VISIBILITY 1068bool 1069operator==(const istream_iterator<_Tp, _CharT, _Traits, _Distance>& __x, 1070 const istream_iterator<_Tp, _CharT, _Traits, _Distance>& __y) 1071{ 1072 return __x.__in_stream_ == __y.__in_stream_; 1073} 1074 1075template <class _Tp, class _CharT, class _Traits, class _Distance> 1076inline _LIBCPP_INLINE_VISIBILITY 1077bool 1078operator!=(const istream_iterator<_Tp, _CharT, _Traits, _Distance>& __x, 1079 const istream_iterator<_Tp, _CharT, _Traits, _Distance>& __y) 1080{ 1081 return !(__x == __y); 1082} 1083 1084_LIBCPP_SUPPRESS_DEPRECATED_PUSH 1085template <class _Tp, class _CharT = char, class _Traits = char_traits<_CharT> > 1086class _LIBCPP_TEMPLATE_VIS ostream_iterator 1087#if _LIBCPP_STD_VER <= 14 || !defined(_LIBCPP_ABI_NO_ITERATOR_BASES) 1088 : public iterator<output_iterator_tag, void, void, void, void> 1089#endif 1090{ 1091_LIBCPP_SUPPRESS_DEPRECATED_POP 1092public: 1093 typedef output_iterator_tag iterator_category; 1094 typedef void value_type; 1095#if _LIBCPP_STD_VER > 17 1096 typedef ptrdiff_t difference_type; 1097#else 1098 typedef void difference_type; 1099#endif 1100 typedef void pointer; 1101 typedef void reference; 1102 typedef _CharT char_type; 1103 typedef _Traits traits_type; 1104 typedef basic_ostream<_CharT, _Traits> ostream_type; 1105 1106private: 1107 ostream_type* __out_stream_; 1108 const char_type* __delim_; 1109public: 1110#if _LIBCPP_STD_VER > 17 1111 _LIBCPP_INLINE_VISIBILITY constexpr ostream_iterator() noexcept = default; 1112#endif 1113 _LIBCPP_INLINE_VISIBILITY ostream_iterator(ostream_type& __s) _NOEXCEPT 1114 : __out_stream_(_VSTD::addressof(__s)), __delim_(nullptr) {} 1115 _LIBCPP_INLINE_VISIBILITY ostream_iterator(ostream_type& __s, const _CharT* __delimiter) _NOEXCEPT 1116 : __out_stream_(_VSTD::addressof(__s)), __delim_(__delimiter) {} 1117 _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator=(const _Tp& __value_) 1118 { 1119 *__out_stream_ << __value_; 1120 if (__delim_) 1121 *__out_stream_ << __delim_; 1122 return *this; 1123 } 1124 1125 _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator*() {return *this;} 1126 _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator++() {return *this;} 1127 _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator++(int) {return *this;} 1128}; 1129 1130_LIBCPP_SUPPRESS_DEPRECATED_PUSH 1131template<class _CharT, class _Traits> 1132class _LIBCPP_TEMPLATE_VIS istreambuf_iterator 1133#if _LIBCPP_STD_VER <= 14 || !defined(_LIBCPP_ABI_NO_ITERATOR_BASES) 1134 : public iterator<input_iterator_tag, _CharT, 1135 typename _Traits::off_type, _CharT*, 1136 _CharT> 1137#endif 1138{ 1139_LIBCPP_SUPPRESS_DEPRECATED_POP 1140public: 1141 typedef input_iterator_tag iterator_category; 1142 typedef _CharT value_type; 1143 typedef typename _Traits::off_type difference_type; 1144 typedef _CharT* pointer; 1145 typedef _CharT reference; 1146 typedef _CharT char_type; 1147 typedef _Traits traits_type; 1148 typedef typename _Traits::int_type int_type; 1149 typedef basic_streambuf<_CharT,_Traits> streambuf_type; 1150 typedef basic_istream<_CharT,_Traits> istream_type; 1151private: 1152 mutable streambuf_type* __sbuf_; 1153 1154 class __proxy 1155 { 1156 char_type __keep_; 1157 streambuf_type* __sbuf_; 1158 _LIBCPP_INLINE_VISIBILITY __proxy(char_type __c, streambuf_type* __s) 1159 : __keep_(__c), __sbuf_(__s) {} 1160 friend class istreambuf_iterator; 1161 public: 1162 _LIBCPP_INLINE_VISIBILITY char_type operator*() const {return __keep_;} 1163 }; 1164 1165 _LIBCPP_INLINE_VISIBILITY 1166 bool __test_for_eof() const 1167 { 1168 if (__sbuf_ && traits_type::eq_int_type(__sbuf_->sgetc(), traits_type::eof())) 1169 __sbuf_ = nullptr; 1170 return __sbuf_ == nullptr; 1171 } 1172public: 1173 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR istreambuf_iterator() _NOEXCEPT : __sbuf_(nullptr) {} 1174 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(istream_type& __s) _NOEXCEPT 1175 : __sbuf_(__s.rdbuf()) {} 1176 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(streambuf_type* __s) _NOEXCEPT 1177 : __sbuf_(__s) {} 1178 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(const __proxy& __p) _NOEXCEPT 1179 : __sbuf_(__p.__sbuf_) {} 1180 1181 _LIBCPP_INLINE_VISIBILITY char_type operator*() const 1182 {return static_cast<char_type>(__sbuf_->sgetc());} 1183 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator& operator++() 1184 { 1185 __sbuf_->sbumpc(); 1186 return *this; 1187 } 1188 _LIBCPP_INLINE_VISIBILITY __proxy operator++(int) 1189 { 1190 return __proxy(__sbuf_->sbumpc(), __sbuf_); 1191 } 1192 1193 _LIBCPP_INLINE_VISIBILITY bool equal(const istreambuf_iterator& __b) const 1194 {return __test_for_eof() == __b.__test_for_eof();} 1195}; 1196 1197template <class _CharT, class _Traits> 1198inline _LIBCPP_INLINE_VISIBILITY 1199bool operator==(const istreambuf_iterator<_CharT,_Traits>& __a, 1200 const istreambuf_iterator<_CharT,_Traits>& __b) 1201 {return __a.equal(__b);} 1202 1203template <class _CharT, class _Traits> 1204inline _LIBCPP_INLINE_VISIBILITY 1205bool operator!=(const istreambuf_iterator<_CharT,_Traits>& __a, 1206 const istreambuf_iterator<_CharT,_Traits>& __b) 1207 {return !__a.equal(__b);} 1208 1209_LIBCPP_SUPPRESS_DEPRECATED_PUSH 1210template <class _CharT, class _Traits> 1211class _LIBCPP_TEMPLATE_VIS ostreambuf_iterator 1212#if _LIBCPP_STD_VER <= 14 || !defined(_LIBCPP_ABI_NO_ITERATOR_BASES) 1213 : public iterator<output_iterator_tag, void, void, void, void> 1214#endif 1215{ 1216_LIBCPP_SUPPRESS_DEPRECATED_POP 1217public: 1218 typedef output_iterator_tag iterator_category; 1219 typedef void value_type; 1220#if _LIBCPP_STD_VER > 17 1221 typedef ptrdiff_t difference_type; 1222#else 1223 typedef void difference_type; 1224#endif 1225 typedef void pointer; 1226 typedef void reference; 1227 typedef _CharT char_type; 1228 typedef _Traits traits_type; 1229 typedef basic_streambuf<_CharT, _Traits> streambuf_type; 1230 typedef basic_ostream<_CharT, _Traits> ostream_type; 1231 1232private: 1233 streambuf_type* __sbuf_; 1234public: 1235#if _LIBCPP_STD_VER > 17 1236 _LIBCPP_INLINE_VISIBILITY constexpr ostreambuf_iterator() noexcept = default; 1237#endif 1238 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator(ostream_type& __s) _NOEXCEPT 1239 : __sbuf_(__s.rdbuf()) {} 1240 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator(streambuf_type* __s) _NOEXCEPT 1241 : __sbuf_(__s) {} 1242 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator=(_CharT __c) 1243 { 1244 if (__sbuf_ && traits_type::eq_int_type(__sbuf_->sputc(__c), traits_type::eof())) 1245 __sbuf_ = nullptr; 1246 return *this; 1247 } 1248 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator*() {return *this;} 1249 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator++() {return *this;} 1250 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator++(int) {return *this;} 1251 _LIBCPP_INLINE_VISIBILITY bool failed() const _NOEXCEPT {return __sbuf_ == nullptr;} 1252 1253 template <class _Ch, class _Tr> 1254 friend 1255 _LIBCPP_HIDDEN 1256 ostreambuf_iterator<_Ch, _Tr> 1257 __pad_and_output(ostreambuf_iterator<_Ch, _Tr> __s, 1258 const _Ch* __ob, const _Ch* __op, const _Ch* __oe, 1259 ios_base& __iob, _Ch __fl); 1260}; 1261 1262template <class _Iter> 1263class _LIBCPP_TEMPLATE_VIS move_iterator 1264{ 1265private: 1266 _Iter __i; 1267public: 1268 typedef _Iter iterator_type; 1269 typedef typename iterator_traits<iterator_type>::value_type value_type; 1270 typedef typename iterator_traits<iterator_type>::difference_type difference_type; 1271 typedef iterator_type pointer; 1272 typedef _If<__is_cpp17_random_access_iterator<_Iter>::value, 1273 random_access_iterator_tag, 1274 typename iterator_traits<_Iter>::iterator_category> iterator_category; 1275#if _LIBCPP_STD_VER > 17 1276 typedef input_iterator_tag iterator_concept; 1277#endif 1278 1279#ifndef _LIBCPP_CXX03_LANG 1280 typedef typename iterator_traits<iterator_type>::reference __reference; 1281 typedef typename conditional< 1282 is_reference<__reference>::value, 1283 typename remove_reference<__reference>::type&&, 1284 __reference 1285 >::type reference; 1286#else 1287 typedef typename iterator_traits<iterator_type>::reference reference; 1288#endif 1289 1290 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1291 move_iterator() : __i() {} 1292 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1293 explicit move_iterator(_Iter __x) : __i(__x) {} 1294 template <class _Up> 1295 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1296 move_iterator(const move_iterator<_Up>& __u) : __i(__u.base()) {} 1297 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 _Iter base() const {return __i;} 1298 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1299 reference operator*() const { return static_cast<reference>(*__i); } 1300 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1301 pointer operator->() const { return __i;} 1302 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1303 move_iterator& operator++() {++__i; return *this;} 1304 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1305 move_iterator operator++(int) {move_iterator __tmp(*this); ++__i; return __tmp;} 1306 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1307 move_iterator& operator--() {--__i; return *this;} 1308 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1309 move_iterator operator--(int) {move_iterator __tmp(*this); --__i; return __tmp;} 1310 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1311 move_iterator operator+ (difference_type __n) const {return move_iterator(__i + __n);} 1312 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1313 move_iterator& operator+=(difference_type __n) {__i += __n; return *this;} 1314 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1315 move_iterator operator- (difference_type __n) const {return move_iterator(__i - __n);} 1316 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1317 move_iterator& operator-=(difference_type __n) {__i -= __n; return *this;} 1318 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1319 reference operator[](difference_type __n) const { return static_cast<reference>(__i[__n]); } 1320}; 1321 1322template <class _Iter1, class _Iter2> 1323inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1324bool 1325operator==(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y) 1326{ 1327 return __x.base() == __y.base(); 1328} 1329 1330template <class _Iter1, class _Iter2> 1331inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1332bool 1333operator<(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y) 1334{ 1335 return __x.base() < __y.base(); 1336} 1337 1338template <class _Iter1, class _Iter2> 1339inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1340bool 1341operator!=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y) 1342{ 1343 return __x.base() != __y.base(); 1344} 1345 1346template <class _Iter1, class _Iter2> 1347inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1348bool 1349operator>(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y) 1350{ 1351 return __x.base() > __y.base(); 1352} 1353 1354template <class _Iter1, class _Iter2> 1355inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1356bool 1357operator>=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y) 1358{ 1359 return __x.base() >= __y.base(); 1360} 1361 1362template <class _Iter1, class _Iter2> 1363inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1364bool 1365operator<=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y) 1366{ 1367 return __x.base() <= __y.base(); 1368} 1369 1370#ifndef _LIBCPP_CXX03_LANG 1371template <class _Iter1, class _Iter2> 1372inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1373auto 1374operator-(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y) 1375-> decltype(__x.base() - __y.base()) 1376{ 1377 return __x.base() - __y.base(); 1378} 1379#else 1380template <class _Iter1, class _Iter2> 1381inline _LIBCPP_INLINE_VISIBILITY 1382typename move_iterator<_Iter1>::difference_type 1383operator-(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y) 1384{ 1385 return __x.base() - __y.base(); 1386} 1387#endif 1388 1389template <class _Iter> 1390inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1391move_iterator<_Iter> 1392operator+(typename move_iterator<_Iter>::difference_type __n, const move_iterator<_Iter>& __x) 1393{ 1394 return move_iterator<_Iter>(__x.base() + __n); 1395} 1396 1397template <class _Iter> 1398inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1399move_iterator<_Iter> 1400make_move_iterator(_Iter __i) 1401{ 1402 return move_iterator<_Iter>(__i); 1403} 1404 1405// __wrap_iter 1406 1407template <class _Iter> class __wrap_iter; 1408 1409template <class _Iter1, class _Iter2> 1410_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG 1411bool 1412operator==(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1413 1414template <class _Iter1, class _Iter2> 1415_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG 1416bool 1417operator<(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1418 1419template <class _Iter1, class _Iter2> 1420_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG 1421bool 1422operator!=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1423 1424template <class _Iter1, class _Iter2> 1425_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG 1426bool 1427operator>(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1428 1429template <class _Iter1, class _Iter2> 1430_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG 1431bool 1432operator>=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1433 1434template <class _Iter1, class _Iter2> 1435_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG 1436bool 1437operator<=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1438 1439#ifndef _LIBCPP_CXX03_LANG 1440template <class _Iter1, class _Iter2> 1441_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG 1442auto 1443operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT 1444-> decltype(__x.base() - __y.base()); 1445#else 1446template <class _Iter1, class _Iter2> 1447_LIBCPP_INLINE_VISIBILITY 1448typename __wrap_iter<_Iter1>::difference_type 1449operator-(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1450#endif 1451 1452template <class _Iter> 1453_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG 1454__wrap_iter<_Iter> 1455operator+(typename __wrap_iter<_Iter>::difference_type, __wrap_iter<_Iter>) _NOEXCEPT; 1456 1457template <class _Ip, class _Op> _Op _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 copy(_Ip, _Ip, _Op); 1458template <class _B1, class _B2> _B2 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 copy_backward(_B1, _B1, _B2); 1459template <class _Ip, class _Op> _Op _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 move(_Ip, _Ip, _Op); 1460template <class _B1, class _B2> _B2 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 move_backward(_B1, _B1, _B2); 1461 1462template <class _Iter> 1463class __wrap_iter 1464{ 1465public: 1466 typedef _Iter iterator_type; 1467 typedef typename iterator_traits<iterator_type>::value_type value_type; 1468 typedef typename iterator_traits<iterator_type>::difference_type difference_type; 1469 typedef typename iterator_traits<iterator_type>::pointer pointer; 1470 typedef typename iterator_traits<iterator_type>::reference reference; 1471 typedef typename iterator_traits<iterator_type>::iterator_category iterator_category; 1472#if _LIBCPP_STD_VER > 17 1473 typedef contiguous_iterator_tag iterator_concept; 1474#endif 1475 1476private: 1477 iterator_type __i; 1478public: 1479 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter() _NOEXCEPT 1480#if _LIBCPP_STD_VER > 11 1481 : __i{} 1482#endif 1483 { 1484#if _LIBCPP_DEBUG_LEVEL == 2 1485 __get_db()->__insert_i(this); 1486#endif 1487 } 1488 template <class _Up> _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG 1489 __wrap_iter(const __wrap_iter<_Up>& __u, 1490 typename enable_if<is_convertible<_Up, iterator_type>::value>::type* = nullptr) _NOEXCEPT 1491 : __i(__u.base()) 1492 { 1493#if _LIBCPP_DEBUG_LEVEL == 2 1494 __get_db()->__iterator_copy(this, &__u); 1495#endif 1496 } 1497#if _LIBCPP_DEBUG_LEVEL == 2 1498 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG 1499 __wrap_iter(const __wrap_iter& __x) 1500 : __i(__x.base()) 1501 { 1502 __get_db()->__iterator_copy(this, &__x); 1503 } 1504 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG 1505 __wrap_iter& operator=(const __wrap_iter& __x) 1506 { 1507 if (this != &__x) 1508 { 1509 __get_db()->__iterator_copy(this, &__x); 1510 __i = __x.__i; 1511 } 1512 return *this; 1513 } 1514 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG 1515 ~__wrap_iter() 1516 { 1517 __get_db()->__erase_i(this); 1518 } 1519#endif 1520 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG reference operator*() const _NOEXCEPT 1521 { 1522#if _LIBCPP_DEBUG_LEVEL == 2 1523 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 1524 "Attempted to dereference a non-dereferenceable iterator"); 1525#endif 1526 return *__i; 1527 } 1528 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG pointer operator->() const _NOEXCEPT 1529 { 1530#if _LIBCPP_DEBUG_LEVEL == 2 1531 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 1532 "Attempted to dereference a non-dereferenceable iterator"); 1533#endif 1534 return _VSTD::__to_address(__i); 1535 } 1536 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter& operator++() _NOEXCEPT 1537 { 1538#if _LIBCPP_DEBUG_LEVEL == 2 1539 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 1540 "Attempted to increment a non-incrementable iterator"); 1541#endif 1542 ++__i; 1543 return *this; 1544 } 1545 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter operator++(int) _NOEXCEPT 1546 {__wrap_iter __tmp(*this); ++(*this); return __tmp;} 1547 1548 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter& operator--() _NOEXCEPT 1549 { 1550#if _LIBCPP_DEBUG_LEVEL == 2 1551 _LIBCPP_ASSERT(__get_const_db()->__decrementable(this), 1552 "Attempted to decrement a non-decrementable iterator"); 1553#endif 1554 --__i; 1555 return *this; 1556 } 1557 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter operator--(int) _NOEXCEPT 1558 {__wrap_iter __tmp(*this); --(*this); return __tmp;} 1559 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter operator+ (difference_type __n) const _NOEXCEPT 1560 {__wrap_iter __w(*this); __w += __n; return __w;} 1561 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter& operator+=(difference_type __n) _NOEXCEPT 1562 { 1563#if _LIBCPP_DEBUG_LEVEL == 2 1564 _LIBCPP_ASSERT(__get_const_db()->__addable(this, __n), 1565 "Attempted to add/subtract an iterator outside its valid range"); 1566#endif 1567 __i += __n; 1568 return *this; 1569 } 1570 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter operator- (difference_type __n) const _NOEXCEPT 1571 {return *this + (-__n);} 1572 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter& operator-=(difference_type __n) _NOEXCEPT 1573 {*this += -__n; return *this;} 1574 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG reference operator[](difference_type __n) const _NOEXCEPT 1575 { 1576#if _LIBCPP_DEBUG_LEVEL == 2 1577 _LIBCPP_ASSERT(__get_const_db()->__subscriptable(this, __n), 1578 "Attempted to subscript an iterator outside its valid range"); 1579#endif 1580 return __i[__n]; 1581 } 1582 1583 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG iterator_type base() const _NOEXCEPT {return __i;} 1584 1585private: 1586#if _LIBCPP_DEBUG_LEVEL == 2 1587 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter(const void* __p, iterator_type __x) : __i(__x) 1588 { 1589 __get_db()->__insert_ic(this, __p); 1590 } 1591#else 1592 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter(iterator_type __x) _NOEXCEPT : __i(__x) {} 1593#endif 1594 1595 template <class _Up> friend class __wrap_iter; 1596 template <class _CharT, class _Traits, class _Alloc> friend class basic_string; 1597 template <class _Tp, class _Alloc> friend class _LIBCPP_TEMPLATE_VIS vector; 1598 template <class _Tp, size_t> friend class _LIBCPP_TEMPLATE_VIS span; 1599 1600 template <class _Iter1, class _Iter2> 1601 _LIBCPP_CONSTEXPR_IF_NODEBUG friend 1602 bool 1603 operator==(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1604 1605 template <class _Iter1, class _Iter2> 1606 _LIBCPP_CONSTEXPR_IF_NODEBUG friend 1607 bool 1608 operator<(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1609 1610 template <class _Iter1, class _Iter2> 1611 _LIBCPP_CONSTEXPR_IF_NODEBUG friend 1612 bool 1613 operator!=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1614 1615 template <class _Iter1, class _Iter2> 1616 _LIBCPP_CONSTEXPR_IF_NODEBUG friend 1617 bool 1618 operator>(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1619 1620 template <class _Iter1, class _Iter2> 1621 _LIBCPP_CONSTEXPR_IF_NODEBUG friend 1622 bool 1623 operator>=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1624 1625 template <class _Iter1, class _Iter2> 1626 _LIBCPP_CONSTEXPR_IF_NODEBUG friend 1627 bool 1628 operator<=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1629 1630#ifndef _LIBCPP_CXX03_LANG 1631 template <class _Iter1, class _Iter2> 1632 _LIBCPP_CONSTEXPR_IF_NODEBUG friend 1633 auto 1634 operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT 1635 -> decltype(__x.base() - __y.base()); 1636#else 1637 template <class _Iter1, class _Iter2> 1638 _LIBCPP_CONSTEXPR_IF_NODEBUG friend 1639 typename __wrap_iter<_Iter1>::difference_type 1640 operator-(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1641#endif 1642 1643 template <class _Iter1> 1644 _LIBCPP_CONSTEXPR_IF_NODEBUG friend 1645 __wrap_iter<_Iter1> 1646 operator+(typename __wrap_iter<_Iter1>::difference_type, __wrap_iter<_Iter1>) _NOEXCEPT; 1647}; 1648 1649#if _LIBCPP_STD_VER <= 17 1650template <class _It> 1651struct __is_cpp17_contiguous_iterator<__wrap_iter<_It> > : true_type {}; 1652#endif 1653 1654template <class _Iter> 1655_LIBCPP_CONSTEXPR 1656decltype(_VSTD::__to_address(declval<_Iter>())) 1657__to_address(__wrap_iter<_Iter> __w) _NOEXCEPT { 1658 return _VSTD::__to_address(__w.base()); 1659} 1660 1661template <class _Iter1, class _Iter2> 1662inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG 1663bool 1664operator==(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT 1665{ 1666 return __x.base() == __y.base(); 1667} 1668 1669template <class _Iter1, class _Iter2> 1670inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG 1671bool 1672operator<(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT 1673{ 1674#if _LIBCPP_DEBUG_LEVEL == 2 1675 _LIBCPP_ASSERT(__get_const_db()->__less_than_comparable(&__x, &__y), 1676 "Attempted to compare incomparable iterators"); 1677#endif 1678 return __x.base() < __y.base(); 1679} 1680 1681template <class _Iter1, class _Iter2> 1682inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG 1683bool 1684operator!=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT 1685{ 1686 return !(__x == __y); 1687} 1688 1689template <class _Iter1, class _Iter2> 1690inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG 1691bool 1692operator>(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT 1693{ 1694 return __y < __x; 1695} 1696 1697template <class _Iter1, class _Iter2> 1698inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG 1699bool 1700operator>=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT 1701{ 1702 return !(__x < __y); 1703} 1704 1705template <class _Iter1, class _Iter2> 1706inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG 1707bool 1708operator<=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT 1709{ 1710 return !(__y < __x); 1711} 1712 1713template <class _Iter1> 1714inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG 1715bool 1716operator!=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT 1717{ 1718 return !(__x == __y); 1719} 1720 1721template <class _Iter1> 1722inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG 1723bool 1724operator>(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT 1725{ 1726 return __y < __x; 1727} 1728 1729template <class _Iter1> 1730inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG 1731bool 1732operator>=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT 1733{ 1734 return !(__x < __y); 1735} 1736 1737template <class _Iter1> 1738inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG 1739bool 1740operator<=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT 1741{ 1742 return !(__y < __x); 1743} 1744 1745#ifndef _LIBCPP_CXX03_LANG 1746template <class _Iter1, class _Iter2> 1747inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG 1748auto 1749operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT 1750-> decltype(__x.base() - __y.base()) 1751{ 1752#if _LIBCPP_DEBUG_LEVEL == 2 1753 _LIBCPP_ASSERT(__get_const_db()->__less_than_comparable(&__x, &__y), 1754 "Attempted to subtract incompatible iterators"); 1755#endif 1756 return __x.base() - __y.base(); 1757} 1758#else 1759template <class _Iter1, class _Iter2> 1760inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG 1761typename __wrap_iter<_Iter1>::difference_type 1762operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT 1763{ 1764#if _LIBCPP_DEBUG_LEVEL == 2 1765 _LIBCPP_ASSERT(__get_const_db()->__less_than_comparable(&__x, &__y), 1766 "Attempted to subtract incompatible iterators"); 1767#endif 1768 return __x.base() - __y.base(); 1769} 1770#endif 1771 1772template <class _Iter> 1773inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG 1774__wrap_iter<_Iter> 1775operator+(typename __wrap_iter<_Iter>::difference_type __n, 1776 __wrap_iter<_Iter> __x) _NOEXCEPT 1777{ 1778 __x += __n; 1779 return __x; 1780} 1781 1782template <class _Tp, size_t _Np> 1783_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 1784_Tp* 1785begin(_Tp (&__array)[_Np]) 1786{ 1787 return __array; 1788} 1789 1790template <class _Tp, size_t _Np> 1791_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 1792_Tp* 1793end(_Tp (&__array)[_Np]) 1794{ 1795 return __array + _Np; 1796} 1797 1798#if !defined(_LIBCPP_CXX03_LANG) 1799 1800template <class _Cp> 1801_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1802auto 1803begin(_Cp& __c) -> decltype(__c.begin()) 1804{ 1805 return __c.begin(); 1806} 1807 1808template <class _Cp> 1809_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1810auto 1811begin(const _Cp& __c) -> decltype(__c.begin()) 1812{ 1813 return __c.begin(); 1814} 1815 1816template <class _Cp> 1817_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1818auto 1819end(_Cp& __c) -> decltype(__c.end()) 1820{ 1821 return __c.end(); 1822} 1823 1824template <class _Cp> 1825_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1826auto 1827end(const _Cp& __c) -> decltype(__c.end()) 1828{ 1829 return __c.end(); 1830} 1831 1832#if _LIBCPP_STD_VER > 11 1833 1834template <class _Tp, size_t _Np> 1835_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1836reverse_iterator<_Tp*> rbegin(_Tp (&__array)[_Np]) 1837{ 1838 return reverse_iterator<_Tp*>(__array + _Np); 1839} 1840 1841template <class _Tp, size_t _Np> 1842_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1843reverse_iterator<_Tp*> rend(_Tp (&__array)[_Np]) 1844{ 1845 return reverse_iterator<_Tp*>(__array); 1846} 1847 1848template <class _Ep> 1849_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1850reverse_iterator<const _Ep*> rbegin(initializer_list<_Ep> __il) 1851{ 1852 return reverse_iterator<const _Ep*>(__il.end()); 1853} 1854 1855template <class _Ep> 1856_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1857reverse_iterator<const _Ep*> rend(initializer_list<_Ep> __il) 1858{ 1859 return reverse_iterator<const _Ep*>(__il.begin()); 1860} 1861 1862template <class _Cp> 1863_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 1864auto cbegin(const _Cp& __c) -> decltype(_VSTD::begin(__c)) 1865{ 1866 return _VSTD::begin(__c); 1867} 1868 1869template <class _Cp> 1870_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 1871auto cend(const _Cp& __c) -> decltype(_VSTD::end(__c)) 1872{ 1873 return _VSTD::end(__c); 1874} 1875 1876template <class _Cp> 1877_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1878auto rbegin(_Cp& __c) -> decltype(__c.rbegin()) 1879{ 1880 return __c.rbegin(); 1881} 1882 1883template <class _Cp> 1884_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1885auto rbegin(const _Cp& __c) -> decltype(__c.rbegin()) 1886{ 1887 return __c.rbegin(); 1888} 1889 1890template <class _Cp> 1891_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1892auto rend(_Cp& __c) -> decltype(__c.rend()) 1893{ 1894 return __c.rend(); 1895} 1896 1897template <class _Cp> 1898_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1899auto rend(const _Cp& __c) -> decltype(__c.rend()) 1900{ 1901 return __c.rend(); 1902} 1903 1904template <class _Cp> 1905_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1906auto crbegin(const _Cp& __c) -> decltype(_VSTD::rbegin(__c)) 1907{ 1908 return _VSTD::rbegin(__c); 1909} 1910 1911template <class _Cp> 1912_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 1913auto crend(const _Cp& __c) -> decltype(_VSTD::rend(__c)) 1914{ 1915 return _VSTD::rend(__c); 1916} 1917 1918#endif 1919 1920 1921#else // defined(_LIBCPP_CXX03_LANG) 1922 1923template <class _Cp> 1924_LIBCPP_INLINE_VISIBILITY 1925typename _Cp::iterator 1926begin(_Cp& __c) 1927{ 1928 return __c.begin(); 1929} 1930 1931template <class _Cp> 1932_LIBCPP_INLINE_VISIBILITY 1933typename _Cp::const_iterator 1934begin(const _Cp& __c) 1935{ 1936 return __c.begin(); 1937} 1938 1939template <class _Cp> 1940_LIBCPP_INLINE_VISIBILITY 1941typename _Cp::iterator 1942end(_Cp& __c) 1943{ 1944 return __c.end(); 1945} 1946 1947template <class _Cp> 1948_LIBCPP_INLINE_VISIBILITY 1949typename _Cp::const_iterator 1950end(const _Cp& __c) 1951{ 1952 return __c.end(); 1953} 1954 1955#endif // !defined(_LIBCPP_CXX03_LANG) 1956 1957#if _LIBCPP_STD_VER > 14 1958 1959// #if _LIBCPP_STD_VER > 11 1960// template <> 1961// struct _LIBCPP_TEMPLATE_VIS plus<void> 1962// { 1963// template <class _T1, class _T2> 1964// _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY 1965// auto operator()(_T1&& __t, _T2&& __u) const 1966// _NOEXCEPT_(noexcept(_VSTD::forward<_T1>(__t) + _VSTD::forward<_T2>(__u))) 1967// -> decltype (_VSTD::forward<_T1>(__t) + _VSTD::forward<_T2>(__u)) 1968// { return _VSTD::forward<_T1>(__t) + _VSTD::forward<_T2>(__u); } 1969// typedef void is_transparent; 1970// }; 1971// #endif 1972 1973template <class _Cont> 1974_LIBCPP_INLINE_VISIBILITY 1975constexpr auto size(const _Cont& __c) 1976_NOEXCEPT_(noexcept(__c.size())) 1977-> decltype (__c.size()) 1978{ return __c.size(); } 1979 1980template <class _Tp, size_t _Sz> 1981_LIBCPP_INLINE_VISIBILITY 1982constexpr size_t size(const _Tp (&)[_Sz]) noexcept { return _Sz; } 1983 1984#if _LIBCPP_STD_VER > 17 1985template <class _Cont> 1986_LIBCPP_INLINE_VISIBILITY 1987constexpr auto ssize(const _Cont& __c) 1988_NOEXCEPT_(noexcept(static_cast<common_type_t<ptrdiff_t, make_signed_t<decltype(__c.size())>>>(__c.size()))) 1989-> common_type_t<ptrdiff_t, make_signed_t<decltype(__c.size())>> 1990{ return static_cast<common_type_t<ptrdiff_t, make_signed_t<decltype(__c.size())>>>(__c.size()); } 1991 1992template <class _Tp, ptrdiff_t _Sz> 1993_LIBCPP_INLINE_VISIBILITY 1994constexpr ptrdiff_t ssize(const _Tp (&)[_Sz]) noexcept { return _Sz; } 1995#endif 1996 1997template <class _Cont> 1998_LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 1999constexpr auto empty(const _Cont& __c) 2000_NOEXCEPT_(noexcept(__c.empty())) 2001-> decltype (__c.empty()) 2002{ return __c.empty(); } 2003 2004template <class _Tp, size_t _Sz> 2005_LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 2006constexpr bool empty(const _Tp (&)[_Sz]) noexcept { return false; } 2007 2008template <class _Ep> 2009_LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 2010constexpr bool empty(initializer_list<_Ep> __il) noexcept { return __il.size() == 0; } 2011 2012template <class _Cont> constexpr 2013_LIBCPP_INLINE_VISIBILITY 2014auto data(_Cont& __c) 2015_NOEXCEPT_(noexcept(__c.data())) 2016-> decltype (__c.data()) 2017{ return __c.data(); } 2018 2019template <class _Cont> constexpr 2020_LIBCPP_INLINE_VISIBILITY 2021auto data(const _Cont& __c) 2022_NOEXCEPT_(noexcept(__c.data())) 2023-> decltype (__c.data()) 2024{ return __c.data(); } 2025 2026template <class _Tp, size_t _Sz> 2027_LIBCPP_INLINE_VISIBILITY 2028constexpr _Tp* data(_Tp (&__array)[_Sz]) noexcept { return __array; } 2029 2030template <class _Ep> 2031_LIBCPP_INLINE_VISIBILITY 2032constexpr const _Ep* data(initializer_list<_Ep> __il) noexcept { return __il.begin(); } 2033#endif 2034 2035template <class _Container, class _Predicate> 2036typename _Container::size_type 2037__libcpp_erase_if_container(_Container& __c, _Predicate& __pred) { 2038 typename _Container::size_type __old_size = __c.size(); 2039 2040 const typename _Container::iterator __last = __c.end(); 2041 for (typename _Container::iterator __iter = __c.begin(); __iter != __last;) { 2042 if (__pred(*__iter)) 2043 __iter = __c.erase(__iter); 2044 else 2045 ++__iter; 2046 } 2047 2048 return __old_size - __c.size(); 2049} 2050 2051_LIBCPP_END_NAMESPACE_STD 2052 2053#endif // _LIBCPP_ITERATOR 2054