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