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