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