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

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