1// -*- C++ -*-
2//===-------------------------- iterator ----------------------------------===//
3//
4// The LLVM Compiler Infrastructure
5//
6// This file is dual licensed under the MIT and the University of Illinois Open
7// Source Licenses. See LICENSE.TXT for details.
8//
9//===----------------------------------------------------------------------===//
10
11#ifndef _LIBCPP_ITERATOR
12#define _LIBCPP_ITERATOR
13
14/*
15 iterator synopsis
16
17namespace std
18{
19
20template<class Iterator>
21struct iterator_traits
22{
23 typedef typename Iterator::difference_type difference_type;
24 typedef typename Iterator::value_type value_type;
25 typedef typename Iterator::pointer pointer;
26 typedef typename Iterator::reference reference;
27 typedef typename Iterator::iterator_category iterator_category;
28};
29
30template<class T>
31struct iterator_traits<T*>
32{
33 typedef ptrdiff_t difference_type;
34 typedef T value_type;
35 typedef T* pointer;
36 typedef T& reference;
37 typedef random_access_iterator_tag iterator_category;
38};
39
40template<class T>
41struct iterator_traits<const T*>
42{
43 typedef ptrdiff_t difference_type;
44 typedef T value_type;
45 typedef const T* pointer;
46 typedef const T& reference;
47 typedef random_access_iterator_tag iterator_category;
48};
49
50template<class Category, class T, class Distance = ptrdiff_t,
51 class Pointer = T*, class Reference = T&>
52struct iterator
53{
54 typedef T value_type;
55 typedef Distance difference_type;
56 typedef Pointer pointer;
57 typedef Reference reference;
58 typedef Category iterator_category;
59};
60
61struct input_iterator_tag {};
62struct output_iterator_tag {};
63struct forward_iterator_tag : public input_iterator_tag {};
64struct bidirectional_iterator_tag : public forward_iterator_tag {};
65struct random_access_iterator_tag : public bidirectional_iterator_tag {};
66
67// extension: second argument not conforming to C++03
68template <class InputIterator>
69void advance(InputIterator& i,
70 typename iterator_traits<InputIterator>::difference_type n);
71
72template <class InputIterator>
73typename iterator_traits<InputIterator>::difference_type
74distance(InputIterator first, InputIterator last);
75
76template <class Iterator>
77class reverse_iterator
78 : public iterator<typename iterator_traits<Iterator>::iterator_category,
79 typename iterator_traits<Iterator>::value_type,
80 typename iterator_traits<Iterator>::difference_type,
81 typename iterator_traits<Iterator>::pointer,
82 typename iterator_traits<Iterator>::reference>
83{
84protected:
85 Iterator current;
86public:
87 typedef Iterator iterator_type;
88 typedef typename iterator_traits<Iterator>::difference_type difference_type;
89 typedef typename iterator_traits<Iterator>::reference reference;
90 typedef typename iterator_traits<Iterator>::pointer pointer;
91
92 reverse_iterator();
93 explicit reverse_iterator(Iterator x);
94 template <class U> reverse_iterator(const reverse_iterator<U>& u);
95 Iterator base() const;
96 reference operator*() const;
97 pointer operator->() const;
98 reverse_iterator& operator++();
99 reverse_iterator operator++(int);
100 reverse_iterator& operator--();
101 reverse_iterator operator--(int);
102 reverse_iterator operator+ (difference_type n) const;
103 reverse_iterator& operator+=(difference_type n);
104 reverse_iterator operator- (difference_type n) const;
105 reverse_iterator& operator-=(difference_type n);
106 reference operator[](difference_type n) const;
107};
108
109template <class Iterator1, class Iterator2>
110bool
111operator==(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
112
113template <class Iterator1, class Iterator2>
114bool
115operator<(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
116
117template <class Iterator1, class Iterator2>
118bool
119operator!=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
120
121template <class Iterator1, class Iterator2>
122bool
123operator>(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
124
125template <class Iterator1, class Iterator2>
126bool
127operator>=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
128
129template <class Iterator1, class Iterator2>
130bool
131operator<=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
132
133template <class Iterator1, class Iterator2>
134auto
135operator-(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y)
136-> decltype(__y.base() - __x.base());
137
138template <class Iterator>
139reverse_iterator<Iterator>
140operator+(typename reverse_iterator<Iterator>::difference_type n, const reverse_iterator<Iterator>& x);
141
142template <class Iterator> reverse_iterator<Iterator> make_reverse_iterator(Iterator i); // C++14
143
144template <class Container>
145class back_insert_iterator
146{
147protected:
148 Container* container;
149public:
150 typedef Container container_type;
151 typedef void value_type;
152 typedef void difference_type;
153 typedef void reference;
154 typedef void pointer;
155
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);
161};
162
163template <class Container> back_insert_iterator<Container> back_inserter(Container& x);
164
165template <class Container>
166class front_insert_iterator
167{
168protected:
169 Container* container;
170public:
171 typedef Container container_type;
172 typedef void value_type;
173 typedef void difference_type;
174 typedef void reference;
175 typedef void pointer;
176
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);
182};
183
184template <class Container> front_insert_iterator<Container> front_inserter(Container& x);
185
186template <class Container>
187class insert_iterator
188{
189protected:
190 Container* container;
191 typename Container::iterator iter;
192public:
193 typedef Container container_type;
194 typedef void value_type;
195 typedef void difference_type;
196 typedef void reference;
197 typedef void pointer;
198
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);
204};
205
206template <class Container, class Iterator>
207insert_iterator<Container> inserter(Container& x, Iterator i);
208
209template <class Iterator>
210class move_iterator {
211public:
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;
218
219 move_iterator();
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;
235private:
236 Iterator current; // exposition only
237};
238
239template <class Iterator1, class Iterator2>
240bool
241operator==(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
242
243template <class Iterator1, class Iterator2>
244bool
245operator!=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
246
247template <class Iterator1, class Iterator2>
248bool
249operator<(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
250
251template <class Iterator1, class Iterator2>
252bool
253operator<=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
254
255template <class Iterator1, class Iterator2>
256bool
257operator>(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
258
259template <class Iterator1, class Iterator2>
260bool
261operator>=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
262
263template <class Iterator1, class Iterator2>
264auto
265operator-(const move_iterator<Iterator1>& x,
266 const move_iterator<Iterator2>& y) -> decltype(x.base() - y.base());
267
268template <class Iterator>
269move_iterator<Iterator> operator+(typename move_iterator<Iterator>::difference_type n,
270 const move_iterator<Iterator>& x);
271
272template <class Iterator>
273move_iterator<Iterator> make_move_iterator(const Iterator& i);
274
275
276template <class T, class charT = char, class traits = char_traits<charT>, class Distance = ptrdiff_t>
277class istream_iterator
278 : public iterator<input_iterator_tag, T, Distance, const T*, const T&>
279{
280public:
281 typedef charT char_type;
282 typedef traits traits_type;
283 typedef basic_istream<charT,traits> istream_type;
284
285 constexpr istream_iterator();
286 istream_iterator(istream_type& s);
287 istream_iterator(const istream_iterator& x);
288 ~istream_iterator();
289
290 const T& operator*() const;
291 const T* operator->() const;
292 istream_iterator& operator++();
293 istream_iterator operator++(int);
294};
295
296template <class T, class charT, class traits, class Distance>
297bool operator==(const istream_iterator<T,charT,traits,Distance>& x,
298 const istream_iterator<T,charT,traits,Distance>& y);
299template <class T, class charT, class traits, class Distance>
300bool operator!=(const istream_iterator<T,charT,traits,Distance>& x,
301 const istream_iterator<T,charT,traits,Distance>& y);
302
303template <class T, class charT = char, class traits = char_traits<charT> >
304class ostream_iterator
305 : public iterator<output_iterator_tag, void, void, void ,void>
306{
307public:
308 typedef charT char_type;
309 typedef traits traits_type;
310 typedef basic_ostream<charT,traits> ostream_type;
311
312 ostream_iterator(ostream_type& s);
313 ostream_iterator(ostream_type& s, const charT* delimiter);
314 ostream_iterator(const ostream_iterator& x);
315 ~ostream_iterator();
316 ostream_iterator& operator=(const T& value);
317
318 ostream_iterator& operator*();
319 ostream_iterator& operator++();
320 ostream_iterator& operator++(int);
321};
322
323template<class charT, class traits = char_traits<charT> >
324class istreambuf_iterator
325 : public iterator<input_iterator_tag, charT,
326 typename traits::off_type, unspecified,
327 charT>
328{
329public:
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;
335
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;
340
341 charT operator*() const;
342 pointer operator->() const;
343 istreambuf_iterator& operator++();
344 a-private-type operator++(int);
345
346 bool equal(const istreambuf_iterator& b) const;
347};
348
349template <class charT, class traits>
350bool operator==(const istreambuf_iterator<charT,traits>& a,
351 const istreambuf_iterator<charT,traits>& b);
352template <class charT, class traits>
353bool operator!=(const istreambuf_iterator<charT,traits>& a,
354 const istreambuf_iterator<charT,traits>& b);
355
356template <class charT, class traits = char_traits<charT> >
357class ostreambuf_iterator
358 : public iterator<output_iterator_tag, void, void, void, void>
359{
360public:
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;
365
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;
373};
374
375template <class C> auto begin(C& c) -> decltype(c.begin());
376template <class C> auto begin(const C& c) -> decltype(c.begin());
377template <class C> auto end(C& c) -> decltype(c.end());
378template <class C> auto end(const C& c) -> decltype(c.end());
379template <class T, size_t N> T* begin(T (&array)[N]);
380template <class T, size_t N> T* end(T (&array)[N]);
381
382template <class C> auto cbegin(const C& c) -> decltype(std::begin(c)); // C++14
383template <class C> auto cend(const C& c) -> decltype(std::end(c)); // C++14
384template <class C> auto rbegin(C& c) -> decltype(c.rbegin()); // C++14
385template <class C> auto rbegin(const C& c) -> decltype(c.rbegin()); // C++14
386template <class C> auto rend(C& c) -> decltype(c.rend()); // C++14
387template <class C> auto rend(const C& c) -> decltype(c.rend()); // C++14
388template <class E> reverse_iterator<const E*> rbegin(initializer_list<E> il); // C++14
389template <class E> reverse_iterator<const E*> rend(initializer_list<E> il); // C++14
390template <class T, size_t N> reverse_iterator<T*> rbegin(T (&array)[N]); // C++14
391template <class T, size_t N> reverse_iterator<T*> rend(T (&array)[N]); // C++14
392template <class C> auto crbegin(const C& c) -> decltype(std::rbegin(c)); // C++14
393template <class C> auto crend(const C& c) -> decltype(std::rend(c)); // C++14
394
395// 24.8, container access:
396template <class C> constexpr auto size(const C& c) -> decltype(c.size()); // C++17
397template <class T, size_t N> constexpr size_t size(const T (&array)[N]) noexcept; // C++17
398template <class C> constexpr auto empty(const C& c) -> decltype(c.empty()); // C++17
399template <class T, size_t N> constexpr bool empty(const T (&array)[N]) noexcept; // C++17
400template <class E> constexpr bool empty(initializer_list<E> il) noexcept; // C++17
401template <class C> constexpr auto data(C& c) -> decltype(c.data()); // C++17
402template <class C> constexpr auto data(const C& c) -> decltype(c.data()); // C++17
403template <class T, size_t N> constexpr T* data(T (&array)[N]) noexcept; // C++17
404template <class E> constexpr const E* data(initializer_list<E> il) noexcept; // C++17
405
406} // std
407
408*/
409
410#include <__config>
411#include <iosfwd> // for forward declarations of vector and string.
412#include <__functional_base>
413#include <type_traits>
414#include <cstddef>
415#include <initializer_list>
416#ifdef __APPLE__
417#include <Availability.h>
418#endif
419
420#include <__debug>
421
422#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
423#pragma GCC system_header
424#endif
425
426_LIBCPP_BEGIN_NAMESPACE_STD
427
428struct _LIBCPP_TYPE_VIS_ONLY input_iterator_tag {};
429struct _LIBCPP_TYPE_VIS_ONLY output_iterator_tag {};
430struct _LIBCPP_TYPE_VIS_ONLY forward_iterator_tag : public input_iterator_tag {};
431struct _LIBCPP_TYPE_VIS_ONLY bidirectional_iterator_tag : public forward_iterator_tag {};
432struct _LIBCPP_TYPE_VIS_ONLY random_access_iterator_tag : public bidirectional_iterator_tag {};
433
434template <class _Tp>
435struct __has_iterator_category
436{
437private:
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);
441public:
442 static const bool value = sizeof(__test<_Tp>(0)) == 1;
443};
444
445template <class _Iter, bool> struct __iterator_traits_impl {};
446
447template <class _Iter>
448struct __iterator_traits_impl<_Iter, true>
449{
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;
455};
456
457template <class _Iter, bool> struct __iterator_traits {};
458
459template <class _Iter>
460struct __iterator_traits<_Iter, true>
461 : __iterator_traits_impl
462 <
463 _Iter,
464 is_convertible<typename _Iter::iterator_category, input_iterator_tag>::value ||
465 is_convertible<typename _Iter::iterator_category, output_iterator_tag>::value
466 >
467{};
468
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.
473
474template <class _Iter>
475struct _LIBCPP_TYPE_VIS_ONLY iterator_traits
476 : __iterator_traits<_Iter, __has_iterator_category<_Iter>::value> {};
477
478template<class _Tp>
479struct _LIBCPP_TYPE_VIS_ONLY iterator_traits<_Tp*>
480{
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;
486};
487
488template <class _Tp, class _Up, bool = __has_iterator_category<iterator_traits<_Tp> >::value>
489struct __has_iterator_category_convertible_to
490 : public integral_constant<bool, is_convertible<typename iterator_traits<_Tp>::iterator_category, _Up>::value>
491{};
492
493template <class _Tp, class _Up>
494struct __has_iterator_category_convertible_to<_Tp, _Up, false> : public false_type {};
495
496template <class _Tp>
497struct __is_input_iterator : public __has_iterator_category_convertible_to<_Tp, input_iterator_tag> {};
498
499template <class _Tp>
500struct __is_forward_iterator : public __has_iterator_category_convertible_to<_Tp, forward_iterator_tag> {};
501
502template <class _Tp>
503struct __is_bidirectional_iterator : public __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag> {};
504
505template <class _Tp>
506struct __is_random_access_iterator : public __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag> {};
507
508template <class _Tp>
509struct __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> {};
513
514template<class _Category, class _Tp, class _Distance = ptrdiff_t,
515 class _Pointer = _Tp*, class _Reference = _Tp&>
516struct _LIBCPP_TYPE_VIS_ONLY iterator
517{
518 typedef _Tp value_type;
519 typedef _Distance difference_type;
520 typedef _Pointer pointer;
521 typedef _Reference reference;
522 typedef _Category iterator_category;
523};
524
525template <class _InputIter>
526inline _LIBCPP_INLINE_VISIBILITY
527void __advance(_InputIter& __i,
528 typename iterator_traits<_InputIter>::difference_type __n, input_iterator_tag)
529{
530 for (; __n > 0; --__n)
531 ++__i;
532}
533
534template <class _BiDirIter>
535inline _LIBCPP_INLINE_VISIBILITY
536void __advance(_BiDirIter& __i,
537 typename iterator_traits<_BiDirIter>::difference_type __n, bidirectional_iterator_tag)
538{
539 if (__n >= 0)
540 for (; __n > 0; --__n)
541 ++__i;
542 else
543 for (; __n < 0; ++__n)
544 --__i;
545}
546
547template <class _RandIter>
548inline _LIBCPP_INLINE_VISIBILITY
549void __advance(_RandIter& __i,
550 typename iterator_traits<_RandIter>::difference_type __n, random_access_iterator_tag)
551{
552 __i += __n;
553}
554
555template <class _InputIter>
556inline _LIBCPP_INLINE_VISIBILITY
557void advance(_InputIter& __i,
558 typename iterator_traits<_InputIter>::difference_type __n)
559{
560 __advance(__i, __n, typename iterator_traits<_InputIter>::iterator_category());
561}
562
563template <class _InputIter>
564inline _LIBCPP_INLINE_VISIBILITY
565typename iterator_traits<_InputIter>::difference_type
566__distance(_InputIter __first, _InputIter __last, input_iterator_tag)
567{
568 typename iterator_traits<_InputIter>::difference_type __r(0);
569 for (; __first != __last; ++__first)
570 ++__r;
571 return __r;
572}
573
574template <class _RandIter>
575inline _LIBCPP_INLINE_VISIBILITY
576typename iterator_traits<_RandIter>::difference_type
577__distance(_RandIter __first, _RandIter __last, random_access_iterator_tag)
578{
579 return __last - __first;
580}
581
582template <class _InputIter>
583inline _LIBCPP_INLINE_VISIBILITY
584typename iterator_traits<_InputIter>::difference_type
585distance(_InputIter __first, _InputIter __last)
586{
587 return __distance(__first, __last, typename iterator_traits<_InputIter>::iterator_category());
588}
589
590template <class _InputIter>
591inline _LIBCPP_INLINE_VISIBILITY
592_InputIter
593next(_InputIter __x,
594 typename iterator_traits<_InputIter>::difference_type __n = 1,
595 typename enable_if<__is_input_iterator<_InputIter>::value>::type* = 0)
596{
597 _VSTD::advance(__x, __n);
598 return __x;
599}
600
601template <class _BidiretionalIter>
602inline _LIBCPP_INLINE_VISIBILITY
603_BidiretionalIter
604prev(_BidiretionalIter __x,
605 typename iterator_traits<_BidiretionalIter>::difference_type __n = 1,
606 typename enable_if<__is_bidirectional_iterator<_BidiretionalIter>::value>::type* = 0)
607{
608 _VSTD::advance(__x, -__n);
609 return __x;
610}
611
612template <class _Iter>
613class _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>
619{
620private:
621 mutable _Iter __t; // no longer used as of LWG #2360, not removed due to ABI break
622protected:
623 _Iter current;
624public:
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;
629
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);}
653};
654
655template <class _Iter1, class _Iter2>
656inline _LIBCPP_INLINE_VISIBILITY
657bool
658operator==(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
659{
660 return __x.base() == __y.base();
661}
662
663template <class _Iter1, class _Iter2>
664inline _LIBCPP_INLINE_VISIBILITY
665bool
666operator<(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
667{
668 return __x.base() > __y.base();
669}
670
671template <class _Iter1, class _Iter2>
672inline _LIBCPP_INLINE_VISIBILITY
673bool
674operator!=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
675{
676 return __x.base() != __y.base();
677}
678
679template <class _Iter1, class _Iter2>
680inline _LIBCPP_INLINE_VISIBILITY
681bool
682operator>(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
683{
684 return __x.base() < __y.base();
685}
686
687template <class _Iter1, class _Iter2>
688inline _LIBCPP_INLINE_VISIBILITY
689bool
690operator>=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
691{
692 return __x.base() <= __y.base();
693}
694
695template <class _Iter1, class _Iter2>
696inline _LIBCPP_INLINE_VISIBILITY
697bool
698operator<=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
699{
700 return __x.base() >= __y.base();
701}
702
703#ifndef _LIBCPP_CXX03_LANG
704template <class _Iter1, class _Iter2>
705inline _LIBCPP_INLINE_VISIBILITY
706auto
707operator-(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
708-> decltype(__y.base() - __x.base())
709{
710 return __y.base() - __x.base();
711}
712#else
713template <class _Iter1, class _Iter2>
714inline _LIBCPP_INLINE_VISIBILITY
715typename reverse_iterator<_Iter1>::difference_type
716operator-(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
717{
718 return __y.base() - __x.base();
719}
720#endif
721
722template <class _Iter>
723inline _LIBCPP_INLINE_VISIBILITY
724reverse_iterator<_Iter>
725operator+(typename reverse_iterator<_Iter>::difference_type __n, const reverse_iterator<_Iter>& __x)
726{
727 return reverse_iterator<_Iter>(__x.base() - __n);
728}
729
730#if _LIBCPP_STD_VER > 11
731template <class _Iter>
732inline _LIBCPP_INLINE_VISIBILITY
733reverse_iterator<_Iter> make_reverse_iterator(_Iter __i)
734{
735 return reverse_iterator<_Iter>(__i);
736}
737#endif
738
739template <class _Container>
740class _LIBCPP_TYPE_VIS_ONLY back_insert_iterator
741 : public iterator<output_iterator_tag,
742 void,
743 void,
744 void,
745 void>
746{
747protected:
748 _Container* container;
749public:
750 typedef _Container container_type;
751
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;}
762};
763
764template <class _Container>
765inline _LIBCPP_INLINE_VISIBILITY
766back_insert_iterator<_Container>
767back_inserter(_Container& __x)
768{
769 return back_insert_iterator<_Container>(__x);
770}
771
772template <class _Container>
773class _LIBCPP_TYPE_VIS_ONLY front_insert_iterator
774 : public iterator<output_iterator_tag,
775 void,
776 void,
777 void,
778 void>
779{
780protected:
781 _Container* container;
782public:
783 typedef _Container container_type;
784
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;}
795};
796
797template <class _Container>
798inline _LIBCPP_INLINE_VISIBILITY
799front_insert_iterator<_Container>
800front_inserter(_Container& __x)
801{
802 return front_insert_iterator<_Container>(__x);
803}
804
805template <class _Container>
806class _LIBCPP_TYPE_VIS_ONLY insert_iterator
807 : public iterator<output_iterator_tag,
808 void,
809 void,
810 void,
811 void>
812{
813protected:
814 _Container* container;
815 typename _Container::iterator iter;
816public:
817 typedef _Container container_type;
818
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;}
830};
831
832template <class _Container>
833inline _LIBCPP_INLINE_VISIBILITY
834insert_iterator<_Container>
835inserter(_Container& __x, typename _Container::iterator __i)
836{
837 return insert_iterator<_Container>(__x, __i);
838}
839
840template <class _Tp, class _CharT = char,
841 class _Traits = char_traits<_CharT>, class _Distance = ptrdiff_t>
842class _LIBCPP_TYPE_VIS_ONLY istream_iterator
843 : public iterator<input_iterator_tag, _Tp, _Distance, const _Tp*, const _Tp&>
844{
845public:
846 typedef _CharT char_type;
847 typedef _Traits traits_type;
848 typedef basic_istream<_CharT,_Traits> istream_type;
849private:
850 istream_type* __in_stream_;
851 _Tp __value_;
852public:
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))
855 {
856 if (!(*__in_stream_ >> __value_))
857 __in_stream_ = 0;
858 }
859
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++()
863 {
864 if (!(*__in_stream_ >> __value_))
865 __in_stream_ = 0;
866 return *this;
867 }
868 _LIBCPP_INLINE_VISIBILITY istream_iterator operator++(int)
869 {istream_iterator __t(*this); ++(*this); return __t;}
870
871 friend _LIBCPP_INLINE_VISIBILITY
872 bool operator==(const istream_iterator& __x, const istream_iterator& __y)
873 {return __x.__in_stream_ == __y.__in_stream_;}
874
875 friend _LIBCPP_INLINE_VISIBILITY
876 bool operator!=(const istream_iterator& __x, const istream_iterator& __y)
877 {return !(__x == __y);}
878};
879
880template <class _Tp, class _CharT = char, class _Traits = char_traits<_CharT> >
881class _LIBCPP_TYPE_VIS_ONLY ostream_iterator
882 : public iterator<output_iterator_tag, void, void, void, void>
883{
884public:
885 typedef _CharT char_type;
886 typedef _Traits traits_type;
887 typedef basic_ostream<_CharT,_Traits> ostream_type;
888private:
889 ostream_type* __out_stream_;
890 const char_type* __delim_;
891public:
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_)
897 {
898 *__out_stream_ << __value_;
899 if (__delim_)
900 *__out_stream_ << __delim_;
901 return *this;
902 }
903
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;}
907};
908
909template<class _CharT, class _Traits>
910class _LIBCPP_TYPE_VIS_ONLY istreambuf_iterator
911 : public iterator<input_iterator_tag, _CharT,
912 typename _Traits::off_type, _CharT*,
913 _CharT>
914{
915public:
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;
921private:
922 mutable streambuf_type* __sbuf_;
923
924 class __proxy
925 {
926 char_type __keep_;
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;
931 public:
932 _LIBCPP_INLINE_VISIBILITY char_type operator*() const {return __keep_;}
933 };
934
935 _LIBCPP_INLINE_VISIBILITY
936 bool __test_for_eof() const
937 {
938 if (__sbuf_ && traits_type::eq_int_type(__sbuf_->sgetc(), traits_type::eof()))
939 __sbuf_ = 0;
940 return __sbuf_ == 0;
941 }
942public:
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
947 : __sbuf_(__s) {}
948 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(const __proxy& __p) _NOEXCEPT
949 : __sbuf_(__p.__sbuf_) {}
950
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++()
955 {
956 __sbuf_->sbumpc();
957 return *this;
958 }
959 _LIBCPP_INLINE_VISIBILITY __proxy operator++(int)
960 {
961 return __proxy(__sbuf_->sbumpc(), __sbuf_);
962 }
963
964 _LIBCPP_INLINE_VISIBILITY bool equal(const istreambuf_iterator& __b) const
965 {return __test_for_eof() == __b.__test_for_eof();}
966};
967
968template <class _CharT, class _Traits>
969inline _LIBCPP_INLINE_VISIBILITY
970bool operator==(const istreambuf_iterator<_CharT,_Traits>& __a,
971 const istreambuf_iterator<_CharT,_Traits>& __b)
972 {return __a.equal(__b);}
973
974template <class _CharT, class _Traits>
975inline _LIBCPP_INLINE_VISIBILITY
976bool operator!=(const istreambuf_iterator<_CharT,_Traits>& __a,
977 const istreambuf_iterator<_CharT,_Traits>& __b)
978 {return !__a.equal(__b);}
979
980template <class _CharT, class _Traits>
981class _LIBCPP_TYPE_VIS_ONLY ostreambuf_iterator
982 : public iterator<output_iterator_tag, void, void, void, void>
983{
984public:
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;
989private:
990 streambuf_type* __sbuf_;
991public:
992 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator(ostream_type& __s) _NOEXCEPT
993 : __sbuf_(__s.rdbuf()) {}
994 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator(streambuf_type* __s) _NOEXCEPT
995 : __sbuf_(__s) {}
996 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator=(_CharT __c)
997 {
998 if (__sbuf_ && traits_type::eq_int_type(__sbuf_->sputc(__c), traits_type::eof()))
999 __sbuf_ = 0;
1000 return *this;
1001 }
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;}
1006
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)
1010
1011 template <class _Ch, class _Tr>
1012 friend
1013 _LIBCPP_HIDDEN
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);
1018#endif
1019};
1020
1021template <class _Iter>
1022class _LIBCPP_TYPE_VIS_ONLY move_iterator
1023{
1024private:
1025 _Iter __i;
1026public:
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&&,
1037 __reference
1038 >::type reference;
1039#else
1040 typedef typename iterator_traits<iterator_type>::reference reference;
1041#endif
1042
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);
1050 }
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
1067 {
1068 return static_cast<reference>(__i[__n]);
1069 }
1070};
1071
1072template <class _Iter1, class _Iter2>
1073inline _LIBCPP_INLINE_VISIBILITY
1074bool
1075operator==(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1076{
1077 return __x.base() == __y.base();
1078}
1079
1080template <class _Iter1, class _Iter2>
1081inline _LIBCPP_INLINE_VISIBILITY
1082bool
1083operator<(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1084{
1085 return __x.base() < __y.base();
1086}
1087
1088template <class _Iter1, class _Iter2>
1089inline _LIBCPP_INLINE_VISIBILITY
1090bool
1091operator!=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1092{
1093 return __x.base() != __y.base();
1094}
1095
1096template <class _Iter1, class _Iter2>
1097inline _LIBCPP_INLINE_VISIBILITY
1098bool
1099operator>(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1100{
1101 return __x.base() > __y.base();
1102}
1103
1104template <class _Iter1, class _Iter2>
1105inline _LIBCPP_INLINE_VISIBILITY
1106bool
1107operator>=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1108{
1109 return __x.base() >= __y.base();
1110}
1111
1112template <class _Iter1, class _Iter2>
1113inline _LIBCPP_INLINE_VISIBILITY
1114bool
1115operator<=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1116{
1117 return __x.base() <= __y.base();
1118}
1119
1120#ifndef _LIBCPP_CXX03_LANG
1121template <class _Iter1, class _Iter2>
1122inline _LIBCPP_INLINE_VISIBILITY
1123auto
1124operator-(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1125-> decltype(__x.base() - __y.base())
1126{
1127 return __x.base() - __y.base();
1128}
1129#else
1130template <class _Iter1, class _Iter2>
1131inline _LIBCPP_INLINE_VISIBILITY
1132typename move_iterator<_Iter1>::difference_type
1133operator-(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1134{
1135 return __x.base() - __y.base();
1136}
1137#endif
1138
1139template <class _Iter>
1140inline _LIBCPP_INLINE_VISIBILITY
1141move_iterator<_Iter>
1142operator+(typename move_iterator<_Iter>::difference_type __n, const move_iterator<_Iter>& __x)
1143{
1144 return move_iterator<_Iter>(__x.base() + __n);
1145}
1146
1147template <class _Iter>
1148inline _LIBCPP_INLINE_VISIBILITY
1149move_iterator<_Iter>
1150make_move_iterator(_Iter __i)
1151{
1152 return move_iterator<_Iter>(__i);
1153}
1154
1155// __wrap_iter
1156
1157template <class _Iter> class __wrap_iter;
1158
1159template <class _Iter1, class _Iter2>
1160_LIBCPP_INLINE_VISIBILITY
1161bool
1162operator==(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1163
1164template <class _Iter1, class _Iter2>
1165_LIBCPP_INLINE_VISIBILITY
1166bool
1167operator<(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1168
1169template <class _Iter1, class _Iter2>
1170_LIBCPP_INLINE_VISIBILITY
1171bool
1172operator!=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1173
1174template <class _Iter1, class _Iter2>
1175_LIBCPP_INLINE_VISIBILITY
1176bool
1177operator>(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1178
1179template <class _Iter1, class _Iter2>
1180_LIBCPP_INLINE_VISIBILITY
1181bool
1182operator>=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1183
1184template <class _Iter1, class _Iter2>
1185_LIBCPP_INLINE_VISIBILITY
1186bool
1187operator<=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1188
1189#ifndef _LIBCPP_CXX03_LANG
1190template <class _Iter1, class _Iter2>
1191_LIBCPP_INLINE_VISIBILITY
1192auto
1193operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1194-> decltype(__x.base() - __y.base());
1195#else
1196template <class _Iter1, class _Iter2>
1197_LIBCPP_INLINE_VISIBILITY
1198typename __wrap_iter<_Iter1>::difference_type
1199operator-(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1200#endif
1201
1202template <class _Iter>
1203_LIBCPP_INLINE_VISIBILITY
1204__wrap_iter<_Iter>
1205operator+(typename __wrap_iter<_Iter>::difference_type, __wrap_iter<_Iter>) _NOEXCEPT;
1206
1207template <class _Ip, class _Op> _Op _LIBCPP_INLINE_VISIBILITY copy(_Ip, _Ip, _Op);
1208template <class _B1, class _B2> _B2 _LIBCPP_INLINE_VISIBILITY copy_backward(_B1, _B1, _B2);
1209template <class _Ip, class _Op> _Op _LIBCPP_INLINE_VISIBILITY move(_Ip, _Ip, _Op);
1210template <class _B1, class _B2> _B2 _LIBCPP_INLINE_VISIBILITY move_backward(_B1, _B1, _B2);
1211
1212template <class _Tp>
1213_LIBCPP_INLINE_VISIBILITY
1214typename enable_if
1215<
1216 is_trivially_copy_assignable<_Tp>::value,
1217 _Tp*
1218>::type
1219__unwrap_iter(__wrap_iter<_Tp*>);
1220
1221template <class _Iter>
1222class __wrap_iter
1223{
1224public:
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;
1231private:
1232 iterator_type __i;
1233public:
1234 _LIBCPP_INLINE_VISIBILITY __wrap_iter() _NOEXCEPT
1235#if _LIBCPP_STD_VER > 11
1236 : __i{}
1237#endif
1238 {
1239#if _LIBCPP_DEBUG_LEVEL >= 2
1240 __get_db()->__insert_i(this);
1241#endif
1242 }
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
1245 : __i(__u.base())
1246 {
1247#if _LIBCPP_DEBUG_LEVEL >= 2
1248 __get_db()->__iterator_copy(this, &__u);
1249#endif
1250 }
1251#if _LIBCPP_DEBUG_LEVEL >= 2
1252 _LIBCPP_INLINE_VISIBILITY
1253 __wrap_iter(const __wrap_iter& __x)
1254 : __i(__x.base())
1255 {
1256 __get_db()->__iterator_copy(this, &__x);
1257 }
1258 _LIBCPP_INLINE_VISIBILITY
1259 __wrap_iter& operator=(const __wrap_iter& __x)
1260 {
1261 if (this != &__x)
1262 {
1263 __get_db()->__iterator_copy(this, &__x);
1264 __i = __x.__i;
1265 }
1266 return *this;
1267 }
1268 _LIBCPP_INLINE_VISIBILITY
1269 ~__wrap_iter()
1270 {
1271 __get_db()->__erase_i(this);
1272 }
1273#endif
1274 _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT
1275 {
1276#if _LIBCPP_DEBUG_LEVEL >= 2
1277 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
1278 "Attempted to dereference a non-dereferenceable iterator");
1279#endif
1280 return *__i;
1281 }
1282 _LIBCPP_INLINE_VISIBILITY pointer operator->() const _NOEXCEPT
1283 {
1284#if _LIBCPP_DEBUG_LEVEL >= 2
1285 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
1286 "Attempted to dereference a non-dereferenceable iterator");
1287#endif
1288 return (pointer)_VSTD::addressof(*__i);
1289 }
1290 _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator++() _NOEXCEPT
1291 {
1292#if _LIBCPP_DEBUG_LEVEL >= 2
1293 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
1294 "Attempted to increment non-incrementable iterator");
1295#endif
1296 ++__i;
1297 return *this;
1298 }
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
1302 {
1303#if _LIBCPP_DEBUG_LEVEL >= 2
1304 _LIBCPP_ASSERT(__get_const_db()->__decrementable(this),
1305 "Attempted to decrement non-decrementable iterator");
1306#endif
1307 --__i;
1308 return *this;
1309 }
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
1315 {
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");
1319#endif
1320 __i += __n;
1321 return *this;
1322 }
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
1328 {
1329#if _LIBCPP_DEBUG_LEVEL >= 2
1330 _LIBCPP_ASSERT(__get_const_db()->__subscriptable(this, __n),
1331 "Attempted to subscript iterator outside of valid range");
1332#endif
1333 return __i[__n];
1334 }
1335
1336 _LIBCPP_INLINE_VISIBILITY iterator_type base() const _NOEXCEPT {return __i;}
1337
1338private:
1339#if _LIBCPP_DEBUG_LEVEL >= 2
1340 _LIBCPP_INLINE_VISIBILITY __wrap_iter(const void* __p, iterator_type __x) : __i(__x)
1341 {
1342 __get_db()->__insert_ic(this, __p);
1343 }
1344#else
1345 _LIBCPP_INLINE_VISIBILITY __wrap_iter(iterator_type __x) _NOEXCEPT : __i(__x) {}
1346#endif
1347
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;
1351
1352 template <class _Iter1, class _Iter2>
1353 friend
1354 bool
1355 operator==(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1356
1357 template <class _Iter1, class _Iter2>
1358 friend
1359 bool
1360 operator<(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1361
1362 template <class _Iter1, class _Iter2>
1363 friend
1364 bool
1365 operator!=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1366
1367 template <class _Iter1, class _Iter2>
1368 friend
1369 bool
1370 operator>(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1371
1372 template <class _Iter1, class _Iter2>
1373 friend
1374 bool
1375 operator>=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1376
1377 template <class _Iter1, class _Iter2>
1378 friend
1379 bool
1380 operator<=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1381
1382#ifndef _LIBCPP_CXX03_LANG
1383 template <class _Iter1, class _Iter2>
1384 friend
1385 auto
1386 operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1387 -> decltype(__x.base() - __y.base());
1388#else
1389 template <class _Iter1, class _Iter2>
1390 friend
1391 typename __wrap_iter<_Iter1>::difference_type
1392 operator-(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1393#endif
1394
1395 template <class _Iter1>
1396 friend
1397 __wrap_iter<_Iter1>
1398 operator+(typename __wrap_iter<_Iter1>::difference_type, __wrap_iter<_Iter1>) _NOEXCEPT;
1399
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);
1404
1405 template <class _Tp>
1406 friend
1407 typename enable_if
1408 <
1409 is_trivially_copy_assignable<_Tp>::value,
1410 _Tp*
1411 >::type
1412 __unwrap_iter(__wrap_iter<_Tp*>);
1413};
1414
1415template <class _Iter1, class _Iter2>
1416inline _LIBCPP_INLINE_VISIBILITY
1417bool
1418operator==(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1419{
1420 return __x.base() == __y.base();
1421}
1422
1423template <class _Iter1, class _Iter2>
1424inline _LIBCPP_INLINE_VISIBILITY
1425bool
1426operator<(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1427{
1428#if _LIBCPP_DEBUG_LEVEL >= 2
1429 _LIBCPP_ASSERT(__get_const_db()->__less_than_comparable(&__x, &__y),
1430 "Attempted to compare incomparable iterators");
1431#endif
1432 return __x.base() < __y.base();
1433}
1434
1435template <class _Iter1, class _Iter2>
1436inline _LIBCPP_INLINE_VISIBILITY
1437bool
1438operator!=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1439{
1440 return !(__x == __y);
1441}
1442
1443template <class _Iter1, class _Iter2>
1444inline _LIBCPP_INLINE_VISIBILITY
1445bool
1446operator>(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1447{
1448 return __y < __x;
1449}
1450
1451template <class _Iter1, class _Iter2>
1452inline _LIBCPP_INLINE_VISIBILITY
1453bool
1454operator>=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1455{
1456 return !(__x < __y);
1457}
1458
1459template <class _Iter1, class _Iter2>
1460inline _LIBCPP_INLINE_VISIBILITY
1461bool
1462operator<=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1463{
1464 return !(__y < __x);
1465}
1466
1467template <class _Iter1>
1468inline _LIBCPP_INLINE_VISIBILITY
1469bool
1470operator!=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT
1471{
1472 return !(__x == __y);
1473}
1474
1475template <class _Iter1>
1476inline _LIBCPP_INLINE_VISIBILITY
1477bool
1478operator>(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT
1479{
1480 return __y < __x;
1481}
1482
1483template <class _Iter1>
1484inline _LIBCPP_INLINE_VISIBILITY
1485bool
1486operator>=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT
1487{
1488 return !(__x < __y);
1489}
1490
1491template <class _Iter1>
1492inline _LIBCPP_INLINE_VISIBILITY
1493bool
1494operator<=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT
1495{
1496 return !(__y < __x);
1497}
1498
1499#ifndef _LIBCPP_CXX03_LANG
1500template <class _Iter1, class _Iter2>
1501inline _LIBCPP_INLINE_VISIBILITY
1502auto
1503operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1504-> decltype(__x.base() - __y.base())
1505{
1506#if _LIBCPP_DEBUG_LEVEL >= 2
1507 _LIBCPP_ASSERT(__get_const_db()->__less_than_comparable(&__x, &__y),
1508 "Attempted to subtract incompatible iterators");
1509#endif
1510 return __x.base() - __y.base();
1511}
1512#else
1513template <class _Iter1, class _Iter2>
1514inline _LIBCPP_INLINE_VISIBILITY
1515typename __wrap_iter<_Iter1>::difference_type
1516operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1517{
1518#if _LIBCPP_DEBUG_LEVEL >= 2
1519 _LIBCPP_ASSERT(__get_const_db()->__less_than_comparable(&__x, &__y),
1520 "Attempted to subtract incompatible iterators");
1521#endif
1522 return __x.base() - __y.base();
1523}
1524#endif
1525
1526template <class _Iter>
1527inline _LIBCPP_INLINE_VISIBILITY
1528__wrap_iter<_Iter>
1529operator+(typename __wrap_iter<_Iter>::difference_type __n,
1530 __wrap_iter<_Iter> __x) _NOEXCEPT
1531{
1532 __x += __n;
1533 return __x;
1534}
1535
1536template <class _Iter>
1537struct __libcpp_is_trivial_iterator
1538 : public _LIBCPP_BOOL_CONSTANT(is_pointer<_Iter>::value) {};
1539
1540template <class _Iter>
1541struct __libcpp_is_trivial_iterator<move_iterator<_Iter> >
1542 : public _LIBCPP_BOOL_CONSTANT(__libcpp_is_trivial_iterator<_Iter>::value) {};
1543
1544template <class _Iter>
1545struct __libcpp_is_trivial_iterator<reverse_iterator<_Iter> >
1546 : public _LIBCPP_BOOL_CONSTANT(__libcpp_is_trivial_iterator<_Iter>::value) {};
1547
1548template <class _Iter>
1549struct __libcpp_is_trivial_iterator<__wrap_iter<_Iter> >
1550 : public _LIBCPP_BOOL_CONSTANT(__libcpp_is_trivial_iterator<_Iter>::value) {};
1551
1552
1553template <class _Tp, size_t _Np>
1554inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
1555_Tp*
1556begin(_Tp (&__array)[_Np])
1557{
1558 return __array;
1559}
1560
1561template <class _Tp, size_t _Np>
1562inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
1563_Tp*
1564end(_Tp (&__array)[_Np])
1565{
1566 return __array + _Np;
1567}
1568
1569#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_TRAILING_RETURN)
1570
1571template <class _Cp>
1572inline _LIBCPP_INLINE_VISIBILITY
1573auto
1574begin(_Cp& __c) -> decltype(__c.begin())
1575{
1576 return __c.begin();
1577}
1578
1579template <class _Cp>
1580inline _LIBCPP_INLINE_VISIBILITY
1581auto
1582begin(const _Cp& __c) -> decltype(__c.begin())
1583{
1584 return __c.begin();
1585}
1586
1587template <class _Cp>
1588inline _LIBCPP_INLINE_VISIBILITY
1589auto
1590end(_Cp& __c) -> decltype(__c.end())
1591{
1592 return __c.end();
1593}
1594
1595template <class _Cp>
1596inline _LIBCPP_INLINE_VISIBILITY
1597auto
1598end(const _Cp& __c) -> decltype(__c.end())
1599{
1600 return __c.end();
1601}
1602
1603#if _LIBCPP_STD_VER > 11
1604
1605template <class _Tp, size_t _Np>
1606inline _LIBCPP_INLINE_VISIBILITY
1607reverse_iterator<_Tp*> rbegin(_Tp (&__array)[_Np])
1608{
1609 return reverse_iterator<_Tp*>(__array + _Np);
1610}
1611
1612template <class _Tp, size_t _Np>
1613inline _LIBCPP_INLINE_VISIBILITY
1614reverse_iterator<_Tp*> rend(_Tp (&__array)[_Np])
1615{
1616 return reverse_iterator<_Tp*>(__array);
1617}
1618
1619template <class _Ep>
1620inline _LIBCPP_INLINE_VISIBILITY
1621reverse_iterator<const _Ep*> rbegin(initializer_list<_Ep> __il)
1622{
1623 return reverse_iterator<const _Ep*>(__il.end());
1624}
1625
1626template <class _Ep>
1627inline _LIBCPP_INLINE_VISIBILITY
1628reverse_iterator<const _Ep*> rend(initializer_list<_Ep> __il)
1629{
1630 return reverse_iterator<const _Ep*>(__il.begin());
1631}
1632
1633template <class _Cp>
1634inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
1635auto cbegin(const _Cp& __c) -> decltype(_VSTD::begin(__c))
1636{
1637 return _VSTD::begin(__c);
1638}
1639
1640template <class _Cp>
1641inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
1642auto cend(const _Cp& __c) -> decltype(_VSTD::end(__c))
1643{
1644 return _VSTD::end(__c);
1645}
1646
1647template <class _Cp>
1648inline _LIBCPP_INLINE_VISIBILITY
1649auto rbegin(_Cp& __c) -> decltype(__c.rbegin())
1650{
1651 return __c.rbegin();
1652}
1653
1654template <class _Cp>
1655inline _LIBCPP_INLINE_VISIBILITY
1656auto rbegin(const _Cp& __c) -> decltype(__c.rbegin())
1657{
1658 return __c.rbegin();
1659}
1660
1661template <class _Cp>
1662inline _LIBCPP_INLINE_VISIBILITY
1663auto rend(_Cp& __c) -> decltype(__c.rend())
1664{
1665 return __c.rend();
1666}
1667
1668template <class _Cp>
1669inline _LIBCPP_INLINE_VISIBILITY
1670auto rend(const _Cp& __c) -> decltype(__c.rend())
1671{
1672 return __c.rend();
1673}
1674
1675template <class _Cp>
1676inline _LIBCPP_INLINE_VISIBILITY
1677auto crbegin(const _Cp& __c) -> decltype(_VSTD::rbegin(__c))
1678{
1679 return _VSTD::rbegin(__c);
1680}
1681
1682template <class _Cp>
1683inline _LIBCPP_INLINE_VISIBILITY
1684auto crend(const _Cp& __c) -> decltype(_VSTD::rend(__c))
1685{
1686 return _VSTD::rend(__c);
1687}
1688
1689#endif
1690
1691
1692#else // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_TRAILING_RETURN)
1693
1694template <class _Cp>
1695inline _LIBCPP_INLINE_VISIBILITY
1696typename _Cp::iterator
1697begin(_Cp& __c)
1698{
1699 return __c.begin();
1700}
1701
1702template <class _Cp>
1703inline _LIBCPP_INLINE_VISIBILITY
1704typename _Cp::const_iterator
1705begin(const _Cp& __c)
1706{
1707 return __c.begin();
1708}
1709
1710template <class _Cp>
1711inline _LIBCPP_INLINE_VISIBILITY
1712typename _Cp::iterator
1713end(_Cp& __c)
1714{
1715 return __c.end();
1716}
1717
1718template <class _Cp>
1719inline _LIBCPP_INLINE_VISIBILITY
1720typename _Cp::const_iterator
1721end(const _Cp& __c)
1722{
1723 return __c.end();
1724}
1725
1726#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_TRAILING_RETURN)
1727
1728#if _LIBCPP_STD_VER > 14
1729template <class _Cont>
1730constexpr auto size(const _Cont& __c) -> decltype(__c.size()) { return __c.size(); }
1731
1732template <class _Tp, size_t _Sz>
1733constexpr size_t size(const _Tp (&__array)[_Sz]) noexcept { return _Sz; }
1734
1735template <class _Cont>
1736constexpr auto empty(const _Cont& __c) -> decltype(__c.empty()) { return __c.empty(); }
1737
1738template <class _Tp, size_t _Sz>
1739constexpr bool empty(const _Tp (&__array)[_Sz]) noexcept { return false; }
1740
1741template <class _Ep>
1742constexpr bool empty(initializer_list<_Ep> __il) noexcept { return __il.size() == 0; }
1743
1744template <class _Cont> constexpr
1745auto data(_Cont& __c) -> decltype(__c.data()) { return __c.data(); }
1746
1747template <class _Cont> constexpr
1748auto data(const _Cont& __c) -> decltype(__c.data()) { return __c.data(); }
1749
1750template <class _Tp, size_t _Sz>
1751constexpr _Tp* data(_Tp (&__array)[_Sz]) noexcept { return __array; }
1752
1753template <class _Ep>
1754constexpr const _Ep* data(initializer_list<_Ep> __il) noexcept { return __il.begin(); }
1755#endif
1756
1757
1758_LIBCPP_END_NAMESPACE_STD
1759
1760#endif // _LIBCPP_ITERATOR
1761