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