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