blob: b24f25457589d0a9bc8e34f312cd3957f0cfb795 [file] [log] [blame]
Howard Hinnantc51e1022010-05-11 19:42:16 +00001// -*- C++ -*-
2//===-------------------------- iterator ----------------------------------===//
3//
Chandler Carruthd2012102019-01-19 10:56:40 +00004// 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
Howard Hinnantc51e1022010-05-11 19:42:16 +00007//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP_ITERATOR
11#define _LIBCPP_ITERATOR
12
13/*
14 iterator synopsis
15
Christopher Di Bella490fe402021-03-23 03:55:52 +000016#include <concepts>
17
Howard Hinnantc51e1022010-05-11 19:42:16 +000018namespace std
19{
Christopher Di Bellae00eebc2021-03-23 20:48:41 +000020template<class> struct incrementable_traits; // since C++20
21template<class> struct indirectly_readable_traits; // since C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +000022
23template<class Iterator>
zoecarver9f1e2972021-04-20 08:50:11 -040024struct iterator_traits;
Howard Hinnantc51e1022010-05-11 19:42:16 +000025
26template<class T>
zoecarver9f1e2972021-04-20 08:50:11 -040027 requires is_object_v<T> // since C++20
28struct iterator_traits<T*>;
Howard Hinnantc51e1022010-05-11 19:42:16 +000029
Christopher Di Bella875636f2021-04-04 05:12:46 +000030template<dereferenceable T>
31 using iter_reference_t = decltype(*declval<T&>());
32
Howard Hinnantc51e1022010-05-11 19:42:16 +000033template<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
Marshall Clow75468e72017-05-17 18:51:36 +000050// 27.4.3, iterator operations
Louis Dionne45768662020-06-08 16:16:01 -040051template <class InputIterator, class Distance> // constexpr in C++17
52 constexpr void advance(InputIterator& i, Distance n);
Howard Hinnantc51e1022010-05-11 19:42:16 +000053
Marshall Clow75468e72017-05-17 18:51:36 +000054template <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,
Louis Dionne173f29e2019-05-29 16:01:36 +000064 typename iterator_traits<BidirectionalIterator>::difference_type n = 1);
Howard Hinnantc51e1022010-05-11 19:42:16 +000065
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;
Howard Hinnant3b6579a2010-08-22 00:02:43 +000081
Marshall Clow5ace5542016-10-19 15:12:50 +000082 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;
Howard Hinnantc51e1022010-05-11 19:42:16 +000098};
99
100template <class Iterator1, class Iterator2>
Marshall Clow5ace5542016-10-19 15:12:50 +0000101constexpr bool // constexpr in C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000102operator==(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
103
104template <class Iterator1, class Iterator2>
Marshall Clow5ace5542016-10-19 15:12:50 +0000105constexpr bool // constexpr in C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000106operator<(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
107
108template <class Iterator1, class Iterator2>
Marshall Clow5ace5542016-10-19 15:12:50 +0000109constexpr bool // constexpr in C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000110operator!=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
111
112template <class Iterator1, class Iterator2>
Marshall Clow5ace5542016-10-19 15:12:50 +0000113constexpr bool // constexpr in C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000114operator>(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
115
116template <class Iterator1, class Iterator2>
Marshall Clow5ace5542016-10-19 15:12:50 +0000117constexpr bool // constexpr in C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000118operator>=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
119
120template <class Iterator1, class Iterator2>
Marshall Clow5ace5542016-10-19 15:12:50 +0000121constexpr bool // constexpr in C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000122operator<=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
123
124template <class Iterator1, class Iterator2>
Marshall Clow5ace5542016-10-19 15:12:50 +0000125constexpr auto
Marshall Clowf8fec4e2016-07-08 16:54:47 +0000126operator-(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y)
Marshall Clow5ace5542016-10-19 15:12:50 +0000127-> decltype(__y.base() - __x.base()); // constexpr in C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000128
129template <class Iterator>
Marshall Clow5ace5542016-10-19 15:12:50 +0000130constexpr reverse_iterator<Iterator>
Louis Dionne173f29e2019-05-29 16:01:36 +0000131operator+(typename reverse_iterator<Iterator>::difference_type n,
Marshall Clow5ace5542016-10-19 15:12:50 +0000132 const reverse_iterator<Iterator>& x); // constexpr in C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000133
Marshall Clow5ace5542016-10-19 15:12:50 +0000134template <class Iterator>
135constexpr reverse_iterator<Iterator> make_reverse_iterator(Iterator i); // C++14, constexpr in C++17
Marshall Clow6dbbdc92014-03-03 01:24:04 +0000136
Howard Hinnantc51e1022010-05-11 19:42:16 +0000137template <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;
Eric Fiselier9aeea872016-06-30 04:40:50 +0000146 typedef void reference;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000147 typedef void pointer;
148
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -0500149 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
Howard Hinnantc51e1022010-05-11 19:42:16 +0000154};
155
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -0500156template <class Container> back_insert_iterator<Container> back_inserter(Container& x); // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000157
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;
Eric Fiselier9aeea872016-06-30 04:40:50 +0000167 typedef void reference;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000168 typedef void pointer;
169
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -0500170 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
Howard Hinnantc51e1022010-05-11 19:42:16 +0000175};
176
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -0500177template <class Container> front_insert_iterator<Container> front_inserter(Container& x); // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000178
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;
Eric Fiselier9aeea872016-06-30 04:40:50 +0000189 typedef void reference;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000190 typedef void pointer;
191
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -0500192 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
Howard Hinnantc51e1022010-05-11 19:42:16 +0000197};
198
199template <class Container, class Iterator>
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -0500200insert_iterator<Container> inserter(Container& x, Iterator i); // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000201
Marshall Clowf8fec4e2016-07-08 16:54:47 +0000202template <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;
Louis Dionne173f29e2019-05-29 16:01:36 +0000211
Marshall Clowb5f99122016-11-02 15:30:26 +0000212 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);
Louis Dionne173f29e2019-05-29 16:01:36 +0000225 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);
Marshall Clowb5f99122016-11-02 15:30:26 +0000229 constexpr unspecified operator[](difference_type n) const;
Marshall Clowf8fec4e2016-07-08 16:54:47 +0000230private:
231 Iterator current; // exposition only
232};
233
234template <class Iterator1, class Iterator2>
Marshall Clowb5f99122016-11-02 15:30:26 +0000235constexpr bool // constexpr in C++17
Marshall Clowf8fec4e2016-07-08 16:54:47 +0000236operator==(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
237
238template <class Iterator1, class Iterator2>
Marshall Clowb5f99122016-11-02 15:30:26 +0000239constexpr bool // constexpr in C++17
Marshall Clowf8fec4e2016-07-08 16:54:47 +0000240operator!=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
241
242template <class Iterator1, class Iterator2>
Marshall Clowb5f99122016-11-02 15:30:26 +0000243constexpr bool // constexpr in C++17
Marshall Clowf8fec4e2016-07-08 16:54:47 +0000244operator<(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
245
246template <class Iterator1, class Iterator2>
Marshall Clowb5f99122016-11-02 15:30:26 +0000247constexpr bool // constexpr in C++17
Marshall Clowf8fec4e2016-07-08 16:54:47 +0000248operator<=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
249
250template <class Iterator1, class Iterator2>
Marshall Clowb5f99122016-11-02 15:30:26 +0000251constexpr bool // constexpr in C++17
Marshall Clowf8fec4e2016-07-08 16:54:47 +0000252operator>(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
253
254template <class Iterator1, class Iterator2>
Marshall Clowb5f99122016-11-02 15:30:26 +0000255constexpr bool // constexpr in C++17
Marshall Clowf8fec4e2016-07-08 16:54:47 +0000256operator>=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
257
258template <class Iterator1, class Iterator2>
Marshall Clowb5f99122016-11-02 15:30:26 +0000259constexpr auto // constexpr in C++17
Marshall Clowf8fec4e2016-07-08 16:54:47 +0000260operator-(const move_iterator<Iterator1>& x,
261 const move_iterator<Iterator2>& y) -> decltype(x.base() - y.base());
262
263template <class Iterator>
Marshall Clowb5f99122016-11-02 15:30:26 +0000264constexpr move_iterator<Iterator> operator+( // constexpr in C++17
Louis Dionne173f29e2019-05-29 16:01:36 +0000265 typename move_iterator<Iterator>::difference_type n,
Marshall Clowb5f99122016-11-02 15:30:26 +0000266 const move_iterator<Iterator>& x);
Marshall Clowf8fec4e2016-07-08 16:54:47 +0000267
Marshall Clowb5f99122016-11-02 15:30:26 +0000268template <class Iterator> // constexpr in C++17
269constexpr move_iterator<Iterator> make_move_iterator(const Iterator& i);
Marshall Clowf8fec4e2016-07-08 16:54:47 +0000270
271
Howard Hinnantc51e1022010-05-11 19:42:16 +0000272template <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
Marshall Clow0735e4e2015-04-16 21:36:54 +0000281 constexpr istream_iterator();
Howard Hinnantc51e1022010-05-11 19:42:16 +0000282 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
Howard Hinnant011138d2012-07-20 19:36:34 +0000332 istreambuf_iterator() noexcept;
333 istreambuf_iterator(istream_type& s) noexcept;
334 istreambuf_iterator(streambuf_type* s) noexcept;
335 istreambuf_iterator(a-private-type) noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000336
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
Howard Hinnant011138d2012-07-20 19:36:34 +0000362 ostreambuf_iterator(ostream_type& s) noexcept;
363 ostreambuf_iterator(streambuf_type* s) noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000364 ostreambuf_iterator& operator=(charT c);
365 ostreambuf_iterator& operator*();
366 ostreambuf_iterator& operator++();
367 ostreambuf_iterator& operator++(int);
Howard Hinnant011138d2012-07-20 19:36:34 +0000368 bool failed() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000369};
370
Marshall Clow99ba0022017-01-04 17:58:17 +0000371template <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]);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000377
Marshall Clow99ba0022017-01-04 17:58:17 +0000378template <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
Marshall Clowb278e9c2013-08-30 01:17:07 +0000390
Marshall Clowef357272014-11-19 19:43:23 +0000391// 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
Marshall Clow3c5363e2019-02-27 02:58:56 +0000394
395template <class C> constexpr auto ssize(const C& c)
Arthur O'Dwyer2fc9b5d2021-04-17 17:03:20 -0400396 -> common_type_t<ptrdiff_t, make_signed_t<decltype(c.size())>>; // C++20
Marshall Clow3c5363e2019-02-27 02:58:56 +0000397template <class T, ptrdiff_t> constexpr ptrdiff_t ssize(const T (&array)[N]) noexcept; // C++20
398
Marshall Clowef357272014-11-19 19:43:23 +0000399template <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
Howard Hinnantc51e1022010-05-11 19:42:16 +0000407} // std
408
409*/
410
411#include <__config>
Eric Fiselier876c6862016-02-20 00:19:45 +0000412#include <iosfwd> // for forward declarations of vector and string.
Marshall Clow3dc05502014-02-27 02:11:50 +0000413#include <__functional_base>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000414#include <type_traits>
Arthur O'Dwyer7deec122021-03-24 18:19:12 -0400415#include <compare>
416#include <concepts>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000417#include <cstddef>
Marshall Clowb278e9c2013-08-30 01:17:07 +0000418#include <initializer_list>
zoecarver61ae1dc2021-04-19 14:28:27 -0400419#include <__iterator/incrementable_traits.h>
420#include <__iterator/readable_traits.h>
Louis Dionne735bc462021-04-14 13:59:03 -0400421#include <__memory/addressof.h>
Arthur O'Dwyer1ac9f092021-01-15 12:59:56 -0500422#include <__memory/pointer_traits.h>
Marshall Clow0a1e7502018-09-12 19:41:40 +0000423#include <version>
Howard Hinnant48fd5d52012-11-14 21:17:15 +0000424
Eric Fiselier14b6de92014-08-10 23:53:08 +0000425#include <__debug>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000426
Howard Hinnantaaaa52b2011-10-17 20:05:10 +0000427#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000428#pragma GCC system_header
Howard Hinnantaaaa52b2011-10-17 20:05:10 +0000429#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000430
431_LIBCPP_BEGIN_NAMESPACE_STD
Christopher Di Bella490fe402021-03-23 03:55:52 +0000432
433#if !defined(_LIBCPP_HAS_NO_RANGES)
Christopher Di Bella875636f2021-04-04 05:12:46 +0000434
Christopher Di Bella875636f2021-04-04 05:12:46 +0000435// [iterator.traits]
436template<__dereferenceable _Tp>
437using iter_reference_t = decltype(*declval<_Tp&>());
Christopher Di Bella490fe402021-03-23 03:55:52 +0000438#endif // !defined(_LIBCPP_HAS_NO_RANGES)
439
Eric Fiselier7b2a34f2019-11-16 20:24:39 -0500440template <class _Iter>
441struct _LIBCPP_TEMPLATE_VIS iterator_traits;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000442
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000443struct _LIBCPP_TEMPLATE_VIS input_iterator_tag {};
444struct _LIBCPP_TEMPLATE_VIS output_iterator_tag {};
445struct _LIBCPP_TEMPLATE_VIS forward_iterator_tag : public input_iterator_tag {};
446struct _LIBCPP_TEMPLATE_VIS bidirectional_iterator_tag : public forward_iterator_tag {};
447struct _LIBCPP_TEMPLATE_VIS random_access_iterator_tag : public bidirectional_iterator_tag {};
Eric Fiselier30005a92019-11-16 20:12:48 -0500448#if _LIBCPP_STD_VER > 17
Arthur O'Dwyer1ac9f092021-01-15 12:59:56 -0500449struct _LIBCPP_TEMPLATE_VIS contiguous_iterator_tag : public random_access_iterator_tag {};
Eric Fiselier30005a92019-11-16 20:12:48 -0500450#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000451
Eric Fiselier7b2a34f2019-11-16 20:24:39 -0500452template <class _Iter>
453struct __iter_traits_cache {
454 using type = _If<
455 __is_primary_template<iterator_traits<_Iter> >::value,
456 _Iter,
457 iterator_traits<_Iter>
458 >;
459};
460template <class _Iter>
461using _ITER_TRAITS = typename __iter_traits_cache<_Iter>::type;
462
463struct __iter_concept_concept_test {
464 template <class _Iter>
465 using _Apply = typename _ITER_TRAITS<_Iter>::iterator_concept;
466};
467struct __iter_concept_category_test {
468 template <class _Iter>
469 using _Apply = typename _ITER_TRAITS<_Iter>::iterator_category;
470};
471struct __iter_concept_random_fallback {
472 template <class _Iter>
473 using _Apply = _EnableIf<
474 __is_primary_template<iterator_traits<_Iter> >::value,
475 random_access_iterator_tag
476 >;
477};
478
479template <class _Iter, class _Tester> struct __test_iter_concept
480 : _IsValidExpansion<_Tester::template _Apply, _Iter>,
481 _Tester
482{
483};
484
485template <class _Iter>
486struct __iter_concept_cache {
487 using type = _Or<
488 __test_iter_concept<_Iter, __iter_concept_concept_test>,
489 __test_iter_concept<_Iter, __iter_concept_category_test>,
490 __test_iter_concept<_Iter, __iter_concept_random_fallback>
491 >;
492};
493
494template <class _Iter>
495using _ITER_CONCEPT = typename __iter_concept_cache<_Iter>::type::template _Apply<_Iter>;
496
497
Howard Hinnantc51e1022010-05-11 19:42:16 +0000498template <class _Tp>
Marshall Clow50abbe42018-11-13 05:33:31 +0000499struct __has_iterator_typedefs
500{
501private:
502 struct __two {char __lx; char __lxx;};
503 template <class _Up> static __two __test(...);
Arthur O'Dwyer07b22492020-11-27 11:02:06 -0500504 template <class _Up> static char __test(typename __void_t<typename _Up::iterator_category>::type* = 0,
505 typename __void_t<typename _Up::difference_type>::type* = 0,
506 typename __void_t<typename _Up::value_type>::type* = 0,
507 typename __void_t<typename _Up::reference>::type* = 0,
508 typename __void_t<typename _Up::pointer>::type* = 0);
Marshall Clow50abbe42018-11-13 05:33:31 +0000509public:
510 static const bool value = sizeof(__test<_Tp>(0,0,0,0,0)) == 1;
511};
512
513
514template <class _Tp>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000515struct __has_iterator_category
516{
517private:
Howard Hinnant49e145e2012-10-30 19:06:59 +0000518 struct __two {char __lx; char __lxx;};
Howard Hinnantc51e1022010-05-11 19:42:16 +0000519 template <class _Up> static __two __test(...);
Bruce Mitchener170d8972020-11-24 12:53:53 -0500520 template <class _Up> static char __test(typename _Up::iterator_category* = nullptr);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000521public:
Bruce Mitchener170d8972020-11-24 12:53:53 -0500522 static const bool value = sizeof(__test<_Tp>(nullptr)) == 1;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000523};
524
Arthur O'Dwyer1ac9f092021-01-15 12:59:56 -0500525template <class _Tp>
526struct __has_iterator_concept
527{
528private:
529 struct __two {char __lx; char __lxx;};
530 template <class _Up> static __two __test(...);
531 template <class _Up> static char __test(typename _Up::iterator_concept* = nullptr);
532public:
533 static const bool value = sizeof(__test<_Tp>(nullptr)) == 1;
534};
535
Christopher Di Bella875636f2021-04-04 05:12:46 +0000536#if !defined(_LIBCPP_HAS_NO_RANGES)
537
538// The `cpp17-*-iterator` exposition-only concepts are easily confused with the Cpp17*Iterator tables,
539// so they've been banished to a namespace that makes it obvious they have a niche use-case.
540namespace __iterator_traits_detail {
541template<class _Ip>
542concept __cpp17_iterator =
543 requires(_Ip __i) {
544 { *__i } -> __referenceable;
545 { ++__i } -> same_as<_Ip&>;
546 { *__i++ } -> __referenceable;
547 } &&
548 copyable<_Ip>;
549
550template<class _Ip>
551concept __cpp17_input_iterator =
552 __cpp17_iterator<_Ip> &&
553 equality_comparable<_Ip> &&
554 requires(_Ip __i) {
555 typename incrementable_traits<_Ip>::difference_type;
556 typename indirectly_readable_traits<_Ip>::value_type;
557 typename common_reference_t<iter_reference_t<_Ip>&&,
558 typename indirectly_readable_traits<_Ip>::value_type&>;
559 typename common_reference_t<decltype(*__i++)&&,
560 typename indirectly_readable_traits<_Ip>::value_type&>;
561 requires signed_integral<typename incrementable_traits<_Ip>::difference_type>;
562 };
563
564template<class _Ip>
565concept __cpp17_forward_iterator =
566 __cpp17_input_iterator<_Ip> &&
567 constructible_from<_Ip> &&
568 is_lvalue_reference_v<iter_reference_t<_Ip>> &&
569 same_as<remove_cvref_t<iter_reference_t<_Ip>>,
570 typename indirectly_readable_traits<_Ip>::value_type> &&
571 requires(_Ip __i) {
572 { __i++ } -> convertible_to<_Ip const&>;
573 { *__i++ } -> same_as<iter_reference_t<_Ip>>;
574 };
575
576template<class _Ip>
577concept __cpp17_bidirectional_iterator =
578 __cpp17_forward_iterator<_Ip> &&
579 requires(_Ip __i) {
580 { --__i } -> same_as<_Ip&>;
581 { __i-- } -> convertible_to<_Ip const&>;
582 { *__i-- } -> same_as<iter_reference_t<_Ip>>;
583 };
584
585template<class _Ip>
586concept __cpp17_random_access_iterator =
587 __cpp17_bidirectional_iterator<_Ip> and
588 totally_ordered<_Ip> and
589 requires(_Ip __i, typename incrementable_traits<_Ip>::difference_type __n) {
590 { __i += __n } -> same_as<_Ip&>;
591 { __i -= __n } -> same_as<_Ip&>;
592 { __i + __n } -> same_as<_Ip>;
593 { __n + __i } -> same_as<_Ip>;
594 { __i - __n } -> same_as<_Ip>;
595 { __i - __i } -> same_as<decltype(__n)>;
596 { __i[__n] } -> convertible_to<iter_reference_t<_Ip>>;
597 };
598} // namespace __iterator_traits_detail
zoecarver9f1e2972021-04-20 08:50:11 -0400599
600template<class _Ip>
601concept __has_member_reference = requires { typename _Ip::reference; };
602
603template<class _Ip>
604concept __has_member_pointer = requires { typename _Ip::pointer; };
605
606template<class _Ip>
607concept __has_member_iterator_category = requires { typename _Ip::iterator_category; };
608
609template<class _Ip>
610concept __specifies_members = requires {
611 typename _Ip::value_type;
612 typename _Ip::difference_type;
613 requires __has_member_reference<_Ip>;
614 requires __has_member_iterator_category<_Ip>;
615 };
616
617template<class>
618struct __iterator_traits_member_pointer_or_void {
619 using type = void;
620};
621
622template<__has_member_pointer _Tp>
623struct __iterator_traits_member_pointer_or_void<_Tp> {
624 using type = typename _Tp::pointer;
625};
626
627template<class _Tp>
628concept __cpp17_iterator_missing_members =
629 !__specifies_members<_Tp> &&
630 __iterator_traits_detail::__cpp17_iterator<_Tp>;
631
632template<class _Tp>
633concept __cpp17_input_iterator_missing_members =
634 __cpp17_iterator_missing_members<_Tp> &&
635 __iterator_traits_detail::__cpp17_input_iterator<_Tp>;
636
637// Otherwise, `pointer` names `void`.
638template<class>
639struct __iterator_traits_member_pointer_or_arrow_or_void { using type = void; };
640
641// [iterator.traits]/3.2.1
642// If the qualified-id `I::pointer` is valid and denotes a type, `pointer` names that type.
643template<__has_member_pointer _Ip>
644struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> { using type = typename _Ip::pointer; };
645
646// Otherwise, if `decltype(declval<I&>().operator->())` is well-formed, then `pointer` names that
647// type.
648template<class _Ip>
649concept __has_arrow =
650 requires(_Ip& __i) {
651 __i.operator->();
652 };
653
654template<class _Ip>
655 requires __has_arrow<_Ip> && (!__has_member_pointer<_Ip>)
656struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> {
657 using type = decltype(declval<_Ip&>().operator->());
658};
659
660// Otherwise, `reference` names `iter-reference-t<I>`.
661template<class _Ip>
662struct __iterator_traits_member_reference { using type = iter_reference_t<_Ip>; };
663
664// [iterator.traits]/3.2.2
665// If the qualified-id `I::reference` is valid and denotes a type, `reference` names that type.
666template<__has_member_reference _Ip>
667struct __iterator_traits_member_reference<_Ip> { using type = typename _Ip::reference; };
668
669// [iterator.traits]/3.2.3.4
670// input_iterator_tag
671template<class _Ip>
672struct __deduce_iterator_category {
673 using type = input_iterator_tag;
674};
675
676// [iterator.traits]/3.2.3.1
677// `random_access_iterator_tag` if `I` satisfies `cpp17-random-access-iterator`, or otherwise
678template<__iterator_traits_detail::__cpp17_random_access_iterator _Ip>
679struct __deduce_iterator_category<_Ip> {
680 using type = random_access_iterator_tag;
681};
682
683// [iterator.traits]/3.2.3.2
684// `bidirectional_iterator_tag` if `I` satisfies `cpp17-bidirectional-iterator`, or otherwise
685template<__iterator_traits_detail::__cpp17_bidirectional_iterator _Ip>
686struct __deduce_iterator_category<_Ip> {
687 using type = bidirectional_iterator_tag;
688};
689
690// [iterator.traits]/3.2.3.3
691// `forward_iterator_tag` if `I` satisfies `cpp17-forward-iterator`, or otherwise
692template<__iterator_traits_detail::__cpp17_forward_iterator _Ip>
693struct __deduce_iterator_category<_Ip> {
694 using type = forward_iterator_tag;
695};
696
697template<class _Ip>
698struct __iterator_traits_iterator_category : __deduce_iterator_category<_Ip> {};
699
700// [iterator.traits]/3.2.3
701// If the qualified-id `I::iterator-category` is valid and denotes a type, `iterator-category` names
702// that type.
703template<__has_member_iterator_category _Ip>
704struct __iterator_traits_iterator_category<_Ip> {
705 using type = typename _Ip::iterator_category;
706};
707
708// otherwise, it names void.
709template<class>
710struct __iterator_traits_difference_type { using type = void; };
711
712// If the qualified-id `incrementable_traits<I>::difference_type` is valid and denotes a type, then
713// `difference_type` names that type;
714template<class _Ip>
715requires requires { typename incrementable_traits<_Ip>::difference_type; }
716struct __iterator_traits_difference_type<_Ip> {
717 using type = typename incrementable_traits<_Ip>::difference_type;
718};
719
720// [iterator.traits]/3.4
721// Otherwise, `iterator_traits<I>` has no members by any of the above names.
722template<class>
723struct __iterator_traits {};
724
725// [iterator.traits]/3.1
726// If `I` has valid ([temp.deduct]) member types `difference-type`, `value-type`, `reference`, and
727// `iterator-category`, then `iterator-traits<I>` has the following publicly accessible members:
728template<__specifies_members _Ip>
729struct __iterator_traits<_Ip> {
730 using iterator_category = typename _Ip::iterator_category;
731 using value_type = typename _Ip::value_type;
732 using difference_type = typename _Ip::difference_type;
733 using pointer = typename __iterator_traits_member_pointer_or_void<_Ip>::type;
734 using reference = typename _Ip::reference;
735};
736
737// [iterator.traits]/3.2
738// Otherwise, if `I` satisfies the exposition-only concept `cpp17-input-iterator`,
739// `iterator-traits<I>` has the following publicly accessible members:
740template<__cpp17_input_iterator_missing_members _Ip>
741struct __iterator_traits<_Ip> {
742 using iterator_category = typename __iterator_traits_iterator_category<_Ip>::type;
743 using value_type = typename indirectly_readable_traits<_Ip>::value_type;
744 using difference_type = typename incrementable_traits<_Ip>::difference_type;
745 using pointer = typename __iterator_traits_member_pointer_or_arrow_or_void<_Ip>::type;
746 using reference = typename __iterator_traits_member_reference<_Ip>::type;
747};
748
749// Otherwise, if `I` satisfies the exposition-only concept `cpp17-iterator`, then
750// `iterator_traits<I>` has the following publicly accessible members:
751template<__cpp17_iterator_missing_members _Ip>
752struct __iterator_traits<_Ip> {
753 using iterator_category = output_iterator_tag;
754 using value_type = void;
755 using difference_type = typename __iterator_traits_difference_type<_Ip>::type;
756 using pointer = void;
757 using reference = void;
758};
759
760template<class _Ip>
761struct iterator_traits : __iterator_traits<_Ip> {
762 using __primary_template = iterator_traits;
763};
764
765#else // !defined(_LIBCPP_HAS_NO_RANGES)
Christopher Di Bella875636f2021-04-04 05:12:46 +0000766
Howard Hinnantc51e1022010-05-11 19:42:16 +0000767template <class _Iter, bool> struct __iterator_traits {};
768
zoecarver9f1e2972021-04-20 08:50:11 -0400769template <class _Iter, bool> struct __iterator_traits_impl {};
770
771template <class _Iter>
772struct __iterator_traits_impl<_Iter, true>
773{
774 typedef typename _Iter::difference_type difference_type;
775 typedef typename _Iter::value_type value_type;
776 typedef typename _Iter::pointer pointer;
777 typedef typename _Iter::reference reference;
778 typedef typename _Iter::iterator_category iterator_category;
779};
780
Howard Hinnantc51e1022010-05-11 19:42:16 +0000781template <class _Iter>
782struct __iterator_traits<_Iter, true>
Marshall Clow75533b02014-01-03 22:55:49 +0000783 : __iterator_traits_impl
Howard Hinnantc51e1022010-05-11 19:42:16 +0000784 <
785 _Iter,
786 is_convertible<typename _Iter::iterator_category, input_iterator_tag>::value ||
787 is_convertible<typename _Iter::iterator_category, output_iterator_tag>::value
788 >
789{};
790
791// iterator_traits<Iterator> will only have the nested types if Iterator::iterator_category
792// exists. Else iterator_traits<Iterator> will be an empty class. This is a
793// conforming extension which allows some programs to compile and behave as
794// the client expects instead of failing at compile time.
795
796template <class _Iter>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000797struct _LIBCPP_TEMPLATE_VIS iterator_traits
Eric Fiselier7b2a34f2019-11-16 20:24:39 -0500798 : __iterator_traits<_Iter, __has_iterator_typedefs<_Iter>::value> {
799
800 using __primary_template = iterator_traits;
801};
zoecarver9f1e2972021-04-20 08:50:11 -0400802#endif // !defined(_LIBCPP_HAS_NO_RANGES)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000803
804template<class _Tp>
zoecarver9f1e2972021-04-20 08:50:11 -0400805#if !defined(_LIBCPP_HAS_NO_RANGES)
806requires is_object_v<_Tp>
807#endif
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000808struct _LIBCPP_TEMPLATE_VIS iterator_traits<_Tp*>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000809{
810 typedef ptrdiff_t difference_type;
Marshall Clow56d53522017-11-14 00:03:10 +0000811 typedef typename remove_cv<_Tp>::type value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000812 typedef _Tp* pointer;
813 typedef _Tp& reference;
814 typedef random_access_iterator_tag iterator_category;
Eric Fiselier30005a92019-11-16 20:12:48 -0500815#if _LIBCPP_STD_VER > 17
816 typedef contiguous_iterator_tag iterator_concept;
817#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000818};
819
820template <class _Tp, class _Up, bool = __has_iterator_category<iterator_traits<_Tp> >::value>
821struct __has_iterator_category_convertible_to
Arthur O'Dwyer1ac9f092021-01-15 12:59:56 -0500822 : _BoolConstant<is_convertible<typename iterator_traits<_Tp>::iterator_category, _Up>::value>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000823{};
824
825template <class _Tp, class _Up>
Arthur O'Dwyer1ac9f092021-01-15 12:59:56 -0500826struct __has_iterator_category_convertible_to<_Tp, _Up, false> : false_type {};
827
828template <class _Tp, class _Up, bool = __has_iterator_concept<_Tp>::value>
829struct __has_iterator_concept_convertible_to
830 : _BoolConstant<is_convertible<typename _Tp::iterator_concept, _Up>::value>
831{};
832
833template <class _Tp, class _Up>
834struct __has_iterator_concept_convertible_to<_Tp, _Up, false> : false_type {};
Howard Hinnantc51e1022010-05-11 19:42:16 +0000835
836template <class _Tp>
Eric Fiseliercd5a6772019-11-18 01:46:58 -0500837struct __is_cpp17_input_iterator : public __has_iterator_category_convertible_to<_Tp, input_iterator_tag> {};
Howard Hinnantc51e1022010-05-11 19:42:16 +0000838
839template <class _Tp>
Eric Fiseliercd5a6772019-11-18 01:46:58 -0500840struct __is_cpp17_forward_iterator : public __has_iterator_category_convertible_to<_Tp, forward_iterator_tag> {};
Howard Hinnantc51e1022010-05-11 19:42:16 +0000841
842template <class _Tp>
Eric Fiseliercd5a6772019-11-18 01:46:58 -0500843struct __is_cpp17_bidirectional_iterator : public __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag> {};
Howard Hinnantc51e1022010-05-11 19:42:16 +0000844
845template <class _Tp>
Eric Fiseliercd5a6772019-11-18 01:46:58 -0500846struct __is_cpp17_random_access_iterator : public __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag> {};
Howard Hinnantc51e1022010-05-11 19:42:16 +0000847
Arthur O'Dwyer1ac9f092021-01-15 12:59:56 -0500848// __is_cpp17_contiguous_iterator determines if an iterator is contiguous,
849// either because it advertises itself as such (in C++20) or because it
850// is a pointer type or a known trivial wrapper around a pointer type,
851// such as __wrap_iter<T*>.
852//
Eric Fiselier30005a92019-11-16 20:12:48 -0500853#if _LIBCPP_STD_VER > 17
854template <class _Tp>
Arthur O'Dwyer1ac9f092021-01-15 12:59:56 -0500855struct __is_cpp17_contiguous_iterator : _Or<
856 __has_iterator_category_convertible_to<_Tp, contiguous_iterator_tag>,
857 __has_iterator_concept_convertible_to<_Tp, contiguous_iterator_tag>
858> {};
Eric Fiseliercd5a6772019-11-18 01:46:58 -0500859#else
860template <class _Tp>
Arthur O'Dwyer1ac9f092021-01-15 12:59:56 -0500861struct __is_cpp17_contiguous_iterator : false_type {};
Eric Fiselier30005a92019-11-16 20:12:48 -0500862#endif
863
Arthur O'Dwyer1ac9f092021-01-15 12:59:56 -0500864// Any native pointer which is an iterator is also a contiguous iterator.
865template <class _Up>
866struct __is_cpp17_contiguous_iterator<_Up*> : true_type {};
867
Eric Fiseliercd5a6772019-11-18 01:46:58 -0500868
Marshall Clow039b2f02016-01-13 21:54:34 +0000869template <class _Tp>
Eric Fiseliercd5a6772019-11-18 01:46:58 -0500870struct __is_exactly_cpp17_input_iterator
Louis Dionne173f29e2019-05-29 16:01:36 +0000871 : public integral_constant<bool,
872 __has_iterator_category_convertible_to<_Tp, input_iterator_tag>::value &&
Marshall Clowb5f99122016-11-02 15:30:26 +0000873 !__has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value> {};
Marshall Clow039b2f02016-01-13 21:54:34 +0000874
Louis Dionned23a5f22019-06-20 19:32:00 +0000875#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
876template<class _InputIterator>
877using __iter_value_type = typename iterator_traits<_InputIterator>::value_type;
878
879template<class _InputIterator>
880using __iter_key_type = remove_const_t<typename iterator_traits<_InputIterator>::value_type::first_type>;
881
882template<class _InputIterator>
883using __iter_mapped_type = typename iterator_traits<_InputIterator>::value_type::second_type;
884
885template<class _InputIterator>
886using __iter_to_alloc_type = pair<
887 add_const_t<typename iterator_traits<_InputIterator>::value_type::first_type>,
888 typename iterator_traits<_InputIterator>::value_type::second_type>;
889#endif
890
Howard Hinnantc51e1022010-05-11 19:42:16 +0000891template<class _Category, class _Tp, class _Distance = ptrdiff_t,
892 class _Pointer = _Tp*, class _Reference = _Tp&>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000893struct _LIBCPP_TEMPLATE_VIS iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +0000894{
895 typedef _Tp value_type;
896 typedef _Distance difference_type;
897 typedef _Pointer pointer;
898 typedef _Reference reference;
899 typedef _Category iterator_category;
900};
901
902template <class _InputIter>
Marshall Clow75468e72017-05-17 18:51:36 +0000903inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000904void __advance(_InputIter& __i,
905 typename iterator_traits<_InputIter>::difference_type __n, input_iterator_tag)
906{
907 for (; __n > 0; --__n)
908 ++__i;
909}
910
911template <class _BiDirIter>
Marshall Clow75468e72017-05-17 18:51:36 +0000912inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000913void __advance(_BiDirIter& __i,
914 typename iterator_traits<_BiDirIter>::difference_type __n, bidirectional_iterator_tag)
915{
916 if (__n >= 0)
917 for (; __n > 0; --__n)
918 ++__i;
919 else
920 for (; __n < 0; ++__n)
921 --__i;
922}
923
924template <class _RandIter>
Marshall Clow75468e72017-05-17 18:51:36 +0000925inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000926void __advance(_RandIter& __i,
927 typename iterator_traits<_RandIter>::difference_type __n, random_access_iterator_tag)
928{
929 __i += __n;
930}
931
Louis Dionne45768662020-06-08 16:16:01 -0400932template <class _InputIter, class _Distance>
Marshall Clow75468e72017-05-17 18:51:36 +0000933inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Louis Dionne45768662020-06-08 16:16:01 -0400934void advance(_InputIter& __i, _Distance __orig_n)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000935{
Louis Dionne45768662020-06-08 16:16:01 -0400936 _LIBCPP_ASSERT(__orig_n >= 0 || __is_cpp17_bidirectional_iterator<_InputIter>::value,
937 "Attempt to advance(it, n) with negative n on a non-bidirectional iterator");
Arthur O'Dwyer6e9069c2020-12-07 23:42:47 -0500938 typedef decltype(_VSTD::__convert_to_integral(__orig_n)) _IntegralSize;
Louis Dionne45768662020-06-08 16:16:01 -0400939 _IntegralSize __n = __orig_n;
Arthur O'Dwyer6e9069c2020-12-07 23:42:47 -0500940 _VSTD::__advance(__i, __n, typename iterator_traits<_InputIter>::iterator_category());
Howard Hinnantc51e1022010-05-11 19:42:16 +0000941}
942
943template <class _InputIter>
Marshall Clow75468e72017-05-17 18:51:36 +0000944inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000945typename iterator_traits<_InputIter>::difference_type
946__distance(_InputIter __first, _InputIter __last, input_iterator_tag)
947{
948 typename iterator_traits<_InputIter>::difference_type __r(0);
949 for (; __first != __last; ++__first)
950 ++__r;
951 return __r;
952}
953
954template <class _RandIter>
Marshall Clow75468e72017-05-17 18:51:36 +0000955inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000956typename iterator_traits<_RandIter>::difference_type
957__distance(_RandIter __first, _RandIter __last, random_access_iterator_tag)
958{
959 return __last - __first;
960}
961
962template <class _InputIter>
Marshall Clow75468e72017-05-17 18:51:36 +0000963inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000964typename iterator_traits<_InputIter>::difference_type
965distance(_InputIter __first, _InputIter __last)
966{
Arthur O'Dwyer6e9069c2020-12-07 23:42:47 -0500967 return _VSTD::__distance(__first, __last, typename iterator_traits<_InputIter>::iterator_category());
Howard Hinnantc51e1022010-05-11 19:42:16 +0000968}
969
Marshall Clow990c70d2015-11-07 17:48:49 +0000970template <class _InputIter>
Marshall Clow75468e72017-05-17 18:51:36 +0000971inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Rachel Craik2048d822017-07-24 22:17:05 +0000972typename enable_if
973<
Eric Fiseliercd5a6772019-11-18 01:46:58 -0500974 __is_cpp17_input_iterator<_InputIter>::value,
Rachel Craik2048d822017-07-24 22:17:05 +0000975 _InputIter
976>::type
Marshall Clow990c70d2015-11-07 17:48:49 +0000977next(_InputIter __x,
Rachel Craik2048d822017-07-24 22:17:05 +0000978 typename iterator_traits<_InputIter>::difference_type __n = 1)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000979{
Eric Fiseliercd5a6772019-11-18 01:46:58 -0500980 _LIBCPP_ASSERT(__n >= 0 || __is_cpp17_bidirectional_iterator<_InputIter>::value,
Louis Dionne45768662020-06-08 16:16:01 -0400981 "Attempt to next(it, n) with negative n on a non-bidirectional iterator");
Marshall Clow3d435212019-03-22 22:32:20 +0000982
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000983 _VSTD::advance(__x, __n);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000984 return __x;
985}
986
Marshall Clow3d435212019-03-22 22:32:20 +0000987template <class _InputIter>
Marshall Clow75468e72017-05-17 18:51:36 +0000988inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Rachel Craik2048d822017-07-24 22:17:05 +0000989typename enable_if
990<
Eric Fiseliercd5a6772019-11-18 01:46:58 -0500991 __is_cpp17_input_iterator<_InputIter>::value,
Marshall Clow3d435212019-03-22 22:32:20 +0000992 _InputIter
Rachel Craik2048d822017-07-24 22:17:05 +0000993>::type
Marshall Clow3d435212019-03-22 22:32:20 +0000994prev(_InputIter __x,
995 typename iterator_traits<_InputIter>::difference_type __n = 1)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000996{
Eric Fiseliercd5a6772019-11-18 01:46:58 -0500997 _LIBCPP_ASSERT(__n <= 0 || __is_cpp17_bidirectional_iterator<_InputIter>::value,
Louis Dionne45768662020-06-08 16:16:01 -0400998 "Attempt to prev(it, n) with a positive n on a non-bidirectional iterator");
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000999 _VSTD::advance(__x, -__n);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001000 return __x;
1001}
1002
Eric Fiselier883af112017-04-13 02:54:13 +00001003
1004template <class _Tp, class = void>
1005struct __is_stashing_iterator : false_type {};
1006
1007template <class _Tp>
1008struct __is_stashing_iterator<_Tp, typename __void_t<typename _Tp::__stashing_iterator_tag>::type>
1009 : true_type {};
1010
Howard Hinnantc51e1022010-05-11 19:42:16 +00001011template <class _Iter>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +00001012class _LIBCPP_TEMPLATE_VIS reverse_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +00001013 : public iterator<typename iterator_traits<_Iter>::iterator_category,
1014 typename iterator_traits<_Iter>::value_type,
1015 typename iterator_traits<_Iter>::difference_type,
1016 typename iterator_traits<_Iter>::pointer,
1017 typename iterator_traits<_Iter>::reference>
1018{
Marshall Clow0ad029e2014-03-11 22:05:31 +00001019private:
Marshall Clow5ace5542016-10-19 15:12:50 +00001020 /*mutable*/ _Iter __t; // no longer used as of LWG #2360, not removed due to ABI break
Eric Fiselier883af112017-04-13 02:54:13 +00001021
1022 static_assert(!__is_stashing_iterator<_Iter>::value,
1023 "The specified iterator type cannot be used with reverse_iterator; "
1024 "Using stashing iterators with reverse_iterator causes undefined behavior");
1025
Marshall Clow1f61f0a2014-03-12 01:19:36 +00001026protected:
1027 _Iter current;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001028public:
1029 typedef _Iter iterator_type;
1030 typedef typename iterator_traits<_Iter>::difference_type difference_type;
1031 typedef typename iterator_traits<_Iter>::reference reference;
1032 typedef typename iterator_traits<_Iter>::pointer pointer;
Arthur O'Dwyer1ac9f092021-01-15 12:59:56 -05001033 typedef _If<__is_cpp17_random_access_iterator<_Iter>::value,
1034 random_access_iterator_tag,
1035 typename iterator_traits<_Iter>::iterator_category> iterator_category;
1036#if _LIBCPP_STD_VER > 17
1037 typedef _If<__is_cpp17_random_access_iterator<_Iter>::value,
1038 random_access_iterator_tag,
1039 bidirectional_iterator_tag> iterator_concept;
1040#endif
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001041
Marshall Clow5ace5542016-10-19 15:12:50 +00001042 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1043 reverse_iterator() : __t(), current() {}
1044 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1045 explicit reverse_iterator(_Iter __x) : __t(__x), current(__x) {}
1046 template <class _Up>
1047 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1048 reverse_iterator(const reverse_iterator<_Up>& __u) : __t(__u.base()), current(__u.base()) {}
1049 template <class _Up>
1050 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1051 reverse_iterator& operator=(const reverse_iterator<_Up>& __u)
1052 { __t = current = __u.base(); return *this; }
1053 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1054 _Iter base() const {return current;}
1055 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1056 reference operator*() const {_Iter __tmp = current; return *--__tmp;}
1057 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1058 pointer operator->() const {return _VSTD::addressof(operator*());}
1059 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1060 reverse_iterator& operator++() {--current; return *this;}
1061 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1062 reverse_iterator operator++(int) {reverse_iterator __tmp(*this); --current; return __tmp;}
1063 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1064 reverse_iterator& operator--() {++current; return *this;}
1065 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1066 reverse_iterator operator--(int) {reverse_iterator __tmp(*this); ++current; return __tmp;}
1067 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1068 reverse_iterator operator+ (difference_type __n) const {return reverse_iterator(current - __n);}
1069 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1070 reverse_iterator& operator+=(difference_type __n) {current -= __n; return *this;}
1071 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1072 reverse_iterator operator- (difference_type __n) const {return reverse_iterator(current + __n);}
1073 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1074 reverse_iterator& operator-=(difference_type __n) {current += __n; return *this;}
1075 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1076 reference operator[](difference_type __n) const {return *(*this + __n);}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001077};
1078
1079template <class _Iter1, class _Iter2>
Marshall Clow5ace5542016-10-19 15:12:50 +00001080inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00001081bool
1082operator==(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
1083{
1084 return __x.base() == __y.base();
1085}
1086
1087template <class _Iter1, class _Iter2>
Marshall Clow5ace5542016-10-19 15:12:50 +00001088inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00001089bool
1090operator<(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
1091{
1092 return __x.base() > __y.base();
1093}
1094
1095template <class _Iter1, class _Iter2>
Marshall Clow5ace5542016-10-19 15:12:50 +00001096inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00001097bool
1098operator!=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
1099{
1100 return __x.base() != __y.base();
1101}
1102
1103template <class _Iter1, class _Iter2>
Marshall Clow5ace5542016-10-19 15:12:50 +00001104inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00001105bool
1106operator>(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
1107{
1108 return __x.base() < __y.base();
1109}
1110
1111template <class _Iter1, class _Iter2>
Marshall Clow5ace5542016-10-19 15:12:50 +00001112inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00001113bool
1114operator>=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
1115{
1116 return __x.base() <= __y.base();
1117}
1118
1119template <class _Iter1, class _Iter2>
Marshall Clow5ace5542016-10-19 15:12:50 +00001120inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00001121bool
1122operator<=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
1123{
1124 return __x.base() >= __y.base();
1125}
1126
Marshall Clow476d3f42016-07-18 13:19:00 +00001127#ifndef _LIBCPP_CXX03_LANG
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001128template <class _Iter1, class _Iter2>
Marshall Clow5ace5542016-10-19 15:12:50 +00001129inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001130auto
1131operator-(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
1132-> decltype(__y.base() - __x.base())
1133{
1134 return __y.base() - __x.base();
1135}
1136#else
Howard Hinnantc51e1022010-05-11 19:42:16 +00001137template <class _Iter1, class _Iter2>
1138inline _LIBCPP_INLINE_VISIBILITY
1139typename reverse_iterator<_Iter1>::difference_type
1140operator-(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
1141{
1142 return __y.base() - __x.base();
1143}
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001144#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001145
1146template <class _Iter>
Marshall Clow5ace5542016-10-19 15:12:50 +00001147inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00001148reverse_iterator<_Iter>
1149operator+(typename reverse_iterator<_Iter>::difference_type __n, const reverse_iterator<_Iter>& __x)
1150{
1151 return reverse_iterator<_Iter>(__x.base() - __n);
1152}
1153
Marshall Clow6dbbdc92014-03-03 01:24:04 +00001154#if _LIBCPP_STD_VER > 11
1155template <class _Iter>
Marshall Clow5ace5542016-10-19 15:12:50 +00001156inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clow6dbbdc92014-03-03 01:24:04 +00001157reverse_iterator<_Iter> make_reverse_iterator(_Iter __i)
1158{
1159 return reverse_iterator<_Iter>(__i);
1160}
1161#endif
1162
Howard Hinnantc51e1022010-05-11 19:42:16 +00001163template <class _Container>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +00001164class _LIBCPP_TEMPLATE_VIS back_insert_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +00001165 : public iterator<output_iterator_tag,
1166 void,
1167 void,
1168 void,
Eric Fiselier9aeea872016-06-30 04:40:50 +00001169 void>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001170{
1171protected:
1172 _Container* container;
1173public:
1174 typedef _Container container_type;
1175
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -05001176 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 explicit back_insert_iterator(_Container& __x) : container(_VSTD::addressof(__x)) {}
1177 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 back_insert_iterator& operator=(const typename _Container::value_type& __value_)
Howard Hinnantbf074022011-10-22 20:59:45 +00001178 {container->push_back(__value_); return *this;}
Eric Fiselierf07d88c2017-04-19 01:34:08 +00001179#ifndef _LIBCPP_CXX03_LANG
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -05001180 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 back_insert_iterator& operator=(typename _Container::value_type&& __value_)
Howard Hinnantbf074022011-10-22 20:59:45 +00001181 {container->push_back(_VSTD::move(__value_)); return *this;}
Eric Fiselierf07d88c2017-04-19 01:34:08 +00001182#endif // _LIBCPP_CXX03_LANG
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -05001183 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 back_insert_iterator& operator*() {return *this;}
1184 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 back_insert_iterator& operator++() {return *this;}
1185 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 back_insert_iterator operator++(int) {return *this;}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001186};
1187
1188template <class _Container>
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -05001189inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
Howard Hinnantc51e1022010-05-11 19:42:16 +00001190back_insert_iterator<_Container>
1191back_inserter(_Container& __x)
1192{
1193 return back_insert_iterator<_Container>(__x);
1194}
1195
1196template <class _Container>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +00001197class _LIBCPP_TEMPLATE_VIS front_insert_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +00001198 : public iterator<output_iterator_tag,
1199 void,
1200 void,
1201 void,
Eric Fiselier9aeea872016-06-30 04:40:50 +00001202 void>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001203{
1204protected:
1205 _Container* container;
1206public:
1207 typedef _Container container_type;
1208
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -05001209 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 explicit front_insert_iterator(_Container& __x) : container(_VSTD::addressof(__x)) {}
1210 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 front_insert_iterator& operator=(const typename _Container::value_type& __value_)
Howard Hinnantbf074022011-10-22 20:59:45 +00001211 {container->push_front(__value_); return *this;}
Eric Fiselierf07d88c2017-04-19 01:34:08 +00001212#ifndef _LIBCPP_CXX03_LANG
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -05001213 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 front_insert_iterator& operator=(typename _Container::value_type&& __value_)
Howard Hinnantbf074022011-10-22 20:59:45 +00001214 {container->push_front(_VSTD::move(__value_)); return *this;}
Eric Fiselierf07d88c2017-04-19 01:34:08 +00001215#endif // _LIBCPP_CXX03_LANG
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -05001216 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 front_insert_iterator& operator*() {return *this;}
1217 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 front_insert_iterator& operator++() {return *this;}
1218 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 front_insert_iterator operator++(int) {return *this;}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001219};
1220
1221template <class _Container>
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -05001222inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
Howard Hinnantc51e1022010-05-11 19:42:16 +00001223front_insert_iterator<_Container>
1224front_inserter(_Container& __x)
1225{
1226 return front_insert_iterator<_Container>(__x);
1227}
1228
1229template <class _Container>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +00001230class _LIBCPP_TEMPLATE_VIS insert_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +00001231 : public iterator<output_iterator_tag,
1232 void,
1233 void,
1234 void,
Eric Fiselier9aeea872016-06-30 04:40:50 +00001235 void>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001236{
1237protected:
1238 _Container* container;
1239 typename _Container::iterator iter;
1240public:
1241 typedef _Container container_type;
1242
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -05001243 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 insert_iterator(_Container& __x, typename _Container::iterator __i)
Marshall Clowcef31682014-03-03 19:20:40 +00001244 : container(_VSTD::addressof(__x)), iter(__i) {}
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -05001245 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 insert_iterator& operator=(const typename _Container::value_type& __value_)
Howard Hinnantbf074022011-10-22 20:59:45 +00001246 {iter = container->insert(iter, __value_); ++iter; return *this;}
Eric Fiselierf07d88c2017-04-19 01:34:08 +00001247#ifndef _LIBCPP_CXX03_LANG
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -05001248 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 insert_iterator& operator=(typename _Container::value_type&& __value_)
Howard Hinnantbf074022011-10-22 20:59:45 +00001249 {iter = container->insert(iter, _VSTD::move(__value_)); ++iter; return *this;}
Eric Fiselierf07d88c2017-04-19 01:34:08 +00001250#endif // _LIBCPP_CXX03_LANG
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -05001251 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 insert_iterator& operator*() {return *this;}
1252 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 insert_iterator& operator++() {return *this;}
1253 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 insert_iterator& operator++(int) {return *this;}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001254};
1255
1256template <class _Container>
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -05001257inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
Howard Hinnantc51e1022010-05-11 19:42:16 +00001258insert_iterator<_Container>
1259inserter(_Container& __x, typename _Container::iterator __i)
1260{
1261 return insert_iterator<_Container>(__x, __i);
1262}
1263
1264template <class _Tp, class _CharT = char,
1265 class _Traits = char_traits<_CharT>, class _Distance = ptrdiff_t>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +00001266class _LIBCPP_TEMPLATE_VIS istream_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +00001267 : public iterator<input_iterator_tag, _Tp, _Distance, const _Tp*, const _Tp&>
1268{
1269public:
1270 typedef _CharT char_type;
1271 typedef _Traits traits_type;
1272 typedef basic_istream<_CharT,_Traits> istream_type;
1273private:
1274 istream_type* __in_stream_;
1275 _Tp __value_;
1276public:
Bruce Mitchener170d8972020-11-24 12:53:53 -05001277 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR istream_iterator() : __in_stream_(nullptr), __value_() {}
Marshall Clowb7742702016-05-17 17:44:40 +00001278 _LIBCPP_INLINE_VISIBILITY istream_iterator(istream_type& __s) : __in_stream_(_VSTD::addressof(__s))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001279 {
1280 if (!(*__in_stream_ >> __value_))
Bruce Mitchener170d8972020-11-24 12:53:53 -05001281 __in_stream_ = nullptr;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001282 }
1283
1284 _LIBCPP_INLINE_VISIBILITY const _Tp& operator*() const {return __value_;}
Marshall Clowb7742702016-05-17 17:44:40 +00001285 _LIBCPP_INLINE_VISIBILITY const _Tp* operator->() const {return _VSTD::addressof((operator*()));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001286 _LIBCPP_INLINE_VISIBILITY istream_iterator& operator++()
1287 {
1288 if (!(*__in_stream_ >> __value_))
Bruce Mitchener170d8972020-11-24 12:53:53 -05001289 __in_stream_ = nullptr;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001290 return *this;
1291 }
1292 _LIBCPP_INLINE_VISIBILITY istream_iterator operator++(int)
1293 {istream_iterator __t(*this); ++(*this); return __t;}
1294
Roger Ferrer Ibanezd16858b2017-12-11 13:54:58 +00001295 template <class _Up, class _CharU, class _TraitsU, class _DistanceU>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001296 friend _LIBCPP_INLINE_VISIBILITY
Roger Ferrer Ibanezd16858b2017-12-11 13:54:58 +00001297 bool
1298 operator==(const istream_iterator<_Up, _CharU, _TraitsU, _DistanceU>& __x,
1299 const istream_iterator<_Up, _CharU, _TraitsU, _DistanceU>& __y);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001300
Roger Ferrer Ibanezd16858b2017-12-11 13:54:58 +00001301 template <class _Up, class _CharU, class _TraitsU, class _DistanceU>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001302 friend _LIBCPP_INLINE_VISIBILITY
Roger Ferrer Ibanezd16858b2017-12-11 13:54:58 +00001303 bool
1304 operator==(const istream_iterator<_Up, _CharU, _TraitsU, _DistanceU>& __x,
1305 const istream_iterator<_Up, _CharU, _TraitsU, _DistanceU>& __y);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001306};
1307
Roger Ferrer Ibanezd16858b2017-12-11 13:54:58 +00001308template <class _Tp, class _CharT, class _Traits, class _Distance>
1309inline _LIBCPP_INLINE_VISIBILITY
1310bool
1311operator==(const istream_iterator<_Tp, _CharT, _Traits, _Distance>& __x,
1312 const istream_iterator<_Tp, _CharT, _Traits, _Distance>& __y)
1313{
1314 return __x.__in_stream_ == __y.__in_stream_;
1315}
1316
1317template <class _Tp, class _CharT, class _Traits, class _Distance>
1318inline _LIBCPP_INLINE_VISIBILITY
1319bool
1320operator!=(const istream_iterator<_Tp, _CharT, _Traits, _Distance>& __x,
1321 const istream_iterator<_Tp, _CharT, _Traits, _Distance>& __y)
1322{
1323 return !(__x == __y);
1324}
1325
Howard Hinnantc51e1022010-05-11 19:42:16 +00001326template <class _Tp, class _CharT = char, class _Traits = char_traits<_CharT> >
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +00001327class _LIBCPP_TEMPLATE_VIS ostream_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +00001328 : public iterator<output_iterator_tag, void, void, void, void>
1329{
1330public:
Louis Dionnea4d79522020-09-11 10:15:56 -04001331 typedef output_iterator_tag iterator_category;
1332 typedef void value_type;
1333#if _LIBCPP_STD_VER > 17
1334 typedef std::ptrdiff_t difference_type;
1335#else
1336 typedef void difference_type;
1337#endif
1338 typedef void pointer;
1339 typedef void reference;
1340 typedef _CharT char_type;
1341 typedef _Traits traits_type;
1342 typedef basic_ostream<_CharT, _Traits> ostream_type;
1343
Howard Hinnantc51e1022010-05-11 19:42:16 +00001344private:
1345 ostream_type* __out_stream_;
1346 const char_type* __delim_;
1347public:
Marshall Clow27a89512016-10-12 16:13:48 +00001348 _LIBCPP_INLINE_VISIBILITY ostream_iterator(ostream_type& __s) _NOEXCEPT
Bruce Mitchener170d8972020-11-24 12:53:53 -05001349 : __out_stream_(_VSTD::addressof(__s)), __delim_(nullptr) {}
Marshall Clow27a89512016-10-12 16:13:48 +00001350 _LIBCPP_INLINE_VISIBILITY ostream_iterator(ostream_type& __s, const _CharT* __delimiter) _NOEXCEPT
Marshall Clowb7742702016-05-17 17:44:40 +00001351 : __out_stream_(_VSTD::addressof(__s)), __delim_(__delimiter) {}
Howard Hinnantbf074022011-10-22 20:59:45 +00001352 _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator=(const _Tp& __value_)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001353 {
Howard Hinnantbf074022011-10-22 20:59:45 +00001354 *__out_stream_ << __value_;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001355 if (__delim_)
1356 *__out_stream_ << __delim_;
1357 return *this;
1358 }
1359
1360 _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator*() {return *this;}
1361 _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator++() {return *this;}
1362 _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator++(int) {return *this;}
1363};
1364
1365template<class _CharT, class _Traits>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +00001366class _LIBCPP_TEMPLATE_VIS istreambuf_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +00001367 : public iterator<input_iterator_tag, _CharT,
1368 typename _Traits::off_type, _CharT*,
1369 _CharT>
1370{
1371public:
1372 typedef _CharT char_type;
1373 typedef _Traits traits_type;
1374 typedef typename _Traits::int_type int_type;
1375 typedef basic_streambuf<_CharT,_Traits> streambuf_type;
1376 typedef basic_istream<_CharT,_Traits> istream_type;
1377private:
Howard Hinnant3e57b272012-11-16 22:17:23 +00001378 mutable streambuf_type* __sbuf_;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001379
1380 class __proxy
1381 {
1382 char_type __keep_;
1383 streambuf_type* __sbuf_;
1384 _LIBCPP_INLINE_VISIBILITY __proxy(char_type __c, streambuf_type* __s)
1385 : __keep_(__c), __sbuf_(__s) {}
1386 friend class istreambuf_iterator;
1387 public:
1388 _LIBCPP_INLINE_VISIBILITY char_type operator*() const {return __keep_;}
1389 };
1390
Howard Hinnant756c69b2010-09-22 16:48:34 +00001391 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e57b272012-11-16 22:17:23 +00001392 bool __test_for_eof() const
Howard Hinnantc51e1022010-05-11 19:42:16 +00001393 {
1394 if (__sbuf_ && traits_type::eq_int_type(__sbuf_->sgetc(), traits_type::eof()))
Bruce Mitchener170d8972020-11-24 12:53:53 -05001395 __sbuf_ = nullptr;
1396 return __sbuf_ == nullptr;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001397 }
1398public:
Bruce Mitchener170d8972020-11-24 12:53:53 -05001399 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR istreambuf_iterator() _NOEXCEPT : __sbuf_(nullptr) {}
Howard Hinnant011138d2012-07-20 19:36:34 +00001400 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(istream_type& __s) _NOEXCEPT
Howard Hinnantb9af8d82012-12-29 17:45:42 +00001401 : __sbuf_(__s.rdbuf()) {}
Howard Hinnant011138d2012-07-20 19:36:34 +00001402 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(streambuf_type* __s) _NOEXCEPT
Howard Hinnantb9af8d82012-12-29 17:45:42 +00001403 : __sbuf_(__s) {}
Howard Hinnant011138d2012-07-20 19:36:34 +00001404 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(const __proxy& __p) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001405 : __sbuf_(__p.__sbuf_) {}
1406
Howard Hinnant28b24882011-12-01 20:21:04 +00001407 _LIBCPP_INLINE_VISIBILITY char_type operator*() const
1408 {return static_cast<char_type>(__sbuf_->sgetc());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001409 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator& operator++()
1410 {
Howard Hinnant3e57b272012-11-16 22:17:23 +00001411 __sbuf_->sbumpc();
Howard Hinnantc51e1022010-05-11 19:42:16 +00001412 return *this;
1413 }
1414 _LIBCPP_INLINE_VISIBILITY __proxy operator++(int)
1415 {
Howard Hinnant3e57b272012-11-16 22:17:23 +00001416 return __proxy(__sbuf_->sbumpc(), __sbuf_);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001417 }
1418
1419 _LIBCPP_INLINE_VISIBILITY bool equal(const istreambuf_iterator& __b) const
Howard Hinnant3e57b272012-11-16 22:17:23 +00001420 {return __test_for_eof() == __b.__test_for_eof();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001421};
1422
1423template <class _CharT, class _Traits>
1424inline _LIBCPP_INLINE_VISIBILITY
1425bool operator==(const istreambuf_iterator<_CharT,_Traits>& __a,
1426 const istreambuf_iterator<_CharT,_Traits>& __b)
1427 {return __a.equal(__b);}
1428
1429template <class _CharT, class _Traits>
1430inline _LIBCPP_INLINE_VISIBILITY
1431bool operator!=(const istreambuf_iterator<_CharT,_Traits>& __a,
1432 const istreambuf_iterator<_CharT,_Traits>& __b)
1433 {return !__a.equal(__b);}
1434
1435template <class _CharT, class _Traits>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +00001436class _LIBCPP_TEMPLATE_VIS ostreambuf_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +00001437 : public iterator<output_iterator_tag, void, void, void, void>
1438{
1439public:
Louis Dionnea4d79522020-09-11 10:15:56 -04001440 typedef output_iterator_tag iterator_category;
1441 typedef void value_type;
1442#if _LIBCPP_STD_VER > 17
1443 typedef std::ptrdiff_t difference_type;
1444#else
1445 typedef void difference_type;
1446#endif
1447 typedef void pointer;
1448 typedef void reference;
1449 typedef _CharT char_type;
1450 typedef _Traits traits_type;
1451 typedef basic_streambuf<_CharT, _Traits> streambuf_type;
1452 typedef basic_ostream<_CharT, _Traits> ostream_type;
1453
Howard Hinnantc51e1022010-05-11 19:42:16 +00001454private:
1455 streambuf_type* __sbuf_;
1456public:
Howard Hinnant011138d2012-07-20 19:36:34 +00001457 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator(ostream_type& __s) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001458 : __sbuf_(__s.rdbuf()) {}
Howard Hinnant011138d2012-07-20 19:36:34 +00001459 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator(streambuf_type* __s) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001460 : __sbuf_(__s) {}
1461 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator=(_CharT __c)
1462 {
1463 if (__sbuf_ && traits_type::eq_int_type(__sbuf_->sputc(__c), traits_type::eof()))
Bruce Mitchener170d8972020-11-24 12:53:53 -05001464 __sbuf_ = nullptr;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001465 return *this;
1466 }
1467 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator*() {return *this;}
1468 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator++() {return *this;}
1469 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator++(int) {return *this;}
Bruce Mitchener170d8972020-11-24 12:53:53 -05001470 _LIBCPP_INLINE_VISIBILITY bool failed() const _NOEXCEPT {return __sbuf_ == nullptr;}
Howard Hinnant97955172012-09-19 19:14:15 +00001471
1472 template <class _Ch, class _Tr>
1473 friend
1474 _LIBCPP_HIDDEN
1475 ostreambuf_iterator<_Ch, _Tr>
1476 __pad_and_output(ostreambuf_iterator<_Ch, _Tr> __s,
1477 const _Ch* __ob, const _Ch* __op, const _Ch* __oe,
1478 ios_base& __iob, _Ch __fl);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001479};
1480
1481template <class _Iter>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +00001482class _LIBCPP_TEMPLATE_VIS move_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +00001483{
1484private:
1485 _Iter __i;
1486public:
1487 typedef _Iter iterator_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001488 typedef typename iterator_traits<iterator_type>::value_type value_type;
1489 typedef typename iterator_traits<iterator_type>::difference_type difference_type;
Marshall Clowd85a0562016-04-11 03:54:53 +00001490 typedef iterator_type pointer;
Arthur O'Dwyer1ac9f092021-01-15 12:59:56 -05001491 typedef _If<__is_cpp17_random_access_iterator<_Iter>::value,
1492 random_access_iterator_tag,
1493 typename iterator_traits<_Iter>::iterator_category> iterator_category;
1494#if _LIBCPP_STD_VER > 17
1495 typedef input_iterator_tag iterator_concept;
1496#endif
1497
Eric Fiselierf07d88c2017-04-19 01:34:08 +00001498#ifndef _LIBCPP_CXX03_LANG
Eric Fiselier57b8e0e2016-04-22 00:49:12 +00001499 typedef typename iterator_traits<iterator_type>::reference __reference;
1500 typedef typename conditional<
1501 is_reference<__reference>::value,
1502 typename remove_reference<__reference>::type&&,
1503 __reference
1504 >::type reference;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001505#else
1506 typedef typename iterator_traits<iterator_type>::reference reference;
1507#endif
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001508
Marshall Clowb5f99122016-11-02 15:30:26 +00001509 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1510 move_iterator() : __i() {}
1511 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1512 explicit move_iterator(_Iter __x) : __i(__x) {}
1513 template <class _Up>
1514 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1515 move_iterator(const move_iterator<_Up>& __u) : __i(__u.base()) {}
1516 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 _Iter base() const {return __i;}
Louis Dionne173f29e2019-05-29 16:01:36 +00001517 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clowb5f99122016-11-02 15:30:26 +00001518 reference operator*() const { return static_cast<reference>(*__i); }
1519 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1520 pointer operator->() const { return __i;}
1521 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1522 move_iterator& operator++() {++__i; return *this;}
1523 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1524 move_iterator operator++(int) {move_iterator __tmp(*this); ++__i; return __tmp;}
1525 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1526 move_iterator& operator--() {--__i; return *this;}
1527 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1528 move_iterator operator--(int) {move_iterator __tmp(*this); --__i; return __tmp;}
1529 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1530 move_iterator operator+ (difference_type __n) const {return move_iterator(__i + __n);}
1531 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1532 move_iterator& operator+=(difference_type __n) {__i += __n; return *this;}
1533 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1534 move_iterator operator- (difference_type __n) const {return move_iterator(__i - __n);}
1535 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1536 move_iterator& operator-=(difference_type __n) {__i -= __n; return *this;}
1537 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1538 reference operator[](difference_type __n) const { return static_cast<reference>(__i[__n]); }
Howard Hinnantc51e1022010-05-11 19:42:16 +00001539};
1540
1541template <class _Iter1, class _Iter2>
Marshall Clowb5f99122016-11-02 15:30:26 +00001542inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00001543bool
1544operator==(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1545{
1546 return __x.base() == __y.base();
1547}
1548
1549template <class _Iter1, class _Iter2>
Marshall Clowb5f99122016-11-02 15:30:26 +00001550inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00001551bool
1552operator<(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1553{
1554 return __x.base() < __y.base();
1555}
1556
1557template <class _Iter1, class _Iter2>
Marshall Clowb5f99122016-11-02 15:30:26 +00001558inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00001559bool
1560operator!=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1561{
1562 return __x.base() != __y.base();
1563}
1564
1565template <class _Iter1, class _Iter2>
Marshall Clowb5f99122016-11-02 15:30:26 +00001566inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00001567bool
1568operator>(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1569{
1570 return __x.base() > __y.base();
1571}
1572
1573template <class _Iter1, class _Iter2>
Marshall Clowb5f99122016-11-02 15:30:26 +00001574inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00001575bool
1576operator>=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1577{
1578 return __x.base() >= __y.base();
1579}
1580
1581template <class _Iter1, class _Iter2>
Marshall Clowb5f99122016-11-02 15:30:26 +00001582inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00001583bool
1584operator<=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1585{
1586 return __x.base() <= __y.base();
1587}
1588
Marshall Clow476d3f42016-07-18 13:19:00 +00001589#ifndef _LIBCPP_CXX03_LANG
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001590template <class _Iter1, class _Iter2>
Marshall Clowb5f99122016-11-02 15:30:26 +00001591inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001592auto
1593operator-(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1594-> decltype(__x.base() - __y.base())
1595{
1596 return __x.base() - __y.base();
1597}
1598#else
Howard Hinnantc51e1022010-05-11 19:42:16 +00001599template <class _Iter1, class _Iter2>
1600inline _LIBCPP_INLINE_VISIBILITY
1601typename move_iterator<_Iter1>::difference_type
1602operator-(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1603{
1604 return __x.base() - __y.base();
1605}
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001606#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001607
1608template <class _Iter>
Marshall Clowb5f99122016-11-02 15:30:26 +00001609inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00001610move_iterator<_Iter>
1611operator+(typename move_iterator<_Iter>::difference_type __n, const move_iterator<_Iter>& __x)
1612{
1613 return move_iterator<_Iter>(__x.base() + __n);
1614}
1615
1616template <class _Iter>
Marshall Clowb5f99122016-11-02 15:30:26 +00001617inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00001618move_iterator<_Iter>
Marshall Clow84f90cf2013-08-27 13:03:03 +00001619make_move_iterator(_Iter __i)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001620{
1621 return move_iterator<_Iter>(__i);
1622}
1623
1624// __wrap_iter
1625
1626template <class _Iter> class __wrap_iter;
1627
1628template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001629_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001630bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001631operator==(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001632
1633template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001634_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001635bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001636operator<(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001637
1638template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001639_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001640bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001641operator!=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001642
1643template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001644_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001645bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001646operator>(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001647
1648template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001649_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001650bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001651operator>=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001652
1653template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001654_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001655bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001656operator<=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001657
Marshall Clow476d3f42016-07-18 13:19:00 +00001658#ifndef _LIBCPP_CXX03_LANG
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001659template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001660_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001661auto
Eric Fiselier873b8d32019-03-18 21:50:12 +00001662operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001663-> decltype(__x.base() - __y.base());
1664#else
Howard Hinnantc51e1022010-05-11 19:42:16 +00001665template <class _Iter1, class _Iter2>
Howard Hinnanta54386e2012-09-14 00:39:16 +00001666_LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001667typename __wrap_iter<_Iter1>::difference_type
Eric Fiselier873b8d32019-03-18 21:50:12 +00001668operator-(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001669#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001670
1671template <class _Iter>
Marshall Clowae4f8312018-07-13 16:35:26 +00001672_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001673__wrap_iter<_Iter>
Eric Fiselier873b8d32019-03-18 21:50:12 +00001674operator+(typename __wrap_iter<_Iter>::difference_type, __wrap_iter<_Iter>) _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001675
Louis Dionne65b433b2019-11-06 12:02:41 +00001676template <class _Ip, class _Op> _Op _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 copy(_Ip, _Ip, _Op);
1677template <class _B1, class _B2> _B2 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 copy_backward(_B1, _B1, _B2);
zoecarverd0279de2020-09-14 18:11:08 -04001678template <class _Ip, class _Op> _Op _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 move(_Ip, _Ip, _Op);
1679template <class _B1, class _B2> _B2 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 move_backward(_B1, _B1, _B2);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001680
Howard Hinnantc51e1022010-05-11 19:42:16 +00001681template <class _Iter>
1682class __wrap_iter
1683{
1684public:
1685 typedef _Iter iterator_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001686 typedef typename iterator_traits<iterator_type>::value_type value_type;
1687 typedef typename iterator_traits<iterator_type>::difference_type difference_type;
1688 typedef typename iterator_traits<iterator_type>::pointer pointer;
1689 typedef typename iterator_traits<iterator_type>::reference reference;
Arthur O'Dwyer1ac9f092021-01-15 12:59:56 -05001690 typedef typename iterator_traits<iterator_type>::iterator_category iterator_category;
1691#if _LIBCPP_STD_VER > 17
1692 typedef _If<__is_cpp17_contiguous_iterator<_Iter>::value,
1693 contiguous_iterator_tag, iterator_category> iterator_concept;
1694#endif
1695
Howard Hinnantc51e1022010-05-11 19:42:16 +00001696private:
1697 iterator_type __i;
1698public:
Eric Fiselier873b8d32019-03-18 21:50:12 +00001699 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter() _NOEXCEPT
Marshall Clow4e7b35b2013-08-07 20:48:48 +00001700#if _LIBCPP_STD_VER > 11
1701 : __i{}
1702#endif
Howard Hinnantc90aa632011-09-16 19:52:23 +00001703 {
Louis Dionneba400782020-10-02 15:02:52 -04001704#if _LIBCPP_DEBUG_LEVEL == 2
Howard Hinnantc90aa632011-09-16 19:52:23 +00001705 __get_db()->__insert_i(this);
1706#endif
1707 }
Marshall Clowae4f8312018-07-13 16:35:26 +00001708 template <class _Up> _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
1709 __wrap_iter(const __wrap_iter<_Up>& __u,
Bruce Mitchener170d8972020-11-24 12:53:53 -05001710 typename enable_if<is_convertible<_Up, iterator_type>::value>::type* = nullptr) _NOEXCEPT
Marshall Clowae4f8312018-07-13 16:35:26 +00001711 : __i(__u.base())
Howard Hinnant27e0e772011-09-14 18:33:51 +00001712 {
Louis Dionneba400782020-10-02 15:02:52 -04001713#if _LIBCPP_DEBUG_LEVEL == 2
Howard Hinnant27e0e772011-09-14 18:33:51 +00001714 __get_db()->__iterator_copy(this, &__u);
1715#endif
1716 }
Louis Dionneba400782020-10-02 15:02:52 -04001717#if _LIBCPP_DEBUG_LEVEL == 2
Marshall Clowae4f8312018-07-13 16:35:26 +00001718 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnant27e0e772011-09-14 18:33:51 +00001719 __wrap_iter(const __wrap_iter& __x)
1720 : __i(__x.base())
1721 {
1722 __get_db()->__iterator_copy(this, &__x);
1723 }
Marshall Clowae4f8312018-07-13 16:35:26 +00001724 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnant27e0e772011-09-14 18:33:51 +00001725 __wrap_iter& operator=(const __wrap_iter& __x)
1726 {
1727 if (this != &__x)
1728 {
1729 __get_db()->__iterator_copy(this, &__x);
1730 __i = __x.__i;
1731 }
1732 return *this;
1733 }
Marshall Clowae4f8312018-07-13 16:35:26 +00001734 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnant27e0e772011-09-14 18:33:51 +00001735 ~__wrap_iter()
1736 {
1737 __get_db()->__erase_i(this);
1738 }
1739#endif
Eric Fiselier873b8d32019-03-18 21:50:12 +00001740 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG reference operator*() const _NOEXCEPT
Howard Hinnant27e0e772011-09-14 18:33:51 +00001741 {
Louis Dionneba400782020-10-02 15:02:52 -04001742#if _LIBCPP_DEBUG_LEVEL == 2
Howard Hinnant27e0e772011-09-14 18:33:51 +00001743 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
1744 "Attempted to dereference a non-dereferenceable iterator");
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001745#endif
Howard Hinnant27e0e772011-09-14 18:33:51 +00001746 return *__i;
1747 }
Eric Fiselier873b8d32019-03-18 21:50:12 +00001748 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG pointer operator->() const _NOEXCEPT
Howard Hinnant76053d72013-06-27 19:35:32 +00001749 {
Louis Dionneba400782020-10-02 15:02:52 -04001750#if _LIBCPP_DEBUG_LEVEL == 2
Howard Hinnant76053d72013-06-27 19:35:32 +00001751 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
1752 "Attempted to dereference a non-dereferenceable iterator");
1753#endif
Marshall Clowd85a0562016-04-11 03:54:53 +00001754 return (pointer)_VSTD::addressof(*__i);
Howard Hinnant76053d72013-06-27 19:35:32 +00001755 }
Eric Fiselier873b8d32019-03-18 21:50:12 +00001756 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter& operator++() _NOEXCEPT
Howard Hinnant27e0e772011-09-14 18:33:51 +00001757 {
Louis Dionneba400782020-10-02 15:02:52 -04001758#if _LIBCPP_DEBUG_LEVEL == 2
Howard Hinnant27e0e772011-09-14 18:33:51 +00001759 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
1760 "Attempted to increment non-incrementable iterator");
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001761#endif
Howard Hinnant27e0e772011-09-14 18:33:51 +00001762 ++__i;
1763 return *this;
1764 }
Eric Fiselier873b8d32019-03-18 21:50:12 +00001765 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter operator++(int) _NOEXCEPT
Howard Hinnant27e0e772011-09-14 18:33:51 +00001766 {__wrap_iter __tmp(*this); ++(*this); return __tmp;}
Marshall Clow6d553a52018-07-14 03:06:11 +00001767
Eric Fiselier873b8d32019-03-18 21:50:12 +00001768 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter& operator--() _NOEXCEPT
Howard Hinnant27e0e772011-09-14 18:33:51 +00001769 {
Louis Dionneba400782020-10-02 15:02:52 -04001770#if _LIBCPP_DEBUG_LEVEL == 2
Howard Hinnant27e0e772011-09-14 18:33:51 +00001771 _LIBCPP_ASSERT(__get_const_db()->__decrementable(this),
1772 "Attempted to decrement non-decrementable iterator");
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001773#endif
Howard Hinnant27e0e772011-09-14 18:33:51 +00001774 --__i;
1775 return *this;
1776 }
Eric Fiselier873b8d32019-03-18 21:50:12 +00001777 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter operator--(int) _NOEXCEPT
Howard Hinnant27e0e772011-09-14 18:33:51 +00001778 {__wrap_iter __tmp(*this); --(*this); return __tmp;}
Eric Fiselier873b8d32019-03-18 21:50:12 +00001779 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter operator+ (difference_type __n) const _NOEXCEPT
Howard Hinnant27e0e772011-09-14 18:33:51 +00001780 {__wrap_iter __w(*this); __w += __n; return __w;}
Eric Fiselier873b8d32019-03-18 21:50:12 +00001781 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter& operator+=(difference_type __n) _NOEXCEPT
Howard Hinnant27e0e772011-09-14 18:33:51 +00001782 {
Louis Dionneba400782020-10-02 15:02:52 -04001783#if _LIBCPP_DEBUG_LEVEL == 2
Howard Hinnant27e0e772011-09-14 18:33:51 +00001784 _LIBCPP_ASSERT(__get_const_db()->__addable(this, __n),
1785 "Attempted to add/subtract iterator outside of valid range");
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001786#endif
Howard Hinnant27e0e772011-09-14 18:33:51 +00001787 __i += __n;
1788 return *this;
1789 }
Eric Fiselier873b8d32019-03-18 21:50:12 +00001790 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter operator- (difference_type __n) const _NOEXCEPT
Howard Hinnant27e0e772011-09-14 18:33:51 +00001791 {return *this + (-__n);}
Eric Fiselier873b8d32019-03-18 21:50:12 +00001792 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter& operator-=(difference_type __n) _NOEXCEPT
Howard Hinnant27e0e772011-09-14 18:33:51 +00001793 {*this += -__n; return *this;}
Eric Fiselier873b8d32019-03-18 21:50:12 +00001794 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG reference operator[](difference_type __n) const _NOEXCEPT
Howard Hinnant27e0e772011-09-14 18:33:51 +00001795 {
Louis Dionneba400782020-10-02 15:02:52 -04001796#if _LIBCPP_DEBUG_LEVEL == 2
Howard Hinnant27e0e772011-09-14 18:33:51 +00001797 _LIBCPP_ASSERT(__get_const_db()->__subscriptable(this, __n),
1798 "Attempted to subscript iterator outside of valid range");
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001799#endif
Howard Hinnant27e0e772011-09-14 18:33:51 +00001800 return __i[__n];
1801 }
Howard Hinnantc51e1022010-05-11 19:42:16 +00001802
Eric Fiselier873b8d32019-03-18 21:50:12 +00001803 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG iterator_type base() const _NOEXCEPT {return __i;}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001804
1805private:
Louis Dionneba400782020-10-02 15:02:52 -04001806#if _LIBCPP_DEBUG_LEVEL == 2
Marshall Clowae4f8312018-07-13 16:35:26 +00001807 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter(const void* __p, iterator_type __x) : __i(__x)
Howard Hinnant27e0e772011-09-14 18:33:51 +00001808 {
1809 __get_db()->__insert_ic(this, __p);
1810 }
Howard Hinnant8ea98242013-08-23 17:37:05 +00001811#else
Eric Fiselier873b8d32019-03-18 21:50:12 +00001812 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter(iterator_type __x) _NOEXCEPT : __i(__x) {}
Howard Hinnant27e0e772011-09-14 18:33:51 +00001813#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001814
1815 template <class _Up> friend class __wrap_iter;
1816 template <class _CharT, class _Traits, class _Alloc> friend class basic_string;
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +00001817 template <class _Tp, class _Alloc> friend class _LIBCPP_TEMPLATE_VIS vector;
Marshall Clowcd6d8802019-02-27 00:32:16 +00001818 template <class _Tp, size_t> friend class _LIBCPP_TEMPLATE_VIS span;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001819
1820 template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001821 _LIBCPP_CONSTEXPR_IF_NODEBUG friend
Howard Hinnantc51e1022010-05-11 19:42:16 +00001822 bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001823 operator==(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001824
Howard Hinnantc51e1022010-05-11 19:42:16 +00001825 template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001826 _LIBCPP_CONSTEXPR_IF_NODEBUG friend
Howard Hinnantc51e1022010-05-11 19:42:16 +00001827 bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001828 operator<(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001829
Howard Hinnantc51e1022010-05-11 19:42:16 +00001830 template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001831 _LIBCPP_CONSTEXPR_IF_NODEBUG friend
Howard Hinnantc51e1022010-05-11 19:42:16 +00001832 bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001833 operator!=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001834
Howard Hinnantc51e1022010-05-11 19:42:16 +00001835 template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001836 _LIBCPP_CONSTEXPR_IF_NODEBUG friend
Howard Hinnantc51e1022010-05-11 19:42:16 +00001837 bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001838 operator>(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001839
Howard Hinnantc51e1022010-05-11 19:42:16 +00001840 template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001841 _LIBCPP_CONSTEXPR_IF_NODEBUG friend
Howard Hinnantc51e1022010-05-11 19:42:16 +00001842 bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001843 operator>=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001844
Howard Hinnantc51e1022010-05-11 19:42:16 +00001845 template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001846 _LIBCPP_CONSTEXPR_IF_NODEBUG friend
Howard Hinnantc51e1022010-05-11 19:42:16 +00001847 bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001848 operator<=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001849
Marshall Clow476d3f42016-07-18 13:19:00 +00001850#ifndef _LIBCPP_CXX03_LANG
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001851 template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001852 _LIBCPP_CONSTEXPR_IF_NODEBUG friend
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001853 auto
Eric Fiselier873b8d32019-03-18 21:50:12 +00001854 operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001855 -> decltype(__x.base() - __y.base());
1856#else
Howard Hinnantc51e1022010-05-11 19:42:16 +00001857 template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001858 _LIBCPP_CONSTEXPR_IF_NODEBUG friend
Howard Hinnantc51e1022010-05-11 19:42:16 +00001859 typename __wrap_iter<_Iter1>::difference_type
Eric Fiselier873b8d32019-03-18 21:50:12 +00001860 operator-(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001861#endif
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001862
Howard Hinnantc51e1022010-05-11 19:42:16 +00001863 template <class _Iter1>
Marshall Clowae4f8312018-07-13 16:35:26 +00001864 _LIBCPP_CONSTEXPR_IF_NODEBUG friend
Howard Hinnantc51e1022010-05-11 19:42:16 +00001865 __wrap_iter<_Iter1>
Eric Fiselier873b8d32019-03-18 21:50:12 +00001866 operator+(typename __wrap_iter<_Iter1>::difference_type, __wrap_iter<_Iter1>) _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001867
Louis Dionne65b433b2019-11-06 12:02:41 +00001868 template <class _Ip, class _Op> friend _LIBCPP_CONSTEXPR_AFTER_CXX17 _Op copy(_Ip, _Ip, _Op);
1869 template <class _B1, class _B2> friend _LIBCPP_CONSTEXPR_AFTER_CXX17 _B2 copy_backward(_B1, _B1, _B2);
zoecarverd0279de2020-09-14 18:11:08 -04001870 template <class _Ip, class _Op> friend _LIBCPP_CONSTEXPR_AFTER_CXX17 _Op move(_Ip, _Ip, _Op);
1871 template <class _B1, class _B2> friend _LIBCPP_CONSTEXPR_AFTER_CXX17 _B2 move_backward(_B1, _B1, _B2);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001872};
1873
Arthur O'Dwyer1ac9f092021-01-15 12:59:56 -05001874#if _LIBCPP_STD_VER <= 17
1875template <class _It>
1876struct __is_cpp17_contiguous_iterator<__wrap_iter<_It> > : __is_cpp17_contiguous_iterator<_It> {};
1877#endif
1878
1879template <class _Iter>
1880_LIBCPP_CONSTEXPR
1881_EnableIf<__is_cpp17_contiguous_iterator<_Iter>::value, decltype(_VSTD::__to_address(declval<_Iter>()))>
1882__to_address(__wrap_iter<_Iter> __w) _NOEXCEPT {
1883 return _VSTD::__to_address(__w.base());
1884}
1885
Howard Hinnantc51e1022010-05-11 19:42:16 +00001886template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001887inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001888bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001889operator==(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001890{
1891 return __x.base() == __y.base();
1892}
1893
1894template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001895inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001896bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001897operator<(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001898{
Louis Dionneba400782020-10-02 15:02:52 -04001899#if _LIBCPP_DEBUG_LEVEL == 2
Howard Hinnante6ff0b62013-08-02 00:26:35 +00001900 _LIBCPP_ASSERT(__get_const_db()->__less_than_comparable(&__x, &__y),
Howard Hinnant27e0e772011-09-14 18:33:51 +00001901 "Attempted to compare incomparable iterators");
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001902#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001903 return __x.base() < __y.base();
1904}
1905
1906template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001907inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001908bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001909operator!=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001910{
Howard Hinnant27e0e772011-09-14 18:33:51 +00001911 return !(__x == __y);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001912}
1913
1914template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001915inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001916bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001917operator>(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001918{
Howard Hinnant27e0e772011-09-14 18:33:51 +00001919 return __y < __x;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001920}
1921
1922template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001923inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001924bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001925operator>=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001926{
Howard Hinnant27e0e772011-09-14 18:33:51 +00001927 return !(__x < __y);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001928}
1929
1930template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001931inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001932bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001933operator<=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001934{
Howard Hinnant27e0e772011-09-14 18:33:51 +00001935 return !(__y < __x);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001936}
1937
Howard Hinnantf78e32c2012-10-02 19:45:42 +00001938template <class _Iter1>
Marshall Clowae4f8312018-07-13 16:35:26 +00001939inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantf78e32c2012-10-02 19:45:42 +00001940bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001941operator!=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT
Howard Hinnantf78e32c2012-10-02 19:45:42 +00001942{
1943 return !(__x == __y);
1944}
1945
1946template <class _Iter1>
Marshall Clowae4f8312018-07-13 16:35:26 +00001947inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantf78e32c2012-10-02 19:45:42 +00001948bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001949operator>(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT
Howard Hinnantf78e32c2012-10-02 19:45:42 +00001950{
1951 return __y < __x;
1952}
1953
1954template <class _Iter1>
Marshall Clowae4f8312018-07-13 16:35:26 +00001955inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantf78e32c2012-10-02 19:45:42 +00001956bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001957operator>=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT
Howard Hinnantf78e32c2012-10-02 19:45:42 +00001958{
1959 return !(__x < __y);
1960}
1961
1962template <class _Iter1>
Marshall Clowae4f8312018-07-13 16:35:26 +00001963inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantf78e32c2012-10-02 19:45:42 +00001964bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001965operator<=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT
Howard Hinnantf78e32c2012-10-02 19:45:42 +00001966{
1967 return !(__y < __x);
1968}
1969
Marshall Clow476d3f42016-07-18 13:19:00 +00001970#ifndef _LIBCPP_CXX03_LANG
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001971template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001972inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001973auto
Eric Fiselier873b8d32019-03-18 21:50:12 +00001974operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001975-> decltype(__x.base() - __y.base())
1976{
Louis Dionneba400782020-10-02 15:02:52 -04001977#if _LIBCPP_DEBUG_LEVEL == 2
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001978 _LIBCPP_ASSERT(__get_const_db()->__less_than_comparable(&__x, &__y),
1979 "Attempted to subtract incompatible iterators");
1980#endif
1981 return __x.base() - __y.base();
1982}
1983#else
Howard Hinnantc51e1022010-05-11 19:42:16 +00001984template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001985inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001986typename __wrap_iter<_Iter1>::difference_type
Eric Fiselier873b8d32019-03-18 21:50:12 +00001987operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001988{
Louis Dionneba400782020-10-02 15:02:52 -04001989#if _LIBCPP_DEBUG_LEVEL == 2
Howard Hinnante6ff0b62013-08-02 00:26:35 +00001990 _LIBCPP_ASSERT(__get_const_db()->__less_than_comparable(&__x, &__y),
Howard Hinnant27e0e772011-09-14 18:33:51 +00001991 "Attempted to subtract incompatible iterators");
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001992#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001993 return __x.base() - __y.base();
1994}
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001995#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001996
1997template <class _Iter>
Marshall Clowae4f8312018-07-13 16:35:26 +00001998inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001999__wrap_iter<_Iter>
2000operator+(typename __wrap_iter<_Iter>::difference_type __n,
Eric Fiselier873b8d32019-03-18 21:50:12 +00002001 __wrap_iter<_Iter> __x) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00002002{
Howard Hinnant27e0e772011-09-14 18:33:51 +00002003 __x += __n;
2004 return __x;
Howard Hinnantc51e1022010-05-11 19:42:16 +00002005}
2006
Marshall Clow039b2f02016-01-13 21:54:34 +00002007template <class _Iter>
2008struct __libcpp_is_trivial_iterator
Marshall Clowb5f99122016-11-02 15:30:26 +00002009 : public _LIBCPP_BOOL_CONSTANT(is_pointer<_Iter>::value) {};
Louis Dionne173f29e2019-05-29 16:01:36 +00002010
Marshall Clow039b2f02016-01-13 21:54:34 +00002011template <class _Iter>
2012struct __libcpp_is_trivial_iterator<move_iterator<_Iter> >
Marshall Clowb5f99122016-11-02 15:30:26 +00002013 : public _LIBCPP_BOOL_CONSTANT(__libcpp_is_trivial_iterator<_Iter>::value) {};
Marshall Clow039b2f02016-01-13 21:54:34 +00002014
2015template <class _Iter>
2016struct __libcpp_is_trivial_iterator<reverse_iterator<_Iter> >
Marshall Clowb5f99122016-11-02 15:30:26 +00002017 : public _LIBCPP_BOOL_CONSTANT(__libcpp_is_trivial_iterator<_Iter>::value) {};
Marshall Clow039b2f02016-01-13 21:54:34 +00002018
2019template <class _Iter>
2020struct __libcpp_is_trivial_iterator<__wrap_iter<_Iter> >
Marshall Clowb5f99122016-11-02 15:30:26 +00002021 : public _LIBCPP_BOOL_CONSTANT(__libcpp_is_trivial_iterator<_Iter>::value) {};
Marshall Clow039b2f02016-01-13 21:54:34 +00002022
2023
Marshall Clow8411ebf2013-12-02 03:24:33 +00002024template <class _Tp, size_t _Np>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002025_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
Marshall Clow8411ebf2013-12-02 03:24:33 +00002026_Tp*
2027begin(_Tp (&__array)[_Np])
2028{
2029 return __array;
2030}
2031
2032template <class _Tp, size_t _Np>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002033_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
Marshall Clow8411ebf2013-12-02 03:24:33 +00002034_Tp*
2035end(_Tp (&__array)[_Np])
2036{
2037 return __array + _Np;
2038}
2039
Eric Fiselierc6f17cc2016-09-25 03:34:28 +00002040#if !defined(_LIBCPP_CXX03_LANG)
Marshall Clow037fcb72013-12-11 19:32:32 +00002041
Howard Hinnantc834c512011-11-29 18:15:50 +00002042template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002043_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00002044auto
Howard Hinnantc834c512011-11-29 18:15:50 +00002045begin(_Cp& __c) -> decltype(__c.begin())
Howard Hinnantc51e1022010-05-11 19:42:16 +00002046{
2047 return __c.begin();
2048}
2049
Howard Hinnantc834c512011-11-29 18:15:50 +00002050template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002051_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00002052auto
Howard Hinnantc834c512011-11-29 18:15:50 +00002053begin(const _Cp& __c) -> decltype(__c.begin())
Howard Hinnantc51e1022010-05-11 19:42:16 +00002054{
2055 return __c.begin();
2056}
2057
Howard Hinnantc834c512011-11-29 18:15:50 +00002058template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002059_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00002060auto
Howard Hinnantc834c512011-11-29 18:15:50 +00002061end(_Cp& __c) -> decltype(__c.end())
Howard Hinnantc51e1022010-05-11 19:42:16 +00002062{
2063 return __c.end();
2064}
2065
Howard Hinnantc834c512011-11-29 18:15:50 +00002066template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002067_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00002068auto
Howard Hinnantc834c512011-11-29 18:15:50 +00002069end(const _Cp& __c) -> decltype(__c.end())
Howard Hinnantc51e1022010-05-11 19:42:16 +00002070{
2071 return __c.end();
2072}
2073
Marshall Clowb278e9c2013-08-30 01:17:07 +00002074#if _LIBCPP_STD_VER > 11
2075
Marshall Clow8411ebf2013-12-02 03:24:33 +00002076template <class _Tp, size_t _Np>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002077_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clow8411ebf2013-12-02 03:24:33 +00002078reverse_iterator<_Tp*> rbegin(_Tp (&__array)[_Np])
2079{
2080 return reverse_iterator<_Tp*>(__array + _Np);
2081}
2082
2083template <class _Tp, size_t _Np>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002084_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clow8411ebf2013-12-02 03:24:33 +00002085reverse_iterator<_Tp*> rend(_Tp (&__array)[_Np])
2086{
2087 return reverse_iterator<_Tp*>(__array);
2088}
2089
2090template <class _Ep>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002091_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clow8411ebf2013-12-02 03:24:33 +00002092reverse_iterator<const _Ep*> rbegin(initializer_list<_Ep> __il)
2093{
2094 return reverse_iterator<const _Ep*>(__il.end());
2095}
2096
2097template <class _Ep>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002098_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clow8411ebf2013-12-02 03:24:33 +00002099reverse_iterator<const _Ep*> rend(initializer_list<_Ep> __il)
2100{
2101 return reverse_iterator<const _Ep*>(__il.begin());
2102}
2103
Marshall Clowb278e9c2013-08-30 01:17:07 +00002104template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002105_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
Marshall Clow3862f532016-08-10 20:04:46 +00002106auto cbegin(const _Cp& __c) -> decltype(_VSTD::begin(__c))
Marshall Clowb278e9c2013-08-30 01:17:07 +00002107{
Marshall Clow3862f532016-08-10 20:04:46 +00002108 return _VSTD::begin(__c);
Marshall Clowb278e9c2013-08-30 01:17:07 +00002109}
2110
2111template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002112_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
Marshall Clow3862f532016-08-10 20:04:46 +00002113auto cend(const _Cp& __c) -> decltype(_VSTD::end(__c))
Marshall Clowb278e9c2013-08-30 01:17:07 +00002114{
Marshall Clow3862f532016-08-10 20:04:46 +00002115 return _VSTD::end(__c);
Marshall Clowb278e9c2013-08-30 01:17:07 +00002116}
2117
2118template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002119_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clowb278e9c2013-08-30 01:17:07 +00002120auto rbegin(_Cp& __c) -> decltype(__c.rbegin())
2121{
2122 return __c.rbegin();
2123}
2124
2125template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002126_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clowb278e9c2013-08-30 01:17:07 +00002127auto rbegin(const _Cp& __c) -> decltype(__c.rbegin())
2128{
2129 return __c.rbegin();
2130}
2131
2132template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002133_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clowb278e9c2013-08-30 01:17:07 +00002134auto rend(_Cp& __c) -> decltype(__c.rend())
2135{
2136 return __c.rend();
2137}
2138
2139template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002140_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clowb278e9c2013-08-30 01:17:07 +00002141auto rend(const _Cp& __c) -> decltype(__c.rend())
2142{
2143 return __c.rend();
2144}
2145
2146template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002147_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clow3862f532016-08-10 20:04:46 +00002148auto crbegin(const _Cp& __c) -> decltype(_VSTD::rbegin(__c))
Marshall Clowb278e9c2013-08-30 01:17:07 +00002149{
Marshall Clow3862f532016-08-10 20:04:46 +00002150 return _VSTD::rbegin(__c);
Marshall Clowb278e9c2013-08-30 01:17:07 +00002151}
2152
2153template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002154_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clow3862f532016-08-10 20:04:46 +00002155auto crend(const _Cp& __c) -> decltype(_VSTD::rend(__c))
Marshall Clowb278e9c2013-08-30 01:17:07 +00002156{
Marshall Clow3862f532016-08-10 20:04:46 +00002157 return _VSTD::rend(__c);
Marshall Clowb278e9c2013-08-30 01:17:07 +00002158}
2159
2160#endif
2161
2162
Eric Fiselierc6f17cc2016-09-25 03:34:28 +00002163#else // defined(_LIBCPP_CXX03_LANG)
Howard Hinnantc51e1022010-05-11 19:42:16 +00002164
Howard Hinnantc834c512011-11-29 18:15:50 +00002165template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002166_LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00002167typename _Cp::iterator
2168begin(_Cp& __c)
Howard Hinnantc51e1022010-05-11 19:42:16 +00002169{
2170 return __c.begin();
2171}
2172
Howard Hinnantc834c512011-11-29 18:15:50 +00002173template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002174_LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00002175typename _Cp::const_iterator
2176begin(const _Cp& __c)
Howard Hinnantc51e1022010-05-11 19:42:16 +00002177{
2178 return __c.begin();
2179}
2180
Howard Hinnantc834c512011-11-29 18:15:50 +00002181template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002182_LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00002183typename _Cp::iterator
2184end(_Cp& __c)
Howard Hinnantc51e1022010-05-11 19:42:16 +00002185{
2186 return __c.end();
2187}
2188
Howard Hinnantc834c512011-11-29 18:15:50 +00002189template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002190_LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00002191typename _Cp::const_iterator
2192end(const _Cp& __c)
Howard Hinnantc51e1022010-05-11 19:42:16 +00002193{
2194 return __c.end();
2195}
2196
Eric Fiselierc6f17cc2016-09-25 03:34:28 +00002197#endif // !defined(_LIBCPP_CXX03_LANG)
Howard Hinnantc51e1022010-05-11 19:42:16 +00002198
Marshall Clowef357272014-11-19 19:43:23 +00002199#if _LIBCPP_STD_VER > 14
Marshall Clow344c41d2017-11-16 17:55:41 +00002200
2201// #if _LIBCPP_STD_VER > 11
2202// template <>
2203// struct _LIBCPP_TEMPLATE_VIS plus<void>
2204// {
2205// template <class _T1, class _T2>
2206// _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
2207// auto operator()(_T1&& __t, _T2&& __u) const
2208// _NOEXCEPT_(noexcept(_VSTD::forward<_T1>(__t) + _VSTD::forward<_T2>(__u)))
2209// -> decltype (_VSTD::forward<_T1>(__t) + _VSTD::forward<_T2>(__u))
2210// { return _VSTD::forward<_T1>(__t) + _VSTD::forward<_T2>(__u); }
2211// typedef void is_transparent;
2212// };
2213// #endif
2214
Marshall Clowc4b4a342015-02-11 16:14:01 +00002215template <class _Cont>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002216_LIBCPP_INLINE_VISIBILITY
Marshall Clow344c41d2017-11-16 17:55:41 +00002217constexpr auto size(const _Cont& __c)
2218_NOEXCEPT_(noexcept(__c.size()))
2219-> decltype (__c.size())
2220{ return __c.size(); }
Marshall Clowef357272014-11-19 19:43:23 +00002221
Marshall Clowc4b4a342015-02-11 16:14:01 +00002222template <class _Tp, size_t _Sz>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002223_LIBCPP_INLINE_VISIBILITY
Eric Fiselier6003c772016-12-23 23:37:52 +00002224constexpr size_t size(const _Tp (&)[_Sz]) noexcept { return _Sz; }
Marshall Clowef357272014-11-19 19:43:23 +00002225
Marshall Clow3c5363e2019-02-27 02:58:56 +00002226#if _LIBCPP_STD_VER > 17
2227template <class _Cont>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002228_LIBCPP_INLINE_VISIBILITY
Marshall Clow3c5363e2019-02-27 02:58:56 +00002229constexpr auto ssize(const _Cont& __c)
2230_NOEXCEPT_(noexcept(static_cast<common_type_t<ptrdiff_t, make_signed_t<decltype(__c.size())>>>(__c.size())))
2231-> common_type_t<ptrdiff_t, make_signed_t<decltype(__c.size())>>
2232{ return static_cast<common_type_t<ptrdiff_t, make_signed_t<decltype(__c.size())>>>(__c.size()); }
2233
2234template <class _Tp, ptrdiff_t _Sz>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002235_LIBCPP_INLINE_VISIBILITY
Marshall Clow3c5363e2019-02-27 02:58:56 +00002236constexpr ptrdiff_t ssize(const _Tp (&)[_Sz]) noexcept { return _Sz; }
2237#endif
2238
Marshall Clowc4b4a342015-02-11 16:14:01 +00002239template <class _Cont>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002240_LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
Marshall Clow344c41d2017-11-16 17:55:41 +00002241constexpr auto empty(const _Cont& __c)
2242_NOEXCEPT_(noexcept(__c.empty()))
2243-> decltype (__c.empty())
2244{ return __c.empty(); }
Marshall Clowef357272014-11-19 19:43:23 +00002245
Marshall Clowc4b4a342015-02-11 16:14:01 +00002246template <class _Tp, size_t _Sz>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002247_LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
Eric Fiselier6003c772016-12-23 23:37:52 +00002248constexpr bool empty(const _Tp (&)[_Sz]) noexcept { return false; }
Marshall Clowef357272014-11-19 19:43:23 +00002249
2250template <class _Ep>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002251_LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
Marshall Clowef357272014-11-19 19:43:23 +00002252constexpr bool empty(initializer_list<_Ep> __il) noexcept { return __il.size() == 0; }
2253
Marshall Clowc4b4a342015-02-11 16:14:01 +00002254template <class _Cont> constexpr
Marshall Clow0bd662d2019-02-27 03:25:43 +00002255_LIBCPP_INLINE_VISIBILITY
Marshall Clow344c41d2017-11-16 17:55:41 +00002256auto data(_Cont& __c)
2257_NOEXCEPT_(noexcept(__c.data()))
2258-> decltype (__c.data())
2259{ return __c.data(); }
Marshall Clowef357272014-11-19 19:43:23 +00002260
Marshall Clowc4b4a342015-02-11 16:14:01 +00002261template <class _Cont> constexpr
Marshall Clow0bd662d2019-02-27 03:25:43 +00002262_LIBCPP_INLINE_VISIBILITY
Marshall Clow344c41d2017-11-16 17:55:41 +00002263auto data(const _Cont& __c)
2264_NOEXCEPT_(noexcept(__c.data()))
Louis Dionne173f29e2019-05-29 16:01:36 +00002265-> decltype (__c.data())
Marshall Clow344c41d2017-11-16 17:55:41 +00002266{ return __c.data(); }
Marshall Clowef357272014-11-19 19:43:23 +00002267
Marshall Clowc4b4a342015-02-11 16:14:01 +00002268template <class _Tp, size_t _Sz>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002269_LIBCPP_INLINE_VISIBILITY
Marshall Clowc4b4a342015-02-11 16:14:01 +00002270constexpr _Tp* data(_Tp (&__array)[_Sz]) noexcept { return __array; }
Marshall Clowef357272014-11-19 19:43:23 +00002271
2272template <class _Ep>
Marshall Clow0bd662d2019-02-27 03:25:43 +00002273_LIBCPP_INLINE_VISIBILITY
Marshall Clowef357272014-11-19 19:43:23 +00002274constexpr const _Ep* data(initializer_list<_Ep> __il) noexcept { return __il.begin(); }
2275#endif
2276
Arthur O'Dwyerb6738bd2021-03-21 16:53:09 -04002277template <class _Container, class _Predicate>
2278typename _Container::size_type
2279__libcpp_erase_if_container(_Container& __c, _Predicate& __pred) {
2280 typename _Container::size_type __old_size = __c.size();
2281
2282 const typename _Container::iterator __last = __c.end();
2283 for (typename _Container::iterator __iter = __c.begin(); __iter != __last;) {
2284 if (__pred(*__iter))
2285 __iter = __c.erase(__iter);
2286 else
2287 ++__iter;
2288 }
2289
2290 return __old_size - __c.size();
2291}
Marshall Clowef357272014-11-19 19:43:23 +00002292
Howard Hinnantc51e1022010-05-11 19:42:16 +00002293_LIBCPP_END_NAMESPACE_STD
2294
2295#endif // _LIBCPP_ITERATOR