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