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() throw();
 267     istreambuf_iterator(istream_type& s) throw();
 268     istreambuf_iterator(streambuf_type* s) throw();
 269     istreambuf_iterator(a-private-type) throw();
 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) throw();
 297     ostreambuf_iterator(streambuf_type* s) throw();
 298     ostreambuf_iterator& operator=(charT c);
 299     ostreambuf_iterator& operator*();
 300     ostreambuf_iterator& operator++();
 301     ostreambuf_iterator& operator++(int);
 302     bool failed() const throw();
 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() throw() : __sbuf_(0) {}
 819     _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(istream_type& __s) throw()
 820         : __sbuf_(__s.rdbuf()) {__test_for_eof();}
 821     _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(streambuf_type* __s) throw()
 822         : __sbuf_(__s) {__test_for_eof();}
 823     _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(const __proxy& __p) throw()
 824         : __sbuf_(__p.__sbuf_) {}
 825
 826     _LIBCPP_INLINE_VISIBILITY _CharT     operator*() const {return __sbuf_->sgetc();}
 827     _LIBCPP_INLINE_VISIBILITY char_type* operator->() const {return nullptr;}
 828     _LIBCPP_INLINE_VISIBILITY istreambuf_iterator& operator++()
 829         {
 830             if (traits_type::eq_int_type(__sbuf_->snextc(), traits_type::eof()))
 831                 __sbuf_ = 0;
 832             return *this;
 833         }
 834     _LIBCPP_INLINE_VISIBILITY __proxy              operator++(int)
 835         {
 836             char_type __c = __sbuf_->sgetc();
 837             ++(*this);
 838             return __proxy(__c, __sbuf_);
 839         }
 840
 841     _LIBCPP_INLINE_VISIBILITY bool equal(const istreambuf_iterator& __b) const
 842         {return (__sbuf_ == 0) == (__b.__sbuf_ == 0);}
 843 };
 844
 845 template <class _CharT, class _Traits>
 846 inline _LIBCPP_INLINE_VISIBILITY
 847 bool operator==(const istreambuf_iterator<_CharT,_Traits>& __a,
 848                 const istreambuf_iterator<_CharT,_Traits>& __b)
 849                 {return __a.equal(__b);}
 850
 851 template <class _CharT, class _Traits>
 852 inline _LIBCPP_INLINE_VISIBILITY
 853 bool operator!=(const istreambuf_iterator<_CharT,_Traits>& __a,
 854                 const istreambuf_iterator<_CharT,_Traits>& __b)
 855                 {return !__a.equal(__b);}
 856
 857 template <class _CharT, class _Traits>
 858 class _LIBCPP_VISIBLE ostreambuf_iterator
 859     : public iterator<output_iterator_tag, void, void, void, void>
 860 {
 861 public:
 862     typedef _CharT                          char_type;
 863     typedef _Traits                         traits_type;
 864     typedef basic_streambuf<_CharT,_Traits> streambuf_type;
 865     typedef basic_ostream<_CharT,_Traits>   ostream_type;
 866 private:
 867     streambuf_type* __sbuf_;
 868 public:
 869     _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator(ostream_type& __s) throw()
 870         : __sbuf_(__s.rdbuf()) {}
 871     _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator(streambuf_type* __s) throw()
 872         : __sbuf_(__s) {}
 873     _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator=(_CharT __c)
 874         {
 875             if (__sbuf_ && traits_type::eq_int_type(__sbuf_->sputc(__c), traits_type::eof()))
 876                 __sbuf_ = 0;
 877             return *this;
 878         }
 879     _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator*()     {return *this;}
 880     _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator++()    {return *this;}
 881     _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator++(int) {return *this;}
 882     _LIBCPP_INLINE_VISIBILITY bool failed() const throw() {return __sbuf_ == 0;}
 883 };
 884
 885 template <class _Iter>
 886 class _LIBCPP_VISIBLE move_iterator
 887 {
 888 private:
 889     _Iter __i;
 890 public:
 891     typedef _Iter                                            iterator_type;
 892     typedef typename iterator_traits<iterator_type>::iterator_category iterator_category;
 893     typedef typename iterator_traits<iterator_type>::value_type value_type;
 894     typedef typename iterator_traits<iterator_type>::difference_type difference_type;
 895     typedef typename iterator_traits<iterator_type>::pointer pointer;
 896 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
 897     typedef value_type&& reference;
 898 #else
 899     typedef typename iterator_traits<iterator_type>::reference reference;
 900 #endif
 901
 902     _LIBCPP_INLINE_VISIBILITY move_iterator() : __i() {}
 903     _LIBCPP_INLINE_VISIBILITY explicit move_iterator(_Iter __x) : __i(__x) {}
 904     template <class _Up> _LIBCPP_INLINE_VISIBILITY move_iterator(const move_iterator<_Up>& __u)
 905         : __i(__u.base()) {}
 906     _LIBCPP_INLINE_VISIBILITY _Iter base() const {return __i;}
 907     _LIBCPP_INLINE_VISIBILITY reference operator*() const {
 908       return static_cast<reference>(*__i);
 909     }
 910     _LIBCPP_INLINE_VISIBILITY pointer  operator->() const {
 911       typename iterator_traits<iterator_type>::reference __ref = *__i;
 912       return &__ref;
 913     }
 914     _LIBCPP_INLINE_VISIBILITY move_iterator& operator++() {++__i; return *this;}
 915     _LIBCPP_INLINE_VISIBILITY move_iterator  operator++(int)
 916         {move_iterator __tmp(*this); ++__i; return __tmp;}
 917     _LIBCPP_INLINE_VISIBILITY move_iterator& operator--() {--__i; return *this;}
 918     _LIBCPP_INLINE_VISIBILITY move_iterator  operator--(int)
 919         {move_iterator __tmp(*this); --__i; return __tmp;}
 920     _LIBCPP_INLINE_VISIBILITY move_iterator  operator+ (difference_type __n) const
 921         {return move_iterator(__i + __n);}
 922     _LIBCPP_INLINE_VISIBILITY move_iterator& operator+=(difference_type __n)
 923         {__i += __n; return *this;}
 924     _LIBCPP_INLINE_VISIBILITY move_iterator  operator- (difference_type __n) const
 925         {return move_iterator(__i - __n);}
 926     _LIBCPP_INLINE_VISIBILITY move_iterator& operator-=(difference_type __n)
 927         {__i -= __n; return *this;}
 928     _LIBCPP_INLINE_VISIBILITY reference         operator[](difference_type __n) const
 929     {
 930       return static_cast<reference>(__i[__n]);
 931     }
 932 };
 933
 934 template <class _Iter1, class _Iter2>
 935 inline _LIBCPP_INLINE_VISIBILITY
 936 bool
 937 operator==(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
 938 {
 939     return __x.base() == __y.base();
 940 }
 941
 942 template <class _Iter1, class _Iter2>
 943 inline _LIBCPP_INLINE_VISIBILITY
 944 bool
 945 operator<(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
 946 {
 947     return __x.base() < __y.base();
 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 typename move_iterator<_Iter1>::difference_type
 985 operator-(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
 986 {
 987     return __x.base() - __y.base();
 988 }
 989
 990 template <class _Iter>
 991 inline _LIBCPP_INLINE_VISIBILITY
 992 move_iterator<_Iter>
 993 operator+(typename move_iterator<_Iter>::difference_type __n, const move_iterator<_Iter>& __x)
 994 {
 995     return move_iterator<_Iter>(__x.base() + __n);
 996 }
 997
 998 template <class _Iter>
 999 inline _LIBCPP_INLINE_VISIBILITY
1000 move_iterator<_Iter>
1001 make_move_iterator(const _Iter& __i)
1002 {
1003     return move_iterator<_Iter>(__i);
1004 }
1005
1006 // __wrap_iter
1007
1008 template <class _Iter> class __wrap_iter;
1009
1010 template <class _Iter1, class _Iter2>
1011 bool
1012 operator==(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1013
1014 template <class _Iter1, class _Iter2>
1015 bool
1016 operator<(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1017
1018 template <class _Iter1, class _Iter2>
1019 bool
1020 operator!=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1021
1022 template <class _Iter1, class _Iter2>
1023 bool
1024 operator>(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1025
1026 template <class _Iter1, class _Iter2>
1027 bool
1028 operator>=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1029
1030 template <class _Iter1, class _Iter2>
1031 bool
1032 operator<=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1033
1034 template <class _Iter1, class _Iter2>
1035 typename __wrap_iter<_Iter1>::difference_type
1036 operator-(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1037
1038 template <class _Iter>
1039 __wrap_iter<_Iter>
1040 operator+(typename __wrap_iter<_Iter>::difference_type, __wrap_iter<_Iter>) _NOEXCEPT;
1041
1042 template <class _I, class _O> _O copy(_I, _I, _O);
1043 template <class _B1, class _B2> _B2 copy_backward(_B1, _B1, _B2);
1044 template <class _I, class _O> _O move(_I, _I, _O);
1045 template <class _B1, class _B2> _B2 move_backward(_B1, _B1, _B2);
1046
1047 template <class _Tp>
1048 typename enable_if
1049 <
1050     is_trivially_copy_assignable<_Tp>::value,
1051     _Tp*
1052 >::type
1053 __unwrap_iter(__wrap_iter<_Tp*>);
1054
1055 template <class _Iter>
1056 class __wrap_iter
1057 {
1058 public:
1059     typedef _Iter                                                      iterator_type;
1060     typedef typename iterator_traits<iterator_type>::iterator_category iterator_category;
1061     typedef typename iterator_traits<iterator_type>::value_type        value_type;
1062     typedef typename iterator_traits<iterator_type>::difference_type   difference_type;
1063     typedef typename iterator_traits<iterator_type>::pointer           pointer;
1064     typedef typename iterator_traits<iterator_type>::reference         reference;
1065 private:
1066     iterator_type __i;
1067 public:
1068     _LIBCPP_INLINE_VISIBILITY __wrap_iter() _NOEXCEPT
1069     {
1070 #if _LIBCPP_DEBUG_LEVEL >= 2
1071         __get_db()->__insert_i(this);
1072 #endif
1073     }
1074     template <class _Up> _LIBCPP_INLINE_VISIBILITY __wrap_iter(const __wrap_iter<_Up>& __u,
1075         typename enable_if<is_convertible<_Up, iterator_type>::value>::type* = 0) _NOEXCEPT
1076         : __i(__u.base())
1077     {
1078 #if _LIBCPP_DEBUG_LEVEL >= 2
1079         __get_db()->__iterator_copy(this, &__u);
1080 #endif
1081     }
1082 #if _LIBCPP_DEBUG_LEVEL >= 2
1083     _LIBCPP_INLINE_VISIBILITY
1084     __wrap_iter(const __wrap_iter& __x)
1085         : __i(__x.base())
1086     {
1087         __get_db()->__iterator_copy(this, &__x);
1088     }
1089     _LIBCPP_INLINE_VISIBILITY
1090     __wrap_iter& operator=(const __wrap_iter& __x)
1091     {
1092         if (this != &__x)
1093         {
1094             __get_db()->__iterator_copy(this, &__x);
1095             __i = __x.__i;
1096         }
1097         return *this;
1098     }
1099     _LIBCPP_INLINE_VISIBILITY
1100     ~__wrap_iter()
1101     {
1102         __get_db()->__erase_i(this);
1103     }
1104 #endif
1105     _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT
1106     {
1107 #if _LIBCPP_DEBUG_LEVEL >= 2
1108         _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
1109                        "Attempted to dereference a non-dereferenceable iterator");
1110 #endif
1111         return *__i;
1112     }
1113     _LIBCPP_INLINE_VISIBILITY pointer  operator->() const _NOEXCEPT {return &(operator*());}
1114     _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator++() _NOEXCEPT
1115     {
1116 #if _LIBCPP_DEBUG_LEVEL >= 2
1117         _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
1118                        "Attempted to increment non-incrementable iterator");
1119 #endif
1120         ++__i;
1121         return *this;
1122     }
1123     _LIBCPP_INLINE_VISIBILITY __wrap_iter  operator++(int) _NOEXCEPT
1124         {__wrap_iter __tmp(*this); ++(*this); return __tmp;}
1125     _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator--() _NOEXCEPT
1126     {
1127 #if _LIBCPP_DEBUG_LEVEL >= 2
1128         _LIBCPP_ASSERT(__get_const_db()->__decrementable(this),
1129                        "Attempted to decrement non-decrementable iterator");
1130 #endif
1131         --__i;
1132         return *this;
1133     }
1134     _LIBCPP_INLINE_VISIBILITY __wrap_iter  operator--(int) _NOEXCEPT
1135         {__wrap_iter __tmp(*this); --(*this); return __tmp;}
1136     _LIBCPP_INLINE_VISIBILITY __wrap_iter  operator+ (difference_type __n) const _NOEXCEPT
1137         {__wrap_iter __w(*this); __w += __n; return __w;}
1138     _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator+=(difference_type __n) _NOEXCEPT
1139     {
1140 #if _LIBCPP_DEBUG_LEVEL >= 2
1141         _LIBCPP_ASSERT(__get_const_db()->__addable(this, __n),
1142                    "Attempted to add/subtract iterator outside of valid range");
1143 #endif
1144         __i += __n;
1145         return *this;
1146     }
1147     _LIBCPP_INLINE_VISIBILITY __wrap_iter  operator- (difference_type __n) const _NOEXCEPT
1148         {return *this + (-__n);}
1149     _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator-=(difference_type __n) _NOEXCEPT
1150         {*this += -__n; return *this;}
1151     _LIBCPP_INLINE_VISIBILITY reference        operator[](difference_type __n) const _NOEXCEPT
1152     {
1153 #if _LIBCPP_DEBUG_LEVEL >= 2
1154         _LIBCPP_ASSERT(__get_const_db()->__subscriptable(this, __n),
1155                    "Attempted to subscript iterator outside of valid range");
1156 #endif
1157         return __i[__n];
1158     }
1159
1160     _LIBCPP_INLINE_VISIBILITY iterator_type base() const _NOEXCEPT {return __i;}
1161
1162 private:
1163     _LIBCPP_INLINE_VISIBILITY __wrap_iter(iterator_type __x) _NOEXCEPT : __i(__x) {}
1164 #if _LIBCPP_DEBUG_LEVEL >= 2
1165     _LIBCPP_INLINE_VISIBILITY __wrap_iter(const void* __p, iterator_type __x) : __i(__x)
1166     {
1167         __get_db()->__insert_ic(this, __p);
1168     }
1169 #endif
1170
1171     template <class _Up> friend class __wrap_iter;
1172     template <class _CharT, class _Traits, class _Alloc> friend class basic_string;
1173     template <class _Tp, class _Alloc> friend class vector;
1174
1175     template <class _Iter1, class _Iter2>
1176     friend
1177     bool
1178     operator==(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1179
1180     template <class _Iter1, class _Iter2>
1181     friend
1182     bool
1183     operator<(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1184
1185     template <class _Iter1, class _Iter2>
1186     friend
1187     bool
1188     operator!=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1189
1190     template <class _Iter1, class _Iter2>
1191     friend
1192     bool
1193     operator>(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1194
1195     template <class _Iter1, class _Iter2>
1196     friend
1197     bool
1198     operator>=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1199
1200     template <class _Iter1, class _Iter2>
1201     friend
1202     bool
1203     operator<=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1204
1205     template <class _Iter1, class _Iter2>
1206     friend
1207     typename __wrap_iter<_Iter1>::difference_type
1208     operator-(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1209
1210     template <class _Iter1>
1211     friend
1212     __wrap_iter<_Iter1>
1213     operator+(typename __wrap_iter<_Iter1>::difference_type, __wrap_iter<_Iter1>) _NOEXCEPT;
1214
1215     template <class _I, class _O> friend _O copy(_I, _I, _O);
1216     template <class _B1, class _B2> friend _B2 copy_backward(_B1, _B1, _B2);
1217     template <class _I, class _O> friend _O move(_I, _I, _O);
1218     template <class _B1, class _B2> friend _B2 move_backward(_B1, _B1, _B2);
1219
1220     template <class _Tp>
1221     friend
1222     typename enable_if
1223     <
1224         is_trivially_copy_assignable<_Tp>::value,
1225         _Tp*
1226     >::type
1227     __unwrap_iter(__wrap_iter<_Tp*>);
1228 };
1229
1230 template <class _Iter1, class _Iter2>
1231 inline _LIBCPP_INLINE_VISIBILITY
1232 bool
1233 operator==(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1234 {
1235 #if _LIBCPP_DEBUG_LEVEL >= 2
1236     _LIBCPP_ASSERT(__get_const_db()->__comparable(&__x, &__y),
1237                    "Attempted to compare incomparable iterators");
1238 #endif
1239     return __x.base() == __y.base();
1240 }
1241
1242 template <class _Iter1, class _Iter2>
1243 inline _LIBCPP_INLINE_VISIBILITY
1244 bool
1245 operator<(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1246 {
1247 #if _LIBCPP_DEBUG_LEVEL >= 2
1248     _LIBCPP_ASSERT(__get_const_db()->__comparable(&__x, &__y),
1249                    "Attempted to compare incomparable iterators");
1250 #endif
1251     return __x.base() < __y.base();
1252 }
1253
1254 template <class _Iter1, class _Iter2>
1255 inline _LIBCPP_INLINE_VISIBILITY
1256 bool
1257 operator!=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1258 {
1259     return !(__x == __y);
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     return __y < __x;
1268 }
1269
1270 template <class _Iter1, class _Iter2>
1271 inline _LIBCPP_INLINE_VISIBILITY
1272 bool
1273 operator>=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1274 {
1275     return !(__x < __y);
1276 }
1277
1278 template <class _Iter1, class _Iter2>
1279 inline _LIBCPP_INLINE_VISIBILITY
1280 bool
1281 operator<=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1282 {
1283     return !(__y < __x);
1284 }
1285
1286 template <class _Iter1, class _Iter2>
1287 inline _LIBCPP_INLINE_VISIBILITY
1288 typename __wrap_iter<_Iter1>::difference_type
1289 operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1290 {
1291 #if _LIBCPP_DEBUG_LEVEL >= 2
1292     _LIBCPP_ASSERT(__get_const_db()->__comparable(&__x, &__y),
1293                    "Attempted to subtract incompatible iterators");
1294 #endif
1295     return __x.base() - __y.base();
1296 }
1297
1298 template <class _Iter>
1299 inline _LIBCPP_INLINE_VISIBILITY
1300 __wrap_iter<_Iter>
1301 operator+(typename __wrap_iter<_Iter>::difference_type __n,
1302           __wrap_iter<_Iter> __x) _NOEXCEPT
1303 {
1304     __x += __n;
1305     return __x;
1306 }
1307
1308 #ifdef _LIBCPP_DEBUG
1309
1310 // __debug_iter
1311
1312 template <class _Container, class _Iter> class __debug_iter;
1313
1314 template <class _Container, class _Iter1, class _Iter2>
1315 bool
1316 operator==(const __debug_iter<_Container, _Iter1>&, const __debug_iter<_Container, _Iter2>&);
1317
1318 template <class _Container, class _Iter1, class _Iter2>
1319 bool
1320 operator<(const __debug_iter<_Container, _Iter1>&, const __debug_iter<_Container, _Iter2>&);
1321
1322 template <class _Container, class _Iter1, class _Iter2>
1323 bool
1324 operator!=(const __debug_iter<_Container, _Iter1>&, const __debug_iter<_Container, _Iter2>&);
1325
1326 template <class _Container, class _Iter1, class _Iter2>
1327 bool
1328 operator>(const __debug_iter<_Container, _Iter1>&, const __debug_iter<_Container, _Iter2>&);
1329
1330 template <class _Container, class _Iter1, class _Iter2>
1331 bool
1332 operator>=(const __debug_iter<_Container, _Iter1>&, const __debug_iter<_Container, _Iter2>&);
1333
1334 template <class _Container, class _Iter1, class _Iter2>
1335 bool
1336 operator<=(const __debug_iter<_Container, _Iter1>&, const __debug_iter<_Container, _Iter2>&);
1337
1338 template <class _Container, class _Iter1, class _Iter2>
1339 typename __debug_iter<_Container, _Iter1>::difference_type
1340 operator-(const __debug_iter<_Container, _Iter1>&, const __debug_iter<_Container, _Iter2>&);
1341
1342 template <class _Container, class _Iter>
1343 __debug_iter<_Container, _Iter>
1344 operator+(typename __debug_iter<_Container, _Iter>::difference_type, const __debug_iter<_Container, _Iter>&);
1345
1346 template <class _Container, class _Iter>
1347 class __debug_iter
1348 {
1349 public:
1350     typedef _Iter                                                      iterator_type;
1351     typedef _Container                                                 __container_type;
1352     typedef typename iterator_traits<iterator_type>::iterator_category iterator_category;
1353     typedef typename iterator_traits<iterator_type>::value_type        value_type;
1354     typedef typename iterator_traits<iterator_type>::difference_type   difference_type;
1355     typedef typename iterator_traits<iterator_type>::pointer           pointer;
1356     typedef typename iterator_traits<iterator_type>::reference         reference;
1357 private:
1358     iterator_type __i;
1359     __debug_iter* __next;
1360     __container_type* __cont;
1361
1362 public:
1363     _LIBCPP_INLINE_VISIBILITY __debug_iter() : __next(0), __cont(0) {}
1364     _LIBCPP_INLINE_VISIBILITY __debug_iter(const __debug_iter& __x)
1365         : __i(__x.base()), __next(0), __cont(0) {__set_owner(__x.__cont);}
1366     __debug_iter& operator=(const __debug_iter& __x);
1367     template <class _Up> _LIBCPP_INLINE_VISIBILITY __debug_iter(const __debug_iter<_Container, _Up>& __u,
1368         typename enable_if<is_convertible<_Up, iterator_type>::value>::type* = 0)
1369         : __i(__u.base()), __next(0), __cont(0) {__set_owner(__u.__cont);}
1370     _LIBCPP_INLINE_VISIBILITY ~__debug_iter() {__remove_owner();}
1371     _LIBCPP_INLINE_VISIBILITY reference operator*() const {assert(__is_deref()); return *__i;}
1372     _LIBCPP_INLINE_VISIBILITY pointer  operator->() const {return &(operator*());}
1373     _LIBCPP_INLINE_VISIBILITY __debug_iter& operator++() {assert(__can_increment()); ++__i; return *this;}
1374     _LIBCPP_INLINE_VISIBILITY __debug_iter  operator++(int)
1375         {__debug_iter __tmp(*this); operator++(); return __tmp;}
1376     _LIBCPP_INLINE_VISIBILITY __debug_iter& operator--() {assert(__can_decrement()); --__i; return *this;}
1377     _LIBCPP_INLINE_VISIBILITY __debug_iter  operator--(int)
1378         {__debug_iter __tmp(*this); operator--(); return __tmp;}
1379     _LIBCPP_INLINE_VISIBILITY __debug_iter  operator+ (difference_type __n) const
1380         {__debug_iter __t(*this); __t += __n; return __t;}
1381     __debug_iter& operator+=(difference_type __n);
1382     _LIBCPP_INLINE_VISIBILITY __debug_iter  operator- (difference_type __n) const
1383         {__debug_iter __t(*this); __t -= __n; return __t;}
1384     _LIBCPP_INLINE_VISIBILITY __debug_iter& operator-=(difference_type __n)
1385         {*this += -__n; return *this;}
1386     _LIBCPP_INLINE_VISIBILITY reference        operator[](difference_type __n) const
1387         {return *(*this + __n);}
1388
1389 private:
1390     _LIBCPP_INLINE_VISIBILITY __debug_iter(const __container_type* __c, iterator_type __x)
1391         : __i(__x), __next(0), __cont(0) {__set_owner(__c);}
1392     _LIBCPP_INLINE_VISIBILITY iterator_type base() const {return __i;}
1393
1394     void __set_owner(const __container_type* __c);
1395     void __remove_owner();
1396     static void __remove_all(__container_type* __c);
1397     static void swap(__container_type* __x, __container_type* __y);
1398
1399     _LIBCPP_INLINE_VISIBILITY bool __is_deref() const
1400         {return __is_deref(__is_random_access_iterator<iterator_type>());}
1401     bool __is_deref(false_type) const;
1402     bool __is_deref(true_type) const;
1403     _LIBCPP_INLINE_VISIBILITY bool __can_decrement() const
1404         {return __can_decrement(integral_constant<int, is_pointer<iterator_type>::value ? 2:
1405                                                        __is_random_access_iterator<iterator_type>::value ? 1 : 0>());}
1406     bool __can_decrement(integral_constant<int, 0>) const;
1407     bool __can_decrement(integral_constant<int, 1>) const;
1408     bool __can_decrement(integral_constant<int, 2>) const;
1409     _LIBCPP_INLINE_VISIBILITY bool __can_increment() const
1410         {return __can_increment(integral_constant<int, is_pointer<iterator_type>::value ? 2:
1411                                                        __is_random_access_iterator<iterator_type>::value ? 1 : 0>());}
1412     bool __can_increment(integral_constant<int, 0>) const;
1413     bool __can_increment(integral_constant<int, 1>) const;
1414     bool __can_increment(integral_constant<int, 2>) const;
1415
1416     _LIBCPP_INLINE_VISIBILITY bool __can_add(difference_type __n) const
1417         {return __can_add(__n, is_pointer<iterator_type>());}
1418     bool __can_add(difference_type __n, false_type) const;
1419     bool __can_add(difference_type __n, true_type) const;
1420
1421     template <class _Cp, class _Up> friend class __debug_iter;
1422     friend class _Container::__self;
1423
1424     template <class _Cp, class _Iter1, class _Iter2>
1425     friend
1426     bool
1427     operator==(const __debug_iter<_Cp, _Iter1>&, const __debug_iter<_Cp, _Iter2>&);
1428
1429     template <class _Cp, class _Iter1, class _Iter2>
1430     friend
1431     bool
1432     operator<(const __debug_iter<_Cp, _Iter1>&, const __debug_iter<_Cp, _Iter2>&);
1433
1434     template <class _Cp, class _Iter1, class _Iter2>
1435     friend
1436     bool
1437     operator!=(const __debug_iter<_Cp, _Iter1>&, const __debug_iter<_Cp, _Iter2>&);
1438
1439     template <class _Cp, class _Iter1, class _Iter2>
1440     friend
1441     bool
1442     operator>(const __debug_iter<_Cp, _Iter1>&, const __debug_iter<_Cp, _Iter2>&);
1443
1444     template <class _Cp, class _Iter1, class _Iter2>
1445     friend
1446     bool
1447     operator>=(const __debug_iter<_Cp, _Iter1>&, const __debug_iter<_Cp, _Iter2>&);
1448
1449     template <class _Cp, class _Iter1, class _Iter2>
1450     friend
1451     bool
1452     operator<=(const __debug_iter<_Cp, _Iter1>&, const __debug_iter<_Cp, _Iter2>&);
1453
1454     template <class _Cp, class _Iter1, class _Iter2>
1455     friend
1456     typename __debug_iter<_Cp, _Iter1>::difference_type
1457     operator-(const __debug_iter<_Cp, _Iter1>&, const __debug_iter<_Cp, _Iter2>&);
1458
1459     template <class _Cp, class _Iter1>
1460     friend
1461     __debug_iter<_Cp, _Iter1>
1462     operator+(typename __debug_iter<_Cp, _Iter1>::difference_type, const __debug_iter<_Cp, _Iter1>&);
1463 };
1464
1465 template <class _Container, class _Iter>
1466 __debug_iter<_Container, _Iter>&
1467 __debug_iter<_Container, _Iter>::operator=(const __debug_iter& __x)
1468 {
1469     if (this != &__x)
1470     {
1471         __remove_owner();
1472         __i = __x.__i;
1473         __set_owner(__x.__cont);
1474     }
1475     return *this;
1476 }
1477
1478 template <class _Container, class _Iter>
1479 void
1480 __debug_iter<_Container, _Iter>::__set_owner(const __container_type* __c)
1481 {
1482     __cont = const_cast<__container_type*>(__c);
1483     __debug_iter*& __head = __cont->__get_iterator_list(this);
1484     __next = __head;
1485     __head = this;
1486 }
1487
1488 template <class _Container, class _Iter>
1489 void
1490 __debug_iter<_Container, _Iter>::__remove_owner()
1491 {
1492     if (__cont)
1493     {
1494         __debug_iter*& __head = __cont->__get_iterator_list(this);
1495         if (__head == this)
1496             __head = __next;
1497         else
1498         {
1499             __debug_iter* __prev = __head;
1500             for (__debug_iter* __p = __head->__next; __p != this; __p = __p->__next)
1501                 __prev = __p;
1502             __prev->__next = __next;
1503         }
1504         __cont = 0;
1505     }
1506 }
1507
1508 template <class _Container, class _Iter>
1509 void
1510 __debug_iter<_Container, _Iter>::__remove_all(__container_type* __c)
1511 {
1512     __debug_iter*& __head = __c->__get_iterator_list((__debug_iter*)0);
1513     __debug_iter* __p = __head;
1514     __head = 0;
1515     while (__p)
1516     {
1517         __p->__cont = 0;
1518         __debug_iter* __n = __p->__next;
1519         __p->__next = 0;
1520         __p = __n;
1521     }
1522 }
1523
1524 template <class _Container, class _Iter>
1525 void
1526 __debug_iter<_Container, _Iter>::swap(__container_type* __x, __container_type* __y)
1527 {
1528     __debug_iter*& __head_x = __x->__get_iterator_list((__debug_iter*)0);
1529     __debug_iter*& __head_y = __y->__get_iterator_list((__debug_iter*)0);
1530     __debug_iter* __p = __head_x;
1531     __head_x = __head_y;
1532     __head_y = __p;
1533     for (__p = __head_x; __p; __p = __p->__next)
1534         __p->__cont = __x;
1535     for (__p = __head_y; __p; __p = __p->__next)
1536         __p->__cont = __y;
1537 }
1538
1539 template <class _Container, class _Iter>
1540 bool
1541 __debug_iter<_Container, _Iter>::__is_deref(false_type) const
1542 {
1543     if (__cont == 0)
1544         return false;
1545     return __i != __cont->end().base();
1546 }
1547
1548 template <class _Container, class _Iter>
1549 bool
1550 __debug_iter<_Container, _Iter>::__is_deref(true_type) const
1551 {
1552     if (__cont == 0)
1553         return false;
1554     return __i < __cont->end().base();
1555 }
1556
1557 template <class _Container, class _Iter>
1558 bool
1559 __debug_iter<_Container, _Iter>::__can_decrement(integral_constant<int, 0>) const
1560 {
1561     if (__cont == 0)
1562         return false;
1563     return __i != __cont->begin().base();
1564 }
1565
1566 template <class _Container, class _Iter>
1567 bool
1568 __debug_iter<_Container, _Iter>::__can_decrement(integral_constant<int, 1>) const
1569 {
1570     if (__cont == 0)
1571         return false;
1572     iterator_type __b = __cont->begin().base();
1573     return __b < __i && __i <= __b + __cont->size();
1574 }
1575
1576 template <class _Container, class _Iter>
1577 bool
1578 __debug_iter<_Container, _Iter>::__can_decrement(integral_constant<int, 2>) const
1579 {
1580     if (__cont == 0)
1581         return false;
1582     iterator_type __b = __cont->begin().base();
1583     return __b < __i && __i <= __b + __cont->size();
1584 }
1585
1586 template <class _Container, class _Iter>
1587 bool
1588 __debug_iter<_Container, _Iter>::__can_increment(integral_constant<int, 0>) const
1589 {
1590     if (__cont == 0)
1591         return false;
1592     return __i != __cont->end().base();
1593 }
1594
1595 template <class _Container, class _Iter>
1596 bool
1597 __debug_iter<_Container, _Iter>::__can_increment(integral_constant<int, 1>) const
1598 {
1599     if (__cont == 0)
1600         return false;
1601     iterator_type __b = __cont->begin().base();
1602     return __b <= __i && __i < __b + __cont->size();
1603 }
1604
1605 template <class _Container, class _Iter>
1606 bool
1607 __debug_iter<_Container, _Iter>::__can_increment(integral_constant<int, 2>) const
1608 {
1609     if (__cont == 0)
1610         return false;
1611     iterator_type __b = __cont->begin().base();
1612     return __b <= __i && __i < __b + __cont->size();
1613 }
1614
1615 template <class _Container, class _Iter>
1616 bool
1617 __debug_iter<_Container, _Iter>::__can_add(difference_type __n, false_type) const
1618 {
1619     if (__cont == 0)
1620         return false;
1621     iterator_type __b = __cont->begin().base();
1622     iterator_type __j = __i + __n;
1623     return __b <= __j && __j <= __b + __cont->size();
1624 }
1625
1626 template <class _Container, class _Iter>
1627 bool
1628 __debug_iter<_Container, _Iter>::__can_add(difference_type __n, true_type) const
1629 {
1630     if (__cont == 0)
1631         return false;
1632     iterator_type __b = __cont->begin().base();
1633     iterator_type __j = __i + __n;
1634     return __b <= __j && __j <= __b + __cont->size();
1635 }
1636
1637 template <class _Container, class _Iter>
1638 __debug_iter<_Container, _Iter>&
1639 __debug_iter<_Container, _Iter>::operator+=(difference_type __n)
1640 {
1641     assert(__can_add(__n));
1642     __i += __n;
1643     return *this;
1644 }
1645
1646 template <class _Container, class _Iter1, class _Iter2>
1647 inline _LIBCPP_INLINE_VISIBILITY
1648 bool
1649 operator==(const __debug_iter<_Container, _Iter1>& __x, const __debug_iter<_Container, _Iter2>& __y)
1650 {
1651     assert(__x.__cont && __x.__cont == __y.__cont);
1652     return __x.base() == __y.base();
1653 }
1654
1655 template <class _Container, class _Iter1, class _Iter2>
1656 inline _LIBCPP_INLINE_VISIBILITY
1657 bool
1658 operator!=(const __debug_iter<_Container, _Iter1>& __x, const __debug_iter<_Container, _Iter2>& __y)
1659 {
1660     return !(__x == __y);
1661 }
1662
1663 template <class _Container, class _Iter1, class _Iter2>
1664 inline _LIBCPP_INLINE_VISIBILITY
1665 bool
1666 operator<(const __debug_iter<_Container, _Iter1>& __x, const __debug_iter<_Container, _Iter2>& __y)
1667 {
1668     assert(__x.__cont && __x.__cont == __y.__cont);
1669     return __x.base() < __y.base();
1670 }
1671
1672 template <class _Container, class _Iter1, class _Iter2>
1673 inline _LIBCPP_INLINE_VISIBILITY
1674 bool
1675 operator>(const __debug_iter<_Container, _Iter1>& __x, const __debug_iter<_Container, _Iter2>& __y)
1676 {
1677     return __y < __x;
1678 }
1679
1680 template <class _Container, class _Iter1, class _Iter2>
1681 inline _LIBCPP_INLINE_VISIBILITY
1682 bool
1683 operator>=(const __debug_iter<_Container, _Iter1>& __x, const __debug_iter<_Container, _Iter2>& __y)
1684 {
1685     return !(__x < __y);
1686 }
1687
1688 template <class _Container, class _Iter1, class _Iter2>
1689 inline _LIBCPP_INLINE_VISIBILITY
1690 bool
1691 operator<=(const __debug_iter<_Container, _Iter1>& __x, const __debug_iter<_Container, _Iter2>& __y)
1692 {
1693     return !(__y < __x);
1694 }
1695
1696 template <class _Container, class _Iter1, class _Iter2>
1697 inline _LIBCPP_INLINE_VISIBILITY
1698 typename __debug_iter<_Container, _Iter1>::difference_type
1699 operator-(const __debug_iter<_Container, _Iter1>& __x, const __debug_iter<_Container, _Iter2>& __y)
1700 {
1701     assert(__x.__cont && __x.__cont == __y.__cont);
1702     return __x.base() - __y.base();
1703 }
1704
1705 template <class _Container, class _Iter>
1706 inline _LIBCPP_INLINE_VISIBILITY
1707 __debug_iter<_Container, _Iter>
1708 operator+(typename __debug_iter<_Container, _Iter>::difference_type __n,
1709           const __debug_iter<_Container, _Iter>& __x)
1710 {
1711     return __x + __n;
1712 }
1713
1714 #endif  // _LIBCPP_DEBUG
1715
1716 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_TRAILING_RETURN)
1717
1718 template <class _C>
1719 inline _LIBCPP_INLINE_VISIBILITY
1720 auto
1721 begin(_C& __c) -> decltype(__c.begin())
1722 {
1723     return __c.begin();
1724 }
1725
1726 template <class _C>
1727 inline _LIBCPP_INLINE_VISIBILITY
1728 auto
1729 begin(const _C& __c) -> decltype(__c.begin())
1730 {
1731     return __c.begin();
1732 }
1733
1734 template <class _C>
1735 inline _LIBCPP_INLINE_VISIBILITY
1736 auto
1737 end(_C& __c) -> decltype(__c.end())
1738 {
1739     return __c.end();
1740 }
1741
1742 template <class _C>
1743 inline _LIBCPP_INLINE_VISIBILITY
1744 auto
1745 end(const _C& __c) -> decltype(__c.end())
1746 {
1747     return __c.end();
1748 }
1749
1750 #else  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_TRAILING_RETURN)
1751
1752 template <class _C>
1753 inline _LIBCPP_INLINE_VISIBILITY
1754 typename _C::iterator
1755 begin(_C& __c)
1756 {
1757     return __c.begin();
1758 }
1759
1760 template <class _C>
1761 inline _LIBCPP_INLINE_VISIBILITY
1762 typename _C::const_iterator
1763 begin(const _C& __c)
1764 {
1765     return __c.begin();
1766 }
1767
1768 template <class _C>
1769 inline _LIBCPP_INLINE_VISIBILITY
1770 typename _C::iterator
1771 end(_C& __c)
1772 {
1773     return __c.end();
1774 }
1775
1776 template <class _C>
1777 inline _LIBCPP_INLINE_VISIBILITY
1778 typename _C::const_iterator
1779 end(const _C& __c)
1780 {
1781     return __c.end();
1782 }
1783
1784 #endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_TRAILING_RETURN)
1785
1786 template <class _T, size_t _N>
1787 inline _LIBCPP_INLINE_VISIBILITY
1788 _T*
1789 begin(_T (&__array)[_N])
1790 {
1791     return __array;
1792 }
1793
1794 template <class _T, size_t _N>
1795 inline _LIBCPP_INLINE_VISIBILITY
1796 _T*
1797 end(_T (&__array)[_N])
1798 {
1799     return __array + _N;
1800 }
1801
1802 _LIBCPP_END_NAMESPACE_STD
1803
1804 #endif  // _LIBCPP_ITERATOR