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