2 //===-------------------------- iterator ----------------------------------===//
4 // The LLVM Compiler Infrastructure
6 // This file is dual licensed under the MIT and the University of Illinois Open
7 // Source Licenses. See LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
11 #ifndef _LIBCPP_ITERATOR
12 #define _LIBCPP_ITERATOR
20 template<class Iterator>
21 struct iterator_traits
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;
31 struct iterator_traits<T*>
33 typedef ptrdiff_t difference_type;
37 typedef random_access_iterator_tag iterator_category;
41 struct iterator_traits<const T*>
43 typedef ptrdiff_t difference_type;
45 typedef const T* pointer;
46 typedef const T& reference;
47 typedef random_access_iterator_tag iterator_category;
50 template<class Category, class T, class Distance = ptrdiff_t,
51 class Pointer = T*, class Reference = T&>
55 typedef Distance difference_type;
56 typedef Pointer pointer;
57 typedef Reference reference;
58 typedef Category iterator_category;
61 struct input_iterator_tag {};
62 struct output_iterator_tag {};
63 struct forward_iterator_tag : public input_iterator_tag {};
64 struct bidirectional_iterator_tag : public forward_iterator_tag {};
65 struct random_access_iterator_tag : public bidirectional_iterator_tag {};
67 // extension: second argument not conforming to C++03
68 template <class InputIterator>
69 void advance(InputIterator& i,
70 typename iterator_traits<InputIterator>::difference_type n);
72 template <class InputIterator>
73 typename iterator_traits<InputIterator>::difference_type
74 distance(InputIterator first, InputIterator last);
76 template <class Iterator>
77 class 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>
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;
93 explicit reverse_iterator(Iterator x);
94 template <class U> reverse_iterator(const reverse_iterator<U>& u);
95 Iterator base() const;
96 reference operator*() const;
97 pointer operator->() const;
98 reverse_iterator& operator++();
99 reverse_iterator operator++(int);
100 reverse_iterator& operator--();
101 reverse_iterator operator--(int);
102 reverse_iterator operator+ (difference_type n) const;
103 reverse_iterator& operator+=(difference_type n);
104 reverse_iterator operator- (difference_type n) const;
105 reverse_iterator& operator-=(difference_type n);
106 reference operator[](difference_type n) const;
109 template <class Iterator1, class Iterator2>
111 operator==(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
113 template <class Iterator1, class Iterator2>
115 operator<(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
117 template <class Iterator1, class Iterator2>
119 operator!=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
121 template <class Iterator1, class Iterator2>
123 operator>(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
125 template <class Iterator1, class Iterator2>
127 operator>=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
129 template <class Iterator1, class Iterator2>
131 operator<=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
133 template <class Iterator1, class Iterator2>
135 operator-(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y)
136 -> decltype(__y.base() - __x.base());
138 template <class Iterator>
139 reverse_iterator<Iterator>
140 operator+(typename reverse_iterator<Iterator>::difference_type n, const reverse_iterator<Iterator>& x);
142 template <class Iterator> reverse_iterator<Iterator> make_reverse_iterator(Iterator i); // C++14
144 template <class Container>
145 class back_insert_iterator
148 Container* container;
150 typedef Container container_type;
151 typedef void value_type;
152 typedef void difference_type;
153 typedef void reference;
154 typedef void pointer;
156 explicit back_insert_iterator(Container& x);
157 back_insert_iterator& operator=(const typename Container::value_type& value);
158 back_insert_iterator& operator*();
159 back_insert_iterator& operator++();
160 back_insert_iterator operator++(int);
163 template <class Container> back_insert_iterator<Container> back_inserter(Container& x);
165 template <class Container>
166 class front_insert_iterator
169 Container* container;
171 typedef Container container_type;
172 typedef void value_type;
173 typedef void difference_type;
174 typedef void reference;
175 typedef void pointer;
177 explicit front_insert_iterator(Container& x);
178 front_insert_iterator& operator=(const typename Container::value_type& value);
179 front_insert_iterator& operator*();
180 front_insert_iterator& operator++();
181 front_insert_iterator operator++(int);
184 template <class Container> front_insert_iterator<Container> front_inserter(Container& x);
186 template <class Container>
187 class insert_iterator
190 Container* container;
191 typename Container::iterator iter;
193 typedef Container container_type;
194 typedef void value_type;
195 typedef void difference_type;
196 typedef void reference;
197 typedef void pointer;
199 insert_iterator(Container& x, typename Container::iterator i);
200 insert_iterator& operator=(const typename Container::value_type& value);
201 insert_iterator& operator*();
202 insert_iterator& operator++();
203 insert_iterator& operator++(int);
206 template <class Container, class Iterator>
207 insert_iterator<Container> inserter(Container& x, Iterator i);
209 template <class Iterator>
210 class move_iterator {
212 typedef Iterator iterator_type;
213 typedef typename iterator_traits<Iterator>::difference_type difference_type;
214 typedef Iterator pointer;
215 typedef typename iterator_traits<Iterator>::value_type value_type;
216 typedef typename iterator_traits<Iterator>::iterator_category iterator_category;
217 typedef value_type&& reference;
220 explicit move_iterator(Iterator i);
221 template <class U> move_iterator(const move_iterator<U>& u);
222 template <class U> move_iterator& operator=(const move_iterator<U>& u);
223 iterator_type base() const;
224 reference operator*() const;
225 pointer operator->() const;
226 move_iterator& operator++();
227 move_iterator operator++(int);
228 move_iterator& operator--();
229 move_iterator operator--(int);
230 move_iterator operator+(difference_type n) const;
231 move_iterator& operator+=(difference_type n);
232 move_iterator operator-(difference_type n) const;
233 move_iterator& operator-=(difference_type n);
234 unspecified operator[](difference_type n) const;
236 Iterator current; // exposition only
239 template <class Iterator1, class Iterator2>
241 operator==(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
243 template <class Iterator1, class Iterator2>
245 operator!=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
247 template <class Iterator1, class Iterator2>
249 operator<(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
251 template <class Iterator1, class Iterator2>
253 operator<=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
255 template <class Iterator1, class Iterator2>
257 operator>(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
259 template <class Iterator1, class Iterator2>
261 operator>=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
263 template <class Iterator1, class Iterator2>
265 operator-(const move_iterator<Iterator1>& x,
266 const move_iterator<Iterator2>& y) -> decltype(x.base() - y.base());
268 template <class Iterator>
269 move_iterator<Iterator> operator+(typename move_iterator<Iterator>::difference_type n,
270 const move_iterator<Iterator>& x);
272 template <class Iterator>
273 move_iterator<Iterator> make_move_iterator(const Iterator& i);
276 template <class T, class charT = char, class traits = char_traits<charT>, class Distance = ptrdiff_t>
277 class istream_iterator
278 : public iterator<input_iterator_tag, T, Distance, const T*, const T&>
281 typedef charT char_type;
282 typedef traits traits_type;
283 typedef basic_istream<charT,traits> istream_type;
285 constexpr istream_iterator();
286 istream_iterator(istream_type& s);
287 istream_iterator(const istream_iterator& x);
290 const T& operator*() const;
291 const T* operator->() const;
292 istream_iterator& operator++();
293 istream_iterator operator++(int);
296 template <class T, class charT, class traits, class Distance>
297 bool operator==(const istream_iterator<T,charT,traits,Distance>& x,
298 const istream_iterator<T,charT,traits,Distance>& y);
299 template <class T, class charT, class traits, class Distance>
300 bool operator!=(const istream_iterator<T,charT,traits,Distance>& x,
301 const istream_iterator<T,charT,traits,Distance>& y);
303 template <class T, class charT = char, class traits = char_traits<charT> >
304 class ostream_iterator
305 : public iterator<output_iterator_tag, void, void, void ,void>
308 typedef charT char_type;
309 typedef traits traits_type;
310 typedef basic_ostream<charT,traits> ostream_type;
312 ostream_iterator(ostream_type& s);
313 ostream_iterator(ostream_type& s, const charT* delimiter);
314 ostream_iterator(const ostream_iterator& x);
316 ostream_iterator& operator=(const T& value);
318 ostream_iterator& operator*();
319 ostream_iterator& operator++();
320 ostream_iterator& operator++(int);
323 template<class charT, class traits = char_traits<charT> >
324 class istreambuf_iterator
325 : public iterator<input_iterator_tag, charT,
326 typename traits::off_type, unspecified,
330 typedef charT char_type;
331 typedef traits traits_type;
332 typedef typename traits::int_type int_type;
333 typedef basic_streambuf<charT,traits> streambuf_type;
334 typedef basic_istream<charT,traits> istream_type;
336 istreambuf_iterator() noexcept;
337 istreambuf_iterator(istream_type& s) noexcept;
338 istreambuf_iterator(streambuf_type* s) noexcept;
339 istreambuf_iterator(a-private-type) noexcept;
341 charT operator*() const;
342 pointer operator->() const;
343 istreambuf_iterator& operator++();
344 a-private-type operator++(int);
346 bool equal(const istreambuf_iterator& b) const;
349 template <class charT, class traits>
350 bool operator==(const istreambuf_iterator<charT,traits>& a,
351 const istreambuf_iterator<charT,traits>& b);
352 template <class charT, class traits>
353 bool operator!=(const istreambuf_iterator<charT,traits>& a,
354 const istreambuf_iterator<charT,traits>& b);
356 template <class charT, class traits = char_traits<charT> >
357 class ostreambuf_iterator
358 : public iterator<output_iterator_tag, void, void, void, void>
361 typedef charT char_type;
362 typedef traits traits_type;
363 typedef basic_streambuf<charT,traits> streambuf_type;
364 typedef basic_ostream<charT,traits> ostream_type;
366 ostreambuf_iterator(ostream_type& s) noexcept;
367 ostreambuf_iterator(streambuf_type* s) noexcept;
368 ostreambuf_iterator& operator=(charT c);
369 ostreambuf_iterator& operator*();
370 ostreambuf_iterator& operator++();
371 ostreambuf_iterator& operator++(int);
372 bool failed() const noexcept;
375 template <class C> auto begin(C& c) -> decltype(c.begin());
376 template <class C> auto begin(const C& c) -> decltype(c.begin());
377 template <class C> auto end(C& c) -> decltype(c.end());
378 template <class C> auto end(const C& c) -> decltype(c.end());
379 template <class T, size_t N> T* begin(T (&array)[N]);
380 template <class T, size_t N> T* end(T (&array)[N]);
382 template <class C> auto cbegin(const C& c) -> decltype(std::begin(c)); // C++14
383 template <class C> auto cend(const C& c) -> decltype(std::end(c)); // C++14
384 template <class C> auto rbegin(C& c) -> decltype(c.rbegin()); // C++14
385 template <class C> auto rbegin(const C& c) -> decltype(c.rbegin()); // C++14
386 template <class C> auto rend(C& c) -> decltype(c.rend()); // C++14
387 template <class C> auto rend(const C& c) -> decltype(c.rend()); // C++14
388 template <class E> reverse_iterator<const E*> rbegin(initializer_list<E> il); // C++14
389 template <class E> reverse_iterator<const E*> rend(initializer_list<E> il); // C++14
390 template <class T, size_t N> reverse_iterator<T*> rbegin(T (&array)[N]); // C++14
391 template <class T, size_t N> reverse_iterator<T*> rend(T (&array)[N]); // C++14
392 template <class C> auto crbegin(const C& c) -> decltype(std::rbegin(c)); // C++14
393 template <class C> auto crend(const C& c) -> decltype(std::rend(c)); // C++14
395 // 24.8, container access:
396 template <class C> constexpr auto size(const C& c) -> decltype(c.size()); // C++17
397 template <class T, size_t N> constexpr size_t size(const T (&array)[N]) noexcept; // C++17
398 template <class C> constexpr auto empty(const C& c) -> decltype(c.empty()); // C++17
399 template <class T, size_t N> constexpr bool empty(const T (&array)[N]) noexcept; // C++17
400 template <class E> constexpr bool empty(initializer_list<E> il) noexcept; // C++17
401 template <class C> constexpr auto data(C& c) -> decltype(c.data()); // C++17
402 template <class C> constexpr auto data(const C& c) -> decltype(c.data()); // C++17
403 template <class T, size_t N> constexpr T* data(T (&array)[N]) noexcept; // C++17
404 template <class E> constexpr const E* data(initializer_list<E> il) noexcept; // C++17
411 #include <iosfwd> // for forward declarations of vector and string.
412 #include <__functional_base>
413 #include <type_traits>
415 #include <initializer_list>
417 #include <Availability.h>
422 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
423 #pragma GCC system_header
426 _LIBCPP_BEGIN_NAMESPACE_STD
428 struct _LIBCPP_TYPE_VIS_ONLY input_iterator_tag {};
429 struct _LIBCPP_TYPE_VIS_ONLY output_iterator_tag {};
430 struct _LIBCPP_TYPE_VIS_ONLY forward_iterator_tag : public input_iterator_tag {};
431 struct _LIBCPP_TYPE_VIS_ONLY bidirectional_iterator_tag : public forward_iterator_tag {};
432 struct _LIBCPP_TYPE_VIS_ONLY random_access_iterator_tag : public bidirectional_iterator_tag {};
435 struct __has_iterator_category
438 struct __two {char __lx; char __lxx;};
439 template <class _Up> static __two __test(...);
440 template <class _Up> static char __test(typename _Up::iterator_category* = 0);
442 static const bool value = sizeof(__test<_Tp>(0)) == 1;
445 template <class _Iter, bool> struct __iterator_traits_impl {};
447 template <class _Iter>
448 struct __iterator_traits_impl<_Iter, true>
450 typedef typename _Iter::difference_type difference_type;
451 typedef typename _Iter::value_type value_type;
452 typedef typename _Iter::pointer pointer;
453 typedef typename _Iter::reference reference;
454 typedef typename _Iter::iterator_category iterator_category;
457 template <class _Iter, bool> struct __iterator_traits {};
459 template <class _Iter>
460 struct __iterator_traits<_Iter, true>
461 : __iterator_traits_impl
464 is_convertible<typename _Iter::iterator_category, input_iterator_tag>::value ||
465 is_convertible<typename _Iter::iterator_category, output_iterator_tag>::value
469 // iterator_traits<Iterator> will only have the nested types if Iterator::iterator_category
470 // exists. Else iterator_traits<Iterator> will be an empty class. This is a
471 // conforming extension which allows some programs to compile and behave as
472 // the client expects instead of failing at compile time.
474 template <class _Iter>
475 struct _LIBCPP_TYPE_VIS_ONLY iterator_traits
476 : __iterator_traits<_Iter, __has_iterator_category<_Iter>::value> {};
479 struct _LIBCPP_TYPE_VIS_ONLY iterator_traits<_Tp*>
481 typedef ptrdiff_t difference_type;
482 typedef typename remove_const<_Tp>::type value_type;
483 typedef _Tp* pointer;
484 typedef _Tp& reference;
485 typedef random_access_iterator_tag iterator_category;
488 template <class _Tp, class _Up, bool = __has_iterator_category<iterator_traits<_Tp> >::value>
489 struct __has_iterator_category_convertible_to
490 : public integral_constant<bool, is_convertible<typename iterator_traits<_Tp>::iterator_category, _Up>::value>
493 template <class _Tp, class _Up>
494 struct __has_iterator_category_convertible_to<_Tp, _Up, false> : public false_type {};
497 struct __is_input_iterator : public __has_iterator_category_convertible_to<_Tp, input_iterator_tag> {};
500 struct __is_forward_iterator : public __has_iterator_category_convertible_to<_Tp, forward_iterator_tag> {};
503 struct __is_bidirectional_iterator : public __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag> {};
506 struct __is_random_access_iterator : public __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag> {};
509 struct __is_exactly_input_iterator
510 : public integral_constant<bool,
511 __has_iterator_category_convertible_to<_Tp, input_iterator_tag>::value &&
512 !__has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value> {};
514 template<class _Category, class _Tp, class _Distance = ptrdiff_t,
515 class _Pointer = _Tp*, class _Reference = _Tp&>
516 struct _LIBCPP_TYPE_VIS_ONLY iterator
518 typedef _Tp value_type;
519 typedef _Distance difference_type;
520 typedef _Pointer pointer;
521 typedef _Reference reference;
522 typedef _Category iterator_category;
525 template <class _InputIter>
526 inline _LIBCPP_INLINE_VISIBILITY
527 void __advance(_InputIter& __i,
528 typename iterator_traits<_InputIter>::difference_type __n, input_iterator_tag)
530 for (; __n > 0; --__n)
534 template <class _BiDirIter>
535 inline _LIBCPP_INLINE_VISIBILITY
536 void __advance(_BiDirIter& __i,
537 typename iterator_traits<_BiDirIter>::difference_type __n, bidirectional_iterator_tag)
540 for (; __n > 0; --__n)
543 for (; __n < 0; ++__n)
547 template <class _RandIter>
548 inline _LIBCPP_INLINE_VISIBILITY
549 void __advance(_RandIter& __i,
550 typename iterator_traits<_RandIter>::difference_type __n, random_access_iterator_tag)
555 template <class _InputIter>
556 inline _LIBCPP_INLINE_VISIBILITY
557 void advance(_InputIter& __i,
558 typename iterator_traits<_InputIter>::difference_type __n)
560 __advance(__i, __n, typename iterator_traits<_InputIter>::iterator_category());
563 template <class _InputIter>
564 inline _LIBCPP_INLINE_VISIBILITY
565 typename iterator_traits<_InputIter>::difference_type
566 __distance(_InputIter __first, _InputIter __last, input_iterator_tag)
568 typename iterator_traits<_InputIter>::difference_type __r(0);
569 for (; __first != __last; ++__first)
574 template <class _RandIter>
575 inline _LIBCPP_INLINE_VISIBILITY
576 typename iterator_traits<_RandIter>::difference_type
577 __distance(_RandIter __first, _RandIter __last, random_access_iterator_tag)
579 return __last - __first;
582 template <class _InputIter>
583 inline _LIBCPP_INLINE_VISIBILITY
584 typename iterator_traits<_InputIter>::difference_type
585 distance(_InputIter __first, _InputIter __last)
587 return __distance(__first, __last, typename iterator_traits<_InputIter>::iterator_category());
590 template <class _InputIter>
591 inline _LIBCPP_INLINE_VISIBILITY
594 typename iterator_traits<_InputIter>::difference_type __n = 1,
595 typename enable_if<__is_input_iterator<_InputIter>::value>::type* = 0)
597 _VSTD::advance(__x, __n);
601 template <class _BidiretionalIter>
602 inline _LIBCPP_INLINE_VISIBILITY
604 prev(_BidiretionalIter __x,
605 typename iterator_traits<_BidiretionalIter>::difference_type __n = 1,
606 typename enable_if<__is_bidirectional_iterator<_BidiretionalIter>::value>::type* = 0)
608 _VSTD::advance(__x, -__n);
612 template <class _Iter>
613 class _LIBCPP_TYPE_VIS_ONLY reverse_iterator
614 : public iterator<typename iterator_traits<_Iter>::iterator_category,
615 typename iterator_traits<_Iter>::value_type,
616 typename iterator_traits<_Iter>::difference_type,
617 typename iterator_traits<_Iter>::pointer,
618 typename iterator_traits<_Iter>::reference>
621 mutable _Iter __t; // no longer used as of LWG #2360, not removed due to ABI break
625 typedef _Iter iterator_type;
626 typedef typename iterator_traits<_Iter>::difference_type difference_type;
627 typedef typename iterator_traits<_Iter>::reference reference;
628 typedef typename iterator_traits<_Iter>::pointer pointer;
630 _LIBCPP_INLINE_VISIBILITY reverse_iterator() : current() {}
631 _LIBCPP_INLINE_VISIBILITY explicit reverse_iterator(_Iter __x) : __t(__x), current(__x) {}
632 template <class _Up> _LIBCPP_INLINE_VISIBILITY reverse_iterator(const reverse_iterator<_Up>& __u)
633 : __t(__u.base()), current(__u.base()) {}
634 _LIBCPP_INLINE_VISIBILITY _Iter base() const {return current;}
635 _LIBCPP_INLINE_VISIBILITY reference operator*() const {_Iter __tmp = current; return *--__tmp;}
636 _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return _VSTD::addressof(operator*());}
637 _LIBCPP_INLINE_VISIBILITY reverse_iterator& operator++() {--current; return *this;}
638 _LIBCPP_INLINE_VISIBILITY reverse_iterator operator++(int)
639 {reverse_iterator __tmp(*this); --current; return __tmp;}
640 _LIBCPP_INLINE_VISIBILITY reverse_iterator& operator--() {++current; return *this;}
641 _LIBCPP_INLINE_VISIBILITY reverse_iterator operator--(int)
642 {reverse_iterator __tmp(*this); ++current; return __tmp;}
643 _LIBCPP_INLINE_VISIBILITY reverse_iterator operator+ (difference_type __n) const
644 {return reverse_iterator(current - __n);}
645 _LIBCPP_INLINE_VISIBILITY reverse_iterator& operator+=(difference_type __n)
646 {current -= __n; return *this;}
647 _LIBCPP_INLINE_VISIBILITY reverse_iterator operator- (difference_type __n) const
648 {return reverse_iterator(current + __n);}
649 _LIBCPP_INLINE_VISIBILITY reverse_iterator& operator-=(difference_type __n)
650 {current += __n; return *this;}
651 _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const
652 {return *(*this + __n);}
655 template <class _Iter1, class _Iter2>
656 inline _LIBCPP_INLINE_VISIBILITY
658 operator==(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
660 return __x.base() == __y.base();
663 template <class _Iter1, class _Iter2>
664 inline _LIBCPP_INLINE_VISIBILITY
666 operator<(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
668 return __x.base() > __y.base();
671 template <class _Iter1, class _Iter2>
672 inline _LIBCPP_INLINE_VISIBILITY
674 operator!=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
676 return __x.base() != __y.base();
679 template <class _Iter1, class _Iter2>
680 inline _LIBCPP_INLINE_VISIBILITY
682 operator>(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
684 return __x.base() < __y.base();
687 template <class _Iter1, class _Iter2>
688 inline _LIBCPP_INLINE_VISIBILITY
690 operator>=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
692 return __x.base() <= __y.base();
695 template <class _Iter1, class _Iter2>
696 inline _LIBCPP_INLINE_VISIBILITY
698 operator<=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
700 return __x.base() >= __y.base();
703 #ifndef _LIBCPP_CXX03_LANG
704 template <class _Iter1, class _Iter2>
705 inline _LIBCPP_INLINE_VISIBILITY
707 operator-(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
708 -> decltype(__y.base() - __x.base())
710 return __y.base() - __x.base();
713 template <class _Iter1, class _Iter2>
714 inline _LIBCPP_INLINE_VISIBILITY
715 typename reverse_iterator<_Iter1>::difference_type
716 operator-(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
718 return __y.base() - __x.base();
722 template <class _Iter>
723 inline _LIBCPP_INLINE_VISIBILITY
724 reverse_iterator<_Iter>
725 operator+(typename reverse_iterator<_Iter>::difference_type __n, const reverse_iterator<_Iter>& __x)
727 return reverse_iterator<_Iter>(__x.base() - __n);
730 #if _LIBCPP_STD_VER > 11
731 template <class _Iter>
732 inline _LIBCPP_INLINE_VISIBILITY
733 reverse_iterator<_Iter> make_reverse_iterator(_Iter __i)
735 return reverse_iterator<_Iter>(__i);
739 template <class _Container>
740 class _LIBCPP_TYPE_VIS_ONLY back_insert_iterator
741 : public iterator<output_iterator_tag,
748 _Container* container;
750 typedef _Container container_type;
752 _LIBCPP_INLINE_VISIBILITY explicit back_insert_iterator(_Container& __x) : container(_VSTD::addressof(__x)) {}
753 _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator=(const typename _Container::value_type& __value_)
754 {container->push_back(__value_); return *this;}
755 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
756 _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator=(typename _Container::value_type&& __value_)
757 {container->push_back(_VSTD::move(__value_)); return *this;}
758 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
759 _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator*() {return *this;}
760 _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator++() {return *this;}
761 _LIBCPP_INLINE_VISIBILITY back_insert_iterator operator++(int) {return *this;}
764 template <class _Container>
765 inline _LIBCPP_INLINE_VISIBILITY
766 back_insert_iterator<_Container>
767 back_inserter(_Container& __x)
769 return back_insert_iterator<_Container>(__x);
772 template <class _Container>
773 class _LIBCPP_TYPE_VIS_ONLY front_insert_iterator
774 : public iterator<output_iterator_tag,
781 _Container* container;
783 typedef _Container container_type;
785 _LIBCPP_INLINE_VISIBILITY explicit front_insert_iterator(_Container& __x) : container(_VSTD::addressof(__x)) {}
786 _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator=(const typename _Container::value_type& __value_)
787 {container->push_front(__value_); return *this;}
788 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
789 _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator=(typename _Container::value_type&& __value_)
790 {container->push_front(_VSTD::move(__value_)); return *this;}
791 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
792 _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator*() {return *this;}
793 _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator++() {return *this;}
794 _LIBCPP_INLINE_VISIBILITY front_insert_iterator operator++(int) {return *this;}
797 template <class _Container>
798 inline _LIBCPP_INLINE_VISIBILITY
799 front_insert_iterator<_Container>
800 front_inserter(_Container& __x)
802 return front_insert_iterator<_Container>(__x);
805 template <class _Container>
806 class _LIBCPP_TYPE_VIS_ONLY insert_iterator
807 : public iterator<output_iterator_tag,
814 _Container* container;
815 typename _Container::iterator iter;
817 typedef _Container container_type;
819 _LIBCPP_INLINE_VISIBILITY insert_iterator(_Container& __x, typename _Container::iterator __i)
820 : container(_VSTD::addressof(__x)), iter(__i) {}
821 _LIBCPP_INLINE_VISIBILITY insert_iterator& operator=(const typename _Container::value_type& __value_)
822 {iter = container->insert(iter, __value_); ++iter; return *this;}
823 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
824 _LIBCPP_INLINE_VISIBILITY insert_iterator& operator=(typename _Container::value_type&& __value_)
825 {iter = container->insert(iter, _VSTD::move(__value_)); ++iter; return *this;}
826 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
827 _LIBCPP_INLINE_VISIBILITY insert_iterator& operator*() {return *this;}
828 _LIBCPP_INLINE_VISIBILITY insert_iterator& operator++() {return *this;}
829 _LIBCPP_INLINE_VISIBILITY insert_iterator& operator++(int) {return *this;}
832 template <class _Container>
833 inline _LIBCPP_INLINE_VISIBILITY
834 insert_iterator<_Container>
835 inserter(_Container& __x, typename _Container::iterator __i)
837 return insert_iterator<_Container>(__x, __i);
840 template <class _Tp, class _CharT = char,
841 class _Traits = char_traits<_CharT>, class _Distance = ptrdiff_t>
842 class _LIBCPP_TYPE_VIS_ONLY istream_iterator
843 : public iterator<input_iterator_tag, _Tp, _Distance, const _Tp*, const _Tp&>
846 typedef _CharT char_type;
847 typedef _Traits traits_type;
848 typedef basic_istream<_CharT,_Traits> istream_type;
850 istream_type* __in_stream_;
853 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR istream_iterator() : __in_stream_(0), __value_() {}
854 _LIBCPP_INLINE_VISIBILITY istream_iterator(istream_type& __s) : __in_stream_(_VSTD::addressof(__s))
856 if (!(*__in_stream_ >> __value_))
860 _LIBCPP_INLINE_VISIBILITY const _Tp& operator*() const {return __value_;}
861 _LIBCPP_INLINE_VISIBILITY const _Tp* operator->() const {return _VSTD::addressof((operator*()));}
862 _LIBCPP_INLINE_VISIBILITY istream_iterator& operator++()
864 if (!(*__in_stream_ >> __value_))
868 _LIBCPP_INLINE_VISIBILITY istream_iterator operator++(int)
869 {istream_iterator __t(*this); ++(*this); return __t;}
871 friend _LIBCPP_INLINE_VISIBILITY
872 bool operator==(const istream_iterator& __x, const istream_iterator& __y)
873 {return __x.__in_stream_ == __y.__in_stream_;}
875 friend _LIBCPP_INLINE_VISIBILITY
876 bool operator!=(const istream_iterator& __x, const istream_iterator& __y)
877 {return !(__x == __y);}
880 template <class _Tp, class _CharT = char, class _Traits = char_traits<_CharT> >
881 class _LIBCPP_TYPE_VIS_ONLY ostream_iterator
882 : public iterator<output_iterator_tag, void, void, void, void>
885 typedef _CharT char_type;
886 typedef _Traits traits_type;
887 typedef basic_ostream<_CharT,_Traits> ostream_type;
889 ostream_type* __out_stream_;
890 const char_type* __delim_;
892 _LIBCPP_INLINE_VISIBILITY ostream_iterator(ostream_type& __s)
893 : __out_stream_(_VSTD::addressof(__s)), __delim_(0) {}
894 _LIBCPP_INLINE_VISIBILITY ostream_iterator(ostream_type& __s, const _CharT* __delimiter)
895 : __out_stream_(_VSTD::addressof(__s)), __delim_(__delimiter) {}
896 _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator=(const _Tp& __value_)
898 *__out_stream_ << __value_;
900 *__out_stream_ << __delim_;
904 _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator*() {return *this;}
905 _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator++() {return *this;}
906 _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator++(int) {return *this;}
909 template<class _CharT, class _Traits>
910 class _LIBCPP_TYPE_VIS_ONLY istreambuf_iterator
911 : public iterator<input_iterator_tag, _CharT,
912 typename _Traits::off_type, _CharT*,
916 typedef _CharT char_type;
917 typedef _Traits traits_type;
918 typedef typename _Traits::int_type int_type;
919 typedef basic_streambuf<_CharT,_Traits> streambuf_type;
920 typedef basic_istream<_CharT,_Traits> istream_type;
922 mutable streambuf_type* __sbuf_;
927 streambuf_type* __sbuf_;
928 _LIBCPP_INLINE_VISIBILITY __proxy(char_type __c, streambuf_type* __s)
929 : __keep_(__c), __sbuf_(__s) {}
930 friend class istreambuf_iterator;
932 _LIBCPP_INLINE_VISIBILITY char_type operator*() const {return __keep_;}
935 _LIBCPP_INLINE_VISIBILITY
936 bool __test_for_eof() const
938 if (__sbuf_ && traits_type::eq_int_type(__sbuf_->sgetc(), traits_type::eof()))
943 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR istreambuf_iterator() _NOEXCEPT : __sbuf_(0) {}
944 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(istream_type& __s) _NOEXCEPT
945 : __sbuf_(__s.rdbuf()) {}
946 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(streambuf_type* __s) _NOEXCEPT
948 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(const __proxy& __p) _NOEXCEPT
949 : __sbuf_(__p.__sbuf_) {}
951 _LIBCPP_INLINE_VISIBILITY char_type operator*() const
952 {return static_cast<char_type>(__sbuf_->sgetc());}
953 _LIBCPP_INLINE_VISIBILITY char_type* operator->() const {return nullptr;}
954 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator& operator++()
959 _LIBCPP_INLINE_VISIBILITY __proxy operator++(int)
961 return __proxy(__sbuf_->sbumpc(), __sbuf_);
964 _LIBCPP_INLINE_VISIBILITY bool equal(const istreambuf_iterator& __b) const
965 {return __test_for_eof() == __b.__test_for_eof();}
968 template <class _CharT, class _Traits>
969 inline _LIBCPP_INLINE_VISIBILITY
970 bool operator==(const istreambuf_iterator<_CharT,_Traits>& __a,
971 const istreambuf_iterator<_CharT,_Traits>& __b)
972 {return __a.equal(__b);}
974 template <class _CharT, class _Traits>
975 inline _LIBCPP_INLINE_VISIBILITY
976 bool operator!=(const istreambuf_iterator<_CharT,_Traits>& __a,
977 const istreambuf_iterator<_CharT,_Traits>& __b)
978 {return !__a.equal(__b);}
980 template <class _CharT, class _Traits>
981 class _LIBCPP_TYPE_VIS_ONLY ostreambuf_iterator
982 : public iterator<output_iterator_tag, void, void, void, void>
985 typedef _CharT char_type;
986 typedef _Traits traits_type;
987 typedef basic_streambuf<_CharT,_Traits> streambuf_type;
988 typedef basic_ostream<_CharT,_Traits> ostream_type;
990 streambuf_type* __sbuf_;
992 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator(ostream_type& __s) _NOEXCEPT
993 : __sbuf_(__s.rdbuf()) {}
994 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator(streambuf_type* __s) _NOEXCEPT
996 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator=(_CharT __c)
998 if (__sbuf_ && traits_type::eq_int_type(__sbuf_->sputc(__c), traits_type::eof()))
1002 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator*() {return *this;}
1003 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator++() {return *this;}
1004 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator++(int) {return *this;}
1005 _LIBCPP_INLINE_VISIBILITY bool failed() const _NOEXCEPT {return __sbuf_ == 0;}
1007 #if !defined(__APPLE__) || \
1008 (defined(__MAC_OS_X_VERSION_MIN_REQUIRED) && __MAC_OS_X_VERSION_MIN_REQUIRED > __MAC_10_8) || \
1009 (defined(__IPHONE_OS_VERSION_MIN_REQUIRED) && __IPHONE_OS_VERSION_MIN_REQUIRED > __IPHONE_6_0)
1011 template <class _Ch, class _Tr>
1014 ostreambuf_iterator<_Ch, _Tr>
1015 __pad_and_output(ostreambuf_iterator<_Ch, _Tr> __s,
1016 const _Ch* __ob, const _Ch* __op, const _Ch* __oe,
1017 ios_base& __iob, _Ch __fl);
1021 template <class _Iter>
1022 class _LIBCPP_TYPE_VIS_ONLY move_iterator
1027 typedef _Iter iterator_type;
1028 typedef typename iterator_traits<iterator_type>::iterator_category iterator_category;
1029 typedef typename iterator_traits<iterator_type>::value_type value_type;
1030 typedef typename iterator_traits<iterator_type>::difference_type difference_type;
1031 typedef iterator_type pointer;
1032 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1033 typedef typename iterator_traits<iterator_type>::reference __reference;
1034 typedef typename conditional<
1035 is_reference<__reference>::value,
1036 typename remove_reference<__reference>::type&&,
1040 typedef typename iterator_traits<iterator_type>::reference reference;
1043 _LIBCPP_INLINE_VISIBILITY move_iterator() : __i() {}
1044 _LIBCPP_INLINE_VISIBILITY explicit move_iterator(_Iter __x) : __i(__x) {}
1045 template <class _Up> _LIBCPP_INLINE_VISIBILITY move_iterator(const move_iterator<_Up>& __u)
1046 : __i(__u.base()) {}
1047 _LIBCPP_INLINE_VISIBILITY _Iter base() const {return __i;}
1048 _LIBCPP_INLINE_VISIBILITY reference operator*() const {
1049 return static_cast<reference>(*__i);
1051 _LIBCPP_INLINE_VISIBILITY pointer operator->() const { return __i;}
1052 _LIBCPP_INLINE_VISIBILITY move_iterator& operator++() {++__i; return *this;}
1053 _LIBCPP_INLINE_VISIBILITY move_iterator operator++(int)
1054 {move_iterator __tmp(*this); ++__i; return __tmp;}
1055 _LIBCPP_INLINE_VISIBILITY move_iterator& operator--() {--__i; return *this;}
1056 _LIBCPP_INLINE_VISIBILITY move_iterator operator--(int)
1057 {move_iterator __tmp(*this); --__i; return __tmp;}
1058 _LIBCPP_INLINE_VISIBILITY move_iterator operator+ (difference_type __n) const
1059 {return move_iterator(__i + __n);}
1060 _LIBCPP_INLINE_VISIBILITY move_iterator& operator+=(difference_type __n)
1061 {__i += __n; return *this;}
1062 _LIBCPP_INLINE_VISIBILITY move_iterator operator- (difference_type __n) const
1063 {return move_iterator(__i - __n);}
1064 _LIBCPP_INLINE_VISIBILITY move_iterator& operator-=(difference_type __n)
1065 {__i -= __n; return *this;}
1066 _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const
1068 return static_cast<reference>(__i[__n]);
1072 template <class _Iter1, class _Iter2>
1073 inline _LIBCPP_INLINE_VISIBILITY
1075 operator==(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1077 return __x.base() == __y.base();
1080 template <class _Iter1, class _Iter2>
1081 inline _LIBCPP_INLINE_VISIBILITY
1083 operator<(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1085 return __x.base() < __y.base();
1088 template <class _Iter1, class _Iter2>
1089 inline _LIBCPP_INLINE_VISIBILITY
1091 operator!=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1093 return __x.base() != __y.base();
1096 template <class _Iter1, class _Iter2>
1097 inline _LIBCPP_INLINE_VISIBILITY
1099 operator>(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1101 return __x.base() > __y.base();
1104 template <class _Iter1, class _Iter2>
1105 inline _LIBCPP_INLINE_VISIBILITY
1107 operator>=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1109 return __x.base() >= __y.base();
1112 template <class _Iter1, class _Iter2>
1113 inline _LIBCPP_INLINE_VISIBILITY
1115 operator<=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1117 return __x.base() <= __y.base();
1120 #ifndef _LIBCPP_CXX03_LANG
1121 template <class _Iter1, class _Iter2>
1122 inline _LIBCPP_INLINE_VISIBILITY
1124 operator-(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1125 -> decltype(__x.base() - __y.base())
1127 return __x.base() - __y.base();
1130 template <class _Iter1, class _Iter2>
1131 inline _LIBCPP_INLINE_VISIBILITY
1132 typename move_iterator<_Iter1>::difference_type
1133 operator-(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1135 return __x.base() - __y.base();
1139 template <class _Iter>
1140 inline _LIBCPP_INLINE_VISIBILITY
1141 move_iterator<_Iter>
1142 operator+(typename move_iterator<_Iter>::difference_type __n, const move_iterator<_Iter>& __x)
1144 return move_iterator<_Iter>(__x.base() + __n);
1147 template <class _Iter>
1148 inline _LIBCPP_INLINE_VISIBILITY
1149 move_iterator<_Iter>
1150 make_move_iterator(_Iter __i)
1152 return move_iterator<_Iter>(__i);
1157 template <class _Iter> class __wrap_iter;
1159 template <class _Iter1, class _Iter2>
1160 _LIBCPP_INLINE_VISIBILITY
1162 operator==(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1164 template <class _Iter1, class _Iter2>
1165 _LIBCPP_INLINE_VISIBILITY
1167 operator<(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1169 template <class _Iter1, class _Iter2>
1170 _LIBCPP_INLINE_VISIBILITY
1172 operator!=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1174 template <class _Iter1, class _Iter2>
1175 _LIBCPP_INLINE_VISIBILITY
1177 operator>(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1179 template <class _Iter1, class _Iter2>
1180 _LIBCPP_INLINE_VISIBILITY
1182 operator>=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1184 template <class _Iter1, class _Iter2>
1185 _LIBCPP_INLINE_VISIBILITY
1187 operator<=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1189 #ifndef _LIBCPP_CXX03_LANG
1190 template <class _Iter1, class _Iter2>
1191 _LIBCPP_INLINE_VISIBILITY
1193 operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1194 -> decltype(__x.base() - __y.base());
1196 template <class _Iter1, class _Iter2>
1197 _LIBCPP_INLINE_VISIBILITY
1198 typename __wrap_iter<_Iter1>::difference_type
1199 operator-(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1202 template <class _Iter>
1203 _LIBCPP_INLINE_VISIBILITY
1205 operator+(typename __wrap_iter<_Iter>::difference_type, __wrap_iter<_Iter>) _NOEXCEPT;
1207 template <class _Ip, class _Op> _Op _LIBCPP_INLINE_VISIBILITY copy(_Ip, _Ip, _Op);
1208 template <class _B1, class _B2> _B2 _LIBCPP_INLINE_VISIBILITY copy_backward(_B1, _B1, _B2);
1209 template <class _Ip, class _Op> _Op _LIBCPP_INLINE_VISIBILITY move(_Ip, _Ip, _Op);
1210 template <class _B1, class _B2> _B2 _LIBCPP_INLINE_VISIBILITY move_backward(_B1, _B1, _B2);
1212 template <class _Tp>
1213 _LIBCPP_INLINE_VISIBILITY
1216 is_trivially_copy_assignable<_Tp>::value,
1219 __unwrap_iter(__wrap_iter<_Tp*>);
1221 template <class _Iter>
1225 typedef _Iter iterator_type;
1226 typedef typename iterator_traits<iterator_type>::iterator_category iterator_category;
1227 typedef typename iterator_traits<iterator_type>::value_type value_type;
1228 typedef typename iterator_traits<iterator_type>::difference_type difference_type;
1229 typedef typename iterator_traits<iterator_type>::pointer pointer;
1230 typedef typename iterator_traits<iterator_type>::reference reference;
1234 _LIBCPP_INLINE_VISIBILITY __wrap_iter() _NOEXCEPT
1235 #if _LIBCPP_STD_VER > 11
1239 #if _LIBCPP_DEBUG_LEVEL >= 2
1240 __get_db()->__insert_i(this);
1243 template <class _Up> _LIBCPP_INLINE_VISIBILITY __wrap_iter(const __wrap_iter<_Up>& __u,
1244 typename enable_if<is_convertible<_Up, iterator_type>::value>::type* = 0) _NOEXCEPT
1247 #if _LIBCPP_DEBUG_LEVEL >= 2
1248 __get_db()->__iterator_copy(this, &__u);
1251 #if _LIBCPP_DEBUG_LEVEL >= 2
1252 _LIBCPP_INLINE_VISIBILITY
1253 __wrap_iter(const __wrap_iter& __x)
1256 __get_db()->__iterator_copy(this, &__x);
1258 _LIBCPP_INLINE_VISIBILITY
1259 __wrap_iter& operator=(const __wrap_iter& __x)
1263 __get_db()->__iterator_copy(this, &__x);
1268 _LIBCPP_INLINE_VISIBILITY
1271 __get_db()->__erase_i(this);
1274 _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT
1276 #if _LIBCPP_DEBUG_LEVEL >= 2
1277 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
1278 "Attempted to dereference a non-dereferenceable iterator");
1282 _LIBCPP_INLINE_VISIBILITY pointer operator->() const _NOEXCEPT
1284 #if _LIBCPP_DEBUG_LEVEL >= 2
1285 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
1286 "Attempted to dereference a non-dereferenceable iterator");
1288 return (pointer)_VSTD::addressof(*__i);
1290 _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator++() _NOEXCEPT
1292 #if _LIBCPP_DEBUG_LEVEL >= 2
1293 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
1294 "Attempted to increment non-incrementable iterator");
1299 _LIBCPP_INLINE_VISIBILITY __wrap_iter operator++(int) _NOEXCEPT
1300 {__wrap_iter __tmp(*this); ++(*this); return __tmp;}
1301 _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator--() _NOEXCEPT
1303 #if _LIBCPP_DEBUG_LEVEL >= 2
1304 _LIBCPP_ASSERT(__get_const_db()->__decrementable(this),
1305 "Attempted to decrement non-decrementable iterator");
1310 _LIBCPP_INLINE_VISIBILITY __wrap_iter operator--(int) _NOEXCEPT
1311 {__wrap_iter __tmp(*this); --(*this); return __tmp;}
1312 _LIBCPP_INLINE_VISIBILITY __wrap_iter operator+ (difference_type __n) const _NOEXCEPT
1313 {__wrap_iter __w(*this); __w += __n; return __w;}
1314 _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator+=(difference_type __n) _NOEXCEPT
1316 #if _LIBCPP_DEBUG_LEVEL >= 2
1317 _LIBCPP_ASSERT(__get_const_db()->__addable(this, __n),
1318 "Attempted to add/subtract iterator outside of valid range");
1323 _LIBCPP_INLINE_VISIBILITY __wrap_iter operator- (difference_type __n) const _NOEXCEPT
1324 {return *this + (-__n);}
1325 _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator-=(difference_type __n) _NOEXCEPT
1326 {*this += -__n; return *this;}
1327 _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const _NOEXCEPT
1329 #if _LIBCPP_DEBUG_LEVEL >= 2
1330 _LIBCPP_ASSERT(__get_const_db()->__subscriptable(this, __n),
1331 "Attempted to subscript iterator outside of valid range");
1336 _LIBCPP_INLINE_VISIBILITY iterator_type base() const _NOEXCEPT {return __i;}
1339 #if _LIBCPP_DEBUG_LEVEL >= 2
1340 _LIBCPP_INLINE_VISIBILITY __wrap_iter(const void* __p, iterator_type __x) : __i(__x)
1342 __get_db()->__insert_ic(this, __p);
1345 _LIBCPP_INLINE_VISIBILITY __wrap_iter(iterator_type __x) _NOEXCEPT : __i(__x) {}
1348 template <class _Up> friend class __wrap_iter;
1349 template <class _CharT, class _Traits, class _Alloc> friend class basic_string;
1350 template <class _Tp, class _Alloc> friend class _LIBCPP_TYPE_VIS_ONLY vector;
1352 template <class _Iter1, class _Iter2>
1355 operator==(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1357 template <class _Iter1, class _Iter2>
1360 operator<(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1362 template <class _Iter1, class _Iter2>
1365 operator!=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1367 template <class _Iter1, class _Iter2>
1370 operator>(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1372 template <class _Iter1, class _Iter2>
1375 operator>=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1377 template <class _Iter1, class _Iter2>
1380 operator<=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1382 #ifndef _LIBCPP_CXX03_LANG
1383 template <class _Iter1, class _Iter2>
1386 operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1387 -> decltype(__x.base() - __y.base());
1389 template <class _Iter1, class _Iter2>
1391 typename __wrap_iter<_Iter1>::difference_type
1392 operator-(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1395 template <class _Iter1>
1398 operator+(typename __wrap_iter<_Iter1>::difference_type, __wrap_iter<_Iter1>) _NOEXCEPT;
1400 template <class _Ip, class _Op> friend _Op copy(_Ip, _Ip, _Op);
1401 template <class _B1, class _B2> friend _B2 copy_backward(_B1, _B1, _B2);
1402 template <class _Ip, class _Op> friend _Op move(_Ip, _Ip, _Op);
1403 template <class _B1, class _B2> friend _B2 move_backward(_B1, _B1, _B2);
1405 template <class _Tp>
1409 is_trivially_copy_assignable<_Tp>::value,
1412 __unwrap_iter(__wrap_iter<_Tp*>);
1415 template <class _Iter1, class _Iter2>
1416 inline _LIBCPP_INLINE_VISIBILITY
1418 operator==(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1420 return __x.base() == __y.base();
1423 template <class _Iter1, class _Iter2>
1424 inline _LIBCPP_INLINE_VISIBILITY
1426 operator<(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1428 #if _LIBCPP_DEBUG_LEVEL >= 2
1429 _LIBCPP_ASSERT(__get_const_db()->__less_than_comparable(&__x, &__y),
1430 "Attempted to compare incomparable iterators");
1432 return __x.base() < __y.base();
1435 template <class _Iter1, class _Iter2>
1436 inline _LIBCPP_INLINE_VISIBILITY
1438 operator!=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1440 return !(__x == __y);
1443 template <class _Iter1, class _Iter2>
1444 inline _LIBCPP_INLINE_VISIBILITY
1446 operator>(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1451 template <class _Iter1, class _Iter2>
1452 inline _LIBCPP_INLINE_VISIBILITY
1454 operator>=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1456 return !(__x < __y);
1459 template <class _Iter1, class _Iter2>
1460 inline _LIBCPP_INLINE_VISIBILITY
1462 operator<=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1464 return !(__y < __x);
1467 template <class _Iter1>
1468 inline _LIBCPP_INLINE_VISIBILITY
1470 operator!=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT
1472 return !(__x == __y);
1475 template <class _Iter1>
1476 inline _LIBCPP_INLINE_VISIBILITY
1478 operator>(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT
1483 template <class _Iter1>
1484 inline _LIBCPP_INLINE_VISIBILITY
1486 operator>=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT
1488 return !(__x < __y);
1491 template <class _Iter1>
1492 inline _LIBCPP_INLINE_VISIBILITY
1494 operator<=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT
1496 return !(__y < __x);
1499 #ifndef _LIBCPP_CXX03_LANG
1500 template <class _Iter1, class _Iter2>
1501 inline _LIBCPP_INLINE_VISIBILITY
1503 operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1504 -> decltype(__x.base() - __y.base())
1506 #if _LIBCPP_DEBUG_LEVEL >= 2
1507 _LIBCPP_ASSERT(__get_const_db()->__less_than_comparable(&__x, &__y),
1508 "Attempted to subtract incompatible iterators");
1510 return __x.base() - __y.base();
1513 template <class _Iter1, class _Iter2>
1514 inline _LIBCPP_INLINE_VISIBILITY
1515 typename __wrap_iter<_Iter1>::difference_type
1516 operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1518 #if _LIBCPP_DEBUG_LEVEL >= 2
1519 _LIBCPP_ASSERT(__get_const_db()->__less_than_comparable(&__x, &__y),
1520 "Attempted to subtract incompatible iterators");
1522 return __x.base() - __y.base();
1526 template <class _Iter>
1527 inline _LIBCPP_INLINE_VISIBILITY
1529 operator+(typename __wrap_iter<_Iter>::difference_type __n,
1530 __wrap_iter<_Iter> __x) _NOEXCEPT
1536 template <class _Iter>
1537 struct __libcpp_is_trivial_iterator
1538 : public _LIBCPP_BOOL_CONSTANT(is_pointer<_Iter>::value) {};
1540 template <class _Iter>
1541 struct __libcpp_is_trivial_iterator<move_iterator<_Iter> >
1542 : public _LIBCPP_BOOL_CONSTANT(__libcpp_is_trivial_iterator<_Iter>::value) {};
1544 template <class _Iter>
1545 struct __libcpp_is_trivial_iterator<reverse_iterator<_Iter> >
1546 : public _LIBCPP_BOOL_CONSTANT(__libcpp_is_trivial_iterator<_Iter>::value) {};
1548 template <class _Iter>
1549 struct __libcpp_is_trivial_iterator<__wrap_iter<_Iter> >
1550 : public _LIBCPP_BOOL_CONSTANT(__libcpp_is_trivial_iterator<_Iter>::value) {};
1553 template <class _Tp, size_t _Np>
1554 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
1556 begin(_Tp (&__array)[_Np])
1561 template <class _Tp, size_t _Np>
1562 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
1564 end(_Tp (&__array)[_Np])
1566 return __array + _Np;
1569 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_TRAILING_RETURN)
1571 template <class _Cp>
1572 inline _LIBCPP_INLINE_VISIBILITY
1574 begin(_Cp& __c) -> decltype(__c.begin())
1579 template <class _Cp>
1580 inline _LIBCPP_INLINE_VISIBILITY
1582 begin(const _Cp& __c) -> decltype(__c.begin())
1587 template <class _Cp>
1588 inline _LIBCPP_INLINE_VISIBILITY
1590 end(_Cp& __c) -> decltype(__c.end())
1595 template <class _Cp>
1596 inline _LIBCPP_INLINE_VISIBILITY
1598 end(const _Cp& __c) -> decltype(__c.end())
1603 #if _LIBCPP_STD_VER > 11
1605 template <class _Tp, size_t _Np>
1606 inline _LIBCPP_INLINE_VISIBILITY
1607 reverse_iterator<_Tp*> rbegin(_Tp (&__array)[_Np])
1609 return reverse_iterator<_Tp*>(__array + _Np);
1612 template <class _Tp, size_t _Np>
1613 inline _LIBCPP_INLINE_VISIBILITY
1614 reverse_iterator<_Tp*> rend(_Tp (&__array)[_Np])
1616 return reverse_iterator<_Tp*>(__array);
1619 template <class _Ep>
1620 inline _LIBCPP_INLINE_VISIBILITY
1621 reverse_iterator<const _Ep*> rbegin(initializer_list<_Ep> __il)
1623 return reverse_iterator<const _Ep*>(__il.end());
1626 template <class _Ep>
1627 inline _LIBCPP_INLINE_VISIBILITY
1628 reverse_iterator<const _Ep*> rend(initializer_list<_Ep> __il)
1630 return reverse_iterator<const _Ep*>(__il.begin());
1633 template <class _Cp>
1634 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
1635 auto cbegin(const _Cp& __c) -> decltype(_VSTD::begin(__c))
1637 return _VSTD::begin(__c);
1640 template <class _Cp>
1641 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
1642 auto cend(const _Cp& __c) -> decltype(_VSTD::end(__c))
1644 return _VSTD::end(__c);
1647 template <class _Cp>
1648 inline _LIBCPP_INLINE_VISIBILITY
1649 auto rbegin(_Cp& __c) -> decltype(__c.rbegin())
1651 return __c.rbegin();
1654 template <class _Cp>
1655 inline _LIBCPP_INLINE_VISIBILITY
1656 auto rbegin(const _Cp& __c) -> decltype(__c.rbegin())
1658 return __c.rbegin();
1661 template <class _Cp>
1662 inline _LIBCPP_INLINE_VISIBILITY
1663 auto rend(_Cp& __c) -> decltype(__c.rend())
1668 template <class _Cp>
1669 inline _LIBCPP_INLINE_VISIBILITY
1670 auto rend(const _Cp& __c) -> decltype(__c.rend())
1675 template <class _Cp>
1676 inline _LIBCPP_INLINE_VISIBILITY
1677 auto crbegin(const _Cp& __c) -> decltype(_VSTD::rbegin(__c))
1679 return _VSTD::rbegin(__c);
1682 template <class _Cp>
1683 inline _LIBCPP_INLINE_VISIBILITY
1684 auto crend(const _Cp& __c) -> decltype(_VSTD::rend(__c))
1686 return _VSTD::rend(__c);
1692 #else // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_TRAILING_RETURN)
1694 template <class _Cp>
1695 inline _LIBCPP_INLINE_VISIBILITY
1696 typename _Cp::iterator
1702 template <class _Cp>
1703 inline _LIBCPP_INLINE_VISIBILITY
1704 typename _Cp::const_iterator
1705 begin(const _Cp& __c)
1710 template <class _Cp>
1711 inline _LIBCPP_INLINE_VISIBILITY
1712 typename _Cp::iterator
1718 template <class _Cp>
1719 inline _LIBCPP_INLINE_VISIBILITY
1720 typename _Cp::const_iterator
1726 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_TRAILING_RETURN)
1728 #if _LIBCPP_STD_VER > 14
1729 template <class _Cont>
1730 constexpr auto size(const _Cont& __c) -> decltype(__c.size()) { return __c.size(); }
1732 template <class _Tp, size_t _Sz>
1733 constexpr size_t size(const _Tp (&__array)[_Sz]) noexcept { return _Sz; }
1735 template <class _Cont>
1736 constexpr auto empty(const _Cont& __c) -> decltype(__c.empty()) { return __c.empty(); }
1738 template <class _Tp, size_t _Sz>
1739 constexpr bool empty(const _Tp (&__array)[_Sz]) noexcept { return false; }
1741 template <class _Ep>
1742 constexpr bool empty(initializer_list<_Ep> __il) noexcept { return __il.size() == 0; }
1744 template <class _Cont> constexpr
1745 auto data(_Cont& __c) -> decltype(__c.data()) { return __c.data(); }
1747 template <class _Cont> constexpr
1748 auto data(const _Cont& __c) -> decltype(__c.data()) { return __c.data(); }
1750 template <class _Tp, size_t _Sz>
1751 constexpr _Tp* data(_Tp (&__array)[_Sz]) noexcept { return __array; }
1753 template <class _Ep>
1754 constexpr const _Ep* data(initializer_list<_Ep> __il) noexcept { return __il.begin(); }
1758 _LIBCPP_END_NAMESPACE_STD
1760 #endif // _LIBCPP_ITERATOR