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