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