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