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