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
607_InputIter
608next(_InputIter __x,
609     typename iterator_traits<_InputIter>::difference_type __n = 1,
610     typename enable_if<__is_input_iterator<_InputIter>::value>::type* = 0)
611{
612    _VSTD::advance(__x, __n);
613    return __x;
614}
615
616template <class _BidiretionalIter>
617inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
618_BidiretionalIter
619prev(_BidiretionalIter __x,
620     typename iterator_traits<_BidiretionalIter>::difference_type __n = 1,
621     typename enable_if<__is_bidirectional_iterator<_BidiretionalIter>::value>::type* = 0)
622{
623    _VSTD::advance(__x, -__n);
624    return __x;
625}
626
627
628template <class _Tp, class = void>
629struct __is_stashing_iterator : false_type {};
630
631template <class _Tp>
632struct __is_stashing_iterator<_Tp, typename __void_t<typename _Tp::__stashing_iterator_tag>::type>
633  : true_type {};
634
635template <class _Iter>
636class _LIBCPP_TEMPLATE_VIS reverse_iterator
637    : public iterator<typename iterator_traits<_Iter>::iterator_category,
638                      typename iterator_traits<_Iter>::value_type,
639                      typename iterator_traits<_Iter>::difference_type,
640                      typename iterator_traits<_Iter>::pointer,
641                      typename iterator_traits<_Iter>::reference>
642{
643private:
644    /*mutable*/ _Iter __t;  // no longer used as of LWG #2360, not removed due to ABI break
645
646    static_assert(!__is_stashing_iterator<_Iter>::value,
647      "The specified iterator type cannot be used with reverse_iterator; "
648      "Using stashing iterators with reverse_iterator causes undefined behavior");
649
650protected:
651    _Iter current;
652public:
653    typedef _Iter                                            iterator_type;
654    typedef typename iterator_traits<_Iter>::difference_type difference_type;
655    typedef typename iterator_traits<_Iter>::reference       reference;
656    typedef typename iterator_traits<_Iter>::pointer         pointer;
657
658    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
659    reverse_iterator() : __t(), current() {}
660    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
661    explicit reverse_iterator(_Iter __x) : __t(__x), current(__x) {}
662    template <class _Up>
663        _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
664        reverse_iterator(const reverse_iterator<_Up>& __u) : __t(__u.base()), current(__u.base()) {}
665    template <class _Up>
666        _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
667        reverse_iterator& operator=(const reverse_iterator<_Up>& __u)
668            { __t = current = __u.base(); return *this; }
669    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
670    _Iter base() const {return current;}
671    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
672    reference operator*() const {_Iter __tmp = current; return *--__tmp;}
673    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
674    pointer  operator->() const {return _VSTD::addressof(operator*());}
675    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
676    reverse_iterator& operator++() {--current; return *this;}
677    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
678    reverse_iterator  operator++(int) {reverse_iterator __tmp(*this); --current; return __tmp;}
679    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
680    reverse_iterator& operator--() {++current; return *this;}
681    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
682    reverse_iterator  operator--(int) {reverse_iterator __tmp(*this); ++current; return __tmp;}
683    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
684    reverse_iterator  operator+ (difference_type __n) const {return reverse_iterator(current - __n);}
685    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
686    reverse_iterator& operator+=(difference_type __n) {current -= __n; return *this;}
687    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
688    reverse_iterator  operator- (difference_type __n) const {return reverse_iterator(current + __n);}
689    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
690    reverse_iterator& operator-=(difference_type __n) {current += __n; return *this;}
691    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
692    reference         operator[](difference_type __n) const {return *(*this + __n);}
693};
694
695template <class _Iter1, class _Iter2>
696inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
697bool
698operator==(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
699{
700    return __x.base() == __y.base();
701}
702
703template <class _Iter1, class _Iter2>
704inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
705bool
706operator<(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
707{
708    return __x.base() > __y.base();
709}
710
711template <class _Iter1, class _Iter2>
712inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
713bool
714operator!=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
715{
716    return __x.base() != __y.base();
717}
718
719template <class _Iter1, class _Iter2>
720inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
721bool
722operator>(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
723{
724    return __x.base() < __y.base();
725}
726
727template <class _Iter1, class _Iter2>
728inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
729bool
730operator>=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
731{
732    return __x.base() <= __y.base();
733}
734
735template <class _Iter1, class _Iter2>
736inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
737bool
738operator<=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
739{
740    return __x.base() >= __y.base();
741}
742
743#ifndef _LIBCPP_CXX03_LANG
744template <class _Iter1, class _Iter2>
745inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
746auto
747operator-(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
748-> decltype(__y.base() - __x.base())
749{
750    return __y.base() - __x.base();
751}
752#else
753template <class _Iter1, class _Iter2>
754inline _LIBCPP_INLINE_VISIBILITY
755typename reverse_iterator<_Iter1>::difference_type
756operator-(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
757{
758    return __y.base() - __x.base();
759}
760#endif
761
762template <class _Iter>
763inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
764reverse_iterator<_Iter>
765operator+(typename reverse_iterator<_Iter>::difference_type __n, const reverse_iterator<_Iter>& __x)
766{
767    return reverse_iterator<_Iter>(__x.base() - __n);
768}
769
770#if _LIBCPP_STD_VER > 11
771template <class _Iter>
772inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
773reverse_iterator<_Iter> make_reverse_iterator(_Iter __i)
774{
775    return reverse_iterator<_Iter>(__i);
776}
777#endif
778
779template <class _Container>
780class _LIBCPP_TEMPLATE_VIS back_insert_iterator
781    : public iterator<output_iterator_tag,
782                      void,
783                      void,
784                      void,
785                      void>
786{
787protected:
788    _Container* container;
789public:
790    typedef _Container container_type;
791
792    _LIBCPP_INLINE_VISIBILITY explicit back_insert_iterator(_Container& __x) : container(_VSTD::addressof(__x)) {}
793    _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator=(const typename _Container::value_type& __value_)
794        {container->push_back(__value_); return *this;}
795#ifndef _LIBCPP_CXX03_LANG
796    _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator=(typename _Container::value_type&& __value_)
797        {container->push_back(_VSTD::move(__value_)); return *this;}
798#endif  // _LIBCPP_CXX03_LANG
799    _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator*()     {return *this;}
800    _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator++()    {return *this;}
801    _LIBCPP_INLINE_VISIBILITY back_insert_iterator  operator++(int) {return *this;}
802};
803
804template <class _Container>
805inline _LIBCPP_INLINE_VISIBILITY
806back_insert_iterator<_Container>
807back_inserter(_Container& __x)
808{
809    return back_insert_iterator<_Container>(__x);
810}
811
812template <class _Container>
813class _LIBCPP_TEMPLATE_VIS front_insert_iterator
814    : public iterator<output_iterator_tag,
815                      void,
816                      void,
817                      void,
818                      void>
819{
820protected:
821    _Container* container;
822public:
823    typedef _Container container_type;
824
825    _LIBCPP_INLINE_VISIBILITY explicit front_insert_iterator(_Container& __x) : container(_VSTD::addressof(__x)) {}
826    _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator=(const typename _Container::value_type& __value_)
827        {container->push_front(__value_); return *this;}
828#ifndef _LIBCPP_CXX03_LANG
829    _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator=(typename _Container::value_type&& __value_)
830        {container->push_front(_VSTD::move(__value_)); return *this;}
831#endif  // _LIBCPP_CXX03_LANG
832    _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator*()     {return *this;}
833    _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator++()    {return *this;}
834    _LIBCPP_INLINE_VISIBILITY front_insert_iterator  operator++(int) {return *this;}
835};
836
837template <class _Container>
838inline _LIBCPP_INLINE_VISIBILITY
839front_insert_iterator<_Container>
840front_inserter(_Container& __x)
841{
842    return front_insert_iterator<_Container>(__x);
843}
844
845template <class _Container>
846class _LIBCPP_TEMPLATE_VIS insert_iterator
847    : public iterator<output_iterator_tag,
848                      void,
849                      void,
850                      void,
851                      void>
852{
853protected:
854    _Container* container;
855    typename _Container::iterator iter;
856public:
857    typedef _Container container_type;
858
859    _LIBCPP_INLINE_VISIBILITY insert_iterator(_Container& __x, typename _Container::iterator __i)
860        : container(_VSTD::addressof(__x)), iter(__i) {}
861    _LIBCPP_INLINE_VISIBILITY insert_iterator& operator=(const typename _Container::value_type& __value_)
862        {iter = container->insert(iter, __value_); ++iter; return *this;}
863#ifndef _LIBCPP_CXX03_LANG
864    _LIBCPP_INLINE_VISIBILITY insert_iterator& operator=(typename _Container::value_type&& __value_)
865        {iter = container->insert(iter, _VSTD::move(__value_)); ++iter; return *this;}
866#endif  // _LIBCPP_CXX03_LANG
867    _LIBCPP_INLINE_VISIBILITY insert_iterator& operator*()        {return *this;}
868    _LIBCPP_INLINE_VISIBILITY insert_iterator& operator++()       {return *this;}
869    _LIBCPP_INLINE_VISIBILITY insert_iterator& operator++(int)    {return *this;}
870};
871
872template <class _Container>
873inline _LIBCPP_INLINE_VISIBILITY
874insert_iterator<_Container>
875inserter(_Container& __x, typename _Container::iterator __i)
876{
877    return insert_iterator<_Container>(__x, __i);
878}
879
880template <class _Tp, class _CharT = char,
881          class _Traits = char_traits<_CharT>, class _Distance = ptrdiff_t>
882class _LIBCPP_TEMPLATE_VIS istream_iterator
883    : public iterator<input_iterator_tag, _Tp, _Distance, const _Tp*, const _Tp&>
884{
885public:
886    typedef _CharT char_type;
887    typedef _Traits traits_type;
888    typedef basic_istream<_CharT,_Traits> istream_type;
889private:
890    istream_type* __in_stream_;
891    _Tp __value_;
892public:
893    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR istream_iterator() : __in_stream_(0), __value_() {}
894    _LIBCPP_INLINE_VISIBILITY istream_iterator(istream_type& __s) : __in_stream_(_VSTD::addressof(__s))
895        {
896            if (!(*__in_stream_ >> __value_))
897                __in_stream_ = 0;
898        }
899
900    _LIBCPP_INLINE_VISIBILITY const _Tp& operator*() const {return __value_;}
901    _LIBCPP_INLINE_VISIBILITY const _Tp* operator->() const {return _VSTD::addressof((operator*()));}
902    _LIBCPP_INLINE_VISIBILITY istream_iterator& operator++()
903        {
904            if (!(*__in_stream_ >> __value_))
905                __in_stream_ = 0;
906            return *this;
907        }
908    _LIBCPP_INLINE_VISIBILITY istream_iterator  operator++(int)
909        {istream_iterator __t(*this); ++(*this); return __t;}
910
911    friend _LIBCPP_INLINE_VISIBILITY
912    bool operator==(const istream_iterator& __x, const istream_iterator& __y)
913        {return __x.__in_stream_ == __y.__in_stream_;}
914
915    friend _LIBCPP_INLINE_VISIBILITY
916    bool operator!=(const istream_iterator& __x, const istream_iterator& __y)
917        {return !(__x == __y);}
918};
919
920template <class _Tp, class _CharT = char, class _Traits = char_traits<_CharT> >
921class _LIBCPP_TEMPLATE_VIS ostream_iterator
922    : public iterator<output_iterator_tag, void, void, void, void>
923{
924public:
925    typedef _CharT char_type;
926    typedef _Traits traits_type;
927    typedef basic_ostream<_CharT,_Traits> ostream_type;
928private:
929    ostream_type* __out_stream_;
930    const char_type* __delim_;
931public:
932    _LIBCPP_INLINE_VISIBILITY ostream_iterator(ostream_type& __s) _NOEXCEPT
933        : __out_stream_(_VSTD::addressof(__s)), __delim_(0) {}
934    _LIBCPP_INLINE_VISIBILITY ostream_iterator(ostream_type& __s, const _CharT* __delimiter) _NOEXCEPT
935        : __out_stream_(_VSTD::addressof(__s)), __delim_(__delimiter) {}
936    _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator=(const _Tp& __value_)
937        {
938            *__out_stream_ << __value_;
939            if (__delim_)
940                *__out_stream_ << __delim_;
941            return *this;
942        }
943
944    _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator*()     {return *this;}
945    _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator++()    {return *this;}
946    _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator++(int) {return *this;}
947};
948
949template<class _CharT, class _Traits>
950class _LIBCPP_TEMPLATE_VIS istreambuf_iterator
951    : public iterator<input_iterator_tag, _CharT,
952                      typename _Traits::off_type, _CharT*,
953                      _CharT>
954{
955public:
956    typedef _CharT                          char_type;
957    typedef _Traits                         traits_type;
958    typedef typename _Traits::int_type      int_type;
959    typedef basic_streambuf<_CharT,_Traits> streambuf_type;
960    typedef basic_istream<_CharT,_Traits>   istream_type;
961private:
962    mutable streambuf_type* __sbuf_;
963
964    class __proxy
965    {
966        char_type __keep_;
967        streambuf_type* __sbuf_;
968        _LIBCPP_INLINE_VISIBILITY __proxy(char_type __c, streambuf_type* __s)
969            : __keep_(__c), __sbuf_(__s) {}
970        friend class istreambuf_iterator;
971    public:
972        _LIBCPP_INLINE_VISIBILITY char_type operator*() const {return __keep_;}
973    };
974
975    _LIBCPP_INLINE_VISIBILITY
976    bool __test_for_eof() const
977    {
978        if (__sbuf_ && traits_type::eq_int_type(__sbuf_->sgetc(), traits_type::eof()))
979            __sbuf_ = 0;
980        return __sbuf_ == 0;
981    }
982public:
983    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR istreambuf_iterator() _NOEXCEPT : __sbuf_(0) {}
984    _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(istream_type& __s) _NOEXCEPT
985        : __sbuf_(__s.rdbuf()) {}
986    _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(streambuf_type* __s) _NOEXCEPT
987        : __sbuf_(__s) {}
988    _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(const __proxy& __p) _NOEXCEPT
989        : __sbuf_(__p.__sbuf_) {}
990
991    _LIBCPP_INLINE_VISIBILITY char_type  operator*() const
992        {return static_cast<char_type>(__sbuf_->sgetc());}
993    _LIBCPP_INLINE_VISIBILITY char_type* operator->() const {return nullptr;}
994    _LIBCPP_INLINE_VISIBILITY istreambuf_iterator& operator++()
995        {
996            __sbuf_->sbumpc();
997            return *this;
998        }
999    _LIBCPP_INLINE_VISIBILITY __proxy              operator++(int)
1000        {
1001            return __proxy(__sbuf_->sbumpc(), __sbuf_);
1002        }
1003
1004    _LIBCPP_INLINE_VISIBILITY bool equal(const istreambuf_iterator& __b) const
1005        {return __test_for_eof() == __b.__test_for_eof();}
1006};
1007
1008template <class _CharT, class _Traits>
1009inline _LIBCPP_INLINE_VISIBILITY
1010bool operator==(const istreambuf_iterator<_CharT,_Traits>& __a,
1011                const istreambuf_iterator<_CharT,_Traits>& __b)
1012                {return __a.equal(__b);}
1013
1014template <class _CharT, class _Traits>
1015inline _LIBCPP_INLINE_VISIBILITY
1016bool operator!=(const istreambuf_iterator<_CharT,_Traits>& __a,
1017                const istreambuf_iterator<_CharT,_Traits>& __b)
1018                {return !__a.equal(__b);}
1019
1020template <class _CharT, class _Traits>
1021class _LIBCPP_TEMPLATE_VIS ostreambuf_iterator
1022    : public iterator<output_iterator_tag, void, void, void, void>
1023{
1024public:
1025    typedef _CharT                          char_type;
1026    typedef _Traits                         traits_type;
1027    typedef basic_streambuf<_CharT,_Traits> streambuf_type;
1028    typedef basic_ostream<_CharT,_Traits>   ostream_type;
1029private:
1030    streambuf_type* __sbuf_;
1031public:
1032    _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator(ostream_type& __s) _NOEXCEPT
1033        : __sbuf_(__s.rdbuf()) {}
1034    _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator(streambuf_type* __s) _NOEXCEPT
1035        : __sbuf_(__s) {}
1036    _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator=(_CharT __c)
1037        {
1038            if (__sbuf_ && traits_type::eq_int_type(__sbuf_->sputc(__c), traits_type::eof()))
1039                __sbuf_ = 0;
1040            return *this;
1041        }
1042    _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator*()     {return *this;}
1043    _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator++()    {return *this;}
1044    _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator++(int) {return *this;}
1045    _LIBCPP_INLINE_VISIBILITY bool failed() const _NOEXCEPT {return __sbuf_ == 0;}
1046
1047#if !defined(__APPLE__) || \
1048    (defined(__MAC_OS_X_VERSION_MIN_REQUIRED) && __MAC_OS_X_VERSION_MIN_REQUIRED > __MAC_10_8) || \
1049    (defined(__IPHONE_OS_VERSION_MIN_REQUIRED) && __IPHONE_OS_VERSION_MIN_REQUIRED > __IPHONE_6_0)
1050
1051    template <class _Ch, class _Tr>
1052    friend
1053    _LIBCPP_HIDDEN
1054    ostreambuf_iterator<_Ch, _Tr>
1055    __pad_and_output(ostreambuf_iterator<_Ch, _Tr> __s,
1056                     const _Ch* __ob, const _Ch* __op, const _Ch* __oe,
1057                     ios_base& __iob, _Ch __fl);
1058#endif
1059};
1060
1061template <class _Iter>
1062class _LIBCPP_TEMPLATE_VIS move_iterator
1063{
1064private:
1065    _Iter __i;
1066public:
1067    typedef _Iter                                            iterator_type;
1068    typedef typename iterator_traits<iterator_type>::iterator_category iterator_category;
1069    typedef typename iterator_traits<iterator_type>::value_type value_type;
1070    typedef typename iterator_traits<iterator_type>::difference_type difference_type;
1071    typedef iterator_type pointer;
1072#ifndef _LIBCPP_CXX03_LANG
1073    typedef typename iterator_traits<iterator_type>::reference __reference;
1074    typedef typename conditional<
1075            is_reference<__reference>::value,
1076            typename remove_reference<__reference>::type&&,
1077            __reference
1078        >::type reference;
1079#else
1080    typedef typename iterator_traits<iterator_type>::reference reference;
1081#endif
1082
1083    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1084    move_iterator() : __i() {}
1085    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1086    explicit move_iterator(_Iter __x) : __i(__x) {}
1087    template <class _Up>
1088      _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1089      move_iterator(const move_iterator<_Up>& __u) : __i(__u.base()) {}
1090    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 _Iter base() const {return __i;}
1091    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1092    reference operator*() const { return static_cast<reference>(*__i); }
1093    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1094    pointer  operator->() const { return __i;}
1095    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1096    move_iterator& operator++() {++__i; return *this;}
1097    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1098    move_iterator  operator++(int) {move_iterator __tmp(*this); ++__i; return __tmp;}
1099    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1100    move_iterator& operator--() {--__i; return *this;}
1101    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1102    move_iterator  operator--(int) {move_iterator __tmp(*this); --__i; return __tmp;}
1103    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1104    move_iterator  operator+ (difference_type __n) const {return move_iterator(__i + __n);}
1105    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1106    move_iterator& operator+=(difference_type __n) {__i += __n; return *this;}
1107    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1108    move_iterator  operator- (difference_type __n) const {return move_iterator(__i - __n);}
1109    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1110    move_iterator& operator-=(difference_type __n) {__i -= __n; return *this;}
1111    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1112    reference operator[](difference_type __n) const { return static_cast<reference>(__i[__n]); }
1113};
1114
1115template <class _Iter1, class _Iter2>
1116inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1117bool
1118operator==(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1119{
1120    return __x.base() == __y.base();
1121}
1122
1123template <class _Iter1, class _Iter2>
1124inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1125bool
1126operator<(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1127{
1128    return __x.base() < __y.base();
1129}
1130
1131template <class _Iter1, class _Iter2>
1132inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1133bool
1134operator!=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1135{
1136    return __x.base() != __y.base();
1137}
1138
1139template <class _Iter1, class _Iter2>
1140inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1141bool
1142operator>(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1143{
1144    return __x.base() > __y.base();
1145}
1146
1147template <class _Iter1, class _Iter2>
1148inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1149bool
1150operator>=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1151{
1152    return __x.base() >= __y.base();
1153}
1154
1155template <class _Iter1, class _Iter2>
1156inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1157bool
1158operator<=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1159{
1160    return __x.base() <= __y.base();
1161}
1162
1163#ifndef _LIBCPP_CXX03_LANG
1164template <class _Iter1, class _Iter2>
1165inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1166auto
1167operator-(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1168-> decltype(__x.base() - __y.base())
1169{
1170    return __x.base() - __y.base();
1171}
1172#else
1173template <class _Iter1, class _Iter2>
1174inline _LIBCPP_INLINE_VISIBILITY
1175typename move_iterator<_Iter1>::difference_type
1176operator-(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1177{
1178    return __x.base() - __y.base();
1179}
1180#endif
1181
1182template <class _Iter>
1183inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1184move_iterator<_Iter>
1185operator+(typename move_iterator<_Iter>::difference_type __n, const move_iterator<_Iter>& __x)
1186{
1187    return move_iterator<_Iter>(__x.base() + __n);
1188}
1189
1190template <class _Iter>
1191inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1192move_iterator<_Iter>
1193make_move_iterator(_Iter __i)
1194{
1195    return move_iterator<_Iter>(__i);
1196}
1197
1198// __wrap_iter
1199
1200template <class _Iter> class __wrap_iter;
1201
1202template <class _Iter1, class _Iter2>
1203_LIBCPP_INLINE_VISIBILITY
1204bool
1205operator==(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT_DEBUG;
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
1232#ifndef _LIBCPP_CXX03_LANG
1233template <class _Iter1, class _Iter2>
1234_LIBCPP_INLINE_VISIBILITY
1235auto
1236operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT_DEBUG
1237-> decltype(__x.base() - __y.base());
1238#else
1239template <class _Iter1, class _Iter2>
1240_LIBCPP_INLINE_VISIBILITY
1241typename __wrap_iter<_Iter1>::difference_type
1242operator-(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT_DEBUG;
1243#endif
1244
1245template <class _Iter>
1246_LIBCPP_INLINE_VISIBILITY
1247__wrap_iter<_Iter>
1248operator+(typename __wrap_iter<_Iter>::difference_type, __wrap_iter<_Iter>) _NOEXCEPT_DEBUG;
1249
1250template <class _Ip, class _Op> _Op _LIBCPP_INLINE_VISIBILITY copy(_Ip, _Ip, _Op);
1251template <class _B1, class _B2> _B2 _LIBCPP_INLINE_VISIBILITY copy_backward(_B1, _B1, _B2);
1252template <class _Ip, class _Op> _Op _LIBCPP_INLINE_VISIBILITY move(_Ip, _Ip, _Op);
1253template <class _B1, class _B2> _B2 _LIBCPP_INLINE_VISIBILITY move_backward(_B1, _B1, _B2);
1254
1255#if _LIBCPP_DEBUG_LEVEL < 2
1256
1257template <class _Tp>
1258_LIBCPP_INLINE_VISIBILITY
1259typename enable_if
1260<
1261    is_trivially_copy_assignable<_Tp>::value,
1262    _Tp*
1263>::type
1264__unwrap_iter(__wrap_iter<_Tp*>);
1265
1266#else
1267
1268template <class _Tp>
1269inline _LIBCPP_INLINE_VISIBILITY
1270typename enable_if
1271<
1272    is_trivially_copy_assignable<_Tp>::value,
1273    __wrap_iter<_Tp*>
1274>::type
1275__unwrap_iter(__wrap_iter<_Tp*> __i);
1276
1277#endif
1278
1279template <class _Iter>
1280class __wrap_iter
1281{
1282public:
1283    typedef _Iter                                                      iterator_type;
1284    typedef typename iterator_traits<iterator_type>::iterator_category iterator_category;
1285    typedef typename iterator_traits<iterator_type>::value_type        value_type;
1286    typedef typename iterator_traits<iterator_type>::difference_type   difference_type;
1287    typedef typename iterator_traits<iterator_type>::pointer           pointer;
1288    typedef typename iterator_traits<iterator_type>::reference         reference;
1289private:
1290    iterator_type __i;
1291public:
1292    _LIBCPP_INLINE_VISIBILITY __wrap_iter() _NOEXCEPT_DEBUG
1293#if _LIBCPP_STD_VER > 11
1294                : __i{}
1295#endif
1296    {
1297#if _LIBCPP_DEBUG_LEVEL >= 2
1298        __get_db()->__insert_i(this);
1299#endif
1300    }
1301    template <class _Up> _LIBCPP_INLINE_VISIBILITY __wrap_iter(const __wrap_iter<_Up>& __u,
1302        typename enable_if<is_convertible<_Up, iterator_type>::value>::type* = 0) _NOEXCEPT_DEBUG
1303        : __i(__u.base())
1304    {
1305#if _LIBCPP_DEBUG_LEVEL >= 2
1306        __get_db()->__iterator_copy(this, &__u);
1307#endif
1308    }
1309#if _LIBCPP_DEBUG_LEVEL >= 2
1310    _LIBCPP_INLINE_VISIBILITY
1311    __wrap_iter(const __wrap_iter& __x)
1312        : __i(__x.base())
1313    {
1314        __get_db()->__iterator_copy(this, &__x);
1315    }
1316    _LIBCPP_INLINE_VISIBILITY
1317    __wrap_iter& operator=(const __wrap_iter& __x)
1318    {
1319        if (this != &__x)
1320        {
1321            __get_db()->__iterator_copy(this, &__x);
1322            __i = __x.__i;
1323        }
1324        return *this;
1325    }
1326    _LIBCPP_INLINE_VISIBILITY
1327    ~__wrap_iter()
1328    {
1329        __get_db()->__erase_i(this);
1330    }
1331#endif
1332    _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT_DEBUG
1333    {
1334#if _LIBCPP_DEBUG_LEVEL >= 2
1335        _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
1336                       "Attempted to dereference a non-dereferenceable iterator");
1337#endif
1338        return *__i;
1339    }
1340    _LIBCPP_INLINE_VISIBILITY pointer  operator->() const _NOEXCEPT_DEBUG
1341    {
1342#if _LIBCPP_DEBUG_LEVEL >= 2
1343        _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
1344                       "Attempted to dereference a non-dereferenceable iterator");
1345#endif
1346        return (pointer)_VSTD::addressof(*__i);
1347    }
1348    _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator++() _NOEXCEPT_DEBUG
1349    {
1350#if _LIBCPP_DEBUG_LEVEL >= 2
1351        _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
1352                       "Attempted to increment non-incrementable iterator");
1353#endif
1354        ++__i;
1355        return *this;
1356    }
1357    _LIBCPP_INLINE_VISIBILITY __wrap_iter  operator++(int) _NOEXCEPT_DEBUG
1358        {__wrap_iter __tmp(*this); ++(*this); return __tmp;}
1359    _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator--() _NOEXCEPT_DEBUG
1360    {
1361#if _LIBCPP_DEBUG_LEVEL >= 2
1362        _LIBCPP_ASSERT(__get_const_db()->__decrementable(this),
1363                       "Attempted to decrement non-decrementable iterator");
1364#endif
1365        --__i;
1366        return *this;
1367    }
1368    _LIBCPP_INLINE_VISIBILITY __wrap_iter  operator--(int) _NOEXCEPT_DEBUG
1369        {__wrap_iter __tmp(*this); --(*this); return __tmp;}
1370    _LIBCPP_INLINE_VISIBILITY __wrap_iter  operator+ (difference_type __n) const _NOEXCEPT_DEBUG
1371        {__wrap_iter __w(*this); __w += __n; return __w;}
1372    _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator+=(difference_type __n) _NOEXCEPT_DEBUG
1373    {
1374#if _LIBCPP_DEBUG_LEVEL >= 2
1375        _LIBCPP_ASSERT(__get_const_db()->__addable(this, __n),
1376                   "Attempted to add/subtract iterator outside of valid range");
1377#endif
1378        __i += __n;
1379        return *this;
1380    }
1381    _LIBCPP_INLINE_VISIBILITY __wrap_iter  operator- (difference_type __n) const _NOEXCEPT_DEBUG
1382        {return *this + (-__n);}
1383    _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator-=(difference_type __n) _NOEXCEPT_DEBUG
1384        {*this += -__n; return *this;}
1385    _LIBCPP_INLINE_VISIBILITY reference        operator[](difference_type __n) const _NOEXCEPT_DEBUG
1386    {
1387#if _LIBCPP_DEBUG_LEVEL >= 2
1388        _LIBCPP_ASSERT(__get_const_db()->__subscriptable(this, __n),
1389                   "Attempted to subscript iterator outside of valid range");
1390#endif
1391        return __i[__n];
1392    }
1393
1394    _LIBCPP_INLINE_VISIBILITY iterator_type base() const _NOEXCEPT_DEBUG {return __i;}
1395
1396private:
1397#if _LIBCPP_DEBUG_LEVEL >= 2
1398    _LIBCPP_INLINE_VISIBILITY __wrap_iter(const void* __p, iterator_type __x) : __i(__x)
1399    {
1400        __get_db()->__insert_ic(this, __p);
1401    }
1402#else
1403    _LIBCPP_INLINE_VISIBILITY __wrap_iter(iterator_type __x) _NOEXCEPT_DEBUG : __i(__x) {}
1404#endif
1405
1406    template <class _Up> friend class __wrap_iter;
1407    template <class _CharT, class _Traits, class _Alloc> friend class basic_string;
1408    template <class _Tp, class _Alloc> friend class _LIBCPP_TEMPLATE_VIS vector;
1409
1410    template <class _Iter1, class _Iter2>
1411    friend
1412    bool
1413    operator==(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT_DEBUG;
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#ifndef _LIBCPP_CXX03_LANG
1441    template <class _Iter1, class _Iter2>
1442    friend
1443    auto
1444    operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT_DEBUG
1445    -> decltype(__x.base() - __y.base());
1446#else
1447    template <class _Iter1, class _Iter2>
1448    friend
1449    typename __wrap_iter<_Iter1>::difference_type
1450    operator-(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT_DEBUG;
1451#endif
1452
1453    template <class _Iter1>
1454    friend
1455    __wrap_iter<_Iter1>
1456    operator+(typename __wrap_iter<_Iter1>::difference_type, __wrap_iter<_Iter1>) _NOEXCEPT_DEBUG;
1457
1458    template <class _Ip, class _Op> friend _Op copy(_Ip, _Ip, _Op);
1459    template <class _B1, class _B2> friend _B2 copy_backward(_B1, _B1, _B2);
1460    template <class _Ip, class _Op> friend _Op move(_Ip, _Ip, _Op);
1461    template <class _B1, class _B2> friend _B2 move_backward(_B1, _B1, _B2);
1462
1463#if _LIBCPP_DEBUG_LEVEL < 2
1464    template <class _Tp>
1465    friend
1466    typename enable_if
1467    <
1468        is_trivially_copy_assignable<_Tp>::value,
1469        _Tp*
1470    >::type
1471    __unwrap_iter(__wrap_iter<_Tp*>);
1472#else
1473  template <class _Tp>
1474  inline _LIBCPP_INLINE_VISIBILITY
1475  typename enable_if
1476  <
1477      is_trivially_copy_assignable<_Tp>::value,
1478      __wrap_iter<_Tp*>
1479  >::type
1480  __unwrap_iter(__wrap_iter<_Tp*> __i);
1481#endif
1482};
1483
1484template <class _Iter1, class _Iter2>
1485inline _LIBCPP_INLINE_VISIBILITY
1486bool
1487operator==(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT_DEBUG
1488{
1489    return __x.base() == __y.base();
1490}
1491
1492template <class _Iter1, class _Iter2>
1493inline _LIBCPP_INLINE_VISIBILITY
1494bool
1495operator<(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT_DEBUG
1496{
1497#if _LIBCPP_DEBUG_LEVEL >= 2
1498    _LIBCPP_ASSERT(__get_const_db()->__less_than_comparable(&__x, &__y),
1499                   "Attempted to compare incomparable iterators");
1500#endif
1501    return __x.base() < __y.base();
1502}
1503
1504template <class _Iter1, class _Iter2>
1505inline _LIBCPP_INLINE_VISIBILITY
1506bool
1507operator!=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT_DEBUG
1508{
1509    return !(__x == __y);
1510}
1511
1512template <class _Iter1, class _Iter2>
1513inline _LIBCPP_INLINE_VISIBILITY
1514bool
1515operator>(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT_DEBUG
1516{
1517    return __y < __x;
1518}
1519
1520template <class _Iter1, class _Iter2>
1521inline _LIBCPP_INLINE_VISIBILITY
1522bool
1523operator>=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT_DEBUG
1524{
1525    return !(__x < __y);
1526}
1527
1528template <class _Iter1, class _Iter2>
1529inline _LIBCPP_INLINE_VISIBILITY
1530bool
1531operator<=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT_DEBUG
1532{
1533    return !(__y < __x);
1534}
1535
1536template <class _Iter1>
1537inline _LIBCPP_INLINE_VISIBILITY
1538bool
1539operator!=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT_DEBUG
1540{
1541    return !(__x == __y);
1542}
1543
1544template <class _Iter1>
1545inline _LIBCPP_INLINE_VISIBILITY
1546bool
1547operator>(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT_DEBUG
1548{
1549    return __y < __x;
1550}
1551
1552template <class _Iter1>
1553inline _LIBCPP_INLINE_VISIBILITY
1554bool
1555operator>=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT_DEBUG
1556{
1557    return !(__x < __y);
1558}
1559
1560template <class _Iter1>
1561inline _LIBCPP_INLINE_VISIBILITY
1562bool
1563operator<=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT_DEBUG
1564{
1565    return !(__y < __x);
1566}
1567
1568#ifndef _LIBCPP_CXX03_LANG
1569template <class _Iter1, class _Iter2>
1570inline _LIBCPP_INLINE_VISIBILITY
1571auto
1572operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT_DEBUG
1573-> decltype(__x.base() - __y.base())
1574{
1575#if _LIBCPP_DEBUG_LEVEL >= 2
1576    _LIBCPP_ASSERT(__get_const_db()->__less_than_comparable(&__x, &__y),
1577                   "Attempted to subtract incompatible iterators");
1578#endif
1579    return __x.base() - __y.base();
1580}
1581#else
1582template <class _Iter1, class _Iter2>
1583inline _LIBCPP_INLINE_VISIBILITY
1584typename __wrap_iter<_Iter1>::difference_type
1585operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT_DEBUG
1586{
1587#if _LIBCPP_DEBUG_LEVEL >= 2
1588    _LIBCPP_ASSERT(__get_const_db()->__less_than_comparable(&__x, &__y),
1589                   "Attempted to subtract incompatible iterators");
1590#endif
1591    return __x.base() - __y.base();
1592}
1593#endif
1594
1595template <class _Iter>
1596inline _LIBCPP_INLINE_VISIBILITY
1597__wrap_iter<_Iter>
1598operator+(typename __wrap_iter<_Iter>::difference_type __n,
1599          __wrap_iter<_Iter> __x) _NOEXCEPT_DEBUG
1600{
1601    __x += __n;
1602    return __x;
1603}
1604
1605template <class _Iter>
1606struct __libcpp_is_trivial_iterator
1607    : public _LIBCPP_BOOL_CONSTANT(is_pointer<_Iter>::value) {};
1608
1609template <class _Iter>
1610struct __libcpp_is_trivial_iterator<move_iterator<_Iter> >
1611    : public _LIBCPP_BOOL_CONSTANT(__libcpp_is_trivial_iterator<_Iter>::value) {};
1612
1613template <class _Iter>
1614struct __libcpp_is_trivial_iterator<reverse_iterator<_Iter> >
1615    : public _LIBCPP_BOOL_CONSTANT(__libcpp_is_trivial_iterator<_Iter>::value) {};
1616
1617template <class _Iter>
1618struct __libcpp_is_trivial_iterator<__wrap_iter<_Iter> >
1619    : public _LIBCPP_BOOL_CONSTANT(__libcpp_is_trivial_iterator<_Iter>::value) {};
1620
1621
1622template <class _Tp, size_t _Np>
1623inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
1624_Tp*
1625begin(_Tp (&__array)[_Np])
1626{
1627    return __array;
1628}
1629
1630template <class _Tp, size_t _Np>
1631inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
1632_Tp*
1633end(_Tp (&__array)[_Np])
1634{
1635    return __array + _Np;
1636}
1637
1638#if !defined(_LIBCPP_CXX03_LANG)
1639
1640template <class _Cp>
1641inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1642auto
1643begin(_Cp& __c) -> decltype(__c.begin())
1644{
1645    return __c.begin();
1646}
1647
1648template <class _Cp>
1649inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1650auto
1651begin(const _Cp& __c) -> decltype(__c.begin())
1652{
1653    return __c.begin();
1654}
1655
1656template <class _Cp>
1657inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1658auto
1659end(_Cp& __c) -> decltype(__c.end())
1660{
1661    return __c.end();
1662}
1663
1664template <class _Cp>
1665inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1666auto
1667end(const _Cp& __c) -> decltype(__c.end())
1668{
1669    return __c.end();
1670}
1671
1672#if _LIBCPP_STD_VER > 11
1673
1674template <class _Tp, size_t _Np>
1675inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1676reverse_iterator<_Tp*> rbegin(_Tp (&__array)[_Np])
1677{
1678    return reverse_iterator<_Tp*>(__array + _Np);
1679}
1680
1681template <class _Tp, size_t _Np>
1682inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1683reverse_iterator<_Tp*> rend(_Tp (&__array)[_Np])
1684{
1685    return reverse_iterator<_Tp*>(__array);
1686}
1687
1688template <class _Ep>
1689inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1690reverse_iterator<const _Ep*> rbegin(initializer_list<_Ep> __il)
1691{
1692    return reverse_iterator<const _Ep*>(__il.end());
1693}
1694
1695template <class _Ep>
1696inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1697reverse_iterator<const _Ep*> rend(initializer_list<_Ep> __il)
1698{
1699    return reverse_iterator<const _Ep*>(__il.begin());
1700}
1701
1702template <class _Cp>
1703inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
1704auto cbegin(const _Cp& __c) -> decltype(_VSTD::begin(__c))
1705{
1706    return _VSTD::begin(__c);
1707}
1708
1709template <class _Cp>
1710inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
1711auto cend(const _Cp& __c) -> decltype(_VSTD::end(__c))
1712{
1713    return _VSTD::end(__c);
1714}
1715
1716template <class _Cp>
1717inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1718auto rbegin(_Cp& __c) -> decltype(__c.rbegin())
1719{
1720    return __c.rbegin();
1721}
1722
1723template <class _Cp>
1724inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1725auto rbegin(const _Cp& __c) -> decltype(__c.rbegin())
1726{
1727    return __c.rbegin();
1728}
1729
1730template <class _Cp>
1731inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1732auto rend(_Cp& __c) -> decltype(__c.rend())
1733{
1734    return __c.rend();
1735}
1736
1737template <class _Cp>
1738inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1739auto rend(const _Cp& __c) -> decltype(__c.rend())
1740{
1741    return __c.rend();
1742}
1743
1744template <class _Cp>
1745inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1746auto crbegin(const _Cp& __c) -> decltype(_VSTD::rbegin(__c))
1747{
1748    return _VSTD::rbegin(__c);
1749}
1750
1751template <class _Cp>
1752inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1753auto crend(const _Cp& __c) -> decltype(_VSTD::rend(__c))
1754{
1755    return _VSTD::rend(__c);
1756}
1757
1758#endif
1759
1760
1761#else  // defined(_LIBCPP_CXX03_LANG)
1762
1763template <class _Cp>
1764inline _LIBCPP_INLINE_VISIBILITY
1765typename _Cp::iterator
1766begin(_Cp& __c)
1767{
1768    return __c.begin();
1769}
1770
1771template <class _Cp>
1772inline _LIBCPP_INLINE_VISIBILITY
1773typename _Cp::const_iterator
1774begin(const _Cp& __c)
1775{
1776    return __c.begin();
1777}
1778
1779template <class _Cp>
1780inline _LIBCPP_INLINE_VISIBILITY
1781typename _Cp::iterator
1782end(_Cp& __c)
1783{
1784    return __c.end();
1785}
1786
1787template <class _Cp>
1788inline _LIBCPP_INLINE_VISIBILITY
1789typename _Cp::const_iterator
1790end(const _Cp& __c)
1791{
1792    return __c.end();
1793}
1794
1795#endif  // !defined(_LIBCPP_CXX03_LANG)
1796
1797#if _LIBCPP_STD_VER > 14
1798template <class _Cont>
1799constexpr auto size(const _Cont& __c) -> decltype(__c.size()) { return __c.size(); }
1800
1801template <class _Tp, size_t _Sz>
1802constexpr size_t size(const _Tp (&)[_Sz]) noexcept { return _Sz; }
1803
1804template <class _Cont>
1805constexpr auto empty(const _Cont& __c) -> decltype(__c.empty()) { return __c.empty(); }
1806
1807template <class _Tp, size_t _Sz>
1808constexpr bool empty(const _Tp (&)[_Sz]) noexcept { return false; }
1809
1810template <class _Ep>
1811constexpr bool empty(initializer_list<_Ep> __il) noexcept { return __il.size() == 0; }
1812
1813template <class _Cont> constexpr
1814auto data(_Cont& __c) -> decltype(__c.data()) { return __c.data(); }
1815
1816template <class _Cont> constexpr
1817auto data(const _Cont& __c) -> decltype(__c.data()) { return __c.data(); }
1818
1819template <class _Tp, size_t _Sz>
1820constexpr _Tp* data(_Tp (&__array)[_Sz]) noexcept { return __array; }
1821
1822template <class _Ep>
1823constexpr const _Ep* data(initializer_list<_Ep> __il) noexcept { return __il.begin(); }
1824#endif
1825
1826
1827_LIBCPP_END_NAMESPACE_STD
1828
1829#endif  // _LIBCPP_ITERATOR
1830