1// -*- C++ -*- 2//===-------------------------- iterator ----------------------------------===// 3// 4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5// See https://llvm.org/LICENSE.txt for license information. 6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7// 8//===----------------------------------------------------------------------===// 9 10#ifndef _LIBCPP_ITERATOR 11#define _LIBCPP_ITERATOR 12 13/* 14 iterator synopsis 15 16#include <concepts> 17 18namespace std 19{ 20template<class> struct incrementable_traits; // since C++20 21template<class T> 22 using iter_difference_t = see below; // since C++20 23 24template<class> struct indirectly_readable_traits; // since C++20 25template<class T> 26 using iter_value_t = see below; // since C++20 27 28template<class Iterator> 29struct iterator_traits; 30 31template<class T> 32 requires is_object_v<T> // since C++20 33struct iterator_traits<T*>; 34 35template<dereferenceable T> 36 using iter_reference_t = decltype(*declval<T&>()); 37 38namespace ranges::inline unspecified { 39 inline constexpr unspecified iter_move = unspecified; // since C++20, nodiscard as an extension 40}} 41 42template<dereferenceable T> 43 requires ... 44using iter_rvalue_reference_t = decltype(ranges::iter_move(declval<T&>())); // since C++20 45 46// [iterator.concepts], iterator concepts 47// [iterator.concept.readable], concept indirectly_readable 48template<class In> 49 concept indirectly_readable = see below; // since C++20 50 51template<indirectly_readable T> 52 using iter_common_reference_t = 53 common_reference_t<iter_reference_t<T>, iter_value_t<T>&>; // since C++20 54 55// [iterator.concept.writable], concept indirectly_writable 56template<class Out, class T> 57 concept indirectly_writable = see below; // since C++20 58 59// [iterator.concept.winc], concept weakly_incrementable 60template<class I> 61 concept weakly_incrementable = see below; // since C++20 62 63// [iterator.concept.inc], concept incrementable 64template<class I> 65 concept incrementable = see below; // since C++20 66 67// [iterator.concept.iterator], concept input_or_output_iterator 68 template<class I> 69 concept input_or_output_iterator = see below; // since C++20 70 71// [iterator.concept.sentinel], concept sentinel_for 72template<class S, class I> 73 concept sentinel_for = see below; // since C++20 74 75// [iterator.concept.sizedsentinel], concept sized_sentinel_for 76template<class S, class I> 77 inline constexpr bool disable_sized_sentinel_for = false; 78 79template<class S, class I> 80 concept sized_sentinel_for = see below; 81 82// [iterator.concept.input], concept input_iterator 83template<class I> 84 concept input_iterator = see below; // since C++20 85 86// [iterator.concept.forward], concept forward_iterator 87template<class I> 88 concept forward_iterator = see below; // since C++20 89 90// [iterator.concept.bidir], concept bidirectional_iterator 91template<class I> 92 concept bidirectional_iterator = see below; // since C++20 93 94// [iterator.concept.random.access], concept random_access_iterator 95template<class I> 96 concept random_access_iterator = see below; // since C++20 97 98// [indirectcallable] 99// [indirectcallable.indirectinvocable] 100template<class F, class I> 101 concept indirectly_unary_invocable = see below; // since C++20 102 103template<class F, class I> 104 concept indirectly_regular_unary_invocable = see below; // since C++20 105 106template<class F, class I> 107 concept indirect_unary_predicate = see below; // since C++20 108 109template<class F, class I1, class I2> 110 concept indirect_binary_predicate = see below; // since C++20 111 112template<class F, class I1, class I2 = I1> 113 concept indirect_equivalence_relation = see below; // since C++20 114 115template<class F, class I1, class I2 = I1> 116 concept indirect_strict_weak_order = see below; // since C++20 117 118template<class F, class... Is> 119 using indirect_result_t = see below; // since C++20 120 121// [projected], projected 122template<indirectly_readable I, indirectly_regular_unary_invocable<I> Proj> 123 struct projected; // since C++20 124 125template<weakly_incrementable I, indirectly_regular_unary_invocable<I> Proj> 126 struct incrementable_traits<projected<I, Proj>>; // since C++20 127 128// [alg.req.ind.move], concept indirectly_movable 129template<class In, class Out> 130 concept indirectly_movable = see below; // since C++20 131 132template<class In, class Out> 133 concept indirectly_movable_storable = see below; // since C++20 134 135template<class Category, class T, class Distance = ptrdiff_t, 136 class Pointer = T*, class Reference = T&> 137struct iterator // deprecated in C++17 138{ 139 typedef T value_type; 140 typedef Distance difference_type; 141 typedef Pointer pointer; 142 typedef Reference reference; 143 typedef Category iterator_category; 144}; 145 146struct input_iterator_tag {}; 147struct output_iterator_tag {}; 148struct forward_iterator_tag : public input_iterator_tag {}; 149struct bidirectional_iterator_tag : public forward_iterator_tag {}; 150struct random_access_iterator_tag : public bidirectional_iterator_tag {}; 151 152// 27.4.3, iterator operations 153template <class InputIterator, class Distance> // constexpr in C++17 154 constexpr void advance(InputIterator& i, Distance n); 155 156template <class InputIterator> // constexpr in C++17 157 constexpr typename iterator_traits<InputIterator>::difference_type 158 distance(InputIterator first, InputIterator last); 159 160template <class InputIterator> // constexpr in C++17 161 constexpr InputIterator next(InputIterator x, 162typename iterator_traits<InputIterator>::difference_type n = 1); 163 164template <class BidirectionalIterator> // constexpr in C++17 165 constexpr BidirectionalIterator prev(BidirectionalIterator x, 166 typename iterator_traits<BidirectionalIterator>::difference_type n = 1); 167 168// [range.iter.ops], range iterator operations 169namespace ranges { 170 // [range.iter.op.advance], ranges::advance 171 template<input_or_output_iterator I> 172 constexpr void advance(I& i, iter_difference_t<I> n); // since C++20 173 template<input_or_output_iterator I, sentinel_for<I> S> 174 constexpr void advance(I& i, S bound); // since C++20 175 template<input_or_output_iterator I, sentinel_for<I> S> 176 constexpr iter_difference_t<I> advance(I& i, iter_difference_t<I> n, S bound); // since C++20 177} 178 179template <class Iterator> 180class reverse_iterator 181 : public iterator<typename iterator_traits<Iterator>::iterator_category, // until C++17 182 typename iterator_traits<Iterator>::value_type, 183 typename iterator_traits<Iterator>::difference_type, 184 typename iterator_traits<Iterator>::pointer, 185 typename iterator_traits<Iterator>::reference> 186{ 187protected: 188 Iterator current; 189public: 190 typedef Iterator iterator_type; 191 typedef typename iterator_traits<Iterator>::difference_type difference_type; 192 typedef typename iterator_traits<Iterator>::reference reference; 193 typedef typename iterator_traits<Iterator>::pointer pointer; 194 195 constexpr reverse_iterator(); 196 constexpr explicit reverse_iterator(Iterator x); 197 template <class U> constexpr reverse_iterator(const reverse_iterator<U>& u); 198 template <class U> constexpr reverse_iterator& operator=(const reverse_iterator<U>& u); 199 constexpr Iterator base() const; 200 constexpr reference operator*() const; 201 constexpr pointer operator->() const; 202 constexpr reverse_iterator& operator++(); 203 constexpr reverse_iterator operator++(int); 204 constexpr reverse_iterator& operator--(); 205 constexpr reverse_iterator operator--(int); 206 constexpr reverse_iterator operator+ (difference_type n) const; 207 constexpr reverse_iterator& operator+=(difference_type n); 208 constexpr reverse_iterator operator- (difference_type n) const; 209 constexpr reverse_iterator& operator-=(difference_type n); 210 constexpr reference operator[](difference_type n) const; 211}; 212 213template <class Iterator1, class Iterator2> 214constexpr bool // constexpr in C++17 215operator==(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 216 217template <class Iterator1, class Iterator2> 218constexpr bool // constexpr in C++17 219operator<(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 220 221template <class Iterator1, class Iterator2> 222constexpr bool // constexpr in C++17 223operator!=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 224 225template <class Iterator1, class Iterator2> 226constexpr bool // constexpr in C++17 227operator>(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 228 229template <class Iterator1, class Iterator2> 230constexpr bool // constexpr in C++17 231operator>=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 232 233template <class Iterator1, class Iterator2> 234constexpr bool // constexpr in C++17 235operator<=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y); 236 237template <class Iterator1, class Iterator2> 238constexpr auto 239operator-(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y) 240-> decltype(__y.base() - __x.base()); // constexpr in C++17 241 242template <class Iterator> 243constexpr reverse_iterator<Iterator> 244operator+(typename reverse_iterator<Iterator>::difference_type n, 245 const reverse_iterator<Iterator>& x); // constexpr in C++17 246 247template <class Iterator> 248constexpr reverse_iterator<Iterator> make_reverse_iterator(Iterator i); // C++14, constexpr in C++17 249 250template <class Container> 251class back_insert_iterator 252 : public iterator<output_iterator_tag, void, void, void, void> // until C++17 253{ 254protected: 255 Container* container; 256public: 257 typedef Container container_type; 258 typedef void value_type; 259 typedef void difference_type; // until C++20 260 typedef ptrdiff_t difference_type; // since C++20 261 typedef void reference; 262 typedef void pointer; 263 264 explicit back_insert_iterator(Container& x); // constexpr in C++20 265 back_insert_iterator& operator=(const typename Container::value_type& value); // constexpr in C++20 266 back_insert_iterator& operator*(); // constexpr in C++20 267 back_insert_iterator& operator++(); // constexpr in C++20 268 back_insert_iterator operator++(int); // constexpr in C++20 269}; 270 271template <class Container> back_insert_iterator<Container> back_inserter(Container& x); // constexpr in C++20 272 273template <class Container> 274class front_insert_iterator 275 : public iterator<output_iterator_tag, void, void, void, void> // until C++17 276{ 277protected: 278 Container* container; 279public: 280 typedef Container container_type; 281 typedef void value_type; 282 typedef void difference_type; // until C++20 283 typedef ptrdiff_t difference_type; // since C++20 284 typedef void reference; 285 typedef void pointer; 286 287 explicit front_insert_iterator(Container& x); // constexpr in C++20 288 front_insert_iterator& operator=(const typename Container::value_type& value); // constexpr in C++20 289 front_insert_iterator& operator*(); // constexpr in C++20 290 front_insert_iterator& operator++(); // constexpr in C++20 291 front_insert_iterator operator++(int); // constexpr in C++20 292}; 293 294template <class Container> front_insert_iterator<Container> front_inserter(Container& x); // constexpr in C++20 295 296template <class Container> 297class insert_iterator 298 : public iterator<output_iterator_tag, void, void, void, void> // until C++17 299{ 300protected: 301 Container* container; 302 typename Container::iterator iter; 303public: 304 typedef Container container_type; 305 typedef void value_type; 306 typedef void difference_type; // until C++20 307 typedef ptrdiff_t difference_type; // since C++20 308 typedef void reference; 309 typedef void pointer; 310 311 insert_iterator(Container& x, typename Container::iterator i); // constexpr in C++20 312 insert_iterator& operator=(const typename Container::value_type& value); // constexpr in C++20 313 insert_iterator& operator*(); // constexpr in C++20 314 insert_iterator& operator++(); // constexpr in C++20 315 insert_iterator& operator++(int); // constexpr in C++20 316}; 317 318template <class Container, class Iterator> 319insert_iterator<Container> inserter(Container& x, Iterator i); // constexpr in C++20 320 321template <class Iterator> 322class move_iterator { 323public: 324 typedef Iterator iterator_type; 325 typedef typename iterator_traits<Iterator>::difference_type difference_type; 326 typedef Iterator pointer; 327 typedef typename iterator_traits<Iterator>::value_type value_type; 328 typedef typename iterator_traits<Iterator>::iterator_category iterator_category; 329 typedef value_type&& reference; 330 331 constexpr move_iterator(); // all the constexprs are in C++17 332 constexpr explicit move_iterator(Iterator i); 333 template <class U> 334 constexpr move_iterator(const move_iterator<U>& u); 335 template <class U> 336 constexpr move_iterator& operator=(const move_iterator<U>& u); 337 constexpr iterator_type base() const; 338 constexpr reference operator*() const; 339 constexpr pointer operator->() const; 340 constexpr move_iterator& operator++(); 341 constexpr move_iterator operator++(int); 342 constexpr move_iterator& operator--(); 343 constexpr move_iterator operator--(int); 344 constexpr move_iterator operator+(difference_type n) const; 345 constexpr move_iterator& operator+=(difference_type n); 346 constexpr move_iterator operator-(difference_type n) const; 347 constexpr move_iterator& operator-=(difference_type n); 348 constexpr unspecified operator[](difference_type n) const; 349private: 350 Iterator current; // exposition only 351}; 352 353template <class Iterator1, class Iterator2> 354constexpr bool // constexpr in C++17 355operator==(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y); 356 357template <class Iterator1, class Iterator2> 358constexpr bool // constexpr in C++17 359operator!=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y); 360 361template <class Iterator1, class Iterator2> 362constexpr bool // constexpr in C++17 363operator<(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y); 364 365template <class Iterator1, class Iterator2> 366constexpr bool // constexpr in C++17 367operator<=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y); 368 369template <class Iterator1, class Iterator2> 370constexpr bool // constexpr in C++17 371operator>(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y); 372 373template <class Iterator1, class Iterator2> 374constexpr bool // constexpr in C++17 375operator>=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y); 376 377template <class Iterator1, class Iterator2> 378constexpr auto // constexpr in C++17 379operator-(const move_iterator<Iterator1>& x, 380 const move_iterator<Iterator2>& y) -> decltype(x.base() - y.base()); 381 382template <class Iterator> 383constexpr move_iterator<Iterator> operator+( // constexpr in C++17 384 typename move_iterator<Iterator>::difference_type n, 385 const move_iterator<Iterator>& x); 386 387template <class Iterator> // constexpr in C++17 388constexpr move_iterator<Iterator> make_move_iterator(const Iterator& i); 389 390// [default.sentinel], default sentinel 391struct default_sentinel_t; 392inline constexpr default_sentinel_t default_sentinel{}; 393 394template <class T, class charT = char, class traits = char_traits<charT>, class Distance = ptrdiff_t> 395class istream_iterator 396 : public iterator<input_iterator_tag, T, Distance, const T*, const T&> // until C++17 397{ 398public: 399 typedef input_iterator_tag iterator_category; 400 typedef T value_type; 401 typedef Distance difference_type; 402 typedef const T* pointer; 403 typedef const T& reference; 404 405 typedef charT char_type; 406 typedef traits traits_type; 407 typedef basic_istream<charT, traits> istream_type; 408 409 constexpr istream_iterator(); 410 istream_iterator(istream_type& s); 411 istream_iterator(const istream_iterator& x); 412 ~istream_iterator(); 413 414 const T& operator*() const; 415 const T* operator->() const; 416 istream_iterator& operator++(); 417 istream_iterator operator++(int); 418}; 419 420template <class T, class charT, class traits, class Distance> 421bool operator==(const istream_iterator<T,charT,traits,Distance>& x, 422 const istream_iterator<T,charT,traits,Distance>& y); 423template <class T, class charT, class traits, class Distance> 424bool operator!=(const istream_iterator<T,charT,traits,Distance>& x, 425 const istream_iterator<T,charT,traits,Distance>& y); 426 427template <class T, class charT = char, class traits = char_traits<charT> > 428class ostream_iterator 429 : public iterator<output_iterator_tag, void, void, void, void> // until C++17 430{ 431public: 432 typedef output_iterator_tag iterator_category; 433 typedef void value_type; 434 typedef void difference_type; // until C++20 435 typedef ptrdiff_t difference_type; // since C++20 436 typedef void pointer; 437 typedef void reference; 438 439 typedef charT char_type; 440 typedef traits traits_type; 441 typedef basic_ostream<charT,traits> ostream_type; 442 443 ostream_iterator(ostream_type& s); 444 ostream_iterator(ostream_type& s, const charT* delimiter); 445 ostream_iterator(const ostream_iterator& x); 446 ~ostream_iterator(); 447 ostream_iterator& operator=(const T& value); 448 449 ostream_iterator& operator*(); 450 ostream_iterator& operator++(); 451 ostream_iterator& operator++(int); 452}; 453 454template<class charT, class traits = char_traits<charT> > 455class istreambuf_iterator 456 : public iterator<input_iterator_tag, charT, traits::off_type, unspecified, charT> // until C++17 457{ 458public: 459 typedef input_iterator_tag iterator_category; 460 typedef charT value_type; 461 typedef traits::off_type difference_type; 462 typedef unspecified pointer; 463 typedef charT reference; 464 465 typedef charT char_type; 466 typedef traits traits_type; 467 typedef traits::int_type int_type; 468 typedef basic_streambuf<charT, traits> streambuf_type; 469 typedef basic_istream<charT, traits> istream_type; 470 471 istreambuf_iterator() noexcept; 472 istreambuf_iterator(istream_type& s) noexcept; 473 istreambuf_iterator(streambuf_type* s) noexcept; 474 istreambuf_iterator(a-private-type) noexcept; 475 476 charT operator*() const; 477 pointer operator->() const; 478 istreambuf_iterator& operator++(); 479 a-private-type operator++(int); 480 481 bool equal(const istreambuf_iterator& b) const; 482}; 483 484template <class charT, class traits> 485bool operator==(const istreambuf_iterator<charT,traits>& a, 486 const istreambuf_iterator<charT,traits>& b); 487template <class charT, class traits> 488bool operator!=(const istreambuf_iterator<charT,traits>& a, 489 const istreambuf_iterator<charT,traits>& b); 490 491template <class charT, class traits = char_traits<charT> > 492class ostreambuf_iterator 493 : public iterator<output_iterator_tag, void, void, void, void> // until C++17 494{ 495public: 496 typedef output_iterator_tag iterator_category; 497 typedef void value_type; 498 typedef void difference_type; // until C++20 499 typedef ptrdiff_t difference_type; // since C++20 500 typedef void pointer; 501 typedef void reference; 502 503 typedef charT char_type; 504 typedef traits traits_type; 505 typedef basic_streambuf<charT, traits> streambuf_type; 506 typedef basic_ostream<charT, traits> ostream_type; 507 508 ostreambuf_iterator(ostream_type& s) noexcept; 509 ostreambuf_iterator(streambuf_type* s) noexcept; 510 ostreambuf_iterator& operator=(charT c); 511 ostreambuf_iterator& operator*(); 512 ostreambuf_iterator& operator++(); 513 ostreambuf_iterator& operator++(int); 514 bool failed() const noexcept; 515}; 516 517template <class C> constexpr auto begin(C& c) -> decltype(c.begin()); 518template <class C> constexpr auto begin(const C& c) -> decltype(c.begin()); 519template <class C> constexpr auto end(C& c) -> decltype(c.end()); 520template <class C> constexpr auto end(const C& c) -> decltype(c.end()); 521template <class T, size_t N> constexpr T* begin(T (&array)[N]); 522template <class T, size_t N> constexpr T* end(T (&array)[N]); 523 524template <class C> auto constexpr cbegin(const C& c) -> decltype(std::begin(c)); // C++14 525template <class C> auto constexpr cend(const C& c) -> decltype(std::end(c)); // C++14 526template <class C> auto constexpr rbegin(C& c) -> decltype(c.rbegin()); // C++14 527template <class C> auto constexpr rbegin(const C& c) -> decltype(c.rbegin()); // C++14 528template <class C> auto constexpr rend(C& c) -> decltype(c.rend()); // C++14 529template <class C> constexpr auto rend(const C& c) -> decltype(c.rend()); // C++14 530template <class E> reverse_iterator<const E*> constexpr rbegin(initializer_list<E> il); // C++14 531template <class E> reverse_iterator<const E*> constexpr rend(initializer_list<E> il); // C++14 532template <class T, size_t N> reverse_iterator<T*> constexpr rbegin(T (&array)[N]); // C++14 533template <class T, size_t N> reverse_iterator<T*> constexpr rend(T (&array)[N]); // C++14 534template <class C> constexpr auto crbegin(const C& c) -> decltype(std::rbegin(c)); // C++14 535template <class C> constexpr auto crend(const C& c) -> decltype(std::rend(c)); // C++14 536 537// 24.8, container access: 538template <class C> constexpr auto size(const C& c) -> decltype(c.size()); // C++17 539template <class T, size_t N> constexpr size_t size(const T (&array)[N]) noexcept; // C++17 540 541template <class C> constexpr auto ssize(const C& c) 542 -> common_type_t<ptrdiff_t, make_signed_t<decltype(c.size())>>; // C++20 543template <class T, ptrdiff_t> constexpr ptrdiff_t ssize(const T (&array)[N]) noexcept; // C++20 544 545template <class C> constexpr auto empty(const C& c) -> decltype(c.empty()); // C++17 546template <class T, size_t N> constexpr bool empty(const T (&array)[N]) noexcept; // C++17 547template <class E> constexpr bool empty(initializer_list<E> il) noexcept; // C++17 548template <class C> constexpr auto data(C& c) -> decltype(c.data()); // C++17 549template <class C> constexpr auto data(const C& c) -> decltype(c.data()); // C++17 550template <class T, size_t N> constexpr T* data(T (&array)[N]) noexcept; // C++17 551template <class E> constexpr const E* data(initializer_list<E> il) noexcept; // C++17 552 553} // std 554 555*/ 556 557#include <__config> 558#include <__debug> 559#include <__functional_base> 560#include <__iterator/advance.h> 561#include <__iterator/back_insert_iterator.h> 562#include <__iterator/concepts.h> 563#include <__iterator/default_sentinel.h> 564#include <__iterator/front_insert_iterator.h> 565#include <__iterator/incrementable_traits.h> 566#include <__iterator/insert_iterator.h> 567#include <__iterator/istream_iterator.h> 568#include <__iterator/istreambuf_iterator.h> 569#include <__iterator/iter_move.h> 570#include <__iterator/iter_swap.h> 571#include <__iterator/iterator_traits.h> 572#include <__iterator/iterator.h> 573#include <__iterator/move_iterator.h> 574#include <__iterator/next.h> 575#include <__iterator/ostream_iterator.h> 576#include <__iterator/ostreambuf_iterator.h> 577#include <__iterator/prev.h> 578#include <__iterator/projected.h> 579#include <__iterator/readable_traits.h> 580#include <__iterator/reverse_iterator.h> 581#include <__iterator/wrap_iter.h> 582#include <__memory/addressof.h> 583#include <__memory/pointer_traits.h> 584#include <__utility/forward.h> 585#include <compare> 586#include <concepts> // Mandated by the Standard. 587#include <cstddef> 588#include <initializer_list> 589#include <type_traits> 590#include <version> 591 592#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 593#pragma GCC system_header 594#endif 595 596_LIBCPP_BEGIN_NAMESPACE_STD 597 598template <class _InputIter> 599inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 600typename iterator_traits<_InputIter>::difference_type 601__distance(_InputIter __first, _InputIter __last, input_iterator_tag) 602{ 603 typename iterator_traits<_InputIter>::difference_type __r(0); 604 for (; __first != __last; ++__first) 605 ++__r; 606 return __r; 607} 608 609template <class _RandIter> 610inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 611typename iterator_traits<_RandIter>::difference_type 612__distance(_RandIter __first, _RandIter __last, random_access_iterator_tag) 613{ 614 return __last - __first; 615} 616 617template <class _InputIter> 618inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 619typename iterator_traits<_InputIter>::difference_type 620distance(_InputIter __first, _InputIter __last) 621{ 622 return _VSTD::__distance(__first, __last, typename iterator_traits<_InputIter>::iterator_category()); 623} 624 625template <class _Tp, size_t _Np> 626_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 627_Tp* 628begin(_Tp (&__array)[_Np]) 629{ 630 return __array; 631} 632 633template <class _Tp, size_t _Np> 634_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 635_Tp* 636end(_Tp (&__array)[_Np]) 637{ 638 return __array + _Np; 639} 640 641#if !defined(_LIBCPP_CXX03_LANG) 642 643template <class _Cp> 644_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 645auto 646begin(_Cp& __c) -> decltype(__c.begin()) 647{ 648 return __c.begin(); 649} 650 651template <class _Cp> 652_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 653auto 654begin(const _Cp& __c) -> decltype(__c.begin()) 655{ 656 return __c.begin(); 657} 658 659template <class _Cp> 660_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 661auto 662end(_Cp& __c) -> decltype(__c.end()) 663{ 664 return __c.end(); 665} 666 667template <class _Cp> 668_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 669auto 670end(const _Cp& __c) -> decltype(__c.end()) 671{ 672 return __c.end(); 673} 674 675#if _LIBCPP_STD_VER > 11 676 677template <class _Tp, size_t _Np> 678_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 679reverse_iterator<_Tp*> rbegin(_Tp (&__array)[_Np]) 680{ 681 return reverse_iterator<_Tp*>(__array + _Np); 682} 683 684template <class _Tp, size_t _Np> 685_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 686reverse_iterator<_Tp*> rend(_Tp (&__array)[_Np]) 687{ 688 return reverse_iterator<_Tp*>(__array); 689} 690 691template <class _Ep> 692_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 693reverse_iterator<const _Ep*> rbegin(initializer_list<_Ep> __il) 694{ 695 return reverse_iterator<const _Ep*>(__il.end()); 696} 697 698template <class _Ep> 699_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 700reverse_iterator<const _Ep*> rend(initializer_list<_Ep> __il) 701{ 702 return reverse_iterator<const _Ep*>(__il.begin()); 703} 704 705template <class _Cp> 706_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 707auto cbegin(const _Cp& __c) -> decltype(_VSTD::begin(__c)) 708{ 709 return _VSTD::begin(__c); 710} 711 712template <class _Cp> 713_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 714auto cend(const _Cp& __c) -> decltype(_VSTD::end(__c)) 715{ 716 return _VSTD::end(__c); 717} 718 719template <class _Cp> 720_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 721auto rbegin(_Cp& __c) -> decltype(__c.rbegin()) 722{ 723 return __c.rbegin(); 724} 725 726template <class _Cp> 727_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 728auto rbegin(const _Cp& __c) -> decltype(__c.rbegin()) 729{ 730 return __c.rbegin(); 731} 732 733template <class _Cp> 734_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 735auto rend(_Cp& __c) -> decltype(__c.rend()) 736{ 737 return __c.rend(); 738} 739 740template <class _Cp> 741_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 742auto rend(const _Cp& __c) -> decltype(__c.rend()) 743{ 744 return __c.rend(); 745} 746 747template <class _Cp> 748_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 749auto crbegin(const _Cp& __c) -> decltype(_VSTD::rbegin(__c)) 750{ 751 return _VSTD::rbegin(__c); 752} 753 754template <class _Cp> 755_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 756auto crend(const _Cp& __c) -> decltype(_VSTD::rend(__c)) 757{ 758 return _VSTD::rend(__c); 759} 760 761#endif 762 763 764#else // defined(_LIBCPP_CXX03_LANG) 765 766template <class _Cp> 767_LIBCPP_INLINE_VISIBILITY 768typename _Cp::iterator 769begin(_Cp& __c) 770{ 771 return __c.begin(); 772} 773 774template <class _Cp> 775_LIBCPP_INLINE_VISIBILITY 776typename _Cp::const_iterator 777begin(const _Cp& __c) 778{ 779 return __c.begin(); 780} 781 782template <class _Cp> 783_LIBCPP_INLINE_VISIBILITY 784typename _Cp::iterator 785end(_Cp& __c) 786{ 787 return __c.end(); 788} 789 790template <class _Cp> 791_LIBCPP_INLINE_VISIBILITY 792typename _Cp::const_iterator 793end(const _Cp& __c) 794{ 795 return __c.end(); 796} 797 798#endif // !defined(_LIBCPP_CXX03_LANG) 799 800#if _LIBCPP_STD_VER > 14 801 802// #if _LIBCPP_STD_VER > 11 803// template <> 804// struct _LIBCPP_TEMPLATE_VIS plus<void> 805// { 806// template <class _T1, class _T2> 807// _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY 808// auto operator()(_T1&& __t, _T2&& __u) const 809// _NOEXCEPT_(noexcept(_VSTD::forward<_T1>(__t) + _VSTD::forward<_T2>(__u))) 810// -> decltype (_VSTD::forward<_T1>(__t) + _VSTD::forward<_T2>(__u)) 811// { return _VSTD::forward<_T1>(__t) + _VSTD::forward<_T2>(__u); } 812// typedef void is_transparent; 813// }; 814// #endif 815 816template <class _Cont> 817_LIBCPP_INLINE_VISIBILITY 818constexpr auto size(const _Cont& __c) 819_NOEXCEPT_(noexcept(__c.size())) 820-> decltype (__c.size()) 821{ return __c.size(); } 822 823template <class _Tp, size_t _Sz> 824_LIBCPP_INLINE_VISIBILITY 825constexpr size_t size(const _Tp (&)[_Sz]) noexcept { return _Sz; } 826 827#if _LIBCPP_STD_VER > 17 828template <class _Cont> 829_LIBCPP_INLINE_VISIBILITY 830constexpr auto ssize(const _Cont& __c) 831_NOEXCEPT_(noexcept(static_cast<common_type_t<ptrdiff_t, make_signed_t<decltype(__c.size())>>>(__c.size()))) 832-> common_type_t<ptrdiff_t, make_signed_t<decltype(__c.size())>> 833{ return static_cast<common_type_t<ptrdiff_t, make_signed_t<decltype(__c.size())>>>(__c.size()); } 834 835template <class _Tp, ptrdiff_t _Sz> 836_LIBCPP_INLINE_VISIBILITY 837constexpr ptrdiff_t ssize(const _Tp (&)[_Sz]) noexcept { return _Sz; } 838#endif 839 840template <class _Cont> 841_LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 842constexpr auto empty(const _Cont& __c) 843_NOEXCEPT_(noexcept(__c.empty())) 844-> decltype (__c.empty()) 845{ return __c.empty(); } 846 847template <class _Tp, size_t _Sz> 848_LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 849constexpr bool empty(const _Tp (&)[_Sz]) noexcept { return false; } 850 851template <class _Ep> 852_LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 853constexpr bool empty(initializer_list<_Ep> __il) noexcept { return __il.size() == 0; } 854 855template <class _Cont> constexpr 856_LIBCPP_INLINE_VISIBILITY 857auto data(_Cont& __c) 858_NOEXCEPT_(noexcept(__c.data())) 859-> decltype (__c.data()) 860{ return __c.data(); } 861 862template <class _Cont> constexpr 863_LIBCPP_INLINE_VISIBILITY 864auto data(const _Cont& __c) 865_NOEXCEPT_(noexcept(__c.data())) 866-> decltype (__c.data()) 867{ return __c.data(); } 868 869template <class _Tp, size_t _Sz> 870_LIBCPP_INLINE_VISIBILITY 871constexpr _Tp* data(_Tp (&__array)[_Sz]) noexcept { return __array; } 872 873template <class _Ep> 874_LIBCPP_INLINE_VISIBILITY 875constexpr const _Ep* data(initializer_list<_Ep> __il) noexcept { return __il.begin(); } 876#endif 877 878template <class _Container, class _Predicate> 879typename _Container::size_type 880__libcpp_erase_if_container(_Container& __c, _Predicate& __pred) { 881 typename _Container::size_type __old_size = __c.size(); 882 883 const typename _Container::iterator __last = __c.end(); 884 for (typename _Container::iterator __iter = __c.begin(); __iter != __last;) { 885 if (__pred(*__iter)) 886 __iter = __c.erase(__iter); 887 else 888 ++__iter; 889 } 890 891 return __old_size - __c.size(); 892} 893 894_LIBCPP_END_NAMESPACE_STD 895 896#endif // _LIBCPP_ITERATOR 897