iterator revision 262801
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 312template <class C> auto cbegin(const C& c) -> decltype(std::begin(c)); // C++14 313template <class C> auto cend(const C& c) -> decltype(std::end(c)); // C++14 314template <class C> auto rbegin(C& c) -> decltype(c.rbegin()); // C++14 315template <class C> auto rbegin(const C& c) -> decltype(c.rbegin()); // C++14 316template <class C> auto rend(C& c) -> decltype(c.rend()); // C++14 317template <class C> auto rend(const C& c) -> decltype(c.rend()); // C++14 318template <class E> reverse_iterator<const E*> rbegin(initializer_list<E> il); // C++14 319template <class E> reverse_iterator<const E*> rend(initializer_list<E> il); // C++14 320template <class T, size_t N> reverse_iterator<T*> rbegin(T (&array)[N]); // C++14 321template <class T, size_t N> reverse_iterator<T*> rend(T (&array)[N]); // C++14 322template <class C> auto crbegin(const C& c) -> decltype(std::rbegin(c)); // C++14 323template <class C> auto crend(const C& c) -> decltype(std::rend(c)); // C++14 324 325} // std 326 327*/ 328 329#include <__config> 330#include <type_traits> 331#include <cstddef> 332#include <iosfwd> 333#include <initializer_list> 334#ifdef __APPLE__ 335#include <Availability.h> 336#endif 337 338#ifdef _LIBCPP_DEBUG 339# include <__debug> 340#else 341# define _LIBCPP_ASSERT(x, m) ((void)0) 342#endif 343 344#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 345#pragma GCC system_header 346#endif 347 348_LIBCPP_BEGIN_NAMESPACE_STD 349 350struct _LIBCPP_TYPE_VIS_ONLY input_iterator_tag {}; 351struct _LIBCPP_TYPE_VIS_ONLY output_iterator_tag {}; 352struct _LIBCPP_TYPE_VIS_ONLY forward_iterator_tag : public input_iterator_tag {}; 353struct _LIBCPP_TYPE_VIS_ONLY bidirectional_iterator_tag : public forward_iterator_tag {}; 354struct _LIBCPP_TYPE_VIS_ONLY random_access_iterator_tag : public bidirectional_iterator_tag {}; 355 356template <class _Tp> 357struct __has_iterator_category 358{ 359private: 360 struct __two {char __lx; char __lxx;}; 361 template <class _Up> static __two __test(...); 362 template <class _Up> static char __test(typename _Up::iterator_category* = 0); 363public: 364 static const bool value = sizeof(__test<_Tp>(0)) == 1; 365}; 366 367template <class _Iter, bool> struct ____iterator_traits {}; 368 369template <class _Iter> 370struct ____iterator_traits<_Iter, true> 371{ 372 typedef typename _Iter::difference_type difference_type; 373 typedef typename _Iter::value_type value_type; 374 typedef typename _Iter::pointer pointer; 375 typedef typename _Iter::reference reference; 376 typedef typename _Iter::iterator_category iterator_category; 377}; 378 379template <class _Iter, bool> struct __iterator_traits {}; 380 381template <class _Iter> 382struct __iterator_traits<_Iter, true> 383 : ____iterator_traits 384 < 385 _Iter, 386 is_convertible<typename _Iter::iterator_category, input_iterator_tag>::value || 387 is_convertible<typename _Iter::iterator_category, output_iterator_tag>::value 388 > 389{}; 390 391// iterator_traits<Iterator> will only have the nested types if Iterator::iterator_category 392// exists. Else iterator_traits<Iterator> will be an empty class. This is a 393// conforming extension which allows some programs to compile and behave as 394// the client expects instead of failing at compile time. 395 396template <class _Iter> 397struct _LIBCPP_TYPE_VIS_ONLY iterator_traits 398 : __iterator_traits<_Iter, __has_iterator_category<_Iter>::value> {}; 399 400template<class _Tp> 401struct _LIBCPP_TYPE_VIS_ONLY iterator_traits<_Tp*> 402{ 403 typedef ptrdiff_t difference_type; 404 typedef typename remove_const<_Tp>::type value_type; 405 typedef _Tp* pointer; 406 typedef _Tp& reference; 407 typedef random_access_iterator_tag iterator_category; 408}; 409 410template <class _Tp, class _Up, bool = __has_iterator_category<iterator_traits<_Tp> >::value> 411struct __has_iterator_category_convertible_to 412 : public integral_constant<bool, is_convertible<typename iterator_traits<_Tp>::iterator_category, _Up>::value> 413{}; 414 415template <class _Tp, class _Up> 416struct __has_iterator_category_convertible_to<_Tp, _Up, false> : public false_type {}; 417 418template <class _Tp> 419struct __is_input_iterator : public __has_iterator_category_convertible_to<_Tp, input_iterator_tag> {}; 420 421template <class _Tp> 422struct __is_forward_iterator : public __has_iterator_category_convertible_to<_Tp, forward_iterator_tag> {}; 423 424template <class _Tp> 425struct __is_bidirectional_iterator : public __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag> {}; 426 427template <class _Tp> 428struct __is_random_access_iterator : public __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag> {}; 429 430template<class _Category, class _Tp, class _Distance = ptrdiff_t, 431 class _Pointer = _Tp*, class _Reference = _Tp&> 432struct _LIBCPP_TYPE_VIS_ONLY iterator 433{ 434 typedef _Tp value_type; 435 typedef _Distance difference_type; 436 typedef _Pointer pointer; 437 typedef _Reference reference; 438 typedef _Category iterator_category; 439}; 440 441template <class _InputIter> 442inline _LIBCPP_INLINE_VISIBILITY 443void __advance(_InputIter& __i, 444 typename iterator_traits<_InputIter>::difference_type __n, input_iterator_tag) 445{ 446 for (; __n > 0; --__n) 447 ++__i; 448} 449 450template <class _BiDirIter> 451inline _LIBCPP_INLINE_VISIBILITY 452void __advance(_BiDirIter& __i, 453 typename iterator_traits<_BiDirIter>::difference_type __n, bidirectional_iterator_tag) 454{ 455 if (__n >= 0) 456 for (; __n > 0; --__n) 457 ++__i; 458 else 459 for (; __n < 0; ++__n) 460 --__i; 461} 462 463template <class _RandIter> 464inline _LIBCPP_INLINE_VISIBILITY 465void __advance(_RandIter& __i, 466 typename iterator_traits<_RandIter>::difference_type __n, random_access_iterator_tag) 467{ 468 __i += __n; 469} 470 471template <class _InputIter> 472inline _LIBCPP_INLINE_VISIBILITY 473void advance(_InputIter& __i, 474 typename iterator_traits<_InputIter>::difference_type __n) 475{ 476 __advance(__i, __n, typename iterator_traits<_InputIter>::iterator_category()); 477} 478 479template <class _InputIter> 480inline _LIBCPP_INLINE_VISIBILITY 481typename iterator_traits<_InputIter>::difference_type 482__distance(_InputIter __first, _InputIter __last, input_iterator_tag) 483{ 484 typename iterator_traits<_InputIter>::difference_type __r(0); 485 for (; __first != __last; ++__first) 486 ++__r; 487 return __r; 488} 489 490template <class _RandIter> 491inline _LIBCPP_INLINE_VISIBILITY 492typename iterator_traits<_RandIter>::difference_type 493__distance(_RandIter __first, _RandIter __last, random_access_iterator_tag) 494{ 495 return __last - __first; 496} 497 498template <class _InputIter> 499inline _LIBCPP_INLINE_VISIBILITY 500typename iterator_traits<_InputIter>::difference_type 501distance(_InputIter __first, _InputIter __last) 502{ 503 return __distance(__first, __last, typename iterator_traits<_InputIter>::iterator_category()); 504} 505 506template <class _ForwardIter> 507inline _LIBCPP_INLINE_VISIBILITY 508_ForwardIter 509next(_ForwardIter __x, 510 typename iterator_traits<_ForwardIter>::difference_type __n = 1, 511 typename enable_if<__is_forward_iterator<_ForwardIter>::value>::type* = 0) 512{ 513 _VSTD::advance(__x, __n); 514 return __x; 515} 516 517template <class _BidiretionalIter> 518inline _LIBCPP_INLINE_VISIBILITY 519_BidiretionalIter 520prev(_BidiretionalIter __x, 521 typename iterator_traits<_BidiretionalIter>::difference_type __n = 1, 522 typename enable_if<__is_bidirectional_iterator<_BidiretionalIter>::value>::type* = 0) 523{ 524 _VSTD::advance(__x, -__n); 525 return __x; 526} 527 528template <class _Iter> 529class _LIBCPP_TYPE_VIS_ONLY reverse_iterator 530 : public iterator<typename iterator_traits<_Iter>::iterator_category, 531 typename iterator_traits<_Iter>::value_type, 532 typename iterator_traits<_Iter>::difference_type, 533 typename iterator_traits<_Iter>::pointer, 534 typename iterator_traits<_Iter>::reference> 535{ 536private: 537 mutable _Iter __t; 538protected: 539 _Iter current; 540public: 541 typedef _Iter iterator_type; 542 typedef typename iterator_traits<_Iter>::difference_type difference_type; 543 typedef typename iterator_traits<_Iter>::reference reference; 544 typedef typename iterator_traits<_Iter>::pointer pointer; 545 546 _LIBCPP_INLINE_VISIBILITY reverse_iterator() : current() {} 547 _LIBCPP_INLINE_VISIBILITY explicit reverse_iterator(_Iter __x) : __t(__x), current(__x) {} 548 template <class _Up> _LIBCPP_INLINE_VISIBILITY reverse_iterator(const reverse_iterator<_Up>& __u) 549 : __t(__u.base()), current(__u.base()) {} 550 _LIBCPP_INLINE_VISIBILITY _Iter base() const {return current;} 551 _LIBCPP_INLINE_VISIBILITY reference operator*() const {__t = current; return *--__t;} 552 _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return &(operator*());} 553 _LIBCPP_INLINE_VISIBILITY reverse_iterator& operator++() {--current; return *this;} 554 _LIBCPP_INLINE_VISIBILITY reverse_iterator operator++(int) 555 {reverse_iterator __tmp(*this); --current; return __tmp;} 556 _LIBCPP_INLINE_VISIBILITY reverse_iterator& operator--() {++current; return *this;} 557 _LIBCPP_INLINE_VISIBILITY reverse_iterator operator--(int) 558 {reverse_iterator __tmp(*this); ++current; return __tmp;} 559 _LIBCPP_INLINE_VISIBILITY reverse_iterator operator+ (difference_type __n) const 560 {return reverse_iterator(current - __n);} 561 _LIBCPP_INLINE_VISIBILITY reverse_iterator& operator+=(difference_type __n) 562 {current -= __n; return *this;} 563 _LIBCPP_INLINE_VISIBILITY reverse_iterator operator- (difference_type __n) const 564 {return reverse_iterator(current + __n);} 565 _LIBCPP_INLINE_VISIBILITY reverse_iterator& operator-=(difference_type __n) 566 {current += __n; return *this;} 567 _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const 568 {return current[-__n-1];} 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 605bool 606operator>=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) 607{ 608 return __x.base() <= __y.base(); 609} 610 611template <class _Iter1, class _Iter2> 612inline _LIBCPP_INLINE_VISIBILITY 613bool 614operator<=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) 615{ 616 return __x.base() >= __y.base(); 617} 618 619template <class _Iter1, class _Iter2> 620inline _LIBCPP_INLINE_VISIBILITY 621typename reverse_iterator<_Iter1>::difference_type 622operator-(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y) 623{ 624 return __y.base() - __x.base(); 625} 626 627template <class _Iter> 628inline _LIBCPP_INLINE_VISIBILITY 629reverse_iterator<_Iter> 630operator+(typename reverse_iterator<_Iter>::difference_type __n, const reverse_iterator<_Iter>& __x) 631{ 632 return reverse_iterator<_Iter>(__x.base() - __n); 633} 634 635template <class _Container> 636class _LIBCPP_TYPE_VIS_ONLY back_insert_iterator 637 : public iterator<output_iterator_tag, 638 void, 639 void, 640 void, 641 back_insert_iterator<_Container>&> 642{ 643protected: 644 _Container* container; 645public: 646 typedef _Container container_type; 647 648 _LIBCPP_INLINE_VISIBILITY explicit back_insert_iterator(_Container& __x) : container(&__x) {} 649 _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator=(const typename _Container::value_type& __value_) 650 {container->push_back(__value_); return *this;} 651#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 652 _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator=(typename _Container::value_type&& __value_) 653 {container->push_back(_VSTD::move(__value_)); return *this;} 654#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 655 _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator*() {return *this;} 656 _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator++() {return *this;} 657 _LIBCPP_INLINE_VISIBILITY back_insert_iterator operator++(int) {return *this;} 658}; 659 660template <class _Container> 661inline _LIBCPP_INLINE_VISIBILITY 662back_insert_iterator<_Container> 663back_inserter(_Container& __x) 664{ 665 return back_insert_iterator<_Container>(__x); 666} 667 668template <class _Container> 669class _LIBCPP_TYPE_VIS_ONLY front_insert_iterator 670 : public iterator<output_iterator_tag, 671 void, 672 void, 673 void, 674 front_insert_iterator<_Container>&> 675{ 676protected: 677 _Container* container; 678public: 679 typedef _Container container_type; 680 681 _LIBCPP_INLINE_VISIBILITY explicit front_insert_iterator(_Container& __x) : container(&__x) {} 682 _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator=(const typename _Container::value_type& __value_) 683 {container->push_front(__value_); return *this;} 684#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 685 _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator=(typename _Container::value_type&& __value_) 686 {container->push_front(_VSTD::move(__value_)); return *this;} 687#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 688 _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator*() {return *this;} 689 _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator++() {return *this;} 690 _LIBCPP_INLINE_VISIBILITY front_insert_iterator operator++(int) {return *this;} 691}; 692 693template <class _Container> 694inline _LIBCPP_INLINE_VISIBILITY 695front_insert_iterator<_Container> 696front_inserter(_Container& __x) 697{ 698 return front_insert_iterator<_Container>(__x); 699} 700 701template <class _Container> 702class _LIBCPP_TYPE_VIS_ONLY insert_iterator 703 : public iterator<output_iterator_tag, 704 void, 705 void, 706 void, 707 insert_iterator<_Container>&> 708{ 709protected: 710 _Container* container; 711 typename _Container::iterator iter; 712public: 713 typedef _Container container_type; 714 715 _LIBCPP_INLINE_VISIBILITY insert_iterator(_Container& __x, typename _Container::iterator __i) 716 : container(&__x), iter(__i) {} 717 _LIBCPP_INLINE_VISIBILITY insert_iterator& operator=(const typename _Container::value_type& __value_) 718 {iter = container->insert(iter, __value_); ++iter; return *this;} 719#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 720 _LIBCPP_INLINE_VISIBILITY insert_iterator& operator=(typename _Container::value_type&& __value_) 721 {iter = container->insert(iter, _VSTD::move(__value_)); ++iter; return *this;} 722#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 723 _LIBCPP_INLINE_VISIBILITY insert_iterator& operator*() {return *this;} 724 _LIBCPP_INLINE_VISIBILITY insert_iterator& operator++() {return *this;} 725 _LIBCPP_INLINE_VISIBILITY insert_iterator& operator++(int) {return *this;} 726}; 727 728template <class _Container> 729inline _LIBCPP_INLINE_VISIBILITY 730insert_iterator<_Container> 731inserter(_Container& __x, typename _Container::iterator __i) 732{ 733 return insert_iterator<_Container>(__x, __i); 734} 735 736template <class _Tp, class _CharT = char, 737 class _Traits = char_traits<_CharT>, class _Distance = ptrdiff_t> 738class _LIBCPP_TYPE_VIS_ONLY istream_iterator 739 : public iterator<input_iterator_tag, _Tp, _Distance, const _Tp*, const _Tp&> 740{ 741public: 742 typedef _CharT char_type; 743 typedef _Traits traits_type; 744 typedef basic_istream<_CharT,_Traits> istream_type; 745private: 746 istream_type* __in_stream_; 747 _Tp __value_; 748public: 749 _LIBCPP_INLINE_VISIBILITY istream_iterator() : __in_stream_(0) {} 750 _LIBCPP_INLINE_VISIBILITY istream_iterator(istream_type& __s) : __in_stream_(&__s) 751 { 752 if (!(*__in_stream_ >> __value_)) 753 __in_stream_ = 0; 754 } 755 756 _LIBCPP_INLINE_VISIBILITY const _Tp& operator*() const {return __value_;} 757 _LIBCPP_INLINE_VISIBILITY const _Tp* operator->() const {return &(operator*());} 758 _LIBCPP_INLINE_VISIBILITY istream_iterator& operator++() 759 { 760 if (!(*__in_stream_ >> __value_)) 761 __in_stream_ = 0; 762 return *this; 763 } 764 _LIBCPP_INLINE_VISIBILITY istream_iterator operator++(int) 765 {istream_iterator __t(*this); ++(*this); return __t;} 766 767 friend _LIBCPP_INLINE_VISIBILITY 768 bool operator==(const istream_iterator& __x, const istream_iterator& __y) 769 {return __x.__in_stream_ == __y.__in_stream_;} 770 771 friend _LIBCPP_INLINE_VISIBILITY 772 bool operator!=(const istream_iterator& __x, const istream_iterator& __y) 773 {return !(__x == __y);} 774}; 775 776template <class _Tp, class _CharT = char, class _Traits = char_traits<_CharT> > 777class _LIBCPP_TYPE_VIS_ONLY ostream_iterator 778 : public iterator<output_iterator_tag, void, void, void, void> 779{ 780public: 781 typedef _CharT char_type; 782 typedef _Traits traits_type; 783 typedef basic_ostream<_CharT,_Traits> ostream_type; 784private: 785 ostream_type* __out_stream_; 786 const char_type* __delim_; 787public: 788 _LIBCPP_INLINE_VISIBILITY ostream_iterator(ostream_type& __s) 789 : __out_stream_(&__s), __delim_(0) {} 790 _LIBCPP_INLINE_VISIBILITY ostream_iterator(ostream_type& __s, const _CharT* __delimiter) 791 : __out_stream_(&__s), __delim_(__delimiter) {} 792 _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator=(const _Tp& __value_) 793 { 794 *__out_stream_ << __value_; 795 if (__delim_) 796 *__out_stream_ << __delim_; 797 return *this; 798 } 799 800 _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator*() {return *this;} 801 _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator++() {return *this;} 802 _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator++(int) {return *this;} 803}; 804 805template<class _CharT, class _Traits> 806class _LIBCPP_TYPE_VIS_ONLY istreambuf_iterator 807 : public iterator<input_iterator_tag, _CharT, 808 typename _Traits::off_type, _CharT*, 809 _CharT> 810{ 811public: 812 typedef _CharT char_type; 813 typedef _Traits traits_type; 814 typedef typename _Traits::int_type int_type; 815 typedef basic_streambuf<_CharT,_Traits> streambuf_type; 816 typedef basic_istream<_CharT,_Traits> istream_type; 817private: 818 mutable streambuf_type* __sbuf_; 819 820 class __proxy 821 { 822 char_type __keep_; 823 streambuf_type* __sbuf_; 824 _LIBCPP_INLINE_VISIBILITY __proxy(char_type __c, streambuf_type* __s) 825 : __keep_(__c), __sbuf_(__s) {} 826 friend class istreambuf_iterator; 827 public: 828 _LIBCPP_INLINE_VISIBILITY char_type operator*() const {return __keep_;} 829 }; 830 831 _LIBCPP_INLINE_VISIBILITY 832 bool __test_for_eof() const 833 { 834 if (__sbuf_ && traits_type::eq_int_type(__sbuf_->sgetc(), traits_type::eof())) 835 __sbuf_ = 0; 836 return __sbuf_ == 0; 837 } 838public: 839 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR istreambuf_iterator() _NOEXCEPT : __sbuf_(0) {} 840 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(istream_type& __s) _NOEXCEPT 841 : __sbuf_(__s.rdbuf()) {} 842 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(streambuf_type* __s) _NOEXCEPT 843 : __sbuf_(__s) {} 844 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(const __proxy& __p) _NOEXCEPT 845 : __sbuf_(__p.__sbuf_) {} 846 847 _LIBCPP_INLINE_VISIBILITY char_type operator*() const 848 {return static_cast<char_type>(__sbuf_->sgetc());} 849 _LIBCPP_INLINE_VISIBILITY char_type* operator->() const {return nullptr;} 850 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator& operator++() 851 { 852 __sbuf_->sbumpc(); 853 return *this; 854 } 855 _LIBCPP_INLINE_VISIBILITY __proxy operator++(int) 856 { 857 return __proxy(__sbuf_->sbumpc(), __sbuf_); 858 } 859 860 _LIBCPP_INLINE_VISIBILITY bool equal(const istreambuf_iterator& __b) const 861 {return __test_for_eof() == __b.__test_for_eof();} 862}; 863 864template <class _CharT, class _Traits> 865inline _LIBCPP_INLINE_VISIBILITY 866bool operator==(const istreambuf_iterator<_CharT,_Traits>& __a, 867 const istreambuf_iterator<_CharT,_Traits>& __b) 868 {return __a.equal(__b);} 869 870template <class _CharT, class _Traits> 871inline _LIBCPP_INLINE_VISIBILITY 872bool operator!=(const istreambuf_iterator<_CharT,_Traits>& __a, 873 const istreambuf_iterator<_CharT,_Traits>& __b) 874 {return !__a.equal(__b);} 875 876template <class _CharT, class _Traits> 877class _LIBCPP_TYPE_VIS_ONLY ostreambuf_iterator 878 : public iterator<output_iterator_tag, void, void, void, void> 879{ 880public: 881 typedef _CharT char_type; 882 typedef _Traits traits_type; 883 typedef basic_streambuf<_CharT,_Traits> streambuf_type; 884 typedef basic_ostream<_CharT,_Traits> ostream_type; 885private: 886 streambuf_type* __sbuf_; 887public: 888 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator(ostream_type& __s) _NOEXCEPT 889 : __sbuf_(__s.rdbuf()) {} 890 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator(streambuf_type* __s) _NOEXCEPT 891 : __sbuf_(__s) {} 892 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator=(_CharT __c) 893 { 894 if (__sbuf_ && traits_type::eq_int_type(__sbuf_->sputc(__c), traits_type::eof())) 895 __sbuf_ = 0; 896 return *this; 897 } 898 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator*() {return *this;} 899 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator++() {return *this;} 900 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator++(int) {return *this;} 901 _LIBCPP_INLINE_VISIBILITY bool failed() const _NOEXCEPT {return __sbuf_ == 0;} 902 903#if !defined(__APPLE__) || \ 904 (defined(__MAC_OS_X_VERSION_MIN_REQUIRED) && __MAC_OS_X_VERSION_MIN_REQUIRED > __MAC_10_8) || \ 905 (defined(__IPHONE_OS_VERSION_MIN_REQUIRED) && __IPHONE_OS_VERSION_MIN_REQUIRED > __IPHONE_6_0) 906 907 template <class _Ch, class _Tr> 908 friend 909 _LIBCPP_HIDDEN 910 ostreambuf_iterator<_Ch, _Tr> 911 __pad_and_output(ostreambuf_iterator<_Ch, _Tr> __s, 912 const _Ch* __ob, const _Ch* __op, const _Ch* __oe, 913 ios_base& __iob, _Ch __fl); 914#endif 915}; 916 917template <class _Iter> 918class _LIBCPP_TYPE_VIS_ONLY move_iterator 919{ 920private: 921 _Iter __i; 922public: 923 typedef _Iter iterator_type; 924 typedef typename iterator_traits<iterator_type>::iterator_category iterator_category; 925 typedef typename iterator_traits<iterator_type>::value_type value_type; 926 typedef typename iterator_traits<iterator_type>::difference_type difference_type; 927 typedef typename iterator_traits<iterator_type>::pointer pointer; 928#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 929 typedef value_type&& reference; 930#else 931 typedef typename iterator_traits<iterator_type>::reference reference; 932#endif 933 934 _LIBCPP_INLINE_VISIBILITY move_iterator() : __i() {} 935 _LIBCPP_INLINE_VISIBILITY explicit move_iterator(_Iter __x) : __i(__x) {} 936 template <class _Up> _LIBCPP_INLINE_VISIBILITY move_iterator(const move_iterator<_Up>& __u) 937 : __i(__u.base()) {} 938 _LIBCPP_INLINE_VISIBILITY _Iter base() const {return __i;} 939 _LIBCPP_INLINE_VISIBILITY reference operator*() const { 940 return static_cast<reference>(*__i); 941 } 942 _LIBCPP_INLINE_VISIBILITY pointer operator->() const { 943 typename iterator_traits<iterator_type>::reference __ref = *__i; 944 return &__ref; 945 } 946 _LIBCPP_INLINE_VISIBILITY move_iterator& operator++() {++__i; return *this;} 947 _LIBCPP_INLINE_VISIBILITY move_iterator operator++(int) 948 {move_iterator __tmp(*this); ++__i; return __tmp;} 949 _LIBCPP_INLINE_VISIBILITY move_iterator& operator--() {--__i; return *this;} 950 _LIBCPP_INLINE_VISIBILITY move_iterator operator--(int) 951 {move_iterator __tmp(*this); --__i; return __tmp;} 952 _LIBCPP_INLINE_VISIBILITY move_iterator operator+ (difference_type __n) const 953 {return move_iterator(__i + __n);} 954 _LIBCPP_INLINE_VISIBILITY move_iterator& operator+=(difference_type __n) 955 {__i += __n; return *this;} 956 _LIBCPP_INLINE_VISIBILITY move_iterator operator- (difference_type __n) const 957 {return move_iterator(__i - __n);} 958 _LIBCPP_INLINE_VISIBILITY move_iterator& operator-=(difference_type __n) 959 {__i -= __n; return *this;} 960 _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const 961 { 962 return static_cast<reference>(__i[__n]); 963 } 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 1000bool 1001operator>=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y) 1002{ 1003 return __x.base() >= __y.base(); 1004} 1005 1006template <class _Iter1, class _Iter2> 1007inline _LIBCPP_INLINE_VISIBILITY 1008bool 1009operator<=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y) 1010{ 1011 return __x.base() <= __y.base(); 1012} 1013 1014template <class _Iter1, class _Iter2> 1015inline _LIBCPP_INLINE_VISIBILITY 1016typename move_iterator<_Iter1>::difference_type 1017operator-(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y) 1018{ 1019 return __x.base() - __y.base(); 1020} 1021 1022template <class _Iter> 1023inline _LIBCPP_INLINE_VISIBILITY 1024move_iterator<_Iter> 1025operator+(typename move_iterator<_Iter>::difference_type __n, const move_iterator<_Iter>& __x) 1026{ 1027 return move_iterator<_Iter>(__x.base() + __n); 1028} 1029 1030template <class _Iter> 1031inline _LIBCPP_INLINE_VISIBILITY 1032move_iterator<_Iter> 1033make_move_iterator(_Iter __i) 1034{ 1035 return move_iterator<_Iter>(__i); 1036} 1037 1038// __wrap_iter 1039 1040template <class _Iter> class __wrap_iter; 1041 1042template <class _Iter1, class _Iter2> 1043_LIBCPP_INLINE_VISIBILITY 1044bool 1045operator==(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1046 1047template <class _Iter1, class _Iter2> 1048_LIBCPP_INLINE_VISIBILITY 1049bool 1050operator<(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1051 1052template <class _Iter1, class _Iter2> 1053_LIBCPP_INLINE_VISIBILITY 1054bool 1055operator!=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1056 1057template <class _Iter1, class _Iter2> 1058_LIBCPP_INLINE_VISIBILITY 1059bool 1060operator>(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1061 1062template <class _Iter1, class _Iter2> 1063_LIBCPP_INLINE_VISIBILITY 1064bool 1065operator>=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1066 1067template <class _Iter1, class _Iter2> 1068_LIBCPP_INLINE_VISIBILITY 1069bool 1070operator<=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1071 1072template <class _Iter1, class _Iter2> 1073_LIBCPP_INLINE_VISIBILITY 1074typename __wrap_iter<_Iter1>::difference_type 1075operator-(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1076 1077template <class _Iter> 1078_LIBCPP_INLINE_VISIBILITY 1079__wrap_iter<_Iter> 1080operator+(typename __wrap_iter<_Iter>::difference_type, __wrap_iter<_Iter>) _NOEXCEPT; 1081 1082template <class _Ip, class _Op> _Op _LIBCPP_INLINE_VISIBILITY copy(_Ip, _Ip, _Op); 1083template <class _B1, class _B2> _B2 _LIBCPP_INLINE_VISIBILITY copy_backward(_B1, _B1, _B2); 1084template <class _Ip, class _Op> _Op _LIBCPP_INLINE_VISIBILITY move(_Ip, _Ip, _Op); 1085template <class _B1, class _B2> _B2 _LIBCPP_INLINE_VISIBILITY move_backward(_B1, _B1, _B2); 1086 1087template <class _Tp> 1088_LIBCPP_INLINE_VISIBILITY 1089typename enable_if 1090< 1091 is_trivially_copy_assignable<_Tp>::value, 1092 _Tp* 1093>::type 1094__unwrap_iter(__wrap_iter<_Tp*>); 1095 1096template <class _Iter> 1097class __wrap_iter 1098{ 1099public: 1100 typedef _Iter iterator_type; 1101 typedef typename iterator_traits<iterator_type>::iterator_category iterator_category; 1102 typedef typename iterator_traits<iterator_type>::value_type value_type; 1103 typedef typename iterator_traits<iterator_type>::difference_type difference_type; 1104 typedef typename iterator_traits<iterator_type>::pointer pointer; 1105 typedef typename iterator_traits<iterator_type>::reference reference; 1106private: 1107 iterator_type __i; 1108public: 1109 _LIBCPP_INLINE_VISIBILITY __wrap_iter() _NOEXCEPT 1110#if _LIBCPP_STD_VER > 11 1111 : __i{} 1112#endif 1113 { 1114#if _LIBCPP_DEBUG_LEVEL >= 2 1115 __get_db()->__insert_i(this); 1116#endif 1117 } 1118 template <class _Up> _LIBCPP_INLINE_VISIBILITY __wrap_iter(const __wrap_iter<_Up>& __u, 1119 typename enable_if<is_convertible<_Up, iterator_type>::value>::type* = 0) _NOEXCEPT 1120 : __i(__u.base()) 1121 { 1122#if _LIBCPP_DEBUG_LEVEL >= 2 1123 __get_db()->__iterator_copy(this, &__u); 1124#endif 1125 } 1126#if _LIBCPP_DEBUG_LEVEL >= 2 1127 _LIBCPP_INLINE_VISIBILITY 1128 __wrap_iter(const __wrap_iter& __x) 1129 : __i(__x.base()) 1130 { 1131 __get_db()->__iterator_copy(this, &__x); 1132 } 1133 _LIBCPP_INLINE_VISIBILITY 1134 __wrap_iter& operator=(const __wrap_iter& __x) 1135 { 1136 if (this != &__x) 1137 { 1138 __get_db()->__iterator_copy(this, &__x); 1139 __i = __x.__i; 1140 } 1141 return *this; 1142 } 1143 _LIBCPP_INLINE_VISIBILITY 1144 ~__wrap_iter() 1145 { 1146 __get_db()->__erase_i(this); 1147 } 1148#endif 1149 _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT 1150 { 1151#if _LIBCPP_DEBUG_LEVEL >= 2 1152 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 1153 "Attempted to dereference a non-dereferenceable iterator"); 1154#endif 1155 return *__i; 1156 } 1157 _LIBCPP_INLINE_VISIBILITY pointer operator->() const _NOEXCEPT 1158 { 1159#if _LIBCPP_DEBUG_LEVEL >= 2 1160 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 1161 "Attempted to dereference a non-dereferenceable iterator"); 1162#endif 1163 return (pointer)&reinterpret_cast<const volatile char&>(*__i); 1164 } 1165 _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator++() _NOEXCEPT 1166 { 1167#if _LIBCPP_DEBUG_LEVEL >= 2 1168 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this), 1169 "Attempted to increment non-incrementable iterator"); 1170#endif 1171 ++__i; 1172 return *this; 1173 } 1174 _LIBCPP_INLINE_VISIBILITY __wrap_iter operator++(int) _NOEXCEPT 1175 {__wrap_iter __tmp(*this); ++(*this); return __tmp;} 1176 _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator--() _NOEXCEPT 1177 { 1178#if _LIBCPP_DEBUG_LEVEL >= 2 1179 _LIBCPP_ASSERT(__get_const_db()->__decrementable(this), 1180 "Attempted to decrement non-decrementable iterator"); 1181#endif 1182 --__i; 1183 return *this; 1184 } 1185 _LIBCPP_INLINE_VISIBILITY __wrap_iter operator--(int) _NOEXCEPT 1186 {__wrap_iter __tmp(*this); --(*this); return __tmp;} 1187 _LIBCPP_INLINE_VISIBILITY __wrap_iter operator+ (difference_type __n) const _NOEXCEPT 1188 {__wrap_iter __w(*this); __w += __n; return __w;} 1189 _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator+=(difference_type __n) _NOEXCEPT 1190 { 1191#if _LIBCPP_DEBUG_LEVEL >= 2 1192 _LIBCPP_ASSERT(__get_const_db()->__addable(this, __n), 1193 "Attempted to add/subtract iterator outside of valid range"); 1194#endif 1195 __i += __n; 1196 return *this; 1197 } 1198 _LIBCPP_INLINE_VISIBILITY __wrap_iter operator- (difference_type __n) const _NOEXCEPT 1199 {return *this + (-__n);} 1200 _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator-=(difference_type __n) _NOEXCEPT 1201 {*this += -__n; return *this;} 1202 _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const _NOEXCEPT 1203 { 1204#if _LIBCPP_DEBUG_LEVEL >= 2 1205 _LIBCPP_ASSERT(__get_const_db()->__subscriptable(this, __n), 1206 "Attempted to subscript iterator outside of valid range"); 1207#endif 1208 return __i[__n]; 1209 } 1210 1211 _LIBCPP_INLINE_VISIBILITY iterator_type base() const _NOEXCEPT {return __i;} 1212 1213private: 1214#if _LIBCPP_DEBUG_LEVEL >= 2 1215 _LIBCPP_INLINE_VISIBILITY __wrap_iter(const void* __p, iterator_type __x) : __i(__x) 1216 { 1217 __get_db()->__insert_ic(this, __p); 1218 } 1219#else 1220 _LIBCPP_INLINE_VISIBILITY __wrap_iter(iterator_type __x) _NOEXCEPT : __i(__x) {} 1221#endif 1222 1223 template <class _Up> friend class __wrap_iter; 1224 template <class _CharT, class _Traits, class _Alloc> friend class basic_string; 1225 template <class _Tp, class _Alloc> friend class vector; 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 bool 1245 operator>(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1246 1247 template <class _Iter1, class _Iter2> 1248 friend 1249 bool 1250 operator>=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1251 1252 template <class _Iter1, class _Iter2> 1253 friend 1254 bool 1255 operator<=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1256 1257 template <class _Iter1, class _Iter2> 1258 friend 1259 typename __wrap_iter<_Iter1>::difference_type 1260 operator-(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT; 1261 1262 template <class _Iter1> 1263 friend 1264 __wrap_iter<_Iter1> 1265 operator+(typename __wrap_iter<_Iter1>::difference_type, __wrap_iter<_Iter1>) _NOEXCEPT; 1266 1267 template <class _Ip, class _Op> friend _Op copy(_Ip, _Ip, _Op); 1268 template <class _B1, class _B2> friend _B2 copy_backward(_B1, _B1, _B2); 1269 template <class _Ip, class _Op> friend _Op move(_Ip, _Ip, _Op); 1270 template <class _B1, class _B2> friend _B2 move_backward(_B1, _B1, _B2); 1271 1272 template <class _Tp> 1273 friend 1274 typename enable_if 1275 < 1276 is_trivially_copy_assignable<_Tp>::value, 1277 _Tp* 1278 >::type 1279 __unwrap_iter(__wrap_iter<_Tp*>); 1280}; 1281 1282template <class _Iter1, class _Iter2> 1283inline _LIBCPP_INLINE_VISIBILITY 1284bool 1285operator==(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT 1286{ 1287 return __x.base() == __y.base(); 1288} 1289 1290template <class _Iter1, class _Iter2> 1291inline _LIBCPP_INLINE_VISIBILITY 1292bool 1293operator<(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT 1294{ 1295#if _LIBCPP_DEBUG_LEVEL >= 2 1296 _LIBCPP_ASSERT(__get_const_db()->__less_than_comparable(&__x, &__y), 1297 "Attempted to compare incomparable iterators"); 1298#endif 1299 return __x.base() < __y.base(); 1300} 1301 1302template <class _Iter1, class _Iter2> 1303inline _LIBCPP_INLINE_VISIBILITY 1304bool 1305operator!=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT 1306{ 1307 return !(__x == __y); 1308} 1309 1310template <class _Iter1, class _Iter2> 1311inline _LIBCPP_INLINE_VISIBILITY 1312bool 1313operator>(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT 1314{ 1315 return __y < __x; 1316} 1317 1318template <class _Iter1, class _Iter2> 1319inline _LIBCPP_INLINE_VISIBILITY 1320bool 1321operator>=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT 1322{ 1323 return !(__x < __y); 1324} 1325 1326template <class _Iter1, class _Iter2> 1327inline _LIBCPP_INLINE_VISIBILITY 1328bool 1329operator<=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT 1330{ 1331 return !(__y < __x); 1332} 1333 1334template <class _Iter1> 1335inline _LIBCPP_INLINE_VISIBILITY 1336bool 1337operator!=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT 1338{ 1339 return !(__x == __y); 1340} 1341 1342template <class _Iter1> 1343inline _LIBCPP_INLINE_VISIBILITY 1344bool 1345operator>(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT 1346{ 1347 return __y < __x; 1348} 1349 1350template <class _Iter1> 1351inline _LIBCPP_INLINE_VISIBILITY 1352bool 1353operator>=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT 1354{ 1355 return !(__x < __y); 1356} 1357 1358template <class _Iter1> 1359inline _LIBCPP_INLINE_VISIBILITY 1360bool 1361operator<=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT 1362{ 1363 return !(__y < __x); 1364} 1365 1366template <class _Iter1, class _Iter2> 1367inline _LIBCPP_INLINE_VISIBILITY 1368typename __wrap_iter<_Iter1>::difference_type 1369operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT 1370{ 1371#if _LIBCPP_DEBUG_LEVEL >= 2 1372 _LIBCPP_ASSERT(__get_const_db()->__less_than_comparable(&__x, &__y), 1373 "Attempted to subtract incompatible iterators"); 1374#endif 1375 return __x.base() - __y.base(); 1376} 1377 1378template <class _Iter> 1379inline _LIBCPP_INLINE_VISIBILITY 1380__wrap_iter<_Iter> 1381operator+(typename __wrap_iter<_Iter>::difference_type __n, 1382 __wrap_iter<_Iter> __x) _NOEXCEPT 1383{ 1384 __x += __n; 1385 return __x; 1386} 1387 1388template <class _Tp, size_t _Np> 1389inline _LIBCPP_INLINE_VISIBILITY 1390_Tp* 1391begin(_Tp (&__array)[_Np]) 1392{ 1393 return __array; 1394} 1395 1396template <class _Tp, size_t _Np> 1397inline _LIBCPP_INLINE_VISIBILITY 1398_Tp* 1399end(_Tp (&__array)[_Np]) 1400{ 1401 return __array + _Np; 1402} 1403 1404#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_TRAILING_RETURN) 1405 1406template <class _Cp> 1407inline _LIBCPP_INLINE_VISIBILITY 1408auto 1409begin(_Cp& __c) -> decltype(__c.begin()) 1410{ 1411 return __c.begin(); 1412} 1413 1414template <class _Cp> 1415inline _LIBCPP_INLINE_VISIBILITY 1416auto 1417begin(const _Cp& __c) -> decltype(__c.begin()) 1418{ 1419 return __c.begin(); 1420} 1421 1422template <class _Cp> 1423inline _LIBCPP_INLINE_VISIBILITY 1424auto 1425end(_Cp& __c) -> decltype(__c.end()) 1426{ 1427 return __c.end(); 1428} 1429 1430template <class _Cp> 1431inline _LIBCPP_INLINE_VISIBILITY 1432auto 1433end(const _Cp& __c) -> decltype(__c.end()) 1434{ 1435 return __c.end(); 1436} 1437 1438#if _LIBCPP_STD_VER > 11 1439 1440template <class _Tp, size_t _Np> 1441inline _LIBCPP_INLINE_VISIBILITY 1442reverse_iterator<_Tp*> rbegin(_Tp (&__array)[_Np]) 1443{ 1444 return reverse_iterator<_Tp*>(__array + _Np); 1445} 1446 1447template <class _Tp, size_t _Np> 1448inline _LIBCPP_INLINE_VISIBILITY 1449reverse_iterator<_Tp*> rend(_Tp (&__array)[_Np]) 1450{ 1451 return reverse_iterator<_Tp*>(__array); 1452} 1453 1454template <class _Ep> 1455inline _LIBCPP_INLINE_VISIBILITY 1456reverse_iterator<const _Ep*> rbegin(initializer_list<_Ep> __il) 1457{ 1458 return reverse_iterator<const _Ep*>(__il.end()); 1459} 1460 1461template <class _Ep> 1462inline _LIBCPP_INLINE_VISIBILITY 1463reverse_iterator<const _Ep*> rend(initializer_list<_Ep> __il) 1464{ 1465 return reverse_iterator<const _Ep*>(__il.begin()); 1466} 1467 1468template <class _Cp> 1469inline _LIBCPP_INLINE_VISIBILITY 1470auto cbegin(const _Cp& __c) -> decltype(begin(__c)) 1471{ 1472 return _VSTD::begin(__c); 1473} 1474 1475template <class _Cp> 1476inline _LIBCPP_INLINE_VISIBILITY 1477auto cend(const _Cp& __c) -> decltype(end(__c)) 1478{ 1479 return _VSTD::end(__c); 1480} 1481 1482template <class _Cp> 1483inline _LIBCPP_INLINE_VISIBILITY 1484auto rbegin(_Cp& __c) -> decltype(__c.rbegin()) 1485{ 1486 return __c.rbegin(); 1487} 1488 1489template <class _Cp> 1490inline _LIBCPP_INLINE_VISIBILITY 1491auto rbegin(const _Cp& __c) -> decltype(__c.rbegin()) 1492{ 1493 return __c.rbegin(); 1494} 1495 1496template <class _Cp> 1497inline _LIBCPP_INLINE_VISIBILITY 1498auto rend(_Cp& __c) -> decltype(__c.rend()) 1499{ 1500 return __c.rend(); 1501} 1502 1503template <class _Cp> 1504inline _LIBCPP_INLINE_VISIBILITY 1505auto rend(const _Cp& __c) -> decltype(__c.rend()) 1506{ 1507 return __c.rend(); 1508} 1509 1510template <class _Cp> 1511inline _LIBCPP_INLINE_VISIBILITY 1512auto crbegin(const _Cp& __c) -> decltype(rbegin(__c)) 1513{ 1514 return rbegin(__c); 1515} 1516 1517template <class _Cp> 1518inline _LIBCPP_INLINE_VISIBILITY 1519auto crend(const _Cp& __c) -> decltype(rend(__c)) 1520{ 1521 return rend(__c); 1522} 1523 1524#endif 1525 1526 1527#else // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_TRAILING_RETURN) 1528 1529template <class _Cp> 1530inline _LIBCPP_INLINE_VISIBILITY 1531typename _Cp::iterator 1532begin(_Cp& __c) 1533{ 1534 return __c.begin(); 1535} 1536 1537template <class _Cp> 1538inline _LIBCPP_INLINE_VISIBILITY 1539typename _Cp::const_iterator 1540begin(const _Cp& __c) 1541{ 1542 return __c.begin(); 1543} 1544 1545template <class _Cp> 1546inline _LIBCPP_INLINE_VISIBILITY 1547typename _Cp::iterator 1548end(_Cp& __c) 1549{ 1550 return __c.end(); 1551} 1552 1553template <class _Cp> 1554inline _LIBCPP_INLINE_VISIBILITY 1555typename _Cp::const_iterator 1556end(const _Cp& __c) 1557{ 1558 return __c.end(); 1559} 1560 1561#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_TRAILING_RETURN) 1562 1563_LIBCPP_END_NAMESPACE_STD 1564 1565#endif // _LIBCPP_ITERATOR 1566