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