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