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