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