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>
134typename reverse_iterator<Iterator1>::difference_type
135operator-(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
136
137template <class Iterator>
138reverse_iterator<Iterator>
139operator+(typename reverse_iterator<Iterator>::difference_type n, const reverse_iterator<Iterator>& x);
140
141template <class Iterator> reverse_iterator<Iterator> make_reverse_iterator(Iterator i); // C++14
142
143template <class Container>
144class back_insert_iterator
145{
146protected:
147    Container* container;
148public:
149    typedef Container                   container_type;
150    typedef void                        value_type;
151    typedef void                        difference_type;
152    typedef back_insert_iterator<Cont>& reference;
153    typedef void                        pointer;
154
155    explicit back_insert_iterator(Container& x);
156    back_insert_iterator& operator=(const typename Container::value_type& value);
157    back_insert_iterator& operator*();
158    back_insert_iterator& operator++();
159    back_insert_iterator  operator++(int);
160};
161
162template <class Container> back_insert_iterator<Container> back_inserter(Container& x);
163
164template <class Container>
165class front_insert_iterator
166{
167protected:
168    Container* container;
169public:
170    typedef Container                    container_type;
171    typedef void                         value_type;
172    typedef void                         difference_type;
173    typedef front_insert_iterator<Cont>& reference;
174    typedef void                         pointer;
175
176    explicit front_insert_iterator(Container& x);
177    front_insert_iterator& operator=(const typename Container::value_type& value);
178    front_insert_iterator& operator*();
179    front_insert_iterator& operator++();
180    front_insert_iterator  operator++(int);
181};
182
183template <class Container> front_insert_iterator<Container> front_inserter(Container& x);
184
185template <class Container>
186class insert_iterator
187{
188protected:
189    Container* container;
190    typename Container::iterator iter;
191public:
192    typedef Container              container_type;
193    typedef void                   value_type;
194    typedef void                   difference_type;
195    typedef insert_iterator<Cont>& reference;
196    typedef void                   pointer;
197
198    insert_iterator(Container& x, typename Container::iterator i);
199    insert_iterator& operator=(const typename Container::value_type& value);
200    insert_iterator& operator*();
201    insert_iterator& operator++();
202    insert_iterator& operator++(int);
203};
204
205template <class Container, class Iterator>
206insert_iterator<Container> inserter(Container& x, Iterator i);
207
208template <class T, class charT = char, class traits = char_traits<charT>, class Distance = ptrdiff_t>
209class istream_iterator
210    : public iterator<input_iterator_tag, T, Distance, const T*, const T&>
211{
212public:
213    typedef charT char_type;
214    typedef traits traits_type;
215    typedef basic_istream<charT,traits> istream_type;
216
217    istream_iterator();
218    istream_iterator(istream_type& s);
219    istream_iterator(const istream_iterator& x);
220    ~istream_iterator();
221
222    const T& operator*() const;
223    const T* operator->() const;
224    istream_iterator& operator++();
225    istream_iterator  operator++(int);
226};
227
228template <class T, class charT, class traits, class Distance>
229bool operator==(const istream_iterator<T,charT,traits,Distance>& x,
230                const istream_iterator<T,charT,traits,Distance>& y);
231template <class T, class charT, class traits, class Distance>
232bool operator!=(const istream_iterator<T,charT,traits,Distance>& x,
233                const istream_iterator<T,charT,traits,Distance>& y);
234
235template <class T, class charT = char, class traits = char_traits<charT> >
236class ostream_iterator
237    : public iterator<output_iterator_tag, void, void, void ,void>
238{
239public:
240    typedef charT char_type;
241    typedef traits traits_type;
242    typedef basic_ostream<charT,traits> ostream_type;
243
244    ostream_iterator(ostream_type& s);
245    ostream_iterator(ostream_type& s, const charT* delimiter);
246    ostream_iterator(const ostream_iterator& x);
247    ~ostream_iterator();
248    ostream_iterator& operator=(const T& value);
249
250    ostream_iterator& operator*();
251    ostream_iterator& operator++();
252    ostream_iterator& operator++(int);
253};
254
255template<class charT, class traits = char_traits<charT> >
256class istreambuf_iterator
257    : public iterator<input_iterator_tag, charT,
258                      typename traits::off_type, unspecified,
259                      charT>
260{
261public:
262    typedef charT                         char_type;
263    typedef traits                        traits_type;
264    typedef typename traits::int_type     int_type;
265    typedef basic_streambuf<charT,traits> streambuf_type;
266    typedef basic_istream<charT,traits>   istream_type;
267
268    istreambuf_iterator() noexcept;
269    istreambuf_iterator(istream_type& s) noexcept;
270    istreambuf_iterator(streambuf_type* s) noexcept;
271    istreambuf_iterator(a-private-type) noexcept;
272
273    charT                operator*() const;
274    pointer operator->() const;
275    istreambuf_iterator& operator++();
276    a-private-type       operator++(int);
277
278    bool equal(const istreambuf_iterator& b) const;
279};
280
281template <class charT, class traits>
282bool operator==(const istreambuf_iterator<charT,traits>& a,
283                const istreambuf_iterator<charT,traits>& b);
284template <class charT, class traits>
285bool operator!=(const istreambuf_iterator<charT,traits>& a,
286                const istreambuf_iterator<charT,traits>& b);
287
288template <class charT, class traits = char_traits<charT> >
289class ostreambuf_iterator
290    : public iterator<output_iterator_tag, void, void, void, void>
291{
292public:
293    typedef charT                         char_type;
294    typedef traits                        traits_type;
295    typedef basic_streambuf<charT,traits> streambuf_type;
296    typedef basic_ostream<charT,traits>   ostream_type;
297
298    ostreambuf_iterator(ostream_type& s) noexcept;
299    ostreambuf_iterator(streambuf_type* s) noexcept;
300    ostreambuf_iterator& operator=(charT c);
301    ostreambuf_iterator& operator*();
302    ostreambuf_iterator& operator++();
303    ostreambuf_iterator& operator++(int);
304    bool failed() const noexcept;
305};
306
307template <class C> auto begin(C& c) -> decltype(c.begin());
308template <class C> auto begin(const C& c) -> decltype(c.begin());
309template <class C> auto end(C& c) -> decltype(c.end());
310template <class C> auto end(const C& c) -> decltype(c.end());
311template <class T, size_t N> T* begin(T (&array)[N]);
312template <class T, size_t N> T* end(T (&array)[N]);
313
314template <class C> auto cbegin(const C& c) -> decltype(std::begin(c));        // C++14
315template <class C> auto cend(const C& c) -> decltype(std::end(c));            // C++14
316template <class C> auto rbegin(C& c) -> decltype(c.rbegin());                 // C++14
317template <class C> auto rbegin(const C& c) -> decltype(c.rbegin());           // C++14
318template <class C> auto rend(C& c) -> decltype(c.rend());                     // C++14
319template <class C> auto rend(const C& c) -> decltype(c.rend());               // C++14
320template <class E> reverse_iterator<const E*> rbegin(initializer_list<E> il); // C++14
321template <class E> reverse_iterator<const E*> rend(initializer_list<E> il);   // C++14
322template <class T, size_t N> reverse_iterator<T*> rbegin(T (&array)[N]);      // C++14
323template <class T, size_t N> reverse_iterator<T*> rend(T (&array)[N]);        // C++14
324template <class C> auto crbegin(const C& c) -> decltype(std::rbegin(c));      // C++14
325template <class C> auto crend(const C& c) -> decltype(std::rend(c));          // C++14
326
327}  // std
328
329*/
330
331#include <__config>
332#include <__functional_base>
333#include <type_traits>
334#include <cstddef>
335#include <iosfwd>
336#include <initializer_list>
337#ifdef __APPLE__
338#include <Availability.h>
339#endif
340
341#ifdef _LIBCPP_DEBUG
342#   include <__debug>
343#else
344#   define _LIBCPP_ASSERT(x, m) ((void)0)
345#endif
346
347#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
348#pragma GCC system_header
349#endif
350
351_LIBCPP_BEGIN_NAMESPACE_STD
352
353struct _LIBCPP_TYPE_VIS_ONLY input_iterator_tag {};
354struct _LIBCPP_TYPE_VIS_ONLY output_iterator_tag {};
355struct _LIBCPP_TYPE_VIS_ONLY forward_iterator_tag       : public input_iterator_tag {};
356struct _LIBCPP_TYPE_VIS_ONLY bidirectional_iterator_tag : public forward_iterator_tag {};
357struct _LIBCPP_TYPE_VIS_ONLY random_access_iterator_tag : public bidirectional_iterator_tag {};
358
359template <class _Tp>
360struct __has_iterator_category
361{
362private:
363    struct __two {char __lx; char __lxx;};
364    template <class _Up> static __two __test(...);
365    template <class _Up> static char __test(typename _Up::iterator_category* = 0);
366public:
367    static const bool value = sizeof(__test<_Tp>(0)) == 1;
368};
369
370template <class _Iter, bool> struct __iterator_traits_impl {};
371
372template <class _Iter>
373struct __iterator_traits_impl<_Iter, true>
374{
375    typedef typename _Iter::difference_type   difference_type;
376    typedef typename _Iter::value_type        value_type;
377    typedef typename _Iter::pointer           pointer;
378    typedef typename _Iter::reference         reference;
379    typedef typename _Iter::iterator_category iterator_category;
380};
381
382template <class _Iter, bool> struct __iterator_traits {};
383
384template <class _Iter>
385struct __iterator_traits<_Iter, true>
386    :  __iterator_traits_impl
387      <
388        _Iter,
389        is_convertible<typename _Iter::iterator_category, input_iterator_tag>::value ||
390        is_convertible<typename _Iter::iterator_category, output_iterator_tag>::value
391      >
392{};
393
394// iterator_traits<Iterator> will only have the nested types if Iterator::iterator_category
395//    exists.  Else iterator_traits<Iterator> will be an empty class.  This is a
396//    conforming extension which allows some programs to compile and behave as
397//    the client expects instead of failing at compile time.
398
399template <class _Iter>
400struct _LIBCPP_TYPE_VIS_ONLY iterator_traits
401    : __iterator_traits<_Iter, __has_iterator_category<_Iter>::value> {};
402
403template<class _Tp>
404struct _LIBCPP_TYPE_VIS_ONLY iterator_traits<_Tp*>
405{
406    typedef ptrdiff_t difference_type;
407    typedef typename remove_const<_Tp>::type value_type;
408    typedef _Tp* pointer;
409    typedef _Tp& reference;
410    typedef random_access_iterator_tag iterator_category;
411};
412
413template <class _Tp, class _Up, bool = __has_iterator_category<iterator_traits<_Tp> >::value>
414struct __has_iterator_category_convertible_to
415    : public integral_constant<bool, is_convertible<typename iterator_traits<_Tp>::iterator_category, _Up>::value>
416{};
417
418template <class _Tp, class _Up>
419struct __has_iterator_category_convertible_to<_Tp, _Up, false> : public false_type {};
420
421template <class _Tp>
422struct __is_input_iterator : public __has_iterator_category_convertible_to<_Tp, input_iterator_tag> {};
423
424template <class _Tp>
425struct __is_forward_iterator : public __has_iterator_category_convertible_to<_Tp, forward_iterator_tag> {};
426
427template <class _Tp>
428struct __is_bidirectional_iterator : public __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag> {};
429
430template <class _Tp>
431struct __is_random_access_iterator : public __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag> {};
432
433template<class _Category, class _Tp, class _Distance = ptrdiff_t,
434         class _Pointer = _Tp*, class _Reference = _Tp&>
435struct _LIBCPP_TYPE_VIS_ONLY iterator
436{
437    typedef _Tp        value_type;
438    typedef _Distance  difference_type;
439    typedef _Pointer   pointer;
440    typedef _Reference reference;
441    typedef _Category  iterator_category;
442};
443
444template <class _InputIter>
445inline _LIBCPP_INLINE_VISIBILITY
446void __advance(_InputIter& __i,
447             typename iterator_traits<_InputIter>::difference_type __n, input_iterator_tag)
448{
449    for (; __n > 0; --__n)
450        ++__i;
451}
452
453template <class _BiDirIter>
454inline _LIBCPP_INLINE_VISIBILITY
455void __advance(_BiDirIter& __i,
456             typename iterator_traits<_BiDirIter>::difference_type __n, bidirectional_iterator_tag)
457{
458    if (__n >= 0)
459        for (; __n > 0; --__n)
460            ++__i;
461    else
462        for (; __n < 0; ++__n)
463            --__i;
464}
465
466template <class _RandIter>
467inline _LIBCPP_INLINE_VISIBILITY
468void __advance(_RandIter& __i,
469             typename iterator_traits<_RandIter>::difference_type __n, random_access_iterator_tag)
470{
471   __i += __n;
472}
473
474template <class _InputIter>
475inline _LIBCPP_INLINE_VISIBILITY
476void advance(_InputIter& __i,
477             typename iterator_traits<_InputIter>::difference_type __n)
478{
479    __advance(__i, __n, typename iterator_traits<_InputIter>::iterator_category());
480}
481
482template <class _InputIter>
483inline _LIBCPP_INLINE_VISIBILITY
484typename iterator_traits<_InputIter>::difference_type
485__distance(_InputIter __first, _InputIter __last, input_iterator_tag)
486{
487    typename iterator_traits<_InputIter>::difference_type __r(0);
488    for (; __first != __last; ++__first)
489        ++__r;
490    return __r;
491}
492
493template <class _RandIter>
494inline _LIBCPP_INLINE_VISIBILITY
495typename iterator_traits<_RandIter>::difference_type
496__distance(_RandIter __first, _RandIter __last, random_access_iterator_tag)
497{
498    return __last - __first;
499}
500
501template <class _InputIter>
502inline _LIBCPP_INLINE_VISIBILITY
503typename iterator_traits<_InputIter>::difference_type
504distance(_InputIter __first, _InputIter __last)
505{
506    return __distance(__first, __last, typename iterator_traits<_InputIter>::iterator_category());
507}
508
509template <class _ForwardIter>
510inline _LIBCPP_INLINE_VISIBILITY
511_ForwardIter
512next(_ForwardIter __x,
513     typename iterator_traits<_ForwardIter>::difference_type __n = 1,
514     typename enable_if<__is_forward_iterator<_ForwardIter>::value>::type* = 0)
515{
516    _VSTD::advance(__x, __n);
517    return __x;
518}
519
520template <class _BidiretionalIter>
521inline _LIBCPP_INLINE_VISIBILITY
522_BidiretionalIter
523prev(_BidiretionalIter __x,
524     typename iterator_traits<_BidiretionalIter>::difference_type __n = 1,
525     typename enable_if<__is_bidirectional_iterator<_BidiretionalIter>::value>::type* = 0)
526{
527    _VSTD::advance(__x, -__n);
528    return __x;
529}
530
531template <class _Iter>
532class _LIBCPP_TYPE_VIS_ONLY reverse_iterator
533    : public iterator<typename iterator_traits<_Iter>::iterator_category,
534                      typename iterator_traits<_Iter>::value_type,
535                      typename iterator_traits<_Iter>::difference_type,
536                      typename iterator_traits<_Iter>::pointer,
537                      typename iterator_traits<_Iter>::reference>
538{
539private:
540    mutable _Iter __t;  // no longer used as of LWG #2360, not removed due to ABI break
541protected:
542    _Iter current;
543public:
544    typedef _Iter                                            iterator_type;
545    typedef typename iterator_traits<_Iter>::difference_type difference_type;
546    typedef typename iterator_traits<_Iter>::reference       reference;
547    typedef typename iterator_traits<_Iter>::pointer         pointer;
548
549    _LIBCPP_INLINE_VISIBILITY reverse_iterator() : current() {}
550    _LIBCPP_INLINE_VISIBILITY explicit reverse_iterator(_Iter __x) : __t(__x), current(__x) {}
551    template <class _Up> _LIBCPP_INLINE_VISIBILITY reverse_iterator(const reverse_iterator<_Up>& __u)
552        : __t(__u.base()), current(__u.base()) {}
553    _LIBCPP_INLINE_VISIBILITY _Iter base() const {return current;}
554    _LIBCPP_INLINE_VISIBILITY reference operator*() const {_Iter __tmp = current; return *--__tmp;}
555    _LIBCPP_INLINE_VISIBILITY pointer  operator->() const {return _VSTD::addressof(operator*());}
556    _LIBCPP_INLINE_VISIBILITY reverse_iterator& operator++() {--current; return *this;}
557    _LIBCPP_INLINE_VISIBILITY reverse_iterator  operator++(int)
558        {reverse_iterator __tmp(*this); --current; return __tmp;}
559    _LIBCPP_INLINE_VISIBILITY reverse_iterator& operator--() {++current; return *this;}
560    _LIBCPP_INLINE_VISIBILITY reverse_iterator  operator--(int)
561        {reverse_iterator __tmp(*this); ++current; return __tmp;}
562    _LIBCPP_INLINE_VISIBILITY reverse_iterator  operator+ (difference_type __n) const
563        {return reverse_iterator(current - __n);}
564    _LIBCPP_INLINE_VISIBILITY reverse_iterator& operator+=(difference_type __n)
565        {current -= __n; return *this;}
566    _LIBCPP_INLINE_VISIBILITY reverse_iterator  operator- (difference_type __n) const
567        {return reverse_iterator(current + __n);}
568    _LIBCPP_INLINE_VISIBILITY reverse_iterator& operator-=(difference_type __n)
569        {current += __n; return *this;}
570    _LIBCPP_INLINE_VISIBILITY reference         operator[](difference_type __n) const
571        {return current[-__n-1];}
572};
573
574template <class _Iter1, class _Iter2>
575inline _LIBCPP_INLINE_VISIBILITY
576bool
577operator==(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
578{
579    return __x.base() == __y.base();
580}
581
582template <class _Iter1, class _Iter2>
583inline _LIBCPP_INLINE_VISIBILITY
584bool
585operator<(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
586{
587    return __x.base() > __y.base();
588}
589
590template <class _Iter1, class _Iter2>
591inline _LIBCPP_INLINE_VISIBILITY
592bool
593operator!=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
594{
595    return __x.base() != __y.base();
596}
597
598template <class _Iter1, class _Iter2>
599inline _LIBCPP_INLINE_VISIBILITY
600bool
601operator>(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
602{
603    return __x.base() < __y.base();
604}
605
606template <class _Iter1, class _Iter2>
607inline _LIBCPP_INLINE_VISIBILITY
608bool
609operator>=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
610{
611    return __x.base() <= __y.base();
612}
613
614template <class _Iter1, class _Iter2>
615inline _LIBCPP_INLINE_VISIBILITY
616bool
617operator<=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
618{
619    return __x.base() >= __y.base();
620}
621
622template <class _Iter1, class _Iter2>
623inline _LIBCPP_INLINE_VISIBILITY
624typename reverse_iterator<_Iter1>::difference_type
625operator-(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
626{
627    return __y.base() - __x.base();
628}
629
630template <class _Iter>
631inline _LIBCPP_INLINE_VISIBILITY
632reverse_iterator<_Iter>
633operator+(typename reverse_iterator<_Iter>::difference_type __n, const reverse_iterator<_Iter>& __x)
634{
635    return reverse_iterator<_Iter>(__x.base() - __n);
636}
637
638#if _LIBCPP_STD_VER > 11
639template <class _Iter>
640inline _LIBCPP_INLINE_VISIBILITY
641reverse_iterator<_Iter> make_reverse_iterator(_Iter __i)
642{
643    return reverse_iterator<_Iter>(__i);
644}
645#endif
646
647template <class _Container>
648class _LIBCPP_TYPE_VIS_ONLY back_insert_iterator
649    : public iterator<output_iterator_tag,
650                      void,
651                      void,
652                      void,
653                      back_insert_iterator<_Container>&>
654{
655protected:
656    _Container* container;
657public:
658    typedef _Container container_type;
659
660    _LIBCPP_INLINE_VISIBILITY explicit back_insert_iterator(_Container& __x) : container(_VSTD::addressof(__x)) {}
661    _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator=(const typename _Container::value_type& __value_)
662        {container->push_back(__value_); return *this;}
663#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
664    _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator=(typename _Container::value_type&& __value_)
665        {container->push_back(_VSTD::move(__value_)); return *this;}
666#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
667    _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator*()     {return *this;}
668    _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator++()    {return *this;}
669    _LIBCPP_INLINE_VISIBILITY back_insert_iterator  operator++(int) {return *this;}
670};
671
672template <class _Container>
673inline _LIBCPP_INLINE_VISIBILITY
674back_insert_iterator<_Container>
675back_inserter(_Container& __x)
676{
677    return back_insert_iterator<_Container>(__x);
678}
679
680template <class _Container>
681class _LIBCPP_TYPE_VIS_ONLY front_insert_iterator
682    : public iterator<output_iterator_tag,
683                      void,
684                      void,
685                      void,
686                      front_insert_iterator<_Container>&>
687{
688protected:
689    _Container* container;
690public:
691    typedef _Container container_type;
692
693    _LIBCPP_INLINE_VISIBILITY explicit front_insert_iterator(_Container& __x) : container(_VSTD::addressof(__x)) {}
694    _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator=(const typename _Container::value_type& __value_)
695        {container->push_front(__value_); return *this;}
696#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
697    _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator=(typename _Container::value_type&& __value_)
698        {container->push_front(_VSTD::move(__value_)); return *this;}
699#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
700    _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator*()     {return *this;}
701    _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator++()    {return *this;}
702    _LIBCPP_INLINE_VISIBILITY front_insert_iterator  operator++(int) {return *this;}
703};
704
705template <class _Container>
706inline _LIBCPP_INLINE_VISIBILITY
707front_insert_iterator<_Container>
708front_inserter(_Container& __x)
709{
710    return front_insert_iterator<_Container>(__x);
711}
712
713template <class _Container>
714class _LIBCPP_TYPE_VIS_ONLY insert_iterator
715    : public iterator<output_iterator_tag,
716                      void,
717                      void,
718                      void,
719                      insert_iterator<_Container>&>
720{
721protected:
722    _Container* container;
723    typename _Container::iterator iter;
724public:
725    typedef _Container container_type;
726
727    _LIBCPP_INLINE_VISIBILITY insert_iterator(_Container& __x, typename _Container::iterator __i)
728        : container(_VSTD::addressof(__x)), iter(__i) {}
729    _LIBCPP_INLINE_VISIBILITY insert_iterator& operator=(const typename _Container::value_type& __value_)
730        {iter = container->insert(iter, __value_); ++iter; return *this;}
731#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
732    _LIBCPP_INLINE_VISIBILITY insert_iterator& operator=(typename _Container::value_type&& __value_)
733        {iter = container->insert(iter, _VSTD::move(__value_)); ++iter; return *this;}
734#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
735    _LIBCPP_INLINE_VISIBILITY insert_iterator& operator*()        {return *this;}
736    _LIBCPP_INLINE_VISIBILITY insert_iterator& operator++()       {return *this;}
737    _LIBCPP_INLINE_VISIBILITY insert_iterator& operator++(int)    {return *this;}
738};
739
740template <class _Container>
741inline _LIBCPP_INLINE_VISIBILITY
742insert_iterator<_Container>
743inserter(_Container& __x, typename _Container::iterator __i)
744{
745    return insert_iterator<_Container>(__x, __i);
746}
747
748template <class _Tp, class _CharT = char,
749          class _Traits = char_traits<_CharT>, class _Distance = ptrdiff_t>
750class _LIBCPP_TYPE_VIS_ONLY istream_iterator
751    : public iterator<input_iterator_tag, _Tp, _Distance, const _Tp*, const _Tp&>
752{
753public:
754    typedef _CharT char_type;
755    typedef _Traits traits_type;
756    typedef basic_istream<_CharT,_Traits> istream_type;
757private:
758    istream_type* __in_stream_;
759    _Tp __value_;
760public:
761    _LIBCPP_INLINE_VISIBILITY istream_iterator() : __in_stream_(0) {}
762    _LIBCPP_INLINE_VISIBILITY istream_iterator(istream_type& __s) : __in_stream_(&__s)
763        {
764            if (!(*__in_stream_ >> __value_))
765                __in_stream_ = 0;
766        }
767
768    _LIBCPP_INLINE_VISIBILITY const _Tp& operator*() const {return __value_;}
769    _LIBCPP_INLINE_VISIBILITY const _Tp* operator->() const {return &(operator*());}
770    _LIBCPP_INLINE_VISIBILITY istream_iterator& operator++()
771        {
772            if (!(*__in_stream_ >> __value_))
773                __in_stream_ = 0;
774            return *this;
775        }
776    _LIBCPP_INLINE_VISIBILITY istream_iterator  operator++(int)
777        {istream_iterator __t(*this); ++(*this); return __t;}
778
779    friend _LIBCPP_INLINE_VISIBILITY
780    bool operator==(const istream_iterator& __x, const istream_iterator& __y)
781        {return __x.__in_stream_ == __y.__in_stream_;}
782
783    friend _LIBCPP_INLINE_VISIBILITY
784    bool operator!=(const istream_iterator& __x, const istream_iterator& __y)
785        {return !(__x == __y);}
786};
787
788template <class _Tp, class _CharT = char, class _Traits = char_traits<_CharT> >
789class _LIBCPP_TYPE_VIS_ONLY ostream_iterator
790    : public iterator<output_iterator_tag, void, void, void, void>
791{
792public:
793    typedef _CharT char_type;
794    typedef _Traits traits_type;
795    typedef basic_ostream<_CharT,_Traits> ostream_type;
796private:
797    ostream_type* __out_stream_;
798    const char_type* __delim_;
799public:
800    _LIBCPP_INLINE_VISIBILITY ostream_iterator(ostream_type& __s)
801        : __out_stream_(&__s), __delim_(0) {}
802    _LIBCPP_INLINE_VISIBILITY ostream_iterator(ostream_type& __s, const _CharT* __delimiter)
803        : __out_stream_(&__s), __delim_(__delimiter) {}
804    _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator=(const _Tp& __value_)
805        {
806            *__out_stream_ << __value_;
807            if (__delim_)
808                *__out_stream_ << __delim_;
809            return *this;
810        }
811
812    _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator*()     {return *this;}
813    _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator++()    {return *this;}
814    _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator++(int) {return *this;}
815};
816
817template<class _CharT, class _Traits>
818class _LIBCPP_TYPE_VIS_ONLY istreambuf_iterator
819    : public iterator<input_iterator_tag, _CharT,
820                      typename _Traits::off_type, _CharT*,
821                      _CharT>
822{
823public:
824    typedef _CharT                          char_type;
825    typedef _Traits                         traits_type;
826    typedef typename _Traits::int_type      int_type;
827    typedef basic_streambuf<_CharT,_Traits> streambuf_type;
828    typedef basic_istream<_CharT,_Traits>   istream_type;
829private:
830    mutable streambuf_type* __sbuf_;
831
832    class __proxy
833    {
834        char_type __keep_;
835        streambuf_type* __sbuf_;
836        _LIBCPP_INLINE_VISIBILITY __proxy(char_type __c, streambuf_type* __s)
837            : __keep_(__c), __sbuf_(__s) {}
838        friend class istreambuf_iterator;
839    public:
840        _LIBCPP_INLINE_VISIBILITY char_type operator*() const {return __keep_;}
841    };
842
843    _LIBCPP_INLINE_VISIBILITY
844    bool __test_for_eof() const
845    {
846        if (__sbuf_ && traits_type::eq_int_type(__sbuf_->sgetc(), traits_type::eof()))
847            __sbuf_ = 0;
848        return __sbuf_ == 0;
849    }
850public:
851    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR istreambuf_iterator() _NOEXCEPT : __sbuf_(0) {}
852    _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(istream_type& __s) _NOEXCEPT
853        : __sbuf_(__s.rdbuf()) {}
854    _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(streambuf_type* __s) _NOEXCEPT
855        : __sbuf_(__s) {}
856    _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(const __proxy& __p) _NOEXCEPT
857        : __sbuf_(__p.__sbuf_) {}
858
859    _LIBCPP_INLINE_VISIBILITY char_type  operator*() const
860        {return static_cast<char_type>(__sbuf_->sgetc());}
861    _LIBCPP_INLINE_VISIBILITY char_type* operator->() const {return nullptr;}
862    _LIBCPP_INLINE_VISIBILITY istreambuf_iterator& operator++()
863        {
864            __sbuf_->sbumpc();
865            return *this;
866        }
867    _LIBCPP_INLINE_VISIBILITY __proxy              operator++(int)
868        {
869            return __proxy(__sbuf_->sbumpc(), __sbuf_);
870        }
871
872    _LIBCPP_INLINE_VISIBILITY bool equal(const istreambuf_iterator& __b) const
873        {return __test_for_eof() == __b.__test_for_eof();}
874};
875
876template <class _CharT, class _Traits>
877inline _LIBCPP_INLINE_VISIBILITY
878bool operator==(const istreambuf_iterator<_CharT,_Traits>& __a,
879                const istreambuf_iterator<_CharT,_Traits>& __b)
880                {return __a.equal(__b);}
881
882template <class _CharT, class _Traits>
883inline _LIBCPP_INLINE_VISIBILITY
884bool operator!=(const istreambuf_iterator<_CharT,_Traits>& __a,
885                const istreambuf_iterator<_CharT,_Traits>& __b)
886                {return !__a.equal(__b);}
887
888template <class _CharT, class _Traits>
889class _LIBCPP_TYPE_VIS_ONLY ostreambuf_iterator
890    : public iterator<output_iterator_tag, void, void, void, void>
891{
892public:
893    typedef _CharT                          char_type;
894    typedef _Traits                         traits_type;
895    typedef basic_streambuf<_CharT,_Traits> streambuf_type;
896    typedef basic_ostream<_CharT,_Traits>   ostream_type;
897private:
898    streambuf_type* __sbuf_;
899public:
900    _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator(ostream_type& __s) _NOEXCEPT
901        : __sbuf_(__s.rdbuf()) {}
902    _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator(streambuf_type* __s) _NOEXCEPT
903        : __sbuf_(__s) {}
904    _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator=(_CharT __c)
905        {
906            if (__sbuf_ && traits_type::eq_int_type(__sbuf_->sputc(__c), traits_type::eof()))
907                __sbuf_ = 0;
908            return *this;
909        }
910    _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator*()     {return *this;}
911    _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator++()    {return *this;}
912    _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator++(int) {return *this;}
913    _LIBCPP_INLINE_VISIBILITY bool failed() const _NOEXCEPT {return __sbuf_ == 0;}
914
915#if !defined(__APPLE__) || \
916    (defined(__MAC_OS_X_VERSION_MIN_REQUIRED) && __MAC_OS_X_VERSION_MIN_REQUIRED > __MAC_10_8) || \
917    (defined(__IPHONE_OS_VERSION_MIN_REQUIRED) && __IPHONE_OS_VERSION_MIN_REQUIRED > __IPHONE_6_0)
918
919    template <class _Ch, class _Tr>
920    friend
921    _LIBCPP_HIDDEN
922    ostreambuf_iterator<_Ch, _Tr>
923    __pad_and_output(ostreambuf_iterator<_Ch, _Tr> __s,
924                     const _Ch* __ob, const _Ch* __op, const _Ch* __oe,
925                     ios_base& __iob, _Ch __fl);
926#endif
927};
928
929template <class _Iter>
930class _LIBCPP_TYPE_VIS_ONLY move_iterator
931{
932private:
933    _Iter __i;
934public:
935    typedef _Iter                                            iterator_type;
936    typedef typename iterator_traits<iterator_type>::iterator_category iterator_category;
937    typedef typename iterator_traits<iterator_type>::value_type value_type;
938    typedef typename iterator_traits<iterator_type>::difference_type difference_type;
939    typedef typename iterator_traits<iterator_type>::pointer pointer;
940#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
941    typedef value_type&& reference;
942#else
943    typedef typename iterator_traits<iterator_type>::reference reference;
944#endif
945
946    _LIBCPP_INLINE_VISIBILITY move_iterator() : __i() {}
947    _LIBCPP_INLINE_VISIBILITY explicit move_iterator(_Iter __x) : __i(__x) {}
948    template <class _Up> _LIBCPP_INLINE_VISIBILITY move_iterator(const move_iterator<_Up>& __u)
949        : __i(__u.base()) {}
950    _LIBCPP_INLINE_VISIBILITY _Iter base() const {return __i;}
951    _LIBCPP_INLINE_VISIBILITY reference operator*() const {
952      return static_cast<reference>(*__i);
953    }
954    _LIBCPP_INLINE_VISIBILITY pointer  operator->() const {
955      typename iterator_traits<iterator_type>::reference __ref = *__i;
956      return &__ref;
957    }
958    _LIBCPP_INLINE_VISIBILITY move_iterator& operator++() {++__i; return *this;}
959    _LIBCPP_INLINE_VISIBILITY move_iterator  operator++(int)
960        {move_iterator __tmp(*this); ++__i; return __tmp;}
961    _LIBCPP_INLINE_VISIBILITY move_iterator& operator--() {--__i; return *this;}
962    _LIBCPP_INLINE_VISIBILITY move_iterator  operator--(int)
963        {move_iterator __tmp(*this); --__i; return __tmp;}
964    _LIBCPP_INLINE_VISIBILITY move_iterator  operator+ (difference_type __n) const
965        {return move_iterator(__i + __n);}
966    _LIBCPP_INLINE_VISIBILITY move_iterator& operator+=(difference_type __n)
967        {__i += __n; return *this;}
968    _LIBCPP_INLINE_VISIBILITY move_iterator  operator- (difference_type __n) const
969        {return move_iterator(__i - __n);}
970    _LIBCPP_INLINE_VISIBILITY move_iterator& operator-=(difference_type __n)
971        {__i -= __n; return *this;}
972    _LIBCPP_INLINE_VISIBILITY reference         operator[](difference_type __n) const
973    {
974      return static_cast<reference>(__i[__n]);
975    }
976};
977
978template <class _Iter1, class _Iter2>
979inline _LIBCPP_INLINE_VISIBILITY
980bool
981operator==(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
982{
983    return __x.base() == __y.base();
984}
985
986template <class _Iter1, class _Iter2>
987inline _LIBCPP_INLINE_VISIBILITY
988bool
989operator<(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
990{
991    return __x.base() < __y.base();
992}
993
994template <class _Iter1, class _Iter2>
995inline _LIBCPP_INLINE_VISIBILITY
996bool
997operator!=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
998{
999    return __x.base() != __y.base();
1000}
1001
1002template <class _Iter1, class _Iter2>
1003inline _LIBCPP_INLINE_VISIBILITY
1004bool
1005operator>(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1006{
1007    return __x.base() > __y.base();
1008}
1009
1010template <class _Iter1, class _Iter2>
1011inline _LIBCPP_INLINE_VISIBILITY
1012bool
1013operator>=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1014{
1015    return __x.base() >= __y.base();
1016}
1017
1018template <class _Iter1, class _Iter2>
1019inline _LIBCPP_INLINE_VISIBILITY
1020bool
1021operator<=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1022{
1023    return __x.base() <= __y.base();
1024}
1025
1026template <class _Iter1, class _Iter2>
1027inline _LIBCPP_INLINE_VISIBILITY
1028typename move_iterator<_Iter1>::difference_type
1029operator-(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1030{
1031    return __x.base() - __y.base();
1032}
1033
1034template <class _Iter>
1035inline _LIBCPP_INLINE_VISIBILITY
1036move_iterator<_Iter>
1037operator+(typename move_iterator<_Iter>::difference_type __n, const move_iterator<_Iter>& __x)
1038{
1039    return move_iterator<_Iter>(__x.base() + __n);
1040}
1041
1042template <class _Iter>
1043inline _LIBCPP_INLINE_VISIBILITY
1044move_iterator<_Iter>
1045make_move_iterator(_Iter __i)
1046{
1047    return move_iterator<_Iter>(__i);
1048}
1049
1050// __wrap_iter
1051
1052template <class _Iter> class __wrap_iter;
1053
1054template <class _Iter1, class _Iter2>
1055_LIBCPP_INLINE_VISIBILITY
1056bool
1057operator==(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1058
1059template <class _Iter1, class _Iter2>
1060_LIBCPP_INLINE_VISIBILITY
1061bool
1062operator<(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1063
1064template <class _Iter1, class _Iter2>
1065_LIBCPP_INLINE_VISIBILITY
1066bool
1067operator!=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1068
1069template <class _Iter1, class _Iter2>
1070_LIBCPP_INLINE_VISIBILITY
1071bool
1072operator>(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1073
1074template <class _Iter1, class _Iter2>
1075_LIBCPP_INLINE_VISIBILITY
1076bool
1077operator>=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1078
1079template <class _Iter1, class _Iter2>
1080_LIBCPP_INLINE_VISIBILITY
1081bool
1082operator<=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1083
1084template <class _Iter1, class _Iter2>
1085_LIBCPP_INLINE_VISIBILITY
1086typename __wrap_iter<_Iter1>::difference_type
1087operator-(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1088
1089template <class _Iter>
1090_LIBCPP_INLINE_VISIBILITY
1091__wrap_iter<_Iter>
1092operator+(typename __wrap_iter<_Iter>::difference_type, __wrap_iter<_Iter>) _NOEXCEPT;
1093
1094template <class _Ip, class _Op> _Op _LIBCPP_INLINE_VISIBILITY copy(_Ip, _Ip, _Op);
1095template <class _B1, class _B2> _B2 _LIBCPP_INLINE_VISIBILITY copy_backward(_B1, _B1, _B2);
1096template <class _Ip, class _Op> _Op _LIBCPP_INLINE_VISIBILITY move(_Ip, _Ip, _Op);
1097template <class _B1, class _B2> _B2 _LIBCPP_INLINE_VISIBILITY move_backward(_B1, _B1, _B2);
1098
1099template <class _Tp>
1100_LIBCPP_INLINE_VISIBILITY
1101typename enable_if
1102<
1103    is_trivially_copy_assignable<_Tp>::value,
1104    _Tp*
1105>::type
1106__unwrap_iter(__wrap_iter<_Tp*>);
1107
1108template <class _Tp, class _Alloc> class _LIBCPP_TYPE_VIS_ONLY vector;
1109
1110template <class _Iter>
1111class __wrap_iter
1112{
1113public:
1114    typedef _Iter                                                      iterator_type;
1115    typedef typename iterator_traits<iterator_type>::iterator_category iterator_category;
1116    typedef typename iterator_traits<iterator_type>::value_type        value_type;
1117    typedef typename iterator_traits<iterator_type>::difference_type   difference_type;
1118    typedef typename iterator_traits<iterator_type>::pointer           pointer;
1119    typedef typename iterator_traits<iterator_type>::reference         reference;
1120private:
1121    iterator_type __i;
1122public:
1123    _LIBCPP_INLINE_VISIBILITY __wrap_iter() _NOEXCEPT
1124#if _LIBCPP_STD_VER > 11
1125                : __i{}
1126#endif
1127    {
1128#if _LIBCPP_DEBUG_LEVEL >= 2
1129        __get_db()->__insert_i(this);
1130#endif
1131    }
1132    template <class _Up> _LIBCPP_INLINE_VISIBILITY __wrap_iter(const __wrap_iter<_Up>& __u,
1133        typename enable_if<is_convertible<_Up, iterator_type>::value>::type* = 0) _NOEXCEPT
1134        : __i(__u.base())
1135    {
1136#if _LIBCPP_DEBUG_LEVEL >= 2
1137        __get_db()->__iterator_copy(this, &__u);
1138#endif
1139    }
1140#if _LIBCPP_DEBUG_LEVEL >= 2
1141    _LIBCPP_INLINE_VISIBILITY
1142    __wrap_iter(const __wrap_iter& __x)
1143        : __i(__x.base())
1144    {
1145        __get_db()->__iterator_copy(this, &__x);
1146    }
1147    _LIBCPP_INLINE_VISIBILITY
1148    __wrap_iter& operator=(const __wrap_iter& __x)
1149    {
1150        if (this != &__x)
1151        {
1152            __get_db()->__iterator_copy(this, &__x);
1153            __i = __x.__i;
1154        }
1155        return *this;
1156    }
1157    _LIBCPP_INLINE_VISIBILITY
1158    ~__wrap_iter()
1159    {
1160        __get_db()->__erase_i(this);
1161    }
1162#endif
1163    _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT
1164    {
1165#if _LIBCPP_DEBUG_LEVEL >= 2
1166        _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
1167                       "Attempted to dereference a non-dereferenceable iterator");
1168#endif
1169        return *__i;
1170    }
1171    _LIBCPP_INLINE_VISIBILITY pointer  operator->() const _NOEXCEPT
1172    {
1173#if _LIBCPP_DEBUG_LEVEL >= 2
1174        _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
1175                       "Attempted to dereference a non-dereferenceable iterator");
1176#endif
1177        return (pointer)&reinterpret_cast<const volatile char&>(*__i);
1178    }
1179    _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator++() _NOEXCEPT
1180    {
1181#if _LIBCPP_DEBUG_LEVEL >= 2
1182        _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
1183                       "Attempted to increment non-incrementable iterator");
1184#endif
1185        ++__i;
1186        return *this;
1187    }
1188    _LIBCPP_INLINE_VISIBILITY __wrap_iter  operator++(int) _NOEXCEPT
1189        {__wrap_iter __tmp(*this); ++(*this); return __tmp;}
1190    _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator--() _NOEXCEPT
1191    {
1192#if _LIBCPP_DEBUG_LEVEL >= 2
1193        _LIBCPP_ASSERT(__get_const_db()->__decrementable(this),
1194                       "Attempted to decrement non-decrementable iterator");
1195#endif
1196        --__i;
1197        return *this;
1198    }
1199    _LIBCPP_INLINE_VISIBILITY __wrap_iter  operator--(int) _NOEXCEPT
1200        {__wrap_iter __tmp(*this); --(*this); return __tmp;}
1201    _LIBCPP_INLINE_VISIBILITY __wrap_iter  operator+ (difference_type __n) const _NOEXCEPT
1202        {__wrap_iter __w(*this); __w += __n; return __w;}
1203    _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator+=(difference_type __n) _NOEXCEPT
1204    {
1205#if _LIBCPP_DEBUG_LEVEL >= 2
1206        _LIBCPP_ASSERT(__get_const_db()->__addable(this, __n),
1207                   "Attempted to add/subtract iterator outside of valid range");
1208#endif
1209        __i += __n;
1210        return *this;
1211    }
1212    _LIBCPP_INLINE_VISIBILITY __wrap_iter  operator- (difference_type __n) const _NOEXCEPT
1213        {return *this + (-__n);}
1214    _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator-=(difference_type __n) _NOEXCEPT
1215        {*this += -__n; return *this;}
1216    _LIBCPP_INLINE_VISIBILITY reference        operator[](difference_type __n) const _NOEXCEPT
1217    {
1218#if _LIBCPP_DEBUG_LEVEL >= 2
1219        _LIBCPP_ASSERT(__get_const_db()->__subscriptable(this, __n),
1220                   "Attempted to subscript iterator outside of valid range");
1221#endif
1222        return __i[__n];
1223    }
1224
1225    _LIBCPP_INLINE_VISIBILITY iterator_type base() const _NOEXCEPT {return __i;}
1226
1227private:
1228#if _LIBCPP_DEBUG_LEVEL >= 2
1229    _LIBCPP_INLINE_VISIBILITY __wrap_iter(const void* __p, iterator_type __x) : __i(__x)
1230    {
1231        __get_db()->__insert_ic(this, __p);
1232    }
1233#else
1234    _LIBCPP_INLINE_VISIBILITY __wrap_iter(iterator_type __x) _NOEXCEPT : __i(__x) {}
1235#endif
1236
1237    template <class _Up> friend class __wrap_iter;
1238    template <class _CharT, class _Traits, class _Alloc> friend class basic_string;
1239    template <class _Tp, class _Alloc> friend class vector;
1240
1241    template <class _Iter1, class _Iter2>
1242    friend
1243    bool
1244    operator==(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1245
1246    template <class _Iter1, class _Iter2>
1247    friend
1248    bool
1249    operator<(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1250
1251    template <class _Iter1, class _Iter2>
1252    friend
1253    bool
1254    operator!=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1255
1256    template <class _Iter1, class _Iter2>
1257    friend
1258    bool
1259    operator>(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1260
1261    template <class _Iter1, class _Iter2>
1262    friend
1263    bool
1264    operator>=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1265
1266    template <class _Iter1, class _Iter2>
1267    friend
1268    bool
1269    operator<=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1270
1271    template <class _Iter1, class _Iter2>
1272    friend
1273    typename __wrap_iter<_Iter1>::difference_type
1274    operator-(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1275
1276    template <class _Iter1>
1277    friend
1278    __wrap_iter<_Iter1>
1279    operator+(typename __wrap_iter<_Iter1>::difference_type, __wrap_iter<_Iter1>) _NOEXCEPT;
1280
1281    template <class _Ip, class _Op> friend _Op copy(_Ip, _Ip, _Op);
1282    template <class _B1, class _B2> friend _B2 copy_backward(_B1, _B1, _B2);
1283    template <class _Ip, class _Op> friend _Op move(_Ip, _Ip, _Op);
1284    template <class _B1, class _B2> friend _B2 move_backward(_B1, _B1, _B2);
1285
1286    template <class _Tp>
1287    friend
1288    typename enable_if
1289    <
1290        is_trivially_copy_assignable<_Tp>::value,
1291        _Tp*
1292    >::type
1293    __unwrap_iter(__wrap_iter<_Tp*>);
1294};
1295
1296template <class _Iter1, class _Iter2>
1297inline _LIBCPP_INLINE_VISIBILITY
1298bool
1299operator==(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1300{
1301    return __x.base() == __y.base();
1302}
1303
1304template <class _Iter1, class _Iter2>
1305inline _LIBCPP_INLINE_VISIBILITY
1306bool
1307operator<(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1308{
1309#if _LIBCPP_DEBUG_LEVEL >= 2
1310    _LIBCPP_ASSERT(__get_const_db()->__less_than_comparable(&__x, &__y),
1311                   "Attempted to compare incomparable iterators");
1312#endif
1313    return __x.base() < __y.base();
1314}
1315
1316template <class _Iter1, class _Iter2>
1317inline _LIBCPP_INLINE_VISIBILITY
1318bool
1319operator!=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1320{
1321    return !(__x == __y);
1322}
1323
1324template <class _Iter1, class _Iter2>
1325inline _LIBCPP_INLINE_VISIBILITY
1326bool
1327operator>(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1328{
1329    return __y < __x;
1330}
1331
1332template <class _Iter1, class _Iter2>
1333inline _LIBCPP_INLINE_VISIBILITY
1334bool
1335operator>=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1336{
1337    return !(__x < __y);
1338}
1339
1340template <class _Iter1, class _Iter2>
1341inline _LIBCPP_INLINE_VISIBILITY
1342bool
1343operator<=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1344{
1345    return !(__y < __x);
1346}
1347
1348template <class _Iter1>
1349inline _LIBCPP_INLINE_VISIBILITY
1350bool
1351operator!=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT
1352{
1353    return !(__x == __y);
1354}
1355
1356template <class _Iter1>
1357inline _LIBCPP_INLINE_VISIBILITY
1358bool
1359operator>(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT
1360{
1361    return __y < __x;
1362}
1363
1364template <class _Iter1>
1365inline _LIBCPP_INLINE_VISIBILITY
1366bool
1367operator>=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT
1368{
1369    return !(__x < __y);
1370}
1371
1372template <class _Iter1>
1373inline _LIBCPP_INLINE_VISIBILITY
1374bool
1375operator<=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT
1376{
1377    return !(__y < __x);
1378}
1379
1380template <class _Iter1, class _Iter2>
1381inline _LIBCPP_INLINE_VISIBILITY
1382typename __wrap_iter<_Iter1>::difference_type
1383operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1384{
1385#if _LIBCPP_DEBUG_LEVEL >= 2
1386    _LIBCPP_ASSERT(__get_const_db()->__less_than_comparable(&__x, &__y),
1387                   "Attempted to subtract incompatible iterators");
1388#endif
1389    return __x.base() - __y.base();
1390}
1391
1392template <class _Iter>
1393inline _LIBCPP_INLINE_VISIBILITY
1394__wrap_iter<_Iter>
1395operator+(typename __wrap_iter<_Iter>::difference_type __n,
1396          __wrap_iter<_Iter> __x) _NOEXCEPT
1397{
1398    __x += __n;
1399    return __x;
1400}
1401
1402template <class _Tp, size_t _Np>
1403inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
1404_Tp*
1405begin(_Tp (&__array)[_Np])
1406{
1407    return __array;
1408}
1409
1410template <class _Tp, size_t _Np>
1411inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
1412_Tp*
1413end(_Tp (&__array)[_Np])
1414{
1415    return __array + _Np;
1416}
1417
1418#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_TRAILING_RETURN)
1419
1420template <class _Cp>
1421inline _LIBCPP_INLINE_VISIBILITY
1422auto
1423begin(_Cp& __c) -> decltype(__c.begin())
1424{
1425    return __c.begin();
1426}
1427
1428template <class _Cp>
1429inline _LIBCPP_INLINE_VISIBILITY
1430auto
1431begin(const _Cp& __c) -> decltype(__c.begin())
1432{
1433    return __c.begin();
1434}
1435
1436template <class _Cp>
1437inline _LIBCPP_INLINE_VISIBILITY
1438auto
1439end(_Cp& __c) -> decltype(__c.end())
1440{
1441    return __c.end();
1442}
1443
1444template <class _Cp>
1445inline _LIBCPP_INLINE_VISIBILITY
1446auto
1447end(const _Cp& __c) -> decltype(__c.end())
1448{
1449    return __c.end();
1450}
1451
1452#if _LIBCPP_STD_VER > 11
1453
1454template <class _Tp, size_t _Np>
1455inline _LIBCPP_INLINE_VISIBILITY
1456reverse_iterator<_Tp*> rbegin(_Tp (&__array)[_Np])
1457{
1458    return reverse_iterator<_Tp*>(__array + _Np);
1459}
1460
1461template <class _Tp, size_t _Np>
1462inline _LIBCPP_INLINE_VISIBILITY
1463reverse_iterator<_Tp*> rend(_Tp (&__array)[_Np])
1464{
1465    return reverse_iterator<_Tp*>(__array);
1466}
1467
1468template <class _Ep>
1469inline _LIBCPP_INLINE_VISIBILITY
1470reverse_iterator<const _Ep*> rbegin(initializer_list<_Ep> __il)
1471{
1472    return reverse_iterator<const _Ep*>(__il.end());
1473}
1474
1475template <class _Ep>
1476inline _LIBCPP_INLINE_VISIBILITY
1477reverse_iterator<const _Ep*> rend(initializer_list<_Ep> __il)
1478{
1479    return reverse_iterator<const _Ep*>(__il.begin());
1480}
1481
1482template <class _Cp>
1483inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
1484auto cbegin(const _Cp& __c) -> decltype(begin(__c))
1485{
1486    return begin(__c);
1487}
1488
1489template <class _Cp>
1490inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
1491auto cend(const _Cp& __c) -> decltype(end(__c))
1492{
1493    return end(__c);
1494}
1495
1496template <class _Cp>
1497inline _LIBCPP_INLINE_VISIBILITY
1498auto rbegin(_Cp& __c) -> decltype(__c.rbegin())
1499{
1500    return __c.rbegin();
1501}
1502
1503template <class _Cp>
1504inline _LIBCPP_INLINE_VISIBILITY
1505auto rbegin(const _Cp& __c) -> decltype(__c.rbegin())
1506{
1507    return __c.rbegin();
1508}
1509
1510template <class _Cp>
1511inline _LIBCPP_INLINE_VISIBILITY
1512auto rend(_Cp& __c) -> decltype(__c.rend())
1513{
1514    return __c.rend();
1515}
1516
1517template <class _Cp>
1518inline _LIBCPP_INLINE_VISIBILITY
1519auto rend(const _Cp& __c) -> decltype(__c.rend())
1520{
1521    return __c.rend();
1522}
1523
1524template <class _Cp>
1525inline _LIBCPP_INLINE_VISIBILITY
1526auto crbegin(const _Cp& __c) -> decltype(rbegin(__c))
1527{
1528    return rbegin(__c);
1529}
1530
1531template <class _Cp>
1532inline _LIBCPP_INLINE_VISIBILITY
1533auto crend(const _Cp& __c) -> decltype(rend(__c))
1534{
1535    return rend(__c);
1536}
1537
1538#endif
1539
1540
1541#else  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_TRAILING_RETURN)
1542
1543template <class _Cp>
1544inline _LIBCPP_INLINE_VISIBILITY
1545typename _Cp::iterator
1546begin(_Cp& __c)
1547{
1548    return __c.begin();
1549}
1550
1551template <class _Cp>
1552inline _LIBCPP_INLINE_VISIBILITY
1553typename _Cp::const_iterator
1554begin(const _Cp& __c)
1555{
1556    return __c.begin();
1557}
1558
1559template <class _Cp>
1560inline _LIBCPP_INLINE_VISIBILITY
1561typename _Cp::iterator
1562end(_Cp& __c)
1563{
1564    return __c.end();
1565}
1566
1567template <class _Cp>
1568inline _LIBCPP_INLINE_VISIBILITY
1569typename _Cp::const_iterator
1570end(const _Cp& __c)
1571{
1572    return __c.end();
1573}
1574
1575#endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_TRAILING_RETURN)
1576
1577_LIBCPP_END_NAMESPACE_STD
1578
1579#endif  // _LIBCPP_ITERATOR
1580