1// -*- C++ -*- 2//===-------------------------- iterator ----------------------------------===// 3// 4// The LLVM Compiler Infrastructure 5// 6// This file is dual licensed under the MIT and the University of Illinois Open 7// Source Licenses. See LICENSE.TXT for details. 8// 9//===----------------------------------------------------------------------===// 10 11#ifndef _LIBCPP_ITERATOR 12#define _LIBCPP_ITERATOR 13 14/* 15 iterator synopsis 16 17namespace std 18{ 19 20template<class Iterator> 21struct iterator_traits 22{ 23 typedef typename Iterator::difference_type difference_type; 24 typedef typename Iterator::value_type value_type; 25 typedef typename Iterator::pointer pointer; 26 typedef typename Iterator::reference reference; 27 typedef typename Iterator::iterator_category iterator_category; 28}; 29 30template<class T> 31struct iterator_traits<T*> 32{ 33 typedef ptrdiff_t difference_type; 34 typedef T value_type; 35 typedef T* pointer; 36 typedef T& reference; 37 typedef random_access_iterator_tag iterator_category; 38}; 39 40template<class T> 41struct iterator_traits<const T*> 42{ 43 typedef ptrdiff_t difference_type; 44 typedef T value_type; 45 typedef const T* pointer; 46 typedef const T& reference; 47 typedef random_access_iterator_tag iterator_category; 48}; 49 50template<class Category, class T, class Distance = ptrdiff_t, 51 class Pointer = T*, class Reference = T&> 52struct iterator 53{ 54 typedef T value_type; 55 typedef Distance difference_type; 56 typedef Pointer pointer; 57 typedef Reference reference; 58 typedef Category iterator_category; 59}; 60 61struct input_iterator_tag {}; 62struct output_iterator_tag {}; 63struct forward_iterator_tag : public input_iterator_tag {}; 64struct bidirectional_iterator_tag : public forward_iterator_tag {}; 65struct random_access_iterator_tag : public bidirectional_iterator_tag {}; 66 67// extension: second argument not conforming to C++03 68template <class InputIterator> 69void advance(InputIterator& i, 70 typename iterator_traits<InputIterator>::difference_type n); 71 72template <class InputIterator> 73typename iterator_traits<InputIterator>::difference_type 74distance(InputIterator first, InputIterator last); 75 76template <class Iterator> 77class reverse_iterator 78 : public iterator<typename iterator_traits<Iterator>::iterator_category, 79 typename iterator_traits<Iterator>::value_type, 80 typename iterator_traits<Iterator>::difference_type, 81 typename iterator_traits<Iterator>::pointer, 82 typename iterator_traits<Iterator>::reference> 83{ 84protected: 85 Iterator current; 86public: 87 typedef Iterator iterator_type; 88 typedef typename iterator_traits<Iterator>::difference_type difference_type; 89 typedef typename iterator_traits<Iterator>::reference reference; 90 typedef typename iterator_traits<Iterator>::pointer pointer; 91 92 reverse_iterator(); 93 explicit reverse_iterator(Iterator x); 94 template <class U> reverse_iterator(const reverse_iterator<U>& u); 95 Iterator base() const; 96 reference operator*() const; 97 pointer operator->() const; 98 reverse_iterator& operator++(); 99 reverse_iterator operator++(int); 100 reverse_iterator& operator--(); 101 reverse_iterator operator--(int); 102 reverse_iterator operator+ (difference_type n) const; 103 reverse_iterator& operator+=(difference_type n); 104 reverse_iterator operator- (difference_type n) const; 105 reverse_iterator& operator-=(difference_type n); 106 reference operator[](difference_type n) const; 107}; 108 109template <class Iterator1, class Iterator2> 110bool 111operator==(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 112 113template <class Iterator1, class Iterator2> 114bool 115operator<(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 116 117template <class Iterator1, class Iterator2> 118bool 119operator!=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 120 121template <class Iterator1, class Iterator2> 122bool 123operator>(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 124 125template <class Iterator1, class Iterator2> 126bool 127operator>=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 128 129template <class Iterator1, class Iterator2> 130bool 131operator<=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 132 133template <class Iterator1, class Iterator2> 134auto 135operator-(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y) 136-> decltype(__y.base() - __x.base()); 137 138template <class Iterator> 139reverse_iterator<Iterator> 140operator+(typename reverse_iterator<Iterator>::difference_type n, const reverse_iterator<Iterator>& x); 141 142template <class Iterator> reverse_iterator<Iterator> make_reverse_iterator(Iterator i); // C++14 143 144template <class Container> 145class back_insert_iterator 146{ 147protected: 148 Container* container; 149public: 150 typedef Container container_type; 151 typedef void value_type; 152 typedef void difference_type; 153 typedef void reference; 154 typedef void pointer; 155 156 explicit back_insert_iterator(Container& x); 157 back_insert_iterator& operator=(const typename Container::value_type& value); 158 back_insert_iterator& operator*(); 159 back_insert_iterator& operator++(); 160 back_insert_iterator operator++(int); 161}; 162 163template <class Container> back_insert_iterator<Container> back_inserter(Container& x); 164 165template <class Container> 166class front_insert_iterator 167{ 168protected: 169 Container* container; 170public: 171 typedef Container container_type; 172 typedef void value_type; 173 typedef void difference_type; 174 typedef void reference; 175 typedef void pointer; 176 177 explicit front_insert_iterator(Container& x); 178 front_insert_iterator& operator=(const typename Container::value_type& value); 179 front_insert_iterator& operator*(); 180 front_insert_iterator& operator++(); 181 front_insert_iterator operator++(int); 182}; 183 184template <class Container> front_insert_iterator<Container> front_inserter(Container& x); 185 186template <class Container> 187class insert_iterator 188{ 189protected: 190 Container* container; 191 typename Container::iterator iter; 192public: 193 typedef Container container_type; 194 typedef void value_type; 195 typedef void difference_type; 196 typedef void reference; 197 typedef void pointer; 198 199 insert_iterator(Container& x, typename Container::iterator i); 200 insert_iterator& operator=(const typename Container::value_type& value); 201 insert_iterator& operator*(); 202 insert_iterator& operator++(); 203 insert_iterator& operator++(int); 204}; 205 206template <class Container, class Iterator> 207insert_iterator<Container> inserter(Container& x, Iterator i); 208 209template <class Iterator> 210class move_iterator { 211public: 212 typedef Iterator iterator_type; 213 typedef typename iterator_traits<Iterator>::difference_type difference_type; 214 typedef Iterator pointer; 215 typedef typename iterator_traits<Iterator>::value_type value_type; 216 typedef typename iterator_traits<Iterator>::iterator_category iterator_category; 217 typedef value_type&& reference; 218 219 move_iterator(); 220 explicit move_iterator(Iterator i); 221 template <class U> move_iterator(const move_iterator<U>& u); 222 template <class U> move_iterator& operator=(const move_iterator<U>& u); 223 iterator_type base() const; 224 reference operator*() const; 225 pointer operator->() const; 226 move_iterator& operator++(); 227 move_iterator operator++(int); 228 move_iterator& operator--(); 229 move_iterator operator--(int); 230 move_iterator operator+(difference_type n) const; 231 move_iterator& operator+=(difference_type n); 232 move_iterator operator-(difference_type n) const; 233 move_iterator& operator-=(difference_type n); 234 unspecified operator[](difference_type n) const; 235private: 236 Iterator current; // exposition only 237}; 238 239template <class Iterator1, class Iterator2> 240bool 241operator==(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y); 242 243template <class Iterator1, class Iterator2> 244bool 245operator!=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y); 246 247template <class Iterator1, class Iterator2> 248bool 249operator<(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y); 250 251template <class Iterator1, class Iterator2> 252bool 253operator<=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y); 254 255template <class Iterator1, class Iterator2> 256bool 257operator>(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y); 258 259template <class Iterator1, class Iterator2> 260bool 261operator>=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y); 262 263template <class Iterator1, class Iterator2> 264auto 265operator-(const move_iterator<Iterator1>& x, 266 const move_iterator<Iterator2>& y) -> decltype(x.base() - y.base()); 267 268template <class Iterator> 269move_iterator<Iterator> operator+(typename move_iterator<Iterator>::difference_type n, 270 const move_iterator<Iterator>& x); 271 272template <class Iterator> 273move_iterator<Iterator> make_move_iterator(const Iterator& i); 274 275 276template <class T, class charT = char, class traits = char_traits<charT>, class Distance = ptrdiff_t> 277class istream_iterator 278 : public iterator<input_iterator_tag, T, Distance, const T*, const T&> 279{ 280public: 281 typedef charT char_type; 282 typedef traits traits_type; 283 typedef basic_istream<charT,traits> istream_type; 284 285 constexpr istream_iterator(); 286 istream_iterator(istream_type& s); 287 istream_iterator(const istream_iterator& x); 288 ~istream_iterator(); 289 290 const T& operator*() const; 291 const T* operator->() const; 292 istream_iterator& operator++(); 293 istream_iterator operator++(int); 294}; 295 296template <class T, class charT, class traits, class Distance> 297bool operator==(const istream_iterator<T,charT,traits,Distance>& x, 298 const istream_iterator<T,charT,traits,Distance>& y); 299template <class T, class charT, class traits, class Distance> 300bool operator!=(const istream_iterator<T,charT,traits,Distance>& x, 301 const istream_iterator<T,charT,traits,Distance>& y); 302 303template <class T, class charT = char, class traits = char_traits<charT> > 304class ostream_iterator 305 : public iterator<output_iterator_tag, void, void, void ,void> 306{ 307public: 308 typedef charT char_type; 309 typedef traits traits_type; 310 typedef basic_ostream<charT,traits> ostream_type; 311 312 ostream_iterator(ostream_type& s); 313 ostream_iterator(ostream_type& s, const charT* delimiter); 314 ostream_iterator(const ostream_iterator& x); 315 ~ostream_iterator(); 316 ostream_iterator& operator=(const T& value); 317 318 ostream_iterator& operator*(); 319 ostream_iterator& operator++(); 320 ostream_iterator& operator++(int); 321}; 322 323template<class charT, class traits = char_traits<charT> > 324class istreambuf_iterator 325 : public iterator<input_iterator_tag, charT, 326 typename traits::off_type, unspecified, 327 charT> 328{ 329public: 330 typedef charT char_type; 331 typedef traits traits_type; 332 typedef typename traits::int_type int_type; 333 typedef basic_streambuf<charT,traits> streambuf_type; 334 typedef basic_istream<charT,traits> istream_type; 335 336 istreambuf_iterator() noexcept; 337 istreambuf_iterator(istream_type& s) noexcept; 338 istreambuf_iterator(streambuf_type* s) noexcept; 339 istreambuf_iterator(a-private-type) noexcept; 340 341 charT operator*() const; 342 pointer operator->() const; 343 istreambuf_iterator& operator++(); 344 a-private-type operator++(int); 345 346 bool equal(const istreambuf_iterator& b) const; 347}; 348 349template <class charT, class traits> 350bool operator==(const istreambuf_iterator<charT,traits>& a, 351 const istreambuf_iterator<charT,traits>& b); 352template <class charT, class traits> 353bool operator!=(const istreambuf_iterator<charT,traits>& a, 354 const istreambuf_iterator<charT,traits>& b); 355 356template <class charT, class traits = char_traits<charT> > 357class ostreambuf_iterator 358 : public iterator<output_iterator_tag, void, void, void, void> 359{ 360public: 361 typedef charT char_type; 362 typedef traits traits_type; 363 typedef basic_streambuf<charT,traits> streambuf_type; 364 typedef basic_ostream<charT,traits> ostream_type; 365 366 ostreambuf_iterator(ostream_type& s) noexcept; 367 ostreambuf_iterator(streambuf_type* s) noexcept; 368 ostreambuf_iterator& operator=(charT c); 369 ostreambuf_iterator& operator*(); 370 ostreambuf_iterator& operator++(); 371 ostreambuf_iterator& operator++(int); 372 bool failed() const noexcept; 373}; 374 375template <class C> auto begin(C& c) -> decltype(c.begin()); 376template <class C> auto begin(const C& c) -> decltype(c.begin()); 377template <class C> auto end(C& c) -> decltype(c.end()); 378template <class C> auto end(const C& c) -> decltype(c.end()); 379template <class T, size_t N> T* begin(T (&array)[N]); 380template <class T, size_t N> T* end(T (&array)[N]); 381 382template <class C> auto cbegin(const C& c) -> decltype(std::begin(c)); // C++14 383template <class C> auto cend(const C& c) -> decltype(std::end(c)); // C++14 384template <class C> auto rbegin(C& c) -> decltype(c.rbegin()); // C++14 385template <class C> auto rbegin(const C& c) -> decltype(c.rbegin()); // C++14 386template <class C> auto rend(C& c) -> decltype(c.rend()); // C++14 387template <class C> auto rend(const C& c) -> decltype(c.rend()); // C++14 388template <class E> reverse_iterator<const E*> rbegin(initializer_list<E> il); // C++14 389template <class E> reverse_iterator<const E*> rend(initializer_list<E> il); // C++14 390template <class T, size_t N> reverse_iterator<T*> rbegin(T (&array)[N]); // C++14 391template <class T, size_t N> reverse_iterator<T*> rend(T (&array)[N]); // C++14 392template <class C> auto crbegin(const C& c) -> decltype(std::rbegin(c)); // C++14 393template <class C> auto crend(const C& c) -> decltype(std::rend(c)); // C++14 394 395// 24.8, container access: 396template <class C> constexpr auto size(const C& c) -> decltype(c.size()); // C++17 397template <class T, size_t N> constexpr size_t size(const T (&array)[N]) noexcept; // C++17 398template <class C> constexpr auto empty(const C& c) -> decltype(c.empty()); // C++17 399template <class T, size_t N> constexpr bool empty(const T (&array)[N]) noexcept; // C++17 400template <class E> constexpr bool empty(initializer_list<E> il) noexcept; // C++17 401template <class C> constexpr auto data(C& c) -> decltype(c.data()); // C++17 402template <class C> constexpr auto data(const C& c) -> decltype(c.data()); // C++17 403template <class T, size_t N> constexpr T* data(T (&array)[N]) noexcept; // C++17 404template <class E> constexpr const E* data(initializer_list<E> il) noexcept; // C++17 405 406} // std 407 408*/ 409 410#include <__config> 411#include <iosfwd> // for forward declarations of vector and string. 412#include <__functional_base> 413#include <type_traits> 414#include <cstddef> 415#include <initializer_list> 416#ifdef __APPLE__ 417#include <Availability.h> 418#endif 419 420#include <__debug> 421 422#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 423#pragma GCC system_header 424#endif 425 426_LIBCPP_BEGIN_NAMESPACE_STD 427 428struct _LIBCPP_TYPE_VIS_ONLY input_iterator_tag {}; 429struct _LIBCPP_TYPE_VIS_ONLY output_iterator_tag {}; 430struct _LIBCPP_TYPE_VIS_ONLY forward_iterator_tag : public input_iterator_tag {}; 431struct _LIBCPP_TYPE_VIS_ONLY bidirectional_iterator_tag : public forward_iterator_tag {}; 432struct _LIBCPP_TYPE_VIS_ONLY random_access_iterator_tag : public bidirectional_iterator_tag {}; 433 434template <class _Tp> 435struct __has_iterator_category 436{ 437private: 438 struct __two {char __lx; char __lxx;}; 439 template <class _Up> static __two __test(...); 440 template <class _Up> static char __test(typename _Up::iterator_category* = 0); 441public: 442 static const bool value = sizeof(__test<_Tp>(0)) == 1; 443}; 444 445template <class _Iter, bool> struct __iterator_traits_impl {}; 446 447template <class _Iter> 448struct __iterator_traits_impl<_Iter, true> 449{ 450 typedef typename _Iter::difference_type difference_type; 451 typedef typename _Iter::value_type value_type; 452 typedef typename _Iter::pointer pointer; 453 typedef typename _Iter::reference reference; 454 typedef typename _Iter::iterator_category iterator_category; 455}; 456 457template <class _Iter, bool> struct __iterator_traits {}; 458 459template <class _Iter> 460struct __iterator_traits<_Iter, true> 461 : __iterator_traits_impl 462 < 463 _Iter, 464 is_convertible<typename _Iter::iterator_category, input_iterator_tag>::value || 465 is_convertible<typename _Iter::iterator_category, output_iterator_tag>::value 466 > 467{}; 468 469// iterator_traits<Iterator> will only have the nested types if Iterator::iterator_category 470// exists. Else iterator_traits<Iterator> will be an empty class. This is a 471// conforming extension which allows some programs to compile and behave as 472// the client expects instead of failing at compile time. 473 474template <class _Iter> 475struct _LIBCPP_TYPE_VIS_ONLY iterator_traits 476 : __iterator_traits<_Iter, __has_iterator_category<_Iter>::value> {}; 477 478template<class _Tp> 479struct _LIBCPP_TYPE_VIS_ONLY iterator_traits<_Tp*> 480{ 481 typedef ptrdiff_t difference_type; 482 typedef typename remove_const<_Tp>::type value_type; 483 typedef _Tp* pointer; 484 typedef _Tp& reference; 485 typedef random_access_iterator_tag iterator_category; 486}; 487 488template <class _Tp, class _Up, bool = __has_iterator_category<iterator_traits<_Tp> >::value> 489struct __has_iterator_category_convertible_to 490 : public integral_constant<bool, is_convertible<typename iterator_traits<_Tp>::iterator_category, _Up>::value> 491{}; 492 493template <class _Tp, class _Up> 494struct __has_iterator_category_convertible_to<_Tp, _Up, false> : public false_type {}; 495 496template <class _Tp> 497struct __is_input_iterator : public __has_iterator_category_convertible_to<_Tp, input_iterator_tag> {}; 498 499template <class _Tp> 500struct __is_forward_iterator : public __has_iterator_category_convertible_to<_Tp, forward_iterator_tag> {}; 501 502template <class _Tp> 503struct __is_bidirectional_iterator : public __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag> {}; 504 505template <class _Tp> 506struct __is_random_access_iterator : public __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag> {}; 507 508template <class _Tp> 509struct __is_exactly_input_iterator 510 : public integral_constant<bool, 511 __has_iterator_category_convertible_to<_Tp, input_iterator_tag>::value && 512 !__has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value> {}; 513 514template<class _Category, class _Tp, class _Distance = ptrdiff_t, 515 class _Pointer = _Tp*, class _Reference = _Tp&> 516struct _LIBCPP_TYPE_VIS_ONLY iterator 517{ 518 typedef _Tp value_type; 519 typedef _Distance difference_type; 520 typedef _Pointer pointer; 521 typedef _Reference reference; 522 typedef _Category iterator_category; 523}; 524 525template <class _InputIter> 526inline _LIBCPP_INLINE_VISIBILITY 527void __advance(_InputIter& __i, 528 typename iterator_traits<_InputIter>::difference_type __n, input_iterator_tag) 529{ 530 for (; __n > 0; --__n) 531 ++__i; 532} 533 534template <class _BiDirIter> 535inline _LIBCPP_INLINE_VISIBILITY 536void __advance(_BiDirIter& __i, 537 typename iterator_traits<_BiDirIter>::difference_type __n, bidirectional_iterator_tag) 538{ 539 if (__n >= 0) 540 for (; __n > 0; --__n) 541 ++__i; 542 else 543 for (; __n < 0; ++__n) 544 --__i; 545} 546 547template <class _RandIter> 548inline _LIBCPP_INLINE_VISIBILITY 549void __advance(_RandIter& __i, 550 typename iterator_traits<_RandIter>::difference_type __n, random_access_iterator_tag) 551{ 552 __i += __n; 553} 554 555template <class _InputIter> 556inline _LIBCPP_INLINE_VISIBILITY 557void advance(_InputIter& __i, 558 typename iterator_traits<_InputIter>::difference_type __n) 559{ 560 __advance(__i, __n, typename iterator_traits<_InputIter>::iterator_category()); 561} 562 563template <class _InputIter> 564inline _LIBCPP_INLINE_VISIBILITY 565typename iterator_traits<_InputIter>::difference_type 566__distance(_InputIter __first, _InputIter __last, input_iterator_tag) 567{ 568 typename iterator_traits<_InputIter>::difference_type __r(0); 569 for (; __first != __last; ++__first) 570 ++__r; 571 return __r; 572} 573 574template <class _RandIter> 575inline _LIBCPP_INLINE_VISIBILITY 576typename iterator_traits<_RandIter>::difference_type 577__distance(_RandIter __first, _RandIter __last, random_access_iterator_tag) 578{ 579 return __last - __first; 580} 581 582template <class _InputIter> 583inline _LIBCPP_INLINE_VISIBILITY 584typename iterator_traits<_InputIter>::difference_type 585distance(_InputIter __first, _InputIter __last) 586{ 587 return __distance(__first, __last, typename iterator_traits<_InputIter>::iterator_category()); 588} 589 590template <class _InputIter> 591inline _LIBCPP_INLINE_VISIBILITY 592_InputIter 593next(_InputIter __x, 594 typename iterator_traits<_InputIter>::difference_type __n = 1, 595 typename enable_if<__is_input_iterator<_InputIter>::value>::type* = 0) 596{ 597 _VSTD::advance(__x, __n); 598 return __x; 599} 600 601template <class _BidiretionalIter> 602inline _LIBCPP_INLINE_VISIBILITY 603_BidiretionalIter 604prev(_BidiretionalIter __x, 605 typename iterator_traits<_BidiretionalIter>::difference_type __n = 1, 606 typename enable_if<__is_bidirectional_iterator<_BidiretionalIter>::value>::type* = 0) 607{ 608 _VSTD::advance(__x, -__n); 609 return __x; 610} 611 612template <class _Iter> 613class _LIBCPP_TYPE_VIS_ONLY reverse_iterator 614 : public iterator<typename iterator_traits<_Iter>::iterator_category, 615 typename iterator_traits<_Iter>::value_type, 616 typename iterator_traits<_Iter>::difference_type, 617 typename iterator_traits<_Iter>::pointer, 618 typename iterator_traits<_Iter>::reference> 619{ 620private: 621 mutable _Iter __t; // no longer used as of LWG #2360, not removed due to ABI break 622protected: 623 _Iter current; 624public: 625 typedef _Iter iterator_type; 626 typedef typename iterator_traits<_Iter>::difference_type difference_type; 627 typedef typename iterator_traits<_Iter>::reference reference; 628 typedef typename iterator_traits<_Iter>::pointer pointer; 629 630 _LIBCPP_INLINE_VISIBILITY reverse_iterator() : current() {} 631 _LIBCPP_INLINE_VISIBILITY explicit reverse_iterator(_Iter __x) : __t(__x), current(__x) {} 632 template <class _Up> _LIBCPP_INLINE_VISIBILITY reverse_iterator(const reverse_iterator<_Up>& __u) 633 : __t(__u.base()), current(__u.base()) {} 634 _LIBCPP_INLINE_VISIBILITY _Iter base() const {return current;} 635 _LIBCPP_INLINE_VISIBILITY reference operator*() const {_Iter __tmp = current; return *--__tmp;} 636 _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return _VSTD::addressof(operator*());} 637 _LIBCPP_INLINE_VISIBILITY reverse_iterator& operator++() {--current; return *this;} 638 _LIBCPP_INLINE_VISIBILITY reverse_iterator operator++(int) 639 {reverse_iterator __tmp(*this); --current; return __tmp;} 640 _LIBCPP_INLINE_VISIBILITY reverse_iterator& operator--() {++current; return *this;} 641 _LIBCPP_INLINE_VISIBILITY reverse_iterator operator--(int) 642 {reverse_iterator __tmp(*this); ++current; return __tmp;} 643 _LIBCPP_INLINE_VISIBILITY reverse_iterator operator+ (difference_type __n) const 644 {return reverse_iterator(current - __n);} 645 _LIBCPP_INLINE_VISIBILITY reverse_iterator& operator+=(difference_type __n) 646 {current -= __n; return *this;} 647 _LIBCPP_INLINE_VISIBILITY reverse_iterator operator- (difference_type __n) const 648 {return reverse_iterator(current + __n);} 649 _LIBCPP_INLINE_VISIBILITY reverse_iterator& operator-=(difference_type __n) 650 {current += __n; return *this;} 651 _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const 652 {return *(*this + __n);} 653}; 654 655template <class _Iter1, class _Iter2> 656inline _LIBCPP_INLINE_VISIBILITY 657bool 658operator==(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) 659{ 660 return __x.base() == __y.base(); 661} 662 663template <class _Iter1, class _Iter2> 664inline _LIBCPP_INLINE_VISIBILITY 665bool 666operator<(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) 667{ 668 return __x.base() > __y.base(); 669} 670 671template <class _Iter1, class _Iter2> 672inline _LIBCPP_INLINE_VISIBILITY 673bool 674operator!=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) 675{ 676 return __x.base() != __y.base(); 677} 678 679template <class _Iter1, class _Iter2> 680inline _LIBCPP_INLINE_VISIBILITY 681bool 682operator>(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) 683{ 684 return __x.base() < __y.base(); 685} 686 687template <class _Iter1, class _Iter2> 688inline _LIBCPP_INLINE_VISIBILITY 689bool 690operator>=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) 691{ 692 return __x.base() <= __y.base(); 693} 694 695template <class _Iter1, class _Iter2> 696inline _LIBCPP_INLINE_VISIBILITY 697bool 698operator<=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) 699{ 700 return __x.base() >= __y.base(); 701} 702 703#ifndef _LIBCPP_CXX03_LANG 704template <class _Iter1, class _Iter2> 705inline _LIBCPP_INLINE_VISIBILITY 706auto 707operator-(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) 708-> decltype(__y.base() - __x.base()) 709{ 710 return __y.base() - __x.base(); 711} 712#else 713template <class _Iter1, class _Iter2> 714inline _LIBCPP_INLINE_VISIBILITY 715typename reverse_iterator<_Iter1>::difference_type 716operator-(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) 717{ 718 return __y.base() - __x.base(); 719} 720#endif 721 722template <class _Iter> 723inline _LIBCPP_INLINE_VISIBILITY 724reverse_iterator<_Iter> 725operator+(typename reverse_iterator<_Iter>::difference_type __n, const reverse_iterator<_Iter>& __x) 726{ 727 return reverse_iterator<_Iter>(__x.base() - __n); 728} 729 730#if _LIBCPP_STD_VER > 11 731template <class _Iter> 732inline _LIBCPP_INLINE_VISIBILITY 733reverse_iterator<_Iter> make_reverse_iterator(_Iter __i) 734{ 735 return reverse_iterator<_Iter>(__i); 736} 737#endif 738 739template <class _Container> 740class _LIBCPP_TYPE_VIS_ONLY back_insert_iterator 741 : public iterator<output_iterator_tag, 742 void, 743 void, 744 void, 745 void> 746{ 747protected: 748 _Container* container; 749public: 750 typedef _Container container_type; 751 752 _LIBCPP_INLINE_VISIBILITY explicit back_insert_iterator(_Container& __x) : container(_VSTD::addressof(__x)) {} 753 _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator=(const typename _Container::value_type& __value_) 754 {container->push_back(__value_); return *this;} 755#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 756 _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator=(typename _Container::value_type&& __value_) 757 {container->push_back(_VSTD::move(__value_)); return *this;} 758#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 759 _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator*() {return *this;} 760 _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator++() {return *this;} 761 _LIBCPP_INLINE_VISIBILITY back_insert_iterator operator++(int) {return *this;} 762}; 763 764template <class _Container> 765inline _LIBCPP_INLINE_VISIBILITY 766back_insert_iterator<_Container> 767back_inserter(_Container& __x) 768{ 769 return back_insert_iterator<_Container>(__x); 770} 771 772template <class _Container> 773class _LIBCPP_TYPE_VIS_ONLY front_insert_iterator 774 : public iterator<output_iterator_tag, 775 void, 776 void, 777 void, 778 void> 779{ 780protected: 781 _Container* container; 782public: 783 typedef _Container container_type; 784 785 _LIBCPP_INLINE_VISIBILITY explicit front_insert_iterator(_Container& __x) : container(_VSTD::addressof(__x)) {} 786 _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator=(const typename _Container::value_type& __value_) 787 {container->push_front(__value_); return *this;} 788#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 789 _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator=(typename _Container::value_type&& __value_) 790 {container->push_front(_VSTD::move(__value_)); return *this;} 791#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 792 _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator*() {return *this;} 793 _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator++() {return *this;} 794 _LIBCPP_INLINE_VISIBILITY front_insert_iterator operator++(int) {return *this;} 795}; 796 797template <class _Container> 798inline _LIBCPP_INLINE_VISIBILITY 799front_insert_iterator<_Container> 800front_inserter(_Container& __x) 801{ 802 return front_insert_iterator<_Container>(__x); 803} 804 805template <class _Container> 806class _LIBCPP_TYPE_VIS_ONLY insert_iterator 807 : public iterator<output_iterator_tag, 808 void, 809 void, 810 void, 811 void> 812{ 813protected: 814 _Container* container; 815 typename _Container::iterator iter; 816public: 817 typedef _Container container_type; 818 819 _LIBCPP_INLINE_VISIBILITY insert_iterator(_Container& __x, typename _Container::iterator __i) 820 : container(_VSTD::addressof(__x)), iter(__i) {} 821 _LIBCPP_INLINE_VISIBILITY insert_iterator& operator=(const typename _Container::value_type& __value_) 822 {iter = container->insert(iter, __value_); ++iter; return *this;} 823#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 824 _LIBCPP_INLINE_VISIBILITY insert_iterator& operator=(typename _Container::value_type&& __value_) 825 {iter = container->insert(iter, _VSTD::move(__value_)); ++iter; return *this;} 826#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 827 _LIBCPP_INLINE_VISIBILITY insert_iterator& operator*() {return *this;} 828 _LIBCPP_INLINE_VISIBILITY insert_iterator& operator++() {return *this;} 829 _LIBCPP_INLINE_VISIBILITY insert_iterator& operator++(int) {return *this;} 830}; 831 832template <class _Container> 833inline _LIBCPP_INLINE_VISIBILITY 834insert_iterator<_Container> 835inserter(_Container& __x, typename _Container::iterator __i) 836{ 837 return insert_iterator<_Container>(__x, __i); 838} 839 840template <class _Tp, class _CharT = char, 841 class _Traits = char_traits<_CharT>, class _Distance = ptrdiff_t> 842class _LIBCPP_TYPE_VIS_ONLY istream_iterator 843 : public iterator<input_iterator_tag, _Tp, _Distance, const _Tp*, const _Tp&> 844{ 845public: 846 typedef _CharT char_type; 847 typedef _Traits traits_type; 848 typedef basic_istream<_CharT,_Traits> istream_type; 849private: 850 istream_type* __in_stream_; 851 _Tp __value_; 852public: 853 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR istream_iterator() : __in_stream_(0), __value_() {} 854 _LIBCPP_INLINE_VISIBILITY istream_iterator(istream_type& __s) : __in_stream_(_VSTD::addressof(__s)) 855 { 856 if (!(*__in_stream_ >> __value_)) 857 __in_stream_ = 0; 858 } 859 860 _LIBCPP_INLINE_VISIBILITY const _Tp& operator*() const {return __value_;} 861 _LIBCPP_INLINE_VISIBILITY const _Tp* operator->() const {return _VSTD::addressof((operator*()));} 862 _LIBCPP_INLINE_VISIBILITY istream_iterator& operator++() 863 { 864 if (!(*__in_stream_ >> __value_)) 865 __in_stream_ = 0; 866 return *this; 867 } 868 _LIBCPP_INLINE_VISIBILITY istream_iterator operator++(int) 869 {istream_iterator __t(*this); ++(*this); return __t;} 870 871 friend _LIBCPP_INLINE_VISIBILITY 872 bool operator==(const istream_iterator& __x, const istream_iterator& __y) 873 {return __x.__in_stream_ == __y.__in_stream_;} 874 875 friend _LIBCPP_INLINE_VISIBILITY 876 bool operator!=(const istream_iterator& __x, const istream_iterator& __y) 877 {return !(__x == __y);} 878}; 879 880template <class _Tp, class _CharT = char, class _Traits = char_traits<_CharT> > 881class _LIBCPP_TYPE_VIS_ONLY ostream_iterator 882 : public iterator<output_iterator_tag, void, void, void, void> 883{ 884public: 885 typedef _CharT char_type; 886 typedef _Traits traits_type; 887 typedef basic_ostream<_CharT,_Traits> ostream_type; 888private: 889 ostream_type* __out_stream_; 890 const char_type* __delim_; 891public: 892 _LIBCPP_INLINE_VISIBILITY ostream_iterator(ostream_type& __s) 893 : __out_stream_(_VSTD::addressof(__s)), __delim_(0) {} 894 _LIBCPP_INLINE_VISIBILITY ostream_iterator(ostream_type& __s, const _CharT* __delimiter) 895 : __out_stream_(_VSTD::addressof(__s)), __delim_(__delimiter) {} 896 _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator=(const _Tp& __value_) 897 { 898 *__out_stream_ << __value_; 899 if (__delim_) 900 *__out_stream_ << __delim_; 901 return *this; 902 } 903 904 _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator*() {return *this;} 905 _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator++() {return *this;} 906 _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator++(int) {return *this;} 907}; 908 909template<class _CharT, class _Traits> 910class _LIBCPP_TYPE_VIS_ONLY istreambuf_iterator 911 : public iterator<input_iterator_tag, _CharT, 912 typename _Traits::off_type, _CharT*, 913 _CharT> 914{ 915public: 916 typedef _CharT char_type; 917 typedef _Traits traits_type; 918 typedef typename _Traits::int_type int_type; 919 typedef basic_streambuf<_CharT,_Traits> streambuf_type; 920 typedef basic_istream<_CharT,_Traits> istream_type; 921private: 922 mutable streambuf_type* __sbuf_; 923 924 class __proxy 925 { 926 char_type __keep_; 927 streambuf_type* __sbuf_; 928 _LIBCPP_INLINE_VISIBILITY __proxy(char_type __c, streambuf_type* __s) 929 : __keep_(__c), __sbuf_(__s) {} 930 friend class istreambuf_iterator; 931 public: 932 _LIBCPP_INLINE_VISIBILITY char_type operator*() const {return __keep_;} 933 }; 934 935 _LIBCPP_INLINE_VISIBILITY 936 bool __test_for_eof() const 937 { 938 if (__sbuf_ && traits_type::eq_int_type(__sbuf_->sgetc(), traits_type::eof())) 939 __sbuf_ = 0; 940 return __sbuf_ == 0; 941 } 942public: 943 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR istreambuf_iterator() _NOEXCEPT : __sbuf_(0) {} 944 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(istream_type& __s) _NOEXCEPT 945 : __sbuf_(__s.rdbuf()) {} 946 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(streambuf_type* __s) _NOEXCEPT 947 : __sbuf_(__s) {} 948 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(const __proxy& __p) _NOEXCEPT 949 : __sbuf_(__p.__sbuf_) {} 950 951 _LIBCPP_INLINE_VISIBILITY char_type operator*() const 952 {return static_cast<char_type>(__sbuf_->sgetc());} 953 _LIBCPP_INLINE_VISIBILITY char_type* operator->() const {return nullptr;} 954 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator& operator++() 955 { 956 __sbuf_->sbumpc(); 957 return *this; 958 } 959 _LIBCPP_INLINE_VISIBILITY __proxy operator++(int) 960 { 961 return __proxy(__sbuf_->sbumpc(), __sbuf_); 962 } 963 964 _LIBCPP_INLINE_VISIBILITY bool equal(const istreambuf_iterator& __b) const 965 {return __test_for_eof() == __b.__test_for_eof();} 966}; 967 968template <class _CharT, class _Traits> 969inline _LIBCPP_INLINE_VISIBILITY 970bool operator==(const istreambuf_iterator<_CharT,_Traits>& __a, 971 const istreambuf_iterator<_CharT,_Traits>& __b) 972 {return __a.equal(__b);} 973 974template <class _CharT, class _Traits> 975inline _LIBCPP_INLINE_VISIBILITY 976bool operator!=(const istreambuf_iterator<_CharT,_Traits>& __a, 977 const istreambuf_iterator<_CharT,_Traits>& __b) 978 {return !__a.equal(__b);} 979 980template <class _CharT, class _Traits> 981class _LIBCPP_TYPE_VIS_ONLY ostreambuf_iterator 982 : public iterator<output_iterator_tag, void, void, void, void> 983{ 984public: 985 typedef _CharT char_type; 986 typedef _Traits traits_type; 987 typedef basic_streambuf<_CharT,_Traits> streambuf_type; 988 typedef basic_ostream<_CharT,_Traits> ostream_type; 989private: 990 streambuf_type* __sbuf_; 991public: 992 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator(ostream_type& __s) _NOEXCEPT 993 : __sbuf_(__s.rdbuf()) {} 994 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator(streambuf_type* __s) _NOEXCEPT 995 : __sbuf_(__s) {} 996 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator=(_CharT __c) 997 { 998 if (__sbuf_ && traits_type::eq_int_type(__sbuf_->sputc(__c), traits_type::eof())) 999 __sbuf_ = 0; 1000 return *this; 1001 } 1002 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator*() {return *this;} 1003 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator++() {return *this;} 1004 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator++(int) {return *this;} 1005 _LIBCPP_INLINE_VISIBILITY bool failed() const _NOEXCEPT {return __sbuf_ == 0;} 1006 1007#if !defined(__APPLE__) || \ 1008 (defined(__MAC_OS_X_VERSION_MIN_REQUIRED) && __MAC_OS_X_VERSION_MIN_REQUIRED > __MAC_10_8) || \ 1009 (defined(__IPHONE_OS_VERSION_MIN_REQUIRED) && __IPHONE_OS_VERSION_MIN_REQUIRED > __IPHONE_6_0) 1010 1011 template <class _Ch, class _Tr> 1012 friend 1013 _LIBCPP_HIDDEN 1014 ostreambuf_iterator<_Ch, _Tr> 1015 __pad_and_output(ostreambuf_iterator<_Ch, _Tr> __s, 1016 const _Ch* __ob, const _Ch* __op, const _Ch* __oe, 1017 ios_base& __iob, _Ch __fl); 1018#endif 1019}; 1020 1021template <class _Iter> 1022class _LIBCPP_TYPE_VIS_ONLY move_iterator 1023{ 1024private: 1025 _Iter __i; 1026public: 1027 typedef _Iter iterator_type; 1028 typedef typename iterator_traits<iterator_type>::iterator_category iterator_category; 1029 typedef typename iterator_traits<iterator_type>::value_type value_type; 1030 typedef typename iterator_traits<iterator_type>::difference_type difference_type; 1031 typedef iterator_type pointer; 1032#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1033 typedef typename iterator_traits<iterator_type>::reference __reference; 1034 typedef typename conditional< 1035 is_reference<__reference>::value, 1036 typename remove_reference<__reference>::type&&, 1037 __reference 1038 >::type reference; 1039#else 1040 typedef typename iterator_traits<iterator_type>::reference reference; 1041#endif 1042 1043 _LIBCPP_INLINE_VISIBILITY move_iterator() : __i() {} 1044 _LIBCPP_INLINE_VISIBILITY explicit move_iterator(_Iter __x) : __i(__x) {} 1045 template <class _Up> _LIBCPP_INLINE_VISIBILITY move_iterator(const move_iterator<_Up>& __u) 1046 : __i(__u.base()) {} 1047 _LIBCPP_INLINE_VISIBILITY _Iter base() const {return __i;} 1048 _LIBCPP_INLINE_VISIBILITY reference operator*() const { 1049 return static_cast<reference>(*__i); 1050 } 1051 _LIBCPP_INLINE_VISIBILITY pointer operator->() const { return __i;} 1052 _LIBCPP_INLINE_VISIBILITY move_iterator& operator++() {++__i; return *this;} 1053 _LIBCPP_INLINE_VISIBILITY move_iterator operator++(int) 1054 {move_iterator __tmp(*this); ++__i; return __tmp;} 1055 _LIBCPP_INLINE_VISIBILITY move_iterator& operator--() {--__i; return *this;} 1056 _LIBCPP_INLINE_VISIBILITY move_iterator operator--(int) 1057 {move_iterator __tmp(*this); --__i; return __tmp;} 1058 _LIBCPP_INLINE_VISIBILITY move_iterator operator+ (difference_type __n) const 1059 {return move_iterator(__i + __n);} 1060 _LIBCPP_INLINE_VISIBILITY move_iterator& operator+=(difference_type __n) 1061 {__i += __n; return *this;} 1062 _LIBCPP_INLINE_VISIBILITY move_iterator operator- (difference_type __n) const 1063 {return move_iterator(__i - __n);} 1064 _LIBCPP_INLINE_VISIBILITY move_iterator& operator-=(difference_type __n) 1065 {__i -= __n; return *this;} 1066 _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const 1067 { 1068 return static_cast<reference>(__i[__n]); 1069 } 1070}; 1071 1072template <class _Iter1, class _Iter2> 1073inline _LIBCPP_INLINE_VISIBILITY 1074bool 1075operator==(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y) 1076{ 1077 return __x.base() == __y.base(); 1078} 1079 1080template <class _Iter1, class _Iter2> 1081inline _LIBCPP_INLINE_VISIBILITY 1082bool 1083operator<(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y) 1084{ 1085 return __x.base() < __y.base(); 1086} 1087 1088template <class _Iter1, class _Iter2> 1089inline _LIBCPP_INLINE_VISIBILITY 1090bool 1091operator!=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y) 1092{ 1093 return __x.base() != __y.base(); 1094} 1095 1096template <class _Iter1, class _Iter2> 1097inline _LIBCPP_INLINE_VISIBILITY 1098bool 1099operator>(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y) 1100{ 1101 return __x.base() > __y.base(); 1102} 1103 1104template <class _Iter1, class _Iter2> 1105inline _LIBCPP_INLINE_VISIBILITY 1106bool 1107operator>=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y) 1108{ 1109 return __x.base() >= __y.base(); 1110} 1111 1112template <class _Iter1, class _Iter2> 1113inline _LIBCPP_INLINE_VISIBILITY 1114bool 1115operator<=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y) 1116{ 1117 return __x.base() <= __y.base(); 1118} 1119 1120#ifndef _LIBCPP_CXX03_LANG 1121template <class _Iter1, class _Iter2> 1122inline _LIBCPP_INLINE_VISIBILITY 1123auto 1124operator-(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y) 1125-> decltype(__x.base() - __y.base()) 1126{ 1127 return __x.base() - __y.base(); 1128} 1129#else 1130template <class _Iter1, class _Iter2> 1131inline _LIBCPP_INLINE_VISIBILITY 1132typename move_iterator<_Iter1>::difference_type 1133operator-(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y) 1134{ 1135 return __x.base() - __y.base(); 1136} 1137#endif 1138 1139template <class _Iter> 1140inline _LIBCPP_INLINE_VISIBILITY 1141move_iterator<_Iter> 1142operator+(typename move_iterator<_Iter>::difference_type __n, const move_iterator<_Iter>& __x) 1143{ 1144 return move_iterator<_Iter>(__x.base() + __n); 1145} 1146 1147template <class _Iter> 1148inline _LIBCPP_INLINE_VISIBILITY 1149move_iterator<_Iter> 1150make_move_iterator(_Iter __i) 1151{ 1152 return move_iterator<_Iter>(__i); 1153} 1154 1155// __wrap_iter 1156 1157template <class _Iter> class __wrap_iter; 1158 1159template <class _Iter1, class _Iter2> 1160_LIBCPP_INLINE_VISIBILITY 1161bool 1162operator==(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1163 1164template <class _Iter1, class _Iter2> 1165_LIBCPP_INLINE_VISIBILITY 1166bool 1167operator<(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1168 1169template <class _Iter1, class _Iter2> 1170_LIBCPP_INLINE_VISIBILITY 1171bool 1172operator!=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1173 1174template <class _Iter1, class _Iter2> 1175_LIBCPP_INLINE_VISIBILITY 1176bool 1177operator>(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1178 1179template <class _Iter1, class _Iter2> 1180_LIBCPP_INLINE_VISIBILITY 1181bool 1182operator>=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1183 1184template <class _Iter1, class _Iter2> 1185_LIBCPP_INLINE_VISIBILITY 1186bool 1187operator<=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1188 1189#ifndef _LIBCPP_CXX03_LANG 1190template <class _Iter1, class _Iter2> 1191_LIBCPP_INLINE_VISIBILITY 1192auto 1193operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT 1194-> decltype(__x.base() - __y.base()); 1195#else 1196template <class _Iter1, class _Iter2> 1197_LIBCPP_INLINE_VISIBILITY 1198typename __wrap_iter<_Iter1>::difference_type 1199operator-(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1200#endif 1201 1202template <class _Iter> 1203_LIBCPP_INLINE_VISIBILITY 1204__wrap_iter<_Iter> 1205operator+(typename __wrap_iter<_Iter>::difference_type, __wrap_iter<_Iter>) _NOEXCEPT; 1206 1207template <class _Ip, class _Op> _Op _LIBCPP_INLINE_VISIBILITY copy(_Ip, _Ip, _Op); 1208template <class _B1, class _B2> _B2 _LIBCPP_INLINE_VISIBILITY copy_backward(_B1, _B1, _B2); 1209template <class _Ip, class _Op> _Op _LIBCPP_INLINE_VISIBILITY move(_Ip, _Ip, _Op); 1210template <class _B1, class _B2> _B2 _LIBCPP_INLINE_VISIBILITY move_backward(_B1, _B1, _B2); 1211 1212template <class _Tp> 1213_LIBCPP_INLINE_VISIBILITY 1214typename enable_if 1215< 1216 is_trivially_copy_assignable<_Tp>::value, 1217 _Tp* 1218>::type 1219__unwrap_iter(__wrap_iter<_Tp*>); 1220 1221template <class _Iter> 1222class __wrap_iter 1223{ 1224public: 1225 typedef _Iter iterator_type; 1226 typedef typename iterator_traits<iterator_type>::iterator_category iterator_category; 1227 typedef typename iterator_traits<iterator_type>::value_type value_type; 1228 typedef typename iterator_traits<iterator_type>::difference_type difference_type; 1229 typedef typename iterator_traits<iterator_type>::pointer pointer; 1230 typedef typename iterator_traits<iterator_type>::reference reference; 1231private: 1232 iterator_type __i; 1233public: 1234 _LIBCPP_INLINE_VISIBILITY __wrap_iter() _NOEXCEPT 1235#if _LIBCPP_STD_VER > 11 1236 : __i{} 1237#endif 1238 { 1239#if _LIBCPP_DEBUG_LEVEL >= 2 1240 __get_db()->__insert_i(this); 1241#endif 1242 } 1243 template <class _Up> _LIBCPP_INLINE_VISIBILITY __wrap_iter(const __wrap_iter<_Up>& __u, 1244 typename enable_if<is_convertible<_Up, iterator_type>::value>::type* = 0) _NOEXCEPT 1245 : __i(__u.base()) 1246 { 1247#if _LIBCPP_DEBUG_LEVEL >= 2 1248 __get_db()->__iterator_copy(this, &__u); 1249#endif 1250 } 1251#if _LIBCPP_DEBUG_LEVEL >= 2 1252 _LIBCPP_INLINE_VISIBILITY 1253 __wrap_iter(const __wrap_iter& __x) 1254 : __i(__x.base()) 1255 { 1256 __get_db()->__iterator_copy(this, &__x); 1257 } 1258 _LIBCPP_INLINE_VISIBILITY 1259 __wrap_iter& operator=(const __wrap_iter& __x) 1260 { 1261 if (this != &__x) 1262 { 1263 __get_db()->__iterator_copy(this, &__x); 1264 __i = __x.__i; 1265 } 1266 return *this; 1267 } 1268 _LIBCPP_INLINE_VISIBILITY 1269 ~__wrap_iter() 1270 { 1271 __get_db()->__erase_i(this); 1272 } 1273#endif 1274 _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT 1275 { 1276#if _LIBCPP_DEBUG_LEVEL >= 2 1277 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 1278 "Attempted to dereference a non-dereferenceable iterator"); 1279#endif 1280 return *__i; 1281 } 1282 _LIBCPP_INLINE_VISIBILITY pointer operator->() const _NOEXCEPT 1283 { 1284#if _LIBCPP_DEBUG_LEVEL >= 2 1285 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 1286 "Attempted to dereference a non-dereferenceable iterator"); 1287#endif 1288 return (pointer)_VSTD::addressof(*__i); 1289 } 1290 _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator++() _NOEXCEPT 1291 { 1292#if _LIBCPP_DEBUG_LEVEL >= 2 1293 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 1294 "Attempted to increment non-incrementable iterator"); 1295#endif 1296 ++__i; 1297 return *this; 1298 } 1299 _LIBCPP_INLINE_VISIBILITY __wrap_iter operator++(int) _NOEXCEPT 1300 {__wrap_iter __tmp(*this); ++(*this); return __tmp;} 1301 _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator--() _NOEXCEPT 1302 { 1303#if _LIBCPP_DEBUG_LEVEL >= 2 1304 _LIBCPP_ASSERT(__get_const_db()->__decrementable(this), 1305 "Attempted to decrement non-decrementable iterator"); 1306#endif 1307 --__i; 1308 return *this; 1309 } 1310 _LIBCPP_INLINE_VISIBILITY __wrap_iter operator--(int) _NOEXCEPT 1311 {__wrap_iter __tmp(*this); --(*this); return __tmp;} 1312 _LIBCPP_INLINE_VISIBILITY __wrap_iter operator+ (difference_type __n) const _NOEXCEPT 1313 {__wrap_iter __w(*this); __w += __n; return __w;} 1314 _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator+=(difference_type __n) _NOEXCEPT 1315 { 1316#if _LIBCPP_DEBUG_LEVEL >= 2 1317 _LIBCPP_ASSERT(__get_const_db()->__addable(this, __n), 1318 "Attempted to add/subtract iterator outside of valid range"); 1319#endif 1320 __i += __n; 1321 return *this; 1322 } 1323 _LIBCPP_INLINE_VISIBILITY __wrap_iter operator- (difference_type __n) const _NOEXCEPT 1324 {return *this + (-__n);} 1325 _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator-=(difference_type __n) _NOEXCEPT 1326 {*this += -__n; return *this;} 1327 _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const _NOEXCEPT 1328 { 1329#if _LIBCPP_DEBUG_LEVEL >= 2 1330 _LIBCPP_ASSERT(__get_const_db()->__subscriptable(this, __n), 1331 "Attempted to subscript iterator outside of valid range"); 1332#endif 1333 return __i[__n]; 1334 } 1335 1336 _LIBCPP_INLINE_VISIBILITY iterator_type base() const _NOEXCEPT {return __i;} 1337 1338private: 1339#if _LIBCPP_DEBUG_LEVEL >= 2 1340 _LIBCPP_INLINE_VISIBILITY __wrap_iter(const void* __p, iterator_type __x) : __i(__x) 1341 { 1342 __get_db()->__insert_ic(this, __p); 1343 } 1344#else 1345 _LIBCPP_INLINE_VISIBILITY __wrap_iter(iterator_type __x) _NOEXCEPT : __i(__x) {} 1346#endif 1347 1348 template <class _Up> friend class __wrap_iter; 1349 template <class _CharT, class _Traits, class _Alloc> friend class basic_string; 1350 template <class _Tp, class _Alloc> friend class _LIBCPP_TYPE_VIS_ONLY vector; 1351 1352 template <class _Iter1, class _Iter2> 1353 friend 1354 bool 1355 operator==(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1356 1357 template <class _Iter1, class _Iter2> 1358 friend 1359 bool 1360 operator<(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1361 1362 template <class _Iter1, class _Iter2> 1363 friend 1364 bool 1365 operator!=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1366 1367 template <class _Iter1, class _Iter2> 1368 friend 1369 bool 1370 operator>(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1371 1372 template <class _Iter1, class _Iter2> 1373 friend 1374 bool 1375 operator>=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1376 1377 template <class _Iter1, class _Iter2> 1378 friend 1379 bool 1380 operator<=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1381 1382#ifndef _LIBCPP_CXX03_LANG 1383 template <class _Iter1, class _Iter2> 1384 friend 1385 auto 1386 operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT 1387 -> decltype(__x.base() - __y.base()); 1388#else 1389 template <class _Iter1, class _Iter2> 1390 friend 1391 typename __wrap_iter<_Iter1>::difference_type 1392 operator-(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1393#endif 1394 1395 template <class _Iter1> 1396 friend 1397 __wrap_iter<_Iter1> 1398 operator+(typename __wrap_iter<_Iter1>::difference_type, __wrap_iter<_Iter1>) _NOEXCEPT; 1399 1400 template <class _Ip, class _Op> friend _Op copy(_Ip, _Ip, _Op); 1401 template <class _B1, class _B2> friend _B2 copy_backward(_B1, _B1, _B2); 1402 template <class _Ip, class _Op> friend _Op move(_Ip, _Ip, _Op); 1403 template <class _B1, class _B2> friend _B2 move_backward(_B1, _B1, _B2); 1404 1405 template <class _Tp> 1406 friend 1407 typename enable_if 1408 < 1409 is_trivially_copy_assignable<_Tp>::value, 1410 _Tp* 1411 >::type 1412 __unwrap_iter(__wrap_iter<_Tp*>); 1413}; 1414 1415template <class _Iter1, class _Iter2> 1416inline _LIBCPP_INLINE_VISIBILITY 1417bool 1418operator==(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT 1419{ 1420 return __x.base() == __y.base(); 1421} 1422 1423template <class _Iter1, class _Iter2> 1424inline _LIBCPP_INLINE_VISIBILITY 1425bool 1426operator<(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT 1427{ 1428#if _LIBCPP_DEBUG_LEVEL >= 2 1429 _LIBCPP_ASSERT(__get_const_db()->__less_than_comparable(&__x, &__y), 1430 "Attempted to compare incomparable iterators"); 1431#endif 1432 return __x.base() < __y.base(); 1433} 1434 1435template <class _Iter1, class _Iter2> 1436inline _LIBCPP_INLINE_VISIBILITY 1437bool 1438operator!=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT 1439{ 1440 return !(__x == __y); 1441} 1442 1443template <class _Iter1, class _Iter2> 1444inline _LIBCPP_INLINE_VISIBILITY 1445bool 1446operator>(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT 1447{ 1448 return __y < __x; 1449} 1450 1451template <class _Iter1, class _Iter2> 1452inline _LIBCPP_INLINE_VISIBILITY 1453bool 1454operator>=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT 1455{ 1456 return !(__x < __y); 1457} 1458 1459template <class _Iter1, class _Iter2> 1460inline _LIBCPP_INLINE_VISIBILITY 1461bool 1462operator<=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT 1463{ 1464 return !(__y < __x); 1465} 1466 1467template <class _Iter1> 1468inline _LIBCPP_INLINE_VISIBILITY 1469bool 1470operator!=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT 1471{ 1472 return !(__x == __y); 1473} 1474 1475template <class _Iter1> 1476inline _LIBCPP_INLINE_VISIBILITY 1477bool 1478operator>(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT 1479{ 1480 return __y < __x; 1481} 1482 1483template <class _Iter1> 1484inline _LIBCPP_INLINE_VISIBILITY 1485bool 1486operator>=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT 1487{ 1488 return !(__x < __y); 1489} 1490 1491template <class _Iter1> 1492inline _LIBCPP_INLINE_VISIBILITY 1493bool 1494operator<=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT 1495{ 1496 return !(__y < __x); 1497} 1498 1499#ifndef _LIBCPP_CXX03_LANG 1500template <class _Iter1, class _Iter2> 1501inline _LIBCPP_INLINE_VISIBILITY 1502auto 1503operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT 1504-> decltype(__x.base() - __y.base()) 1505{ 1506#if _LIBCPP_DEBUG_LEVEL >= 2 1507 _LIBCPP_ASSERT(__get_const_db()->__less_than_comparable(&__x, &__y), 1508 "Attempted to subtract incompatible iterators"); 1509#endif 1510 return __x.base() - __y.base(); 1511} 1512#else 1513template <class _Iter1, class _Iter2> 1514inline _LIBCPP_INLINE_VISIBILITY 1515typename __wrap_iter<_Iter1>::difference_type 1516operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT 1517{ 1518#if _LIBCPP_DEBUG_LEVEL >= 2 1519 _LIBCPP_ASSERT(__get_const_db()->__less_than_comparable(&__x, &__y), 1520 "Attempted to subtract incompatible iterators"); 1521#endif 1522 return __x.base() - __y.base(); 1523} 1524#endif 1525 1526template <class _Iter> 1527inline _LIBCPP_INLINE_VISIBILITY 1528__wrap_iter<_Iter> 1529operator+(typename __wrap_iter<_Iter>::difference_type __n, 1530 __wrap_iter<_Iter> __x) _NOEXCEPT 1531{ 1532 __x += __n; 1533 return __x; 1534} 1535 1536template <class _Iter> 1537struct __libcpp_is_trivial_iterator 1538 : public _LIBCPP_BOOL_CONSTANT(is_pointer<_Iter>::value) {}; 1539 1540template <class _Iter> 1541struct __libcpp_is_trivial_iterator<move_iterator<_Iter> > 1542 : public _LIBCPP_BOOL_CONSTANT(__libcpp_is_trivial_iterator<_Iter>::value) {}; 1543 1544template <class _Iter> 1545struct __libcpp_is_trivial_iterator<reverse_iterator<_Iter> > 1546 : public _LIBCPP_BOOL_CONSTANT(__libcpp_is_trivial_iterator<_Iter>::value) {}; 1547 1548template <class _Iter> 1549struct __libcpp_is_trivial_iterator<__wrap_iter<_Iter> > 1550 : public _LIBCPP_BOOL_CONSTANT(__libcpp_is_trivial_iterator<_Iter>::value) {}; 1551 1552 1553template <class _Tp, size_t _Np> 1554inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 1555_Tp* 1556begin(_Tp (&__array)[_Np]) 1557{ 1558 return __array; 1559} 1560 1561template <class _Tp, size_t _Np> 1562inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 1563_Tp* 1564end(_Tp (&__array)[_Np]) 1565{ 1566 return __array + _Np; 1567} 1568 1569#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_TRAILING_RETURN) 1570 1571template <class _Cp> 1572inline _LIBCPP_INLINE_VISIBILITY 1573auto 1574begin(_Cp& __c) -> decltype(__c.begin()) 1575{ 1576 return __c.begin(); 1577} 1578 1579template <class _Cp> 1580inline _LIBCPP_INLINE_VISIBILITY 1581auto 1582begin(const _Cp& __c) -> decltype(__c.begin()) 1583{ 1584 return __c.begin(); 1585} 1586 1587template <class _Cp> 1588inline _LIBCPP_INLINE_VISIBILITY 1589auto 1590end(_Cp& __c) -> decltype(__c.end()) 1591{ 1592 return __c.end(); 1593} 1594 1595template <class _Cp> 1596inline _LIBCPP_INLINE_VISIBILITY 1597auto 1598end(const _Cp& __c) -> decltype(__c.end()) 1599{ 1600 return __c.end(); 1601} 1602 1603#if _LIBCPP_STD_VER > 11 1604 1605template <class _Tp, size_t _Np> 1606inline _LIBCPP_INLINE_VISIBILITY 1607reverse_iterator<_Tp*> rbegin(_Tp (&__array)[_Np]) 1608{ 1609 return reverse_iterator<_Tp*>(__array + _Np); 1610} 1611 1612template <class _Tp, size_t _Np> 1613inline _LIBCPP_INLINE_VISIBILITY 1614reverse_iterator<_Tp*> rend(_Tp (&__array)[_Np]) 1615{ 1616 return reverse_iterator<_Tp*>(__array); 1617} 1618 1619template <class _Ep> 1620inline _LIBCPP_INLINE_VISIBILITY 1621reverse_iterator<const _Ep*> rbegin(initializer_list<_Ep> __il) 1622{ 1623 return reverse_iterator<const _Ep*>(__il.end()); 1624} 1625 1626template <class _Ep> 1627inline _LIBCPP_INLINE_VISIBILITY 1628reverse_iterator<const _Ep*> rend(initializer_list<_Ep> __il) 1629{ 1630 return reverse_iterator<const _Ep*>(__il.begin()); 1631} 1632 1633template <class _Cp> 1634inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 1635auto cbegin(const _Cp& __c) -> decltype(_VSTD::begin(__c)) 1636{ 1637 return _VSTD::begin(__c); 1638} 1639 1640template <class _Cp> 1641inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 1642auto cend(const _Cp& __c) -> decltype(_VSTD::end(__c)) 1643{ 1644 return _VSTD::end(__c); 1645} 1646 1647template <class _Cp> 1648inline _LIBCPP_INLINE_VISIBILITY 1649auto rbegin(_Cp& __c) -> decltype(__c.rbegin()) 1650{ 1651 return __c.rbegin(); 1652} 1653 1654template <class _Cp> 1655inline _LIBCPP_INLINE_VISIBILITY 1656auto rbegin(const _Cp& __c) -> decltype(__c.rbegin()) 1657{ 1658 return __c.rbegin(); 1659} 1660 1661template <class _Cp> 1662inline _LIBCPP_INLINE_VISIBILITY 1663auto rend(_Cp& __c) -> decltype(__c.rend()) 1664{ 1665 return __c.rend(); 1666} 1667 1668template <class _Cp> 1669inline _LIBCPP_INLINE_VISIBILITY 1670auto rend(const _Cp& __c) -> decltype(__c.rend()) 1671{ 1672 return __c.rend(); 1673} 1674 1675template <class _Cp> 1676inline _LIBCPP_INLINE_VISIBILITY 1677auto crbegin(const _Cp& __c) -> decltype(_VSTD::rbegin(__c)) 1678{ 1679 return _VSTD::rbegin(__c); 1680} 1681 1682template <class _Cp> 1683inline _LIBCPP_INLINE_VISIBILITY 1684auto crend(const _Cp& __c) -> decltype(_VSTD::rend(__c)) 1685{ 1686 return _VSTD::rend(__c); 1687} 1688 1689#endif 1690 1691 1692#else // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_TRAILING_RETURN) 1693 1694template <class _Cp> 1695inline _LIBCPP_INLINE_VISIBILITY 1696typename _Cp::iterator 1697begin(_Cp& __c) 1698{ 1699 return __c.begin(); 1700} 1701 1702template <class _Cp> 1703inline _LIBCPP_INLINE_VISIBILITY 1704typename _Cp::const_iterator 1705begin(const _Cp& __c) 1706{ 1707 return __c.begin(); 1708} 1709 1710template <class _Cp> 1711inline _LIBCPP_INLINE_VISIBILITY 1712typename _Cp::iterator 1713end(_Cp& __c) 1714{ 1715 return __c.end(); 1716} 1717 1718template <class _Cp> 1719inline _LIBCPP_INLINE_VISIBILITY 1720typename _Cp::const_iterator 1721end(const _Cp& __c) 1722{ 1723 return __c.end(); 1724} 1725 1726#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_TRAILING_RETURN) 1727 1728#if _LIBCPP_STD_VER > 14 1729template <class _Cont> 1730constexpr auto size(const _Cont& __c) -> decltype(__c.size()) { return __c.size(); } 1731 1732template <class _Tp, size_t _Sz> 1733constexpr size_t size(const _Tp (&__array)[_Sz]) noexcept { return _Sz; } 1734 1735template <class _Cont> 1736constexpr auto empty(const _Cont& __c) -> decltype(__c.empty()) { return __c.empty(); } 1737 1738template <class _Tp, size_t _Sz> 1739constexpr bool empty(const _Tp (&__array)[_Sz]) noexcept { return false; } 1740 1741template <class _Ep> 1742constexpr bool empty(initializer_list<_Ep> __il) noexcept { return __il.size() == 0; } 1743 1744template <class _Cont> constexpr 1745auto data(_Cont& __c) -> decltype(__c.data()) { return __c.data(); } 1746 1747template <class _Cont> constexpr 1748auto data(const _Cont& __c) -> decltype(__c.data()) { return __c.data(); } 1749 1750template <class _Tp, size_t _Sz> 1751constexpr _Tp* data(_Tp (&__array)[_Sz]) noexcept { return __array; } 1752 1753template <class _Ep> 1754constexpr const _Ep* data(initializer_list<_Ep> __il) noexcept { return __il.begin(); } 1755#endif 1756 1757 1758_LIBCPP_END_NAMESPACE_STD 1759 1760#endif // _LIBCPP_ITERATOR 1761