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