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