src/third_party/libc++/trunk/include/iterator

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