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 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 }  // std
 313
 314 */
 315
 316 #include <__config>
 317 #include <type_traits>
 318 #include <cstddef>
 319 #include <iosfwd>
 320 #ifdef __APPLE__
 321 #include <Availability.h>
 322 #endif
 323
 324 #ifdef _LIBCPP_DEBUG
 325 #include <cassert>
 326 #endif
 327
 328 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 329 #pragma GCC system_header
 330 #endif
 331
 332 _LIBCPP_BEGIN_NAMESPACE_STD
 333
 334 struct _LIBCPP_TYPE_VIS input_iterator_tag {};
 335 struct _LIBCPP_TYPE_VIS output_iterator_tag {};
 336 struct _LIBCPP_TYPE_VIS forward_iterator_tag       : public input_iterator_tag {};
 337 struct _LIBCPP_TYPE_VIS bidirectional_iterator_tag : public forward_iterator_tag {};
 338 struct _LIBCPP_TYPE_VIS random_access_iterator_tag : public bidirectional_iterator_tag {};
 339
 340 template <class _Tp>
 341 struct __has_iterator_category
 342 {
 343 private:
 344     struct __two {char __lx; char __lxx;};
 345     template <class _Up> static __two __test(...);
 346     template <class _Up> static char __test(typename _Up::iterator_category* = 0);
 347 public:
 348     static const bool value = sizeof(__test<_Tp>(0)) == 1;
 349 };
 350
 351 template <class _Iter, bool> struct ____iterator_traits {};
 352
 353 template <class _Iter>
 354 struct ____iterator_traits<_Iter, true>
 355 {
 356     typedef typename _Iter::difference_type   difference_type;
 357     typedef typename _Iter::value_type        value_type;
 358     typedef typename _Iter::pointer           pointer;
 359     typedef typename _Iter::reference         reference;
 360     typedef typename _Iter::iterator_category iterator_category;
 361 };
 362
 363 template <class _Iter, bool> struct __iterator_traits {};
 364
 365 template <class _Iter>
 366 struct __iterator_traits<_Iter, true>
 367     :  ____iterator_traits
 368       <
 369         _Iter,
 370         is_convertible<typename _Iter::iterator_category, input_iterator_tag>::value ||
 371         is_convertible<typename _Iter::iterator_category, output_iterator_tag>::value
 372       >
 373 {};
 374
 375 // iterator_traits<Iterator> will only have the nested types if Iterator::iterator_category
 376 //    exists.  Else iterator_traits<Iterator> will be an empty class.  This is a
 377 //    conforming extension which allows some programs to compile and behave as
 378 //    the client expects instead of failing at compile time.
 379
 380 template <class _Iter>
 381 struct _LIBCPP_TYPE_VIS iterator_traits
 382     : __iterator_traits<_Iter, __has_iterator_category<_Iter>::value> {};
 383
 384 template<class _Tp>
 385 struct _LIBCPP_TYPE_VIS iterator_traits<_Tp*>
 386 {
 387     typedef ptrdiff_t difference_type;
 388     typedef typename remove_const<_Tp>::type value_type;
 389     typedef _Tp* pointer;
 390     typedef _Tp& reference;
 391     typedef random_access_iterator_tag iterator_category;
 392 };
 393
 394 template <class _Tp, class _Up, bool = __has_iterator_category<iterator_traits<_Tp> >::value>
 395 struct __has_iterator_category_convertible_to
 396     : public integral_constant<bool, is_convertible<typename iterator_traits<_Tp>::iterator_category, _Up>::value>
 397 {};
 398
 399 template <class _Tp, class _Up>
 400 struct __has_iterator_category_convertible_to<_Tp, _Up, false> : public false_type {};
 401
 402 template <class _Tp>
 403 struct __is_input_iterator : public __has_iterator_category_convertible_to<_Tp, input_iterator_tag> {};
 404
 405 template <class _Tp>
 406 struct __is_forward_iterator : public __has_iterator_category_convertible_to<_Tp, forward_iterator_tag> {};
 407
 408 template <class _Tp>
 409 struct __is_bidirectional_iterator : public __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag> {};
 410
 411 template <class _Tp>
 412 struct __is_random_access_iterator : public __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag> {};
 413
 414 template<class _Category, class _Tp, class _Distance = ptrdiff_t,
 415          class _Pointer = _Tp*, class _Reference = _Tp&>
 416 struct _LIBCPP_TYPE_VIS iterator
 417 {
 418     typedef _Tp        value_type;
 419     typedef _Distance  difference_type;
 420     typedef _Pointer   pointer;
 421     typedef _Reference reference;
 422     typedef _Category  iterator_category;
 423 };
 424
 425 template <class _InputIter>
 426 inline _LIBCPP_INLINE_VISIBILITY
 427 void __advance(_InputIter& __i,
 428              typename iterator_traits<_InputIter>::difference_type __n, input_iterator_tag)
 429 {
 430     for (; __n > 0; --__n)
 431         ++__i;
 432 }
 433
 434 template <class _BiDirIter>
 435 inline _LIBCPP_INLINE_VISIBILITY
 436 void __advance(_BiDirIter& __i,
 437              typename iterator_traits<_BiDirIter>::difference_type __n, bidirectional_iterator_tag)
 438 {
 439     if (__n >= 0)
 440         for (; __n > 0; --__n)
 441             ++__i;
 442     else
 443         for (; __n < 0; ++__n)
 444             --__i;
 445 }
 446
 447 template <class _RandIter>
 448 inline _LIBCPP_INLINE_VISIBILITY
 449 void __advance(_RandIter& __i,
 450              typename iterator_traits<_RandIter>::difference_type __n, random_access_iterator_tag)
 451 {
 452    __i += __n;
 453 }
 454
 455 template <class _InputIter>
 456 inline _LIBCPP_INLINE_VISIBILITY
 457 void advance(_InputIter& __i,
 458              typename iterator_traits<_InputIter>::difference_type __n)
 459 {
 460     __advance(__i, __n, typename iterator_traits<_InputIter>::iterator_category());
 461 }
 462
 463 template <class _InputIter>
 464 inline _LIBCPP_INLINE_VISIBILITY
 465 typename iterator_traits<_InputIter>::difference_type
 466 __distance(_InputIter __first, _InputIter __last, input_iterator_tag)
 467 {
 468     typename iterator_traits<_InputIter>::difference_type __r(0);
 469     for (; __first != __last; ++__first)
 470         ++__r;
 471     return __r;
 472 }
 473
 474 template <class _RandIter>
 475 inline _LIBCPP_INLINE_VISIBILITY
 476 typename iterator_traits<_RandIter>::difference_type
 477 __distance(_RandIter __first, _RandIter __last, random_access_iterator_tag)
 478 {
 479     return __last - __first;
 480 }
 481
 482 template <class _InputIter>
 483 inline _LIBCPP_INLINE_VISIBILITY
 484 typename iterator_traits<_InputIter>::difference_type
 485 distance(_InputIter __first, _InputIter __last)
 486 {
 487     return __distance(__first, __last, typename iterator_traits<_InputIter>::iterator_category());
 488 }
 489
 490 template <class _ForwardIter>
 491 inline _LIBCPP_INLINE_VISIBILITY
 492 _ForwardIter
 493 next(_ForwardIter __x,
 494      typename iterator_traits<_ForwardIter>::difference_type __n = 1,
 495      typename enable_if<__is_forward_iterator<_ForwardIter>::value>::type* = 0)
 496 {
 497     _VSTD::advance(__x, __n);
 498     return __x;
 499 }
 500
 501 template <class _BidiretionalIter>
 502 inline _LIBCPP_INLINE_VISIBILITY
 503 _BidiretionalIter
 504 prev(_BidiretionalIter __x,
 505      typename iterator_traits<_BidiretionalIter>::difference_type __n = 1,
 506      typename enable_if<__is_bidirectional_iterator<_BidiretionalIter>::value>::type* = 0)
 507 {
 508     _VSTD::advance(__x, -__n);
 509     return __x;
 510 }
 511
 512 template <class _Iter>
 513 class _LIBCPP_TYPE_VIS reverse_iterator
 514     : public iterator<typename iterator_traits<_Iter>::iterator_category,
 515                       typename iterator_traits<_Iter>::value_type,
 516                       typename iterator_traits<_Iter>::difference_type,
 517                       typename iterator_traits<_Iter>::pointer,
 518                       typename iterator_traits<_Iter>::reference>
 519 {
 520 private:
 521     mutable _Iter __t;
 522 protected:
 523     _Iter current;
 524 public:
 525     typedef _Iter                                            iterator_type;
 526     typedef typename iterator_traits<_Iter>::difference_type difference_type;
 527     typedef typename iterator_traits<_Iter>::reference       reference;
 528     typedef typename iterator_traits<_Iter>::pointer         pointer;
 529
 530     _LIBCPP_INLINE_VISIBILITY reverse_iterator() : current() {}
 531     _LIBCPP_INLINE_VISIBILITY explicit reverse_iterator(_Iter __x) : __t(__x), current(__x) {}
 532     template <class _Up> _LIBCPP_INLINE_VISIBILITY reverse_iterator(const reverse_iterator<_Up>& __u)
 533         : __t(__u.base()), current(__u.base()) {}
 534     _LIBCPP_INLINE_VISIBILITY _Iter base() const {return current;}
 535     _LIBCPP_INLINE_VISIBILITY reference operator*() const {__t = current; return *--__t;}
 536     _LIBCPP_INLINE_VISIBILITY pointer  operator->() const {return &(operator*());}
 537     _LIBCPP_INLINE_VISIBILITY reverse_iterator& operator++() {--current; return *this;}
 538     _LIBCPP_INLINE_VISIBILITY reverse_iterator  operator++(int)
 539         {reverse_iterator __tmp(*this); --current; return __tmp;}
 540     _LIBCPP_INLINE_VISIBILITY reverse_iterator& operator--() {++current; return *this;}
 541     _LIBCPP_INLINE_VISIBILITY reverse_iterator  operator--(int)
 542         {reverse_iterator __tmp(*this); ++current; return __tmp;}
 543     _LIBCPP_INLINE_VISIBILITY reverse_iterator  operator+ (difference_type __n) const
 544         {return reverse_iterator(current - __n);}
 545     _LIBCPP_INLINE_VISIBILITY reverse_iterator& operator+=(difference_type __n)
 546         {current -= __n; return *this;}
 547     _LIBCPP_INLINE_VISIBILITY reverse_iterator  operator- (difference_type __n) const
 548         {return reverse_iterator(current + __n);}
 549     _LIBCPP_INLINE_VISIBILITY reverse_iterator& operator-=(difference_type __n)
 550         {current += __n; return *this;}
 551     _LIBCPP_INLINE_VISIBILITY reference         operator[](difference_type __n) const
 552         {return current[-__n-1];}
 553 };
 554
 555 template <class _Iter1, class _Iter2>
 556 inline _LIBCPP_INLINE_VISIBILITY
 557 bool
 558 operator==(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
 559 {
 560     return __x.base() == __y.base();
 561 }
 562
 563 template <class _Iter1, class _Iter2>
 564 inline _LIBCPP_INLINE_VISIBILITY
 565 bool
 566 operator<(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
 567 {
 568     return __x.base() > __y.base();
 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 typename reverse_iterator<_Iter1>::difference_type
 606 operator-(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
 607 {
 608     return __y.base() - __x.base();
 609 }
 610
 611 template <class _Iter>
 612 inline _LIBCPP_INLINE_VISIBILITY
 613 reverse_iterator<_Iter>
 614 operator+(typename reverse_iterator<_Iter>::difference_type __n, const reverse_iterator<_Iter>& __x)
 615 {
 616     return reverse_iterator<_Iter>(__x.base() - __n);
 617 }
 618
 619 template <class _Container>
 620 class _LIBCPP_TYPE_VIS back_insert_iterator
 621     : public iterator<output_iterator_tag,
 622                       void,
 623                       void,
 624                       void,
 625                       back_insert_iterator<_Container>&>
 626 {
 627 protected:
 628     _Container* container;
 629 public:
 630     typedef _Container container_type;
 631
 632     _LIBCPP_INLINE_VISIBILITY explicit back_insert_iterator(_Container& __x) : container(&__x) {}
 633     _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator=(const typename _Container::value_type& __value_)
 634         {container->push_back(__value_); return *this;}
 635 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 636     _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator=(typename _Container::value_type&& __value_)
 637         {container->push_back(_VSTD::move(__value_)); return *this;}
 638 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 639     _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator*()     {return *this;}
 640     _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator++()    {return *this;}
 641     _LIBCPP_INLINE_VISIBILITY back_insert_iterator  operator++(int) {return *this;}
 642 };
 643
 644 template <class _Container>
 645 inline _LIBCPP_INLINE_VISIBILITY
 646 back_insert_iterator<_Container>
 647 back_inserter(_Container& __x)
 648 {
 649     return back_insert_iterator<_Container>(__x);
 650 }
 651
 652 template <class _Container>
 653 class _LIBCPP_TYPE_VIS front_insert_iterator
 654     : public iterator<output_iterator_tag,
 655                       void,
 656                       void,
 657                       void,
 658                       front_insert_iterator<_Container>&>
 659 {
 660 protected:
 661     _Container* container;
 662 public:
 663     typedef _Container container_type;
 664
 665     _LIBCPP_INLINE_VISIBILITY explicit front_insert_iterator(_Container& __x) : container(&__x) {}
 666     _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator=(const typename _Container::value_type& __value_)
 667         {container->push_front(__value_); return *this;}
 668 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 669     _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator=(typename _Container::value_type&& __value_)
 670         {container->push_front(_VSTD::move(__value_)); return *this;}
 671 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 672     _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator*()     {return *this;}
 673     _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator++()    {return *this;}
 674     _LIBCPP_INLINE_VISIBILITY front_insert_iterator  operator++(int) {return *this;}
 675 };
 676
 677 template <class _Container>
 678 inline _LIBCPP_INLINE_VISIBILITY
 679 front_insert_iterator<_Container>
 680 front_inserter(_Container& __x)
 681 {
 682     return front_insert_iterator<_Container>(__x);
 683 }
 684
 685 template <class _Container>
 686 class _LIBCPP_TYPE_VIS insert_iterator
 687     : public iterator<output_iterator_tag,
 688                       void,
 689                       void,
 690                       void,
 691                       insert_iterator<_Container>&>
 692 {
 693 protected:
 694     _Container* container;
 695     typename _Container::iterator iter;
 696 public:
 697     typedef _Container container_type;
 698
 699     _LIBCPP_INLINE_VISIBILITY insert_iterator(_Container& __x, typename _Container::iterator __i)
 700         : container(&__x), iter(__i) {}
 701     _LIBCPP_INLINE_VISIBILITY insert_iterator& operator=(const typename _Container::value_type& __value_)
 702         {iter = container->insert(iter, __value_); ++iter; return *this;}
 703 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 704     _LIBCPP_INLINE_VISIBILITY insert_iterator& operator=(typename _Container::value_type&& __value_)
 705         {iter = container->insert(iter, _VSTD::move(__value_)); ++iter; return *this;}
 706 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
 707     _LIBCPP_INLINE_VISIBILITY insert_iterator& operator*()        {return *this;}
 708     _LIBCPP_INLINE_VISIBILITY insert_iterator& operator++()       {return *this;}
 709     _LIBCPP_INLINE_VISIBILITY insert_iterator& operator++(int)    {return *this;}
 710 };
 711
 712 template <class _Container>
 713 inline _LIBCPP_INLINE_VISIBILITY
 714 insert_iterator<_Container>
 715 inserter(_Container& __x, typename _Container::iterator __i)
 716 {
 717     return insert_iterator<_Container>(__x, __i);
 718 }
 719
 720 template <class _Tp, class _CharT = char,
 721           class _Traits = char_traits<_CharT>, class _Distance = ptrdiff_t>
 722 class _LIBCPP_TYPE_VIS istream_iterator
 723     : public iterator<input_iterator_tag, _Tp, _Distance, const _Tp*, const _Tp&>
 724 {
 725 public:
 726     typedef _CharT char_type;
 727     typedef _Traits traits_type;
 728     typedef basic_istream<_CharT,_Traits> istream_type;
 729 private:
 730     istream_type* __in_stream_;
 731     _Tp __value_;
 732 public:
 733     _LIBCPP_INLINE_VISIBILITY istream_iterator() : __in_stream_(0) {}
 734     _LIBCPP_INLINE_VISIBILITY istream_iterator(istream_type& __s) : __in_stream_(&__s)
 735         {
 736             if (!(*__in_stream_ >> __value_))
 737                 __in_stream_ = 0;
 738         }
 739
 740     _LIBCPP_INLINE_VISIBILITY const _Tp& operator*() const {return __value_;}
 741     _LIBCPP_INLINE_VISIBILITY const _Tp* operator->() const {return &(operator*());}
 742     _LIBCPP_INLINE_VISIBILITY istream_iterator& operator++()
 743         {
 744             if (!(*__in_stream_ >> __value_))
 745                 __in_stream_ = 0;
 746             return *this;
 747         }
 748     _LIBCPP_INLINE_VISIBILITY istream_iterator  operator++(int)
 749         {istream_iterator __t(*this); ++(*this); return __t;}
 750
 751     friend _LIBCPP_INLINE_VISIBILITY
 752     bool operator==(const istream_iterator& __x, const istream_iterator& __y)
 753         {return __x.__in_stream_ == __y.__in_stream_;}
 754
 755     friend _LIBCPP_INLINE_VISIBILITY
 756     bool operator!=(const istream_iterator& __x, const istream_iterator& __y)
 757         {return !(__x == __y);}
 758 };
 759
 760 template <class _Tp, class _CharT = char, class _Traits = char_traits<_CharT> >
 761 class _LIBCPP_TYPE_VIS ostream_iterator
 762     : public iterator<output_iterator_tag, void, void, void, void>
 763 {
 764 public:
 765     typedef _CharT char_type;
 766     typedef _Traits traits_type;
 767     typedef basic_ostream<_CharT,_Traits> ostream_type;
 768 private:
 769     ostream_type* __out_stream_;
 770     const char_type* __delim_;
 771 public:
 772     _LIBCPP_INLINE_VISIBILITY ostream_iterator(ostream_type& __s)
 773         : __out_stream_(&__s), __delim_(0) {}
 774     _LIBCPP_INLINE_VISIBILITY ostream_iterator(ostream_type& __s, const _CharT* __delimiter)
 775         : __out_stream_(&__s), __delim_(__delimiter) {}
 776     _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator=(const _Tp& __value_)
 777         {
 778             *__out_stream_ << __value_;
 779             if (__delim_)
 780                 *__out_stream_ << __delim_;
 781             return *this;
 782         }
 783
 784     _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator*()     {return *this;}
 785     _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator++()    {return *this;}
 786     _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator++(int) {return *this;}
 787 };
 788
 789 template<class _CharT, class _Traits>
 790 class _LIBCPP_TYPE_VIS istreambuf_iterator
 791     : public iterator<input_iterator_tag, _CharT,
 792                       typename _Traits::off_type, _CharT*,
 793                       _CharT>
 794 {
 795 public:
 796     typedef _CharT                          char_type;
 797     typedef _Traits                         traits_type;
 798     typedef typename _Traits::int_type      int_type;
 799     typedef basic_streambuf<_CharT,_Traits> streambuf_type;
 800     typedef basic_istream<_CharT,_Traits>   istream_type;
 801 private:
 802     mutable streambuf_type* __sbuf_;
 803
 804     class __proxy
 805     {
 806         char_type __keep_;
 807         streambuf_type* __sbuf_;
 808         _LIBCPP_INLINE_VISIBILITY __proxy(char_type __c, streambuf_type* __s)
 809             : __keep_(__c), __sbuf_(__s) {}
 810         friend class istreambuf_iterator;
 811     public:
 812         _LIBCPP_INLINE_VISIBILITY char_type operator*() const {return __keep_;}
 813     };
 814
 815     _LIBCPP_INLINE_VISIBILITY
 816     bool __test_for_eof() const
 817     {
 818         if (__sbuf_ && traits_type::eq_int_type(__sbuf_->sgetc(), traits_type::eof()))
 819             __sbuf_ = 0;
 820         return __sbuf_ == 0;
 821     }
 822 public:
 823     _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR istreambuf_iterator() _NOEXCEPT : __sbuf_(0) {}
 824     _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(istream_type& __s) _NOEXCEPT
 825         : __sbuf_(__s.rdbuf()) {}
 826     _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(streambuf_type* __s) _NOEXCEPT
 827         : __sbuf_(__s) {}
 828     _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(const __proxy& __p) _NOEXCEPT
 829         : __sbuf_(__p.__sbuf_) {}
 830
 831     _LIBCPP_INLINE_VISIBILITY char_type  operator*() const
 832         {return static_cast<char_type>(__sbuf_->sgetc());}
 833     _LIBCPP_INLINE_VISIBILITY char_type* operator->() const {return nullptr;}
 834     _LIBCPP_INLINE_VISIBILITY istreambuf_iterator& operator++()
 835         {
 836             __sbuf_->sbumpc();
 837             return *this;
 838         }
 839     _LIBCPP_INLINE_VISIBILITY __proxy              operator++(int)
 840         {
 841             return __proxy(__sbuf_->sbumpc(), __sbuf_);
 842         }
 843
 844     _LIBCPP_INLINE_VISIBILITY bool equal(const istreambuf_iterator& __b) const
 845         {return __test_for_eof() == __b.__test_for_eof();}
 846 };
 847
 848 template <class _CharT, class _Traits>
 849 inline _LIBCPP_INLINE_VISIBILITY
 850 bool operator==(const istreambuf_iterator<_CharT,_Traits>& __a,
 851                 const istreambuf_iterator<_CharT,_Traits>& __b)
 852                 {return __a.equal(__b);}
 853
 854 template <class _CharT, class _Traits>
 855 inline _LIBCPP_INLINE_VISIBILITY
 856 bool operator!=(const istreambuf_iterator<_CharT,_Traits>& __a,
 857                 const istreambuf_iterator<_CharT,_Traits>& __b)
 858                 {return !__a.equal(__b);}
 859
 860 template <class _CharT, class _Traits>
 861 class _LIBCPP_TYPE_VIS ostreambuf_iterator
 862     : public iterator<output_iterator_tag, void, void, void, void>
 863 {
 864 public:
 865     typedef _CharT                          char_type;
 866     typedef _Traits                         traits_type;
 867     typedef basic_streambuf<_CharT,_Traits> streambuf_type;
 868     typedef basic_ostream<_CharT,_Traits>   ostream_type;
 869 private:
 870     streambuf_type* __sbuf_;
 871 public:
 872     _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator(ostream_type& __s) _NOEXCEPT
 873         : __sbuf_(__s.rdbuf()) {}
 874     _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator(streambuf_type* __s) _NOEXCEPT
 875         : __sbuf_(__s) {}
 876     _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator=(_CharT __c)
 877         {
 878             if (__sbuf_ && traits_type::eq_int_type(__sbuf_->sputc(__c), traits_type::eof()))
 879                 __sbuf_ = 0;
 880             return *this;
 881         }
 882     _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator*()     {return *this;}
 883     _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator++()    {return *this;}
 884     _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator++(int) {return *this;}
 885     _LIBCPP_INLINE_VISIBILITY bool failed() const _NOEXCEPT {return __sbuf_ == 0;}
 886
 887 #if !defined(__APPLE__) || \
 888     (defined(__MAC_OS_X_VERSION_MIN_REQUIRED) && __MAC_OS_X_VERSION_MIN_REQUIRED > __MAC_10_8) || \
 889     (defined(__IPHONE_OS_VERSION_MIN_REQUIRED) && __IPHONE_OS_VERSION_MIN_REQUIRED > __IPHONE_6_0)
 890
 891     template <class _Ch, class _Tr>
 892     friend
 893     _LIBCPP_HIDDEN
 894     ostreambuf_iterator<_Ch, _Tr>
 895     __pad_and_output(ostreambuf_iterator<_Ch, _Tr> __s,
 896                      const _Ch* __ob, const _Ch* __op, const _Ch* __oe,
 897                      ios_base& __iob, _Ch __fl);
 898 #endif
 899 };
 900
 901 template <class _Iter>
 902 class _LIBCPP_TYPE_VIS move_iterator
 903 {
 904 private:
 905     _Iter __i;
 906 public:
 907     typedef _Iter                                            iterator_type;
 908     typedef typename iterator_traits<iterator_type>::iterator_category iterator_category;
 909     typedef typename iterator_traits<iterator_type>::value_type value_type;
 910     typedef typename iterator_traits<iterator_type>::difference_type difference_type;
 911     typedef typename iterator_traits<iterator_type>::pointer pointer;
 912 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 913     typedef value_type&& reference;
 914 #else
 915     typedef typename iterator_traits<iterator_type>::reference reference;
 916 #endif
 917
 918     _LIBCPP_INLINE_VISIBILITY move_iterator() : __i() {}
 919     _LIBCPP_INLINE_VISIBILITY explicit move_iterator(_Iter __x) : __i(__x) {}
 920     template <class _Up> _LIBCPP_INLINE_VISIBILITY move_iterator(const move_iterator<_Up>& __u)
 921         : __i(__u.base()) {}
 922     _LIBCPP_INLINE_VISIBILITY _Iter base() const {return __i;}
 923     _LIBCPP_INLINE_VISIBILITY reference operator*() const {
 924       return static_cast<reference>(*__i);
 925     }
 926     _LIBCPP_INLINE_VISIBILITY pointer  operator->() const {
 927       typename iterator_traits<iterator_type>::reference __ref = *__i;
 928       return &__ref;
 929     }
 930     _LIBCPP_INLINE_VISIBILITY move_iterator& operator++() {++__i; return *this;}
 931     _LIBCPP_INLINE_VISIBILITY move_iterator  operator++(int)
 932         {move_iterator __tmp(*this); ++__i; return __tmp;}
 933     _LIBCPP_INLINE_VISIBILITY move_iterator& operator--() {--__i; return *this;}
 934     _LIBCPP_INLINE_VISIBILITY move_iterator  operator--(int)
 935         {move_iterator __tmp(*this); --__i; return __tmp;}
 936     _LIBCPP_INLINE_VISIBILITY move_iterator  operator+ (difference_type __n) const
 937         {return move_iterator(__i + __n);}
 938     _LIBCPP_INLINE_VISIBILITY move_iterator& operator+=(difference_type __n)
 939         {__i += __n; return *this;}
 940     _LIBCPP_INLINE_VISIBILITY move_iterator  operator- (difference_type __n) const
 941         {return move_iterator(__i - __n);}
 942     _LIBCPP_INLINE_VISIBILITY move_iterator& operator-=(difference_type __n)
 943         {__i -= __n; return *this;}
 944     _LIBCPP_INLINE_VISIBILITY reference         operator[](difference_type __n) const
 945     {
 946       return static_cast<reference>(__i[__n]);
 947     }
 948 };
 949
 950 template <class _Iter1, class _Iter2>
 951 inline _LIBCPP_INLINE_VISIBILITY
 952 bool
 953 operator==(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
 954 {
 955     return __x.base() == __y.base();
 956 }
 957
 958 template <class _Iter1, class _Iter2>
 959 inline _LIBCPP_INLINE_VISIBILITY
 960 bool
 961 operator<(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
 962 {
 963     return __x.base() < __y.base();
 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 typename move_iterator<_Iter1>::difference_type
1001 operator-(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1002 {
1003     return __x.base() - __y.base();
1004 }
1005
1006 template <class _Iter>
1007 inline _LIBCPP_INLINE_VISIBILITY
1008 move_iterator<_Iter>
1009 operator+(typename move_iterator<_Iter>::difference_type __n, const move_iterator<_Iter>& __x)
1010 {
1011     return move_iterator<_Iter>(__x.base() + __n);
1012 }
1013
1014 template <class _Iter>
1015 inline _LIBCPP_INLINE_VISIBILITY
1016 move_iterator<_Iter>
1017 make_move_iterator(const _Iter& __i)
1018 {
1019     return move_iterator<_Iter>(__i);
1020 }
1021
1022 // __wrap_iter
1023
1024 template <class _Iter> class __wrap_iter;
1025
1026 template <class _Iter1, class _Iter2>
1027 _LIBCPP_INLINE_VISIBILITY
1028 bool
1029 operator==(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1030
1031 template <class _Iter1, class _Iter2>
1032 _LIBCPP_INLINE_VISIBILITY
1033 bool
1034 operator<(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1035
1036 template <class _Iter1, class _Iter2>
1037 _LIBCPP_INLINE_VISIBILITY
1038 bool
1039 operator!=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1040
1041 template <class _Iter1, class _Iter2>
1042 _LIBCPP_INLINE_VISIBILITY
1043 bool
1044 operator>(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1045
1046 template <class _Iter1, class _Iter2>
1047 _LIBCPP_INLINE_VISIBILITY
1048 bool
1049 operator>=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1050
1051 template <class _Iter1, class _Iter2>
1052 _LIBCPP_INLINE_VISIBILITY
1053 bool
1054 operator<=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1055
1056 template <class _Iter1, class _Iter2>
1057 _LIBCPP_INLINE_VISIBILITY
1058 typename __wrap_iter<_Iter1>::difference_type
1059 operator-(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1060
1061 template <class _Iter>
1062 _LIBCPP_INLINE_VISIBILITY
1063 __wrap_iter<_Iter>
1064 operator+(typename __wrap_iter<_Iter>::difference_type, __wrap_iter<_Iter>) _NOEXCEPT;
1065
1066 template <class _Ip, class _Op> _Op _LIBCPP_INLINE_VISIBILITY copy(_Ip, _Ip, _Op);
1067 template <class _B1, class _B2> _B2 _LIBCPP_INLINE_VISIBILITY copy_backward(_B1, _B1, _B2);
1068 template <class _Ip, class _Op> _Op _LIBCPP_INLINE_VISIBILITY move(_Ip, _Ip, _Op);
1069 template <class _B1, class _B2> _B2 _LIBCPP_INLINE_VISIBILITY move_backward(_B1, _B1, _B2);
1070
1071 template <class _Tp>
1072 _LIBCPP_INLINE_VISIBILITY
1073 typename enable_if
1074 <
1075     is_trivially_copy_assignable<_Tp>::value,
1076     _Tp*
1077 >::type
1078 __unwrap_iter(__wrap_iter<_Tp*>);
1079
1080 template <class _Iter>
1081 class __wrap_iter
1082 {
1083 public:
1084     typedef _Iter                                                      iterator_type;
1085     typedef typename iterator_traits<iterator_type>::iterator_category iterator_category;
1086     typedef typename iterator_traits<iterator_type>::value_type        value_type;
1087     typedef typename iterator_traits<iterator_type>::difference_type   difference_type;
1088     typedef typename iterator_traits<iterator_type>::pointer           pointer;
1089     typedef typename iterator_traits<iterator_type>::reference         reference;
1090 private:
1091     iterator_type __i;
1092 public:
1093     _LIBCPP_INLINE_VISIBILITY __wrap_iter() _NOEXCEPT
1094     {
1095 #if _LIBCPP_DEBUG_LEVEL >= 2
1096         __get_db()->__insert_i(this);
1097 #endif
1098     }
1099     template <class _Up> _LIBCPP_INLINE_VISIBILITY __wrap_iter(const __wrap_iter<_Up>& __u,
1100         typename enable_if<is_convertible<_Up, iterator_type>::value>::type* = 0) _NOEXCEPT
1101         : __i(__u.base())
1102     {
1103 #if _LIBCPP_DEBUG_LEVEL >= 2
1104         __get_db()->__iterator_copy(this, &__u);
1105 #endif
1106     }
1107 #if _LIBCPP_DEBUG_LEVEL >= 2
1108     _LIBCPP_INLINE_VISIBILITY
1109     __wrap_iter(const __wrap_iter& __x)
1110         : __i(__x.base())
1111     {
1112         __get_db()->__iterator_copy(this, &__x);
1113     }
1114     _LIBCPP_INLINE_VISIBILITY
1115     __wrap_iter& operator=(const __wrap_iter& __x)
1116     {
1117         if (this != &__x)
1118         {
1119             __get_db()->__iterator_copy(this, &__x);
1120             __i = __x.__i;
1121         }
1122         return *this;
1123     }
1124     _LIBCPP_INLINE_VISIBILITY
1125     ~__wrap_iter()
1126     {
1127         __get_db()->__erase_i(this);
1128     }
1129 #endif
1130     _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT
1131     {
1132 #if _LIBCPP_DEBUG_LEVEL >= 2
1133         _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
1134                        "Attempted to dereference a non-dereferenceable iterator");
1135 #endif
1136         return *__i;
1137     }
1138     _LIBCPP_INLINE_VISIBILITY pointer  operator->() const _NOEXCEPT
1139     {
1140 #if _LIBCPP_DEBUG_LEVEL >= 2
1141         _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
1142                        "Attempted to dereference a non-dereferenceable iterator");
1143 #endif
1144         return (pointer)&reinterpret_cast<const volatile char&>(*__i);
1145     }
1146     _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator++() _NOEXCEPT
1147     {
1148 #if _LIBCPP_DEBUG_LEVEL >= 2
1149         _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
1150                        "Attempted to increment non-incrementable iterator");
1151 #endif
1152         ++__i;
1153         return *this;
1154     }
1155     _LIBCPP_INLINE_VISIBILITY __wrap_iter  operator++(int) _NOEXCEPT
1156         {__wrap_iter __tmp(*this); ++(*this); return __tmp;}
1157     _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator--() _NOEXCEPT
1158     {
1159 #if _LIBCPP_DEBUG_LEVEL >= 2
1160         _LIBCPP_ASSERT(__get_const_db()->__decrementable(this),
1161                        "Attempted to decrement non-decrementable iterator");
1162 #endif
1163         --__i;
1164         return *this;
1165     }
1166     _LIBCPP_INLINE_VISIBILITY __wrap_iter  operator--(int) _NOEXCEPT
1167         {__wrap_iter __tmp(*this); --(*this); return __tmp;}
1168     _LIBCPP_INLINE_VISIBILITY __wrap_iter  operator+ (difference_type __n) const _NOEXCEPT
1169         {__wrap_iter __w(*this); __w += __n; return __w;}
1170     _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator+=(difference_type __n) _NOEXCEPT
1171     {
1172 #if _LIBCPP_DEBUG_LEVEL >= 2
1173         _LIBCPP_ASSERT(__get_const_db()->__addable(this, __n),
1174                    "Attempted to add/subtract iterator outside of valid range");
1175 #endif
1176         __i += __n;
1177         return *this;
1178     }
1179     _LIBCPP_INLINE_VISIBILITY __wrap_iter  operator- (difference_type __n) const _NOEXCEPT
1180         {return *this + (-__n);}
1181     _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator-=(difference_type __n) _NOEXCEPT
1182         {*this += -__n; return *this;}
1183     _LIBCPP_INLINE_VISIBILITY reference        operator[](difference_type __n) const _NOEXCEPT
1184     {
1185 #if _LIBCPP_DEBUG_LEVEL >= 2
1186         _LIBCPP_ASSERT(__get_const_db()->__subscriptable(this, __n),
1187                    "Attempted to subscript iterator outside of valid range");
1188 #endif
1189         return __i[__n];
1190     }
1191
1192     _LIBCPP_INLINE_VISIBILITY iterator_type base() const _NOEXCEPT {return __i;}
1193
1194 private:
1195     _LIBCPP_INLINE_VISIBILITY __wrap_iter(iterator_type __x) _NOEXCEPT : __i(__x) {}
1196 #if _LIBCPP_DEBUG_LEVEL >= 2
1197     _LIBCPP_INLINE_VISIBILITY __wrap_iter(const void* __p, iterator_type __x) : __i(__x)
1198     {
1199         __get_db()->__insert_ic(this, __p);
1200     }
1201 #endif
1202
1203     template <class _Up> friend class __wrap_iter;
1204     template <class _CharT, class _Traits, class _Alloc> friend class basic_string;
1205     template <class _Tp, class _Alloc> friend class vector;
1206
1207     template <class _Iter1, class _Iter2>
1208     friend
1209     bool
1210     operator==(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1211
1212     template <class _Iter1, class _Iter2>
1213     friend
1214     bool
1215     operator<(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1216
1217     template <class _Iter1, class _Iter2>
1218     friend
1219     bool
1220     operator!=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1221
1222     template <class _Iter1, class _Iter2>
1223     friend
1224     bool
1225     operator>(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
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     typename __wrap_iter<_Iter1>::difference_type
1240     operator-(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1241
1242     template <class _Iter1>
1243     friend
1244     __wrap_iter<_Iter1>
1245     operator+(typename __wrap_iter<_Iter1>::difference_type, __wrap_iter<_Iter1>) _NOEXCEPT;
1246
1247     template <class _Ip, class _Op> friend _Op copy(_Ip, _Ip, _Op);
1248     template <class _B1, class _B2> friend _B2 copy_backward(_B1, _B1, _B2);
1249     template <class _Ip, class _Op> friend _Op move(_Ip, _Ip, _Op);
1250     template <class _B1, class _B2> friend _B2 move_backward(_B1, _B1, _B2);
1251
1252     template <class _Tp>
1253     friend
1254     typename enable_if
1255     <
1256         is_trivially_copy_assignable<_Tp>::value,
1257         _Tp*
1258     >::type
1259     __unwrap_iter(__wrap_iter<_Tp*>);
1260 };
1261
1262 template <class _Iter1, class _Iter2>
1263 inline _LIBCPP_INLINE_VISIBILITY
1264 bool
1265 operator==(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1266 {
1267 #if _LIBCPP_DEBUG_LEVEL >= 2
1268     _LIBCPP_ASSERT(__get_const_db()->__comparable(&__x, &__y),
1269                    "Attempted to compare incomparable iterators");
1270 #endif
1271     return __x.base() == __y.base();
1272 }
1273
1274 template <class _Iter1, class _Iter2>
1275 inline _LIBCPP_INLINE_VISIBILITY
1276 bool
1277 operator<(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1278 {
1279 #if _LIBCPP_DEBUG_LEVEL >= 2
1280     _LIBCPP_ASSERT(__get_const_db()->__comparable(&__x, &__y),
1281                    "Attempted to compare incomparable iterators");
1282 #endif
1283     return __x.base() < __y.base();
1284 }
1285
1286 template <class _Iter1, class _Iter2>
1287 inline _LIBCPP_INLINE_VISIBILITY
1288 bool
1289 operator!=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1290 {
1291     return !(__x == __y);
1292 }
1293
1294 template <class _Iter1, class _Iter2>
1295 inline _LIBCPP_INLINE_VISIBILITY
1296 bool
1297 operator>(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1298 {
1299     return __y < __x;
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>
1319 inline _LIBCPP_INLINE_VISIBILITY
1320 bool
1321 operator!=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT
1322 {
1323     return !(__x == __y);
1324 }
1325
1326 template <class _Iter1>
1327 inline _LIBCPP_INLINE_VISIBILITY
1328 bool
1329 operator>(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __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, class _Iter2>
1351 inline _LIBCPP_INLINE_VISIBILITY
1352 typename __wrap_iter<_Iter1>::difference_type
1353 operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1354 {
1355 #if _LIBCPP_DEBUG_LEVEL >= 2
1356     _LIBCPP_ASSERT(__get_const_db()->__comparable(&__x, &__y),
1357                    "Attempted to subtract incompatible iterators");
1358 #endif
1359     return __x.base() - __y.base();
1360 }
1361
1362 template <class _Iter>
1363 inline _LIBCPP_INLINE_VISIBILITY
1364 __wrap_iter<_Iter>
1365 operator+(typename __wrap_iter<_Iter>::difference_type __n,
1366           __wrap_iter<_Iter> __x) _NOEXCEPT
1367 {
1368     __x += __n;
1369     return __x;
1370 }
1371
1372 #ifdef _LIBCPP_DEBUG
1373
1374 // __debug_iter
1375
1376 template <class _Container, class _Iter> class __debug_iter;
1377
1378 template <class _Container, class _Iter1, class _Iter2>
1379 _LIBCPP_INLINE_VISIBILITY
1380 bool
1381 operator==(const __debug_iter<_Container, _Iter1>&, const __debug_iter<_Container, _Iter2>&);
1382
1383 template <class _Container, class _Iter1, class _Iter2>
1384 _LIBCPP_INLINE_VISIBILITY
1385 bool
1386 operator<(const __debug_iter<_Container, _Iter1>&, const __debug_iter<_Container, _Iter2>&);
1387
1388 template <class _Container, class _Iter1, class _Iter2>
1389 _LIBCPP_INLINE_VISIBILITY
1390 bool
1391 operator!=(const __debug_iter<_Container, _Iter1>&, const __debug_iter<_Container, _Iter2>&);
1392
1393 template <class _Container, class _Iter1, class _Iter2>
1394 _LIBCPP_INLINE_VISIBILITY
1395 bool
1396 operator>(const __debug_iter<_Container, _Iter1>&, const __debug_iter<_Container, _Iter2>&);
1397
1398 template <class _Container, class _Iter1, class _Iter2>
1399 _LIBCPP_INLINE_VISIBILITY
1400 bool
1401 operator>=(const __debug_iter<_Container, _Iter1>&, const __debug_iter<_Container, _Iter2>&);
1402
1403 template <class _Container, class _Iter1, class _Iter2>
1404 _LIBCPP_INLINE_VISIBILITY
1405 bool
1406 operator<=(const __debug_iter<_Container, _Iter1>&, const __debug_iter<_Container, _Iter2>&);
1407
1408 template <class _Container, class _Iter1, class _Iter2>
1409 _LIBCPP_INLINE_VISIBILITY
1410 typename __debug_iter<_Container, _Iter1>::difference_type
1411 operator-(const __debug_iter<_Container, _Iter1>&, const __debug_iter<_Container, _Iter2>&);
1412
1413 template <class _Container, class _Iter>
1414 _LIBCPP_INLINE_VISIBILITY
1415 __debug_iter<_Container, _Iter>
1416 operator+(typename __debug_iter<_Container, _Iter>::difference_type, const __debug_iter<_Container, _Iter>&);
1417
1418 template <class _Container, class _Iter>
1419 class __debug_iter
1420 {
1421 public:
1422     typedef _Iter                                                      iterator_type;
1423     typedef _Container                                                 __container_type;
1424     typedef typename iterator_traits<iterator_type>::iterator_category iterator_category;
1425     typedef typename iterator_traits<iterator_type>::value_type        value_type;
1426     typedef typename iterator_traits<iterator_type>::difference_type   difference_type;
1427     typedef typename iterator_traits<iterator_type>::pointer           pointer;
1428     typedef typename iterator_traits<iterator_type>::reference         reference;
1429 private:
1430     iterator_type __i;
1431     __debug_iter* __next;
1432     __container_type* __cont;
1433
1434 public:
1435     _LIBCPP_INLINE_VISIBILITY __debug_iter() : __next(0), __cont(0) {}
1436     _LIBCPP_INLINE_VISIBILITY __debug_iter(const __debug_iter& __x)
1437         : __i(__x.base()), __next(0), __cont(0) {__set_owner(__x.__cont);}
1438     __debug_iter& operator=(const __debug_iter& __x);
1439     template <class _Up> _LIBCPP_INLINE_VISIBILITY __debug_iter(const __debug_iter<_Container, _Up>& __u,
1440         typename enable_if<is_convertible<_Up, iterator_type>::value>::type* = 0)
1441         : __i(__u.base()), __next(0), __cont(0) {__set_owner(__u.__cont);}
1442     _LIBCPP_INLINE_VISIBILITY ~__debug_iter() {__remove_owner();}
1443     _LIBCPP_INLINE_VISIBILITY reference operator*() const {assert(__is_deref()); return *__i;}
1444     _LIBCPP_INLINE_VISIBILITY pointer  operator->() const {return &(operator*());}
1445     _LIBCPP_INLINE_VISIBILITY __debug_iter& operator++() {assert(__can_increment()); ++__i; return *this;}
1446     _LIBCPP_INLINE_VISIBILITY __debug_iter  operator++(int)
1447         {__debug_iter __tmp(*this); operator++(); return __tmp;}
1448     _LIBCPP_INLINE_VISIBILITY __debug_iter& operator--() {assert(__can_decrement()); --__i; return *this;}
1449     _LIBCPP_INLINE_VISIBILITY __debug_iter  operator--(int)
1450         {__debug_iter __tmp(*this); operator--(); return __tmp;}
1451     _LIBCPP_INLINE_VISIBILITY __debug_iter  operator+ (difference_type __n) const
1452         {__debug_iter __t(*this); __t += __n; return __t;}
1453     __debug_iter& operator+=(difference_type __n);
1454     _LIBCPP_INLINE_VISIBILITY __debug_iter  operator- (difference_type __n) const
1455         {__debug_iter __t(*this); __t -= __n; return __t;}
1456     _LIBCPP_INLINE_VISIBILITY __debug_iter& operator-=(difference_type __n)
1457         {*this += -__n; return *this;}
1458     _LIBCPP_INLINE_VISIBILITY reference        operator[](difference_type __n) const
1459         {return *(*this + __n);}
1460
1461 private:
1462     _LIBCPP_INLINE_VISIBILITY __debug_iter(const __container_type* __c, iterator_type __x)
1463         : __i(__x), __next(0), __cont(0) {__set_owner(__c);}
1464     _LIBCPP_INLINE_VISIBILITY iterator_type base() const {return __i;}
1465
1466     void __set_owner(const __container_type* __c);
1467     void __remove_owner();
1468     static void __remove_all(__container_type* __c);
1469     static void swap(__container_type* __x, __container_type* __y);
1470
1471     _LIBCPP_INLINE_VISIBILITY bool __is_deref() const
1472         {return __is_deref(__is_random_access_iterator<iterator_type>());}
1473     bool __is_deref(false_type) const;
1474     bool __is_deref(true_type) const;
1475     _LIBCPP_INLINE_VISIBILITY bool __can_decrement() const
1476         {return __can_decrement(integral_constant<int, is_pointer<iterator_type>::value ? 2:
1477                                                        __is_random_access_iterator<iterator_type>::value ? 1 : 0>());}
1478     bool __can_decrement(integral_constant<int, 0>) const;
1479     bool __can_decrement(integral_constant<int, 1>) const;
1480     bool __can_decrement(integral_constant<int, 2>) const;
1481     _LIBCPP_INLINE_VISIBILITY bool __can_increment() const
1482         {return __can_increment(integral_constant<int, is_pointer<iterator_type>::value ? 2:
1483                                                        __is_random_access_iterator<iterator_type>::value ? 1 : 0>());}
1484     bool __can_increment(integral_constant<int, 0>) const;
1485     bool __can_increment(integral_constant<int, 1>) const;
1486     bool __can_increment(integral_constant<int, 2>) const;
1487
1488     _LIBCPP_INLINE_VISIBILITY bool __can_add(difference_type __n) const
1489         {return __can_add(__n, is_pointer<iterator_type>());}
1490     bool __can_add(difference_type __n, false_type) const;
1491     bool __can_add(difference_type __n, true_type) const;
1492
1493     template <class _Cp, class _Up> friend class __debug_iter;
1494     friend class _Container::__self;
1495
1496     template <class _Cp, class _Iter1, class _Iter2>
1497     friend
1498     bool
1499     operator==(const __debug_iter<_Cp, _Iter1>&, const __debug_iter<_Cp, _Iter2>&);
1500
1501     template <class _Cp, class _Iter1, class _Iter2>
1502     friend
1503     bool
1504     operator<(const __debug_iter<_Cp, _Iter1>&, const __debug_iter<_Cp, _Iter2>&);
1505
1506     template <class _Cp, class _Iter1, class _Iter2>
1507     friend
1508     bool
1509     operator!=(const __debug_iter<_Cp, _Iter1>&, const __debug_iter<_Cp, _Iter2>&);
1510
1511     template <class _Cp, class _Iter1, class _Iter2>
1512     friend
1513     bool
1514     operator>(const __debug_iter<_Cp, _Iter1>&, const __debug_iter<_Cp, _Iter2>&);
1515
1516     template <class _Cp, class _Iter1, class _Iter2>
1517     friend
1518     bool
1519     operator>=(const __debug_iter<_Cp, _Iter1>&, const __debug_iter<_Cp, _Iter2>&);
1520
1521     template <class _Cp, class _Iter1, class _Iter2>
1522     friend
1523     bool
1524     operator<=(const __debug_iter<_Cp, _Iter1>&, const __debug_iter<_Cp, _Iter2>&);
1525
1526     template <class _Cp, class _Iter1, class _Iter2>
1527     friend
1528     typename __debug_iter<_Cp, _Iter1>::difference_type
1529     operator-(const __debug_iter<_Cp, _Iter1>&, const __debug_iter<_Cp, _Iter2>&);
1530
1531     template <class _Cp, class _Iter1>
1532     friend
1533     __debug_iter<_Cp, _Iter1>
1534     operator+(typename __debug_iter<_Cp, _Iter1>::difference_type, const __debug_iter<_Cp, _Iter1>&);
1535 };
1536
1537 template <class _Container, class _Iter>
1538 __debug_iter<_Container, _Iter>&
1539 __debug_iter<_Container, _Iter>::operator=(const __debug_iter& __x)
1540 {
1541     if (this != &__x)
1542     {
1543         __remove_owner();
1544         __i = __x.__i;
1545         __set_owner(__x.__cont);
1546     }
1547     return *this;
1548 }
1549
1550 template <class _Container, class _Iter>
1551 void
1552 __debug_iter<_Container, _Iter>::__set_owner(const __container_type* __c)
1553 {
1554     __cont = const_cast<__container_type*>(__c);
1555     __debug_iter*& __head = __cont->__get_iterator_list(this);
1556     __next = __head;
1557     __head = this;
1558 }
1559
1560 template <class _Container, class _Iter>
1561 void
1562 __debug_iter<_Container, _Iter>::__remove_owner()
1563 {
1564     if (__cont)
1565     {
1566         __debug_iter*& __head = __cont->__get_iterator_list(this);
1567         if (__head == this)
1568             __head = __next;
1569         else
1570         {
1571             __debug_iter* __prev = __head;
1572             for (__debug_iter* __p = __head->__next; __p != this; __p = __p->__next)
1573                 __prev = __p;
1574             __prev->__next = __next;
1575         }
1576         __cont = 0;
1577     }
1578 }
1579
1580 template <class _Container, class _Iter>
1581 void
1582 __debug_iter<_Container, _Iter>::__remove_all(__container_type* __c)
1583 {
1584     __debug_iter*& __head = __c->__get_iterator_list((__debug_iter*)0);
1585     __debug_iter* __p = __head;
1586     __head = 0;
1587     while (__p)
1588     {
1589         __p->__cont = 0;
1590         __debug_iter* __n = __p->__next;
1591         __p->__next = 0;
1592         __p = __n;
1593     }
1594 }
1595
1596 template <class _Container, class _Iter>
1597 void
1598 __debug_iter<_Container, _Iter>::swap(__container_type* __x, __container_type* __y)
1599 {
1600     __debug_iter*& __head_x = __x->__get_iterator_list((__debug_iter*)0);
1601     __debug_iter*& __head_y = __y->__get_iterator_list((__debug_iter*)0);
1602     __debug_iter* __p = __head_x;
1603     __head_x = __head_y;
1604     __head_y = __p;
1605     for (__p = __head_x; __p; __p = __p->__next)
1606         __p->__cont = __x;
1607     for (__p = __head_y; __p; __p = __p->__next)
1608         __p->__cont = __y;
1609 }
1610
1611 template <class _Container, class _Iter>
1612 bool
1613 __debug_iter<_Container, _Iter>::__is_deref(false_type) const
1614 {
1615     if (__cont == 0)
1616         return false;
1617     return __i != __cont->end().base();
1618 }
1619
1620 template <class _Container, class _Iter>
1621 bool
1622 __debug_iter<_Container, _Iter>::__is_deref(true_type) const
1623 {
1624     if (__cont == 0)
1625         return false;
1626     return __i < __cont->end().base();
1627 }
1628
1629 template <class _Container, class _Iter>
1630 bool
1631 __debug_iter<_Container, _Iter>::__can_decrement(integral_constant<int, 0>) const
1632 {
1633     if (__cont == 0)
1634         return false;
1635     return __i != __cont->begin().base();
1636 }
1637
1638 template <class _Container, class _Iter>
1639 bool
1640 __debug_iter<_Container, _Iter>::__can_decrement(integral_constant<int, 1>) const
1641 {
1642     if (__cont == 0)
1643         return false;
1644     iterator_type __b = __cont->begin().base();
1645     return __b < __i && __i <= __b + __cont->size();
1646 }
1647
1648 template <class _Container, class _Iter>
1649 bool
1650 __debug_iter<_Container, _Iter>::__can_decrement(integral_constant<int, 2>) const
1651 {
1652     if (__cont == 0)
1653         return false;
1654     iterator_type __b = __cont->begin().base();
1655     return __b < __i && __i <= __b + __cont->size();
1656 }
1657
1658 template <class _Container, class _Iter>
1659 bool
1660 __debug_iter<_Container, _Iter>::__can_increment(integral_constant<int, 0>) const
1661 {
1662     if (__cont == 0)
1663         return false;
1664     return __i != __cont->end().base();
1665 }
1666
1667 template <class _Container, class _Iter>
1668 bool
1669 __debug_iter<_Container, _Iter>::__can_increment(integral_constant<int, 1>) const
1670 {
1671     if (__cont == 0)
1672         return false;
1673     iterator_type __b = __cont->begin().base();
1674     return __b <= __i && __i < __b + __cont->size();
1675 }
1676
1677 template <class _Container, class _Iter>
1678 bool
1679 __debug_iter<_Container, _Iter>::__can_increment(integral_constant<int, 2>) const
1680 {
1681     if (__cont == 0)
1682         return false;
1683     iterator_type __b = __cont->begin().base();
1684     return __b <= __i && __i < __b + __cont->size();
1685 }
1686
1687 template <class _Container, class _Iter>
1688 bool
1689 __debug_iter<_Container, _Iter>::__can_add(difference_type __n, false_type) const
1690 {
1691     if (__cont == 0)
1692         return false;
1693     iterator_type __b = __cont->begin().base();
1694     iterator_type __j = __i + __n;
1695     return __b <= __j && __j <= __b + __cont->size();
1696 }
1697
1698 template <class _Container, class _Iter>
1699 bool
1700 __debug_iter<_Container, _Iter>::__can_add(difference_type __n, true_type) const
1701 {
1702     if (__cont == 0)
1703         return false;
1704     iterator_type __b = __cont->begin().base();
1705     iterator_type __j = __i + __n;
1706     return __b <= __j && __j <= __b + __cont->size();
1707 }
1708
1709 template <class _Container, class _Iter>
1710 __debug_iter<_Container, _Iter>&
1711 __debug_iter<_Container, _Iter>::operator+=(difference_type __n)
1712 {
1713     assert(__can_add(__n));
1714     __i += __n;
1715     return *this;
1716 }
1717
1718 template <class _Container, class _Iter1, class _Iter2>
1719 inline _LIBCPP_INLINE_VISIBILITY
1720 bool
1721 operator==(const __debug_iter<_Container, _Iter1>& __x, const __debug_iter<_Container, _Iter2>& __y)
1722 {
1723     assert(__x.__cont && __x.__cont == __y.__cont);
1724     return __x.base() == __y.base();
1725 }
1726
1727 template <class _Container, class _Iter1, class _Iter2>
1728 inline _LIBCPP_INLINE_VISIBILITY
1729 bool
1730 operator!=(const __debug_iter<_Container, _Iter1>& __x, const __debug_iter<_Container, _Iter2>& __y)
1731 {
1732     return !(__x == __y);
1733 }
1734
1735 template <class _Container, class _Iter1, class _Iter2>
1736 inline _LIBCPP_INLINE_VISIBILITY
1737 bool
1738 operator<(const __debug_iter<_Container, _Iter1>& __x, const __debug_iter<_Container, _Iter2>& __y)
1739 {
1740     assert(__x.__cont && __x.__cont == __y.__cont);
1741     return __x.base() < __y.base();
1742 }
1743
1744 template <class _Container, class _Iter1, class _Iter2>
1745 inline _LIBCPP_INLINE_VISIBILITY
1746 bool
1747 operator>(const __debug_iter<_Container, _Iter1>& __x, const __debug_iter<_Container, _Iter2>& __y)
1748 {
1749     return __y < __x;
1750 }
1751
1752 template <class _Container, class _Iter1, class _Iter2>
1753 inline _LIBCPP_INLINE_VISIBILITY
1754 bool
1755 operator>=(const __debug_iter<_Container, _Iter1>& __x, const __debug_iter<_Container, _Iter2>& __y)
1756 {
1757     return !(__x < __y);
1758 }
1759
1760 template <class _Container, class _Iter1, class _Iter2>
1761 inline _LIBCPP_INLINE_VISIBILITY
1762 bool
1763 operator<=(const __debug_iter<_Container, _Iter1>& __x, const __debug_iter<_Container, _Iter2>& __y)
1764 {
1765     return !(__y < __x);
1766 }
1767
1768 template <class _Container, class _Iter1, class _Iter2>
1769 inline _LIBCPP_INLINE_VISIBILITY
1770 typename __debug_iter<_Container, _Iter1>::difference_type
1771 operator-(const __debug_iter<_Container, _Iter1>& __x, const __debug_iter<_Container, _Iter2>& __y)
1772 {
1773     assert(__x.__cont && __x.__cont == __y.__cont);
1774     return __x.base() - __y.base();
1775 }
1776
1777 template <class _Container, class _Iter>
1778 inline _LIBCPP_INLINE_VISIBILITY
1779 __debug_iter<_Container, _Iter>
1780 operator+(typename __debug_iter<_Container, _Iter>::difference_type __n,
1781           const __debug_iter<_Container, _Iter>& __x)
1782 {
1783     return __x + __n;
1784 }
1785
1786 #endif  // _LIBCPP_DEBUG
1787
1788 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_TRAILING_RETURN)
1789
1790 template <class _Cp>
1791 inline _LIBCPP_INLINE_VISIBILITY
1792 auto
1793 begin(_Cp& __c) -> decltype(__c.begin())
1794 {
1795     return __c.begin();
1796 }
1797
1798 template <class _Cp>
1799 inline _LIBCPP_INLINE_VISIBILITY
1800 auto
1801 begin(const _Cp& __c) -> decltype(__c.begin())
1802 {
1803     return __c.begin();
1804 }
1805
1806 template <class _Cp>
1807 inline _LIBCPP_INLINE_VISIBILITY
1808 auto
1809 end(_Cp& __c) -> decltype(__c.end())
1810 {
1811     return __c.end();
1812 }
1813
1814 template <class _Cp>
1815 inline _LIBCPP_INLINE_VISIBILITY
1816 auto
1817 end(const _Cp& __c) -> decltype(__c.end())
1818 {
1819     return __c.end();
1820 }
1821
1822 #else  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_TRAILING_RETURN)
1823
1824 template <class _Cp>
1825 inline _LIBCPP_INLINE_VISIBILITY
1826 typename _Cp::iterator
1827 begin(_Cp& __c)
1828 {
1829     return __c.begin();
1830 }
1831
1832 template <class _Cp>
1833 inline _LIBCPP_INLINE_VISIBILITY
1834 typename _Cp::const_iterator
1835 begin(const _Cp& __c)
1836 {
1837     return __c.begin();
1838 }
1839
1840 template <class _Cp>
1841 inline _LIBCPP_INLINE_VISIBILITY
1842 typename _Cp::iterator
1843 end(_Cp& __c)
1844 {
1845     return __c.end();
1846 }
1847
1848 template <class _Cp>
1849 inline _LIBCPP_INLINE_VISIBILITY
1850 typename _Cp::const_iterator
1851 end(const _Cp& __c)
1852 {
1853     return __c.end();
1854 }
1855
1856 #endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_TRAILING_RETURN)
1857
1858 template <class _Tp, size_t _Np>
1859 inline _LIBCPP_INLINE_VISIBILITY
1860 _Tp*
1861 begin(_Tp (&__array)[_Np])
1862 {
1863     return __array;
1864 }
1865
1866 template <class _Tp, size_t _Np>
1867 inline _LIBCPP_INLINE_VISIBILITY
1868 _Tp*
1869 end(_Tp (&__array)[_Np])
1870 {
1871     return __array + _Np;
1872 }
1873
1874 _LIBCPP_END_NAMESPACE_STD
1875
1876 #endif  // _LIBCPP_ITERATOR