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