blob: 2785fec9f756271d1d24bd847d746ebe5bd5956d [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
Christopher Di Bellaa3a10062021-04-20 18:56:08 +000021template<class T>
22 using iter_difference_t = see below; // since C++20
23
Christopher Di Bellae00eebc2021-03-23 20:48:41 +000024template<class> struct indirectly_readable_traits; // since C++20
Christopher Di Bellaa3a10062021-04-20 18:56:08 +000025template<class T>
26 using iter_value_t = see below; // since C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +000027
28template<class Iterator>
zoecarver9f1e2972021-04-20 08:50:11 -040029struct iterator_traits;
Howard Hinnantc51e1022010-05-11 19:42:16 +000030
31template<class T>
zoecarver9f1e2972021-04-20 08:50:11 -040032 requires is_object_v<T> // since C++20
33struct iterator_traits<T*>;
Howard Hinnantc51e1022010-05-11 19:42:16 +000034
Christopher Di Bella875636f2021-04-04 05:12:46 +000035template<dereferenceable T>
36 using iter_reference_t = decltype(*declval<T&>());
37
Howard Hinnantc51e1022010-05-11 19:42:16 +000038template<class Category, class T, class Distance = ptrdiff_t,
39 class Pointer = T*, class Reference = T&>
40struct iterator
41{
42 typedef T value_type;
43 typedef Distance difference_type;
44 typedef Pointer pointer;
45 typedef Reference reference;
46 typedef Category iterator_category;
47};
48
49struct input_iterator_tag {};
50struct output_iterator_tag {};
51struct forward_iterator_tag : public input_iterator_tag {};
52struct bidirectional_iterator_tag : public forward_iterator_tag {};
53struct random_access_iterator_tag : public bidirectional_iterator_tag {};
54
Marshall Clow75468e72017-05-17 18:51:36 +000055// 27.4.3, iterator operations
Louis Dionne45768662020-06-08 16:16:01 -040056template <class InputIterator, class Distance> // constexpr in C++17
57 constexpr void advance(InputIterator& i, Distance n);
Howard Hinnantc51e1022010-05-11 19:42:16 +000058
Marshall Clow75468e72017-05-17 18:51:36 +000059template <class InputIterator> // constexpr in C++17
60 constexpr typename iterator_traits<InputIterator>::difference_type
61 distance(InputIterator first, InputIterator last);
62
63template <class InputIterator> // constexpr in C++17
64 constexpr InputIterator next(InputIterator x,
65typename iterator_traits<InputIterator>::difference_type n = 1);
66
67template <class BidirectionalIterator> // constexpr in C++17
68 constexpr BidirectionalIterator prev(BidirectionalIterator x,
Louis Dionne173f29e2019-05-29 16:01:36 +000069 typename iterator_traits<BidirectionalIterator>::difference_type n = 1);
Howard Hinnantc51e1022010-05-11 19:42:16 +000070
71template <class Iterator>
72class reverse_iterator
73 : public iterator<typename iterator_traits<Iterator>::iterator_category,
74 typename iterator_traits<Iterator>::value_type,
75 typename iterator_traits<Iterator>::difference_type,
76 typename iterator_traits<Iterator>::pointer,
77 typename iterator_traits<Iterator>::reference>
78{
79protected:
80 Iterator current;
81public:
82 typedef Iterator iterator_type;
83 typedef typename iterator_traits<Iterator>::difference_type difference_type;
84 typedef typename iterator_traits<Iterator>::reference reference;
85 typedef typename iterator_traits<Iterator>::pointer pointer;
Howard Hinnant3b6579a2010-08-22 00:02:43 +000086
Marshall Clow5ace5542016-10-19 15:12:50 +000087 constexpr reverse_iterator();
88 constexpr explicit reverse_iterator(Iterator x);
89 template <class U> constexpr reverse_iterator(const reverse_iterator<U>& u);
90 template <class U> constexpr reverse_iterator& operator=(const reverse_iterator<U>& u);
91 constexpr Iterator base() const;
92 constexpr reference operator*() const;
93 constexpr pointer operator->() const;
94 constexpr reverse_iterator& operator++();
95 constexpr reverse_iterator operator++(int);
96 constexpr reverse_iterator& operator--();
97 constexpr reverse_iterator operator--(int);
98 constexpr reverse_iterator operator+ (difference_type n) const;
99 constexpr reverse_iterator& operator+=(difference_type n);
100 constexpr reverse_iterator operator- (difference_type n) const;
101 constexpr reverse_iterator& operator-=(difference_type n);
102 constexpr reference operator[](difference_type n) const;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000103};
104
105template <class Iterator1, class Iterator2>
Marshall Clow5ace5542016-10-19 15:12:50 +0000106constexpr bool // constexpr in C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000107operator==(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
108
109template <class Iterator1, class Iterator2>
Marshall Clow5ace5542016-10-19 15:12:50 +0000110constexpr bool // constexpr in C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000111operator<(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
112
113template <class Iterator1, class Iterator2>
Marshall Clow5ace5542016-10-19 15:12:50 +0000114constexpr bool // constexpr in C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000115operator!=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
116
117template <class Iterator1, class Iterator2>
Marshall Clow5ace5542016-10-19 15:12:50 +0000118constexpr bool // constexpr in C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000119operator>(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
120
121template <class Iterator1, class Iterator2>
Marshall Clow5ace5542016-10-19 15:12:50 +0000122constexpr bool // constexpr in C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000123operator>=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
124
125template <class Iterator1, class Iterator2>
Marshall Clow5ace5542016-10-19 15:12:50 +0000126constexpr bool // constexpr in C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000127operator<=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
128
129template <class Iterator1, class Iterator2>
Marshall Clow5ace5542016-10-19 15:12:50 +0000130constexpr auto
Marshall Clowf8fec4e2016-07-08 16:54:47 +0000131operator-(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y)
Marshall Clow5ace5542016-10-19 15:12:50 +0000132-> decltype(__y.base() - __x.base()); // constexpr in C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000133
134template <class Iterator>
Marshall Clow5ace5542016-10-19 15:12:50 +0000135constexpr reverse_iterator<Iterator>
Louis Dionne173f29e2019-05-29 16:01:36 +0000136operator+(typename reverse_iterator<Iterator>::difference_type n,
Marshall Clow5ace5542016-10-19 15:12:50 +0000137 const reverse_iterator<Iterator>& x); // constexpr in C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000138
Marshall Clow5ace5542016-10-19 15:12:50 +0000139template <class Iterator>
140constexpr reverse_iterator<Iterator> make_reverse_iterator(Iterator i); // C++14, constexpr in C++17
Marshall Clow6dbbdc92014-03-03 01:24:04 +0000141
Howard Hinnantc51e1022010-05-11 19:42:16 +0000142template <class Container>
143class back_insert_iterator
144{
145protected:
146 Container* container;
147public:
148 typedef Container container_type;
149 typedef void value_type;
150 typedef void difference_type;
Eric Fiselier9aeea872016-06-30 04:40:50 +0000151 typedef void reference;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000152 typedef void pointer;
153
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -0500154 explicit back_insert_iterator(Container& x); // constexpr in C++20
155 back_insert_iterator& operator=(const typename Container::value_type& value); // constexpr in C++20
156 back_insert_iterator& operator*(); // constexpr in C++20
157 back_insert_iterator& operator++(); // constexpr in C++20
158 back_insert_iterator operator++(int); // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000159};
160
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -0500161template <class Container> back_insert_iterator<Container> back_inserter(Container& x); // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000162
163template <class Container>
164class front_insert_iterator
165{
166protected:
167 Container* container;
168public:
169 typedef Container container_type;
170 typedef void value_type;
171 typedef void difference_type;
Eric Fiselier9aeea872016-06-30 04:40:50 +0000172 typedef void reference;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000173 typedef void pointer;
174
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -0500175 explicit front_insert_iterator(Container& x); // constexpr in C++20
176 front_insert_iterator& operator=(const typename Container::value_type& value); // constexpr in C++20
177 front_insert_iterator& operator*(); // constexpr in C++20
178 front_insert_iterator& operator++(); // constexpr in C++20
179 front_insert_iterator operator++(int); // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000180};
181
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -0500182template <class Container> front_insert_iterator<Container> front_inserter(Container& x); // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000183
184template <class Container>
185class insert_iterator
186{
187protected:
188 Container* container;
189 typename Container::iterator iter;
190public:
191 typedef Container container_type;
192 typedef void value_type;
193 typedef void difference_type;
Eric Fiselier9aeea872016-06-30 04:40:50 +0000194 typedef void reference;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000195 typedef void pointer;
196
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -0500197 insert_iterator(Container& x, typename Container::iterator i); // constexpr in C++20
198 insert_iterator& operator=(const typename Container::value_type& value); // constexpr in C++20
199 insert_iterator& operator*(); // constexpr in C++20
200 insert_iterator& operator++(); // constexpr in C++20
201 insert_iterator& operator++(int); // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000202};
203
204template <class Container, class Iterator>
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -0500205insert_iterator<Container> inserter(Container& x, Iterator i); // constexpr in C++20
Howard Hinnantc51e1022010-05-11 19:42:16 +0000206
Marshall Clowf8fec4e2016-07-08 16:54:47 +0000207template <class Iterator>
208class move_iterator {
209public:
210 typedef Iterator iterator_type;
211 typedef typename iterator_traits<Iterator>::difference_type difference_type;
212 typedef Iterator pointer;
213 typedef typename iterator_traits<Iterator>::value_type value_type;
214 typedef typename iterator_traits<Iterator>::iterator_category iterator_category;
215 typedef value_type&& reference;
Louis Dionne173f29e2019-05-29 16:01:36 +0000216
Marshall Clowb5f99122016-11-02 15:30:26 +0000217 constexpr move_iterator(); // all the constexprs are in C++17
218 constexpr explicit move_iterator(Iterator i);
219 template <class U>
220 constexpr move_iterator(const move_iterator<U>& u);
221 template <class U>
222 constexpr move_iterator& operator=(const move_iterator<U>& u);
223 constexpr iterator_type base() const;
224 constexpr reference operator*() const;
225 constexpr pointer operator->() const;
226 constexpr move_iterator& operator++();
227 constexpr move_iterator operator++(int);
228 constexpr move_iterator& operator--();
229 constexpr move_iterator operator--(int);
Louis Dionne173f29e2019-05-29 16:01:36 +0000230 constexpr move_iterator operator+(difference_type n) const;
231 constexpr move_iterator& operator+=(difference_type n);
232 constexpr move_iterator operator-(difference_type n) const;
233 constexpr move_iterator& operator-=(difference_type n);
Marshall Clowb5f99122016-11-02 15:30:26 +0000234 constexpr unspecified operator[](difference_type n) const;
Marshall Clowf8fec4e2016-07-08 16:54:47 +0000235private:
236 Iterator current; // exposition only
237};
238
239template <class Iterator1, class Iterator2>
Marshall Clowb5f99122016-11-02 15:30:26 +0000240constexpr bool // constexpr in C++17
Marshall Clowf8fec4e2016-07-08 16:54:47 +0000241operator==(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
242
243template <class Iterator1, class Iterator2>
Marshall Clowb5f99122016-11-02 15:30:26 +0000244constexpr bool // constexpr in C++17
Marshall Clowf8fec4e2016-07-08 16:54:47 +0000245operator!=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
246
247template <class Iterator1, class Iterator2>
Marshall Clowb5f99122016-11-02 15:30:26 +0000248constexpr bool // constexpr in C++17
Marshall Clowf8fec4e2016-07-08 16:54:47 +0000249operator<(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
250
251template <class Iterator1, class Iterator2>
Marshall Clowb5f99122016-11-02 15:30:26 +0000252constexpr bool // constexpr in C++17
Marshall Clowf8fec4e2016-07-08 16:54:47 +0000253operator<=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
254
255template <class Iterator1, class Iterator2>
Marshall Clowb5f99122016-11-02 15:30:26 +0000256constexpr bool // constexpr in C++17
Marshall Clowf8fec4e2016-07-08 16:54:47 +0000257operator>(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
258
259template <class Iterator1, class Iterator2>
Marshall Clowb5f99122016-11-02 15:30:26 +0000260constexpr bool // constexpr in C++17
Marshall Clowf8fec4e2016-07-08 16:54:47 +0000261operator>=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
262
263template <class Iterator1, class Iterator2>
Marshall Clowb5f99122016-11-02 15:30:26 +0000264constexpr auto // constexpr in C++17
Marshall Clowf8fec4e2016-07-08 16:54:47 +0000265operator-(const move_iterator<Iterator1>& x,
266 const move_iterator<Iterator2>& y) -> decltype(x.base() - y.base());
267
268template <class Iterator>
Marshall Clowb5f99122016-11-02 15:30:26 +0000269constexpr move_iterator<Iterator> operator+( // constexpr in C++17
Louis Dionne173f29e2019-05-29 16:01:36 +0000270 typename move_iterator<Iterator>::difference_type n,
Marshall Clowb5f99122016-11-02 15:30:26 +0000271 const move_iterator<Iterator>& x);
Marshall Clowf8fec4e2016-07-08 16:54:47 +0000272
Marshall Clowb5f99122016-11-02 15:30:26 +0000273template <class Iterator> // constexpr in C++17
274constexpr move_iterator<Iterator> make_move_iterator(const Iterator& i);
Marshall Clowf8fec4e2016-07-08 16:54:47 +0000275
276
Howard Hinnantc51e1022010-05-11 19:42:16 +0000277template <class T, class charT = char, class traits = char_traits<charT>, class Distance = ptrdiff_t>
278class istream_iterator
279 : public iterator<input_iterator_tag, T, Distance, const T*, const T&>
280{
281public:
282 typedef charT char_type;
283 typedef traits traits_type;
284 typedef basic_istream<charT,traits> istream_type;
285
Marshall Clow0735e4e2015-04-16 21:36:54 +0000286 constexpr istream_iterator();
Howard Hinnantc51e1022010-05-11 19:42:16 +0000287 istream_iterator(istream_type& s);
288 istream_iterator(const istream_iterator& x);
289 ~istream_iterator();
290
291 const T& operator*() const;
292 const T* operator->() const;
293 istream_iterator& operator++();
294 istream_iterator operator++(int);
295};
296
297template <class T, class charT, class traits, class Distance>
298bool operator==(const istream_iterator<T,charT,traits,Distance>& x,
299 const istream_iterator<T,charT,traits,Distance>& y);
300template <class T, class charT, class traits, class Distance>
301bool operator!=(const istream_iterator<T,charT,traits,Distance>& x,
302 const istream_iterator<T,charT,traits,Distance>& y);
303
304template <class T, class charT = char, class traits = char_traits<charT> >
305class ostream_iterator
306 : public iterator<output_iterator_tag, void, void, void ,void>
307{
308public:
309 typedef charT char_type;
310 typedef traits traits_type;
311 typedef basic_ostream<charT,traits> ostream_type;
312
313 ostream_iterator(ostream_type& s);
314 ostream_iterator(ostream_type& s, const charT* delimiter);
315 ostream_iterator(const ostream_iterator& x);
316 ~ostream_iterator();
317 ostream_iterator& operator=(const T& value);
318
319 ostream_iterator& operator*();
320 ostream_iterator& operator++();
321 ostream_iterator& operator++(int);
322};
323
324template<class charT, class traits = char_traits<charT> >
325class istreambuf_iterator
326 : public iterator<input_iterator_tag, charT,
327 typename traits::off_type, unspecified,
328 charT>
329{
330public:
331 typedef charT char_type;
332 typedef traits traits_type;
333 typedef typename traits::int_type int_type;
334 typedef basic_streambuf<charT,traits> streambuf_type;
335 typedef basic_istream<charT,traits> istream_type;
336
Howard Hinnant011138d2012-07-20 19:36:34 +0000337 istreambuf_iterator() noexcept;
338 istreambuf_iterator(istream_type& s) noexcept;
339 istreambuf_iterator(streambuf_type* s) noexcept;
340 istreambuf_iterator(a-private-type) noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000341
342 charT operator*() const;
343 pointer operator->() const;
344 istreambuf_iterator& operator++();
345 a-private-type operator++(int);
346
347 bool equal(const istreambuf_iterator& b) const;
348};
349
350template <class charT, class traits>
351bool operator==(const istreambuf_iterator<charT,traits>& a,
352 const istreambuf_iterator<charT,traits>& b);
353template <class charT, class traits>
354bool operator!=(const istreambuf_iterator<charT,traits>& a,
355 const istreambuf_iterator<charT,traits>& b);
356
357template <class charT, class traits = char_traits<charT> >
358class ostreambuf_iterator
359 : public iterator<output_iterator_tag, void, void, void, void>
360{
361public:
362 typedef charT char_type;
363 typedef traits traits_type;
364 typedef basic_streambuf<charT,traits> streambuf_type;
365 typedef basic_ostream<charT,traits> ostream_type;
366
Howard Hinnant011138d2012-07-20 19:36:34 +0000367 ostreambuf_iterator(ostream_type& s) noexcept;
368 ostreambuf_iterator(streambuf_type* s) noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000369 ostreambuf_iterator& operator=(charT c);
370 ostreambuf_iterator& operator*();
371 ostreambuf_iterator& operator++();
372 ostreambuf_iterator& operator++(int);
Howard Hinnant011138d2012-07-20 19:36:34 +0000373 bool failed() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000374};
375
Marshall Clow99ba0022017-01-04 17:58:17 +0000376template <class C> constexpr auto begin(C& c) -> decltype(c.begin());
377template <class C> constexpr auto begin(const C& c) -> decltype(c.begin());
378template <class C> constexpr auto end(C& c) -> decltype(c.end());
379template <class C> constexpr auto end(const C& c) -> decltype(c.end());
380template <class T, size_t N> constexpr T* begin(T (&array)[N]);
381template <class T, size_t N> constexpr T* end(T (&array)[N]);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000382
Marshall Clow99ba0022017-01-04 17:58:17 +0000383template <class C> auto constexpr cbegin(const C& c) -> decltype(std::begin(c)); // C++14
384template <class C> auto constexpr cend(const C& c) -> decltype(std::end(c)); // C++14
385template <class C> auto constexpr rbegin(C& c) -> decltype(c.rbegin()); // C++14
386template <class C> auto constexpr rbegin(const C& c) -> decltype(c.rbegin()); // C++14
387template <class C> auto constexpr rend(C& c) -> decltype(c.rend()); // C++14
388template <class C> constexpr auto rend(const C& c) -> decltype(c.rend()); // C++14
389template <class E> reverse_iterator<const E*> constexpr rbegin(initializer_list<E> il); // C++14
390template <class E> reverse_iterator<const E*> constexpr rend(initializer_list<E> il); // C++14
391template <class T, size_t N> reverse_iterator<T*> constexpr rbegin(T (&array)[N]); // C++14
392template <class T, size_t N> reverse_iterator<T*> constexpr rend(T (&array)[N]); // C++14
393template <class C> constexpr auto crbegin(const C& c) -> decltype(std::rbegin(c)); // C++14
394template <class C> constexpr auto crend(const C& c) -> decltype(std::rend(c)); // C++14
Marshall Clowb278e9c2013-08-30 01:17:07 +0000395
Marshall Clowef357272014-11-19 19:43:23 +0000396// 24.8, container access:
397template <class C> constexpr auto size(const C& c) -> decltype(c.size()); // C++17
398template <class T, size_t N> constexpr size_t size(const T (&array)[N]) noexcept; // C++17
Marshall Clow3c5363e2019-02-27 02:58:56 +0000399
400template <class C> constexpr auto ssize(const C& c)
Arthur O'Dwyer2fc9b5d2021-04-17 17:03:20 -0400401 -> common_type_t<ptrdiff_t, make_signed_t<decltype(c.size())>>; // C++20
Marshall Clow3c5363e2019-02-27 02:58:56 +0000402template <class T, ptrdiff_t> constexpr ptrdiff_t ssize(const T (&array)[N]) noexcept; // C++20
403
Marshall Clowef357272014-11-19 19:43:23 +0000404template <class C> constexpr auto empty(const C& c) -> decltype(c.empty()); // C++17
405template <class T, size_t N> constexpr bool empty(const T (&array)[N]) noexcept; // C++17
406template <class E> constexpr bool empty(initializer_list<E> il) noexcept; // C++17
407template <class C> constexpr auto data(C& c) -> decltype(c.data()); // C++17
408template <class C> constexpr auto data(const C& c) -> decltype(c.data()); // C++17
409template <class T, size_t N> constexpr T* data(T (&array)[N]) noexcept; // C++17
410template <class E> constexpr const E* data(initializer_list<E> il) noexcept; // C++17
411
Howard Hinnantc51e1022010-05-11 19:42:16 +0000412} // std
413
414*/
415
416#include <__config>
Eric Fiselier876c6862016-02-20 00:19:45 +0000417#include <iosfwd> // for forward declarations of vector and string.
Marshall Clow3dc05502014-02-27 02:11:50 +0000418#include <__functional_base>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000419#include <type_traits>
Arthur O'Dwyer7deec122021-03-24 18:19:12 -0400420#include <compare>
zoecarver5d41ff52021-04-19 14:44:42 -0700421#include <concepts> // Mandated by the Standard.
Howard Hinnantc51e1022010-05-11 19:42:16 +0000422#include <cstddef>
Marshall Clowb278e9c2013-08-30 01:17:07 +0000423#include <initializer_list>
zoecarver61ae1dc2021-04-19 14:28:27 -0400424#include <__iterator/incrementable_traits.h>
zoecarver5d41ff52021-04-19 14:44:42 -0700425#include <__iterator/iterator_traits.h>
zoecarver61ae1dc2021-04-19 14:28:27 -0400426#include <__iterator/readable_traits.h>
Louis Dionne735bc462021-04-14 13:59:03 -0400427#include <__memory/addressof.h>
Arthur O'Dwyer1ac9f092021-01-15 12:59:56 -0500428#include <__memory/pointer_traits.h>
Marshall Clow0a1e7502018-09-12 19:41:40 +0000429#include <version>
Howard Hinnant48fd5d52012-11-14 21:17:15 +0000430
Eric Fiselier14b6de92014-08-10 23:53:08 +0000431#include <__debug>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000432
Howard Hinnantaaaa52b2011-10-17 20:05:10 +0000433#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000434#pragma GCC system_header
Howard Hinnantaaaa52b2011-10-17 20:05:10 +0000435#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000436
437_LIBCPP_BEGIN_NAMESPACE_STD
Christopher Di Bella490fe402021-03-23 03:55:52 +0000438
Howard Hinnantc51e1022010-05-11 19:42:16 +0000439template<class _Category, class _Tp, class _Distance = ptrdiff_t,
440 class _Pointer = _Tp*, class _Reference = _Tp&>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000441struct _LIBCPP_TEMPLATE_VIS iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +0000442{
443 typedef _Tp value_type;
444 typedef _Distance difference_type;
445 typedef _Pointer pointer;
446 typedef _Reference reference;
447 typedef _Category iterator_category;
448};
449
450template <class _InputIter>
Marshall Clow75468e72017-05-17 18:51:36 +0000451inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000452void __advance(_InputIter& __i,
453 typename iterator_traits<_InputIter>::difference_type __n, input_iterator_tag)
454{
455 for (; __n > 0; --__n)
456 ++__i;
457}
458
459template <class _BiDirIter>
Marshall Clow75468e72017-05-17 18:51:36 +0000460inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000461void __advance(_BiDirIter& __i,
462 typename iterator_traits<_BiDirIter>::difference_type __n, bidirectional_iterator_tag)
463{
464 if (__n >= 0)
465 for (; __n > 0; --__n)
466 ++__i;
467 else
468 for (; __n < 0; ++__n)
469 --__i;
470}
471
472template <class _RandIter>
Marshall Clow75468e72017-05-17 18:51:36 +0000473inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000474void __advance(_RandIter& __i,
475 typename iterator_traits<_RandIter>::difference_type __n, random_access_iterator_tag)
476{
477 __i += __n;
478}
479
Louis Dionne45768662020-06-08 16:16:01 -0400480template <class _InputIter, class _Distance>
Marshall Clow75468e72017-05-17 18:51:36 +0000481inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Louis Dionne45768662020-06-08 16:16:01 -0400482void advance(_InputIter& __i, _Distance __orig_n)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000483{
Louis Dionne45768662020-06-08 16:16:01 -0400484 _LIBCPP_ASSERT(__orig_n >= 0 || __is_cpp17_bidirectional_iterator<_InputIter>::value,
485 "Attempt to advance(it, n) with negative n on a non-bidirectional iterator");
Arthur O'Dwyer6e9069c2020-12-07 23:42:47 -0500486 typedef decltype(_VSTD::__convert_to_integral(__orig_n)) _IntegralSize;
Louis Dionne45768662020-06-08 16:16:01 -0400487 _IntegralSize __n = __orig_n;
Arthur O'Dwyer6e9069c2020-12-07 23:42:47 -0500488 _VSTD::__advance(__i, __n, typename iterator_traits<_InputIter>::iterator_category());
Howard Hinnantc51e1022010-05-11 19:42:16 +0000489}
490
491template <class _InputIter>
Marshall Clow75468e72017-05-17 18:51:36 +0000492inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000493typename iterator_traits<_InputIter>::difference_type
494__distance(_InputIter __first, _InputIter __last, input_iterator_tag)
495{
496 typename iterator_traits<_InputIter>::difference_type __r(0);
497 for (; __first != __last; ++__first)
498 ++__r;
499 return __r;
500}
501
502template <class _RandIter>
Marshall Clow75468e72017-05-17 18:51:36 +0000503inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000504typename iterator_traits<_RandIter>::difference_type
505__distance(_RandIter __first, _RandIter __last, random_access_iterator_tag)
506{
507 return __last - __first;
508}
509
510template <class _InputIter>
Marshall Clow75468e72017-05-17 18:51:36 +0000511inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000512typename iterator_traits<_InputIter>::difference_type
513distance(_InputIter __first, _InputIter __last)
514{
Arthur O'Dwyer6e9069c2020-12-07 23:42:47 -0500515 return _VSTD::__distance(__first, __last, typename iterator_traits<_InputIter>::iterator_category());
Howard Hinnantc51e1022010-05-11 19:42:16 +0000516}
517
Marshall Clow990c70d2015-11-07 17:48:49 +0000518template <class _InputIter>
Marshall Clow75468e72017-05-17 18:51:36 +0000519inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Rachel Craik2048d822017-07-24 22:17:05 +0000520typename enable_if
521<
Eric Fiseliercd5a6772019-11-18 01:46:58 -0500522 __is_cpp17_input_iterator<_InputIter>::value,
Rachel Craik2048d822017-07-24 22:17:05 +0000523 _InputIter
524>::type
Marshall Clow990c70d2015-11-07 17:48:49 +0000525next(_InputIter __x,
Rachel Craik2048d822017-07-24 22:17:05 +0000526 typename iterator_traits<_InputIter>::difference_type __n = 1)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000527{
Eric Fiseliercd5a6772019-11-18 01:46:58 -0500528 _LIBCPP_ASSERT(__n >= 0 || __is_cpp17_bidirectional_iterator<_InputIter>::value,
Louis Dionne45768662020-06-08 16:16:01 -0400529 "Attempt to next(it, n) with negative n on a non-bidirectional iterator");
Marshall Clow3d435212019-03-22 22:32:20 +0000530
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000531 _VSTD::advance(__x, __n);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000532 return __x;
533}
534
Marshall Clow3d435212019-03-22 22:32:20 +0000535template <class _InputIter>
Marshall Clow75468e72017-05-17 18:51:36 +0000536inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Rachel Craik2048d822017-07-24 22:17:05 +0000537typename enable_if
538<
Eric Fiseliercd5a6772019-11-18 01:46:58 -0500539 __is_cpp17_input_iterator<_InputIter>::value,
Marshall Clow3d435212019-03-22 22:32:20 +0000540 _InputIter
Rachel Craik2048d822017-07-24 22:17:05 +0000541>::type
Marshall Clow3d435212019-03-22 22:32:20 +0000542prev(_InputIter __x,
543 typename iterator_traits<_InputIter>::difference_type __n = 1)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000544{
Eric Fiseliercd5a6772019-11-18 01:46:58 -0500545 _LIBCPP_ASSERT(__n <= 0 || __is_cpp17_bidirectional_iterator<_InputIter>::value,
Louis Dionne45768662020-06-08 16:16:01 -0400546 "Attempt to prev(it, n) with a positive n on a non-bidirectional iterator");
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000547 _VSTD::advance(__x, -__n);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000548 return __x;
549}
550
Eric Fiselier883af112017-04-13 02:54:13 +0000551
552template <class _Tp, class = void>
553struct __is_stashing_iterator : false_type {};
554
555template <class _Tp>
556struct __is_stashing_iterator<_Tp, typename __void_t<typename _Tp::__stashing_iterator_tag>::type>
557 : true_type {};
558
Howard Hinnantc51e1022010-05-11 19:42:16 +0000559template <class _Iter>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000560class _LIBCPP_TEMPLATE_VIS reverse_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +0000561 : public iterator<typename iterator_traits<_Iter>::iterator_category,
562 typename iterator_traits<_Iter>::value_type,
563 typename iterator_traits<_Iter>::difference_type,
564 typename iterator_traits<_Iter>::pointer,
565 typename iterator_traits<_Iter>::reference>
566{
Marshall Clow0ad029e2014-03-11 22:05:31 +0000567private:
Marshall Clow5ace5542016-10-19 15:12:50 +0000568 /*mutable*/ _Iter __t; // no longer used as of LWG #2360, not removed due to ABI break
Eric Fiselier883af112017-04-13 02:54:13 +0000569
570 static_assert(!__is_stashing_iterator<_Iter>::value,
571 "The specified iterator type cannot be used with reverse_iterator; "
572 "Using stashing iterators with reverse_iterator causes undefined behavior");
573
Marshall Clow1f61f0a2014-03-12 01:19:36 +0000574protected:
575 _Iter current;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000576public:
577 typedef _Iter iterator_type;
578 typedef typename iterator_traits<_Iter>::difference_type difference_type;
579 typedef typename iterator_traits<_Iter>::reference reference;
580 typedef typename iterator_traits<_Iter>::pointer pointer;
Arthur O'Dwyer1ac9f092021-01-15 12:59:56 -0500581 typedef _If<__is_cpp17_random_access_iterator<_Iter>::value,
582 random_access_iterator_tag,
583 typename iterator_traits<_Iter>::iterator_category> iterator_category;
584#if _LIBCPP_STD_VER > 17
585 typedef _If<__is_cpp17_random_access_iterator<_Iter>::value,
586 random_access_iterator_tag,
587 bidirectional_iterator_tag> iterator_concept;
588#endif
Howard Hinnant3b6579a2010-08-22 00:02:43 +0000589
Marshall Clow5ace5542016-10-19 15:12:50 +0000590 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
591 reverse_iterator() : __t(), current() {}
592 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
593 explicit reverse_iterator(_Iter __x) : __t(__x), current(__x) {}
594 template <class _Up>
595 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
596 reverse_iterator(const reverse_iterator<_Up>& __u) : __t(__u.base()), current(__u.base()) {}
597 template <class _Up>
598 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
599 reverse_iterator& operator=(const reverse_iterator<_Up>& __u)
600 { __t = current = __u.base(); return *this; }
601 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
602 _Iter base() const {return current;}
603 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
604 reference operator*() const {_Iter __tmp = current; return *--__tmp;}
605 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
606 pointer operator->() const {return _VSTD::addressof(operator*());}
607 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
608 reverse_iterator& operator++() {--current; return *this;}
609 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
610 reverse_iterator operator++(int) {reverse_iterator __tmp(*this); --current; return __tmp;}
611 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
612 reverse_iterator& operator--() {++current; return *this;}
613 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
614 reverse_iterator operator--(int) {reverse_iterator __tmp(*this); ++current; return __tmp;}
615 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
616 reverse_iterator operator+ (difference_type __n) const {return reverse_iterator(current - __n);}
617 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
618 reverse_iterator& operator+=(difference_type __n) {current -= __n; return *this;}
619 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
620 reverse_iterator operator- (difference_type __n) const {return reverse_iterator(current + __n);}
621 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
622 reverse_iterator& operator-=(difference_type __n) {current += __n; return *this;}
623 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
624 reference operator[](difference_type __n) const {return *(*this + __n);}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000625};
626
627template <class _Iter1, class _Iter2>
Marshall Clow5ace5542016-10-19 15:12:50 +0000628inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000629bool
630operator==(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
631{
632 return __x.base() == __y.base();
633}
634
635template <class _Iter1, class _Iter2>
Marshall Clow5ace5542016-10-19 15:12:50 +0000636inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000637bool
638operator<(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
639{
640 return __x.base() > __y.base();
641}
642
643template <class _Iter1, class _Iter2>
Marshall Clow5ace5542016-10-19 15:12:50 +0000644inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000645bool
646operator!=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
647{
648 return __x.base() != __y.base();
649}
650
651template <class _Iter1, class _Iter2>
Marshall Clow5ace5542016-10-19 15:12:50 +0000652inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000653bool
654operator>(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
655{
656 return __x.base() < __y.base();
657}
658
659template <class _Iter1, class _Iter2>
Marshall Clow5ace5542016-10-19 15:12:50 +0000660inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000661bool
662operator>=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
663{
664 return __x.base() <= __y.base();
665}
666
667template <class _Iter1, class _Iter2>
Marshall Clow5ace5542016-10-19 15:12:50 +0000668inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000669bool
670operator<=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
671{
672 return __x.base() >= __y.base();
673}
674
Marshall Clow476d3f42016-07-18 13:19:00 +0000675#ifndef _LIBCPP_CXX03_LANG
Marshall Clowf8fec4e2016-07-08 16:54:47 +0000676template <class _Iter1, class _Iter2>
Marshall Clow5ace5542016-10-19 15:12:50 +0000677inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clowf8fec4e2016-07-08 16:54:47 +0000678auto
679operator-(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
680-> decltype(__y.base() - __x.base())
681{
682 return __y.base() - __x.base();
683}
684#else
Howard Hinnantc51e1022010-05-11 19:42:16 +0000685template <class _Iter1, class _Iter2>
686inline _LIBCPP_INLINE_VISIBILITY
687typename reverse_iterator<_Iter1>::difference_type
688operator-(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
689{
690 return __y.base() - __x.base();
691}
Marshall Clowf8fec4e2016-07-08 16:54:47 +0000692#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000693
694template <class _Iter>
Marshall Clow5ace5542016-10-19 15:12:50 +0000695inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000696reverse_iterator<_Iter>
697operator+(typename reverse_iterator<_Iter>::difference_type __n, const reverse_iterator<_Iter>& __x)
698{
699 return reverse_iterator<_Iter>(__x.base() - __n);
700}
701
Marshall Clow6dbbdc92014-03-03 01:24:04 +0000702#if _LIBCPP_STD_VER > 11
703template <class _Iter>
Marshall Clow5ace5542016-10-19 15:12:50 +0000704inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clow6dbbdc92014-03-03 01:24:04 +0000705reverse_iterator<_Iter> make_reverse_iterator(_Iter __i)
706{
707 return reverse_iterator<_Iter>(__i);
708}
709#endif
710
Howard Hinnantc51e1022010-05-11 19:42:16 +0000711template <class _Container>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000712class _LIBCPP_TEMPLATE_VIS back_insert_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +0000713 : public iterator<output_iterator_tag,
714 void,
715 void,
716 void,
Eric Fiselier9aeea872016-06-30 04:40:50 +0000717 void>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000718{
719protected:
720 _Container* container;
721public:
722 typedef _Container container_type;
723
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -0500724 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 explicit back_insert_iterator(_Container& __x) : container(_VSTD::addressof(__x)) {}
725 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 back_insert_iterator& operator=(const typename _Container::value_type& __value_)
Howard Hinnantbf074022011-10-22 20:59:45 +0000726 {container->push_back(__value_); return *this;}
Eric Fiselierf07d88c2017-04-19 01:34:08 +0000727#ifndef _LIBCPP_CXX03_LANG
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -0500728 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 back_insert_iterator& operator=(typename _Container::value_type&& __value_)
Howard Hinnantbf074022011-10-22 20:59:45 +0000729 {container->push_back(_VSTD::move(__value_)); return *this;}
Louis Dionne2b1ceaa2021-04-20 12:03:32 -0400730#endif // _LIBCPP_CXX03_LANG
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -0500731 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 back_insert_iterator& operator*() {return *this;}
732 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 back_insert_iterator& operator++() {return *this;}
733 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 back_insert_iterator operator++(int) {return *this;}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000734};
735
736template <class _Container>
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -0500737inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000738back_insert_iterator<_Container>
739back_inserter(_Container& __x)
740{
741 return back_insert_iterator<_Container>(__x);
742}
743
744template <class _Container>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000745class _LIBCPP_TEMPLATE_VIS front_insert_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +0000746 : public iterator<output_iterator_tag,
747 void,
748 void,
749 void,
Eric Fiselier9aeea872016-06-30 04:40:50 +0000750 void>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000751{
752protected:
753 _Container* container;
754public:
755 typedef _Container container_type;
756
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -0500757 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 explicit front_insert_iterator(_Container& __x) : container(_VSTD::addressof(__x)) {}
758 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 front_insert_iterator& operator=(const typename _Container::value_type& __value_)
Howard Hinnantbf074022011-10-22 20:59:45 +0000759 {container->push_front(__value_); return *this;}
Eric Fiselierf07d88c2017-04-19 01:34:08 +0000760#ifndef _LIBCPP_CXX03_LANG
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -0500761 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 front_insert_iterator& operator=(typename _Container::value_type&& __value_)
Howard Hinnantbf074022011-10-22 20:59:45 +0000762 {container->push_front(_VSTD::move(__value_)); return *this;}
Louis Dionne2b1ceaa2021-04-20 12:03:32 -0400763#endif // _LIBCPP_CXX03_LANG
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -0500764 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 front_insert_iterator& operator*() {return *this;}
765 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 front_insert_iterator& operator++() {return *this;}
766 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 front_insert_iterator operator++(int) {return *this;}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000767};
768
769template <class _Container>
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -0500770inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000771front_insert_iterator<_Container>
772front_inserter(_Container& __x)
773{
774 return front_insert_iterator<_Container>(__x);
775}
776
777template <class _Container>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000778class _LIBCPP_TEMPLATE_VIS insert_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +0000779 : public iterator<output_iterator_tag,
780 void,
781 void,
782 void,
Eric Fiselier9aeea872016-06-30 04:40:50 +0000783 void>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000784{
785protected:
786 _Container* container;
787 typename _Container::iterator iter;
788public:
789 typedef _Container container_type;
790
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -0500791 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 insert_iterator(_Container& __x, typename _Container::iterator __i)
Marshall Clowcef31682014-03-03 19:20:40 +0000792 : container(_VSTD::addressof(__x)), iter(__i) {}
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -0500793 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 insert_iterator& operator=(const typename _Container::value_type& __value_)
Howard Hinnantbf074022011-10-22 20:59:45 +0000794 {iter = container->insert(iter, __value_); ++iter; return *this;}
Eric Fiselierf07d88c2017-04-19 01:34:08 +0000795#ifndef _LIBCPP_CXX03_LANG
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -0500796 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 insert_iterator& operator=(typename _Container::value_type&& __value_)
Howard Hinnantbf074022011-10-22 20:59:45 +0000797 {iter = container->insert(iter, _VSTD::move(__value_)); ++iter; return *this;}
Louis Dionne2b1ceaa2021-04-20 12:03:32 -0400798#endif // _LIBCPP_CXX03_LANG
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -0500799 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 insert_iterator& operator*() {return *this;}
800 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 insert_iterator& operator++() {return *this;}
801 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 insert_iterator& operator++(int) {return *this;}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000802};
803
804template <class _Container>
Arthur O'Dwyer20638cc2021-02-09 19:12:16 -0500805inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000806insert_iterator<_Container>
807inserter(_Container& __x, typename _Container::iterator __i)
808{
809 return insert_iterator<_Container>(__x, __i);
810}
811
812template <class _Tp, class _CharT = char,
813 class _Traits = char_traits<_CharT>, class _Distance = ptrdiff_t>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000814class _LIBCPP_TEMPLATE_VIS istream_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +0000815 : public iterator<input_iterator_tag, _Tp, _Distance, const _Tp*, const _Tp&>
816{
817public:
818 typedef _CharT char_type;
819 typedef _Traits traits_type;
820 typedef basic_istream<_CharT,_Traits> istream_type;
821private:
822 istream_type* __in_stream_;
823 _Tp __value_;
824public:
Bruce Mitchener170d8972020-11-24 12:53:53 -0500825 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR istream_iterator() : __in_stream_(nullptr), __value_() {}
Marshall Clowb7742702016-05-17 17:44:40 +0000826 _LIBCPP_INLINE_VISIBILITY istream_iterator(istream_type& __s) : __in_stream_(_VSTD::addressof(__s))
Howard Hinnantc51e1022010-05-11 19:42:16 +0000827 {
828 if (!(*__in_stream_ >> __value_))
Bruce Mitchener170d8972020-11-24 12:53:53 -0500829 __in_stream_ = nullptr;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000830 }
831
832 _LIBCPP_INLINE_VISIBILITY const _Tp& operator*() const {return __value_;}
Marshall Clowb7742702016-05-17 17:44:40 +0000833 _LIBCPP_INLINE_VISIBILITY const _Tp* operator->() const {return _VSTD::addressof((operator*()));}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000834 _LIBCPP_INLINE_VISIBILITY istream_iterator& operator++()
835 {
836 if (!(*__in_stream_ >> __value_))
Bruce Mitchener170d8972020-11-24 12:53:53 -0500837 __in_stream_ = nullptr;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000838 return *this;
839 }
840 _LIBCPP_INLINE_VISIBILITY istream_iterator operator++(int)
841 {istream_iterator __t(*this); ++(*this); return __t;}
842
Roger Ferrer Ibanezd16858b2017-12-11 13:54:58 +0000843 template <class _Up, class _CharU, class _TraitsU, class _DistanceU>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000844 friend _LIBCPP_INLINE_VISIBILITY
Roger Ferrer Ibanezd16858b2017-12-11 13:54:58 +0000845 bool
846 operator==(const istream_iterator<_Up, _CharU, _TraitsU, _DistanceU>& __x,
847 const istream_iterator<_Up, _CharU, _TraitsU, _DistanceU>& __y);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000848
Roger Ferrer Ibanezd16858b2017-12-11 13:54:58 +0000849 template <class _Up, class _CharU, class _TraitsU, class _DistanceU>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000850 friend _LIBCPP_INLINE_VISIBILITY
Roger Ferrer Ibanezd16858b2017-12-11 13:54:58 +0000851 bool
852 operator==(const istream_iterator<_Up, _CharU, _TraitsU, _DistanceU>& __x,
853 const istream_iterator<_Up, _CharU, _TraitsU, _DistanceU>& __y);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000854};
855
Roger Ferrer Ibanezd16858b2017-12-11 13:54:58 +0000856template <class _Tp, class _CharT, class _Traits, class _Distance>
857inline _LIBCPP_INLINE_VISIBILITY
858bool
859operator==(const istream_iterator<_Tp, _CharT, _Traits, _Distance>& __x,
860 const istream_iterator<_Tp, _CharT, _Traits, _Distance>& __y)
861{
862 return __x.__in_stream_ == __y.__in_stream_;
863}
864
865template <class _Tp, class _CharT, class _Traits, class _Distance>
866inline _LIBCPP_INLINE_VISIBILITY
867bool
868operator!=(const istream_iterator<_Tp, _CharT, _Traits, _Distance>& __x,
869 const istream_iterator<_Tp, _CharT, _Traits, _Distance>& __y)
870{
871 return !(__x == __y);
872}
873
Howard Hinnantc51e1022010-05-11 19:42:16 +0000874template <class _Tp, class _CharT = char, class _Traits = char_traits<_CharT> >
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000875class _LIBCPP_TEMPLATE_VIS ostream_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +0000876 : public iterator<output_iterator_tag, void, void, void, void>
877{
878public:
Louis Dionnea4d79522020-09-11 10:15:56 -0400879 typedef output_iterator_tag iterator_category;
880 typedef void value_type;
881#if _LIBCPP_STD_VER > 17
882 typedef std::ptrdiff_t difference_type;
883#else
884 typedef void difference_type;
885#endif
886 typedef void pointer;
887 typedef void reference;
888 typedef _CharT char_type;
889 typedef _Traits traits_type;
890 typedef basic_ostream<_CharT, _Traits> ostream_type;
891
Howard Hinnantc51e1022010-05-11 19:42:16 +0000892private:
893 ostream_type* __out_stream_;
894 const char_type* __delim_;
895public:
Marshall Clow27a89512016-10-12 16:13:48 +0000896 _LIBCPP_INLINE_VISIBILITY ostream_iterator(ostream_type& __s) _NOEXCEPT
Bruce Mitchener170d8972020-11-24 12:53:53 -0500897 : __out_stream_(_VSTD::addressof(__s)), __delim_(nullptr) {}
Marshall Clow27a89512016-10-12 16:13:48 +0000898 _LIBCPP_INLINE_VISIBILITY ostream_iterator(ostream_type& __s, const _CharT* __delimiter) _NOEXCEPT
Marshall Clowb7742702016-05-17 17:44:40 +0000899 : __out_stream_(_VSTD::addressof(__s)), __delim_(__delimiter) {}
Howard Hinnantbf074022011-10-22 20:59:45 +0000900 _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator=(const _Tp& __value_)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000901 {
Howard Hinnantbf074022011-10-22 20:59:45 +0000902 *__out_stream_ << __value_;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000903 if (__delim_)
904 *__out_stream_ << __delim_;
905 return *this;
906 }
907
908 _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator*() {return *this;}
909 _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator++() {return *this;}
910 _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator++(int) {return *this;}
911};
912
913template<class _CharT, class _Traits>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000914class _LIBCPP_TEMPLATE_VIS istreambuf_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +0000915 : public iterator<input_iterator_tag, _CharT,
916 typename _Traits::off_type, _CharT*,
917 _CharT>
918{
919public:
920 typedef _CharT char_type;
921 typedef _Traits traits_type;
922 typedef typename _Traits::int_type int_type;
923 typedef basic_streambuf<_CharT,_Traits> streambuf_type;
924 typedef basic_istream<_CharT,_Traits> istream_type;
925private:
Howard Hinnant3e57b272012-11-16 22:17:23 +0000926 mutable streambuf_type* __sbuf_;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000927
928 class __proxy
929 {
930 char_type __keep_;
931 streambuf_type* __sbuf_;
932 _LIBCPP_INLINE_VISIBILITY __proxy(char_type __c, streambuf_type* __s)
933 : __keep_(__c), __sbuf_(__s) {}
934 friend class istreambuf_iterator;
935 public:
936 _LIBCPP_INLINE_VISIBILITY char_type operator*() const {return __keep_;}
937 };
938
Howard Hinnant756c69b2010-09-22 16:48:34 +0000939 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant3e57b272012-11-16 22:17:23 +0000940 bool __test_for_eof() const
Howard Hinnantc51e1022010-05-11 19:42:16 +0000941 {
942 if (__sbuf_ && traits_type::eq_int_type(__sbuf_->sgetc(), traits_type::eof()))
Bruce Mitchener170d8972020-11-24 12:53:53 -0500943 __sbuf_ = nullptr;
944 return __sbuf_ == nullptr;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000945 }
946public:
Bruce Mitchener170d8972020-11-24 12:53:53 -0500947 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR istreambuf_iterator() _NOEXCEPT : __sbuf_(nullptr) {}
Howard Hinnant011138d2012-07-20 19:36:34 +0000948 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(istream_type& __s) _NOEXCEPT
Howard Hinnantb9af8d82012-12-29 17:45:42 +0000949 : __sbuf_(__s.rdbuf()) {}
Howard Hinnant011138d2012-07-20 19:36:34 +0000950 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(streambuf_type* __s) _NOEXCEPT
Howard Hinnantb9af8d82012-12-29 17:45:42 +0000951 : __sbuf_(__s) {}
Howard Hinnant011138d2012-07-20 19:36:34 +0000952 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(const __proxy& __p) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000953 : __sbuf_(__p.__sbuf_) {}
954
Howard Hinnant28b24882011-12-01 20:21:04 +0000955 _LIBCPP_INLINE_VISIBILITY char_type operator*() const
956 {return static_cast<char_type>(__sbuf_->sgetc());}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000957 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator& operator++()
958 {
Howard Hinnant3e57b272012-11-16 22:17:23 +0000959 __sbuf_->sbumpc();
Howard Hinnantc51e1022010-05-11 19:42:16 +0000960 return *this;
961 }
962 _LIBCPP_INLINE_VISIBILITY __proxy operator++(int)
963 {
Howard Hinnant3e57b272012-11-16 22:17:23 +0000964 return __proxy(__sbuf_->sbumpc(), __sbuf_);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000965 }
966
967 _LIBCPP_INLINE_VISIBILITY bool equal(const istreambuf_iterator& __b) const
Howard Hinnant3e57b272012-11-16 22:17:23 +0000968 {return __test_for_eof() == __b.__test_for_eof();}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000969};
970
971template <class _CharT, class _Traits>
972inline _LIBCPP_INLINE_VISIBILITY
973bool operator==(const istreambuf_iterator<_CharT,_Traits>& __a,
974 const istreambuf_iterator<_CharT,_Traits>& __b)
975 {return __a.equal(__b);}
976
977template <class _CharT, class _Traits>
978inline _LIBCPP_INLINE_VISIBILITY
979bool operator!=(const istreambuf_iterator<_CharT,_Traits>& __a,
980 const istreambuf_iterator<_CharT,_Traits>& __b)
981 {return !__a.equal(__b);}
982
983template <class _CharT, class _Traits>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000984class _LIBCPP_TEMPLATE_VIS ostreambuf_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +0000985 : public iterator<output_iterator_tag, void, void, void, void>
986{
987public:
Louis Dionnea4d79522020-09-11 10:15:56 -0400988 typedef output_iterator_tag iterator_category;
989 typedef void value_type;
990#if _LIBCPP_STD_VER > 17
991 typedef std::ptrdiff_t difference_type;
992#else
993 typedef void difference_type;
994#endif
995 typedef void pointer;
996 typedef void reference;
997 typedef _CharT char_type;
998 typedef _Traits traits_type;
999 typedef basic_streambuf<_CharT, _Traits> streambuf_type;
1000 typedef basic_ostream<_CharT, _Traits> ostream_type;
1001
Howard Hinnantc51e1022010-05-11 19:42:16 +00001002private:
1003 streambuf_type* __sbuf_;
1004public:
Howard Hinnant011138d2012-07-20 19:36:34 +00001005 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator(ostream_type& __s) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001006 : __sbuf_(__s.rdbuf()) {}
Howard Hinnant011138d2012-07-20 19:36:34 +00001007 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator(streambuf_type* __s) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001008 : __sbuf_(__s) {}
1009 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator=(_CharT __c)
1010 {
1011 if (__sbuf_ && traits_type::eq_int_type(__sbuf_->sputc(__c), traits_type::eof()))
Bruce Mitchener170d8972020-11-24 12:53:53 -05001012 __sbuf_ = nullptr;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001013 return *this;
1014 }
1015 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator*() {return *this;}
1016 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator++() {return *this;}
1017 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator++(int) {return *this;}
Bruce Mitchener170d8972020-11-24 12:53:53 -05001018 _LIBCPP_INLINE_VISIBILITY bool failed() const _NOEXCEPT {return __sbuf_ == nullptr;}
Howard Hinnant97955172012-09-19 19:14:15 +00001019
1020 template <class _Ch, class _Tr>
1021 friend
1022 _LIBCPP_HIDDEN
1023 ostreambuf_iterator<_Ch, _Tr>
1024 __pad_and_output(ostreambuf_iterator<_Ch, _Tr> __s,
1025 const _Ch* __ob, const _Ch* __op, const _Ch* __oe,
1026 ios_base& __iob, _Ch __fl);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001027};
1028
1029template <class _Iter>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +00001030class _LIBCPP_TEMPLATE_VIS move_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +00001031{
1032private:
1033 _Iter __i;
1034public:
1035 typedef _Iter iterator_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001036 typedef typename iterator_traits<iterator_type>::value_type value_type;
1037 typedef typename iterator_traits<iterator_type>::difference_type difference_type;
Marshall Clowd85a0562016-04-11 03:54:53 +00001038 typedef iterator_type pointer;
Arthur O'Dwyer1ac9f092021-01-15 12:59:56 -05001039 typedef _If<__is_cpp17_random_access_iterator<_Iter>::value,
1040 random_access_iterator_tag,
1041 typename iterator_traits<_Iter>::iterator_category> iterator_category;
1042#if _LIBCPP_STD_VER > 17
1043 typedef input_iterator_tag iterator_concept;
1044#endif
1045
Eric Fiselierf07d88c2017-04-19 01:34:08 +00001046#ifndef _LIBCPP_CXX03_LANG
Eric Fiselier57b8e0e2016-04-22 00:49:12 +00001047 typedef typename iterator_traits<iterator_type>::reference __reference;
1048 typedef typename conditional<
1049 is_reference<__reference>::value,
1050 typename remove_reference<__reference>::type&&,
1051 __reference
1052 >::type reference;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001053#else
1054 typedef typename iterator_traits<iterator_type>::reference reference;
1055#endif
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001056
Marshall Clowb5f99122016-11-02 15:30:26 +00001057 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1058 move_iterator() : __i() {}
1059 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1060 explicit move_iterator(_Iter __x) : __i(__x) {}
1061 template <class _Up>
1062 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1063 move_iterator(const move_iterator<_Up>& __u) : __i(__u.base()) {}
1064 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14 _Iter base() const {return __i;}
Louis Dionne173f29e2019-05-29 16:01:36 +00001065 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clowb5f99122016-11-02 15:30:26 +00001066 reference operator*() const { return static_cast<reference>(*__i); }
1067 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1068 pointer operator->() const { return __i;}
1069 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1070 move_iterator& operator++() {++__i; return *this;}
1071 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1072 move_iterator operator++(int) {move_iterator __tmp(*this); ++__i; return __tmp;}
1073 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1074 move_iterator& operator--() {--__i; return *this;}
1075 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1076 move_iterator operator--(int) {move_iterator __tmp(*this); --__i; return __tmp;}
1077 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1078 move_iterator operator+ (difference_type __n) const {return move_iterator(__i + __n);}
1079 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1080 move_iterator& operator+=(difference_type __n) {__i += __n; return *this;}
1081 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1082 move_iterator operator- (difference_type __n) const {return move_iterator(__i - __n);}
1083 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1084 move_iterator& operator-=(difference_type __n) {__i -= __n; return *this;}
1085 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
1086 reference operator[](difference_type __n) const { return static_cast<reference>(__i[__n]); }
Howard Hinnantc51e1022010-05-11 19:42:16 +00001087};
1088
1089template <class _Iter1, class _Iter2>
Marshall Clowb5f99122016-11-02 15:30:26 +00001090inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00001091bool
1092operator==(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1093{
1094 return __x.base() == __y.base();
1095}
1096
1097template <class _Iter1, class _Iter2>
Marshall Clowb5f99122016-11-02 15:30:26 +00001098inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00001099bool
1100operator<(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1101{
1102 return __x.base() < __y.base();
1103}
1104
1105template <class _Iter1, class _Iter2>
Marshall Clowb5f99122016-11-02 15:30:26 +00001106inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00001107bool
1108operator!=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1109{
1110 return __x.base() != __y.base();
1111}
1112
1113template <class _Iter1, class _Iter2>
Marshall Clowb5f99122016-11-02 15:30:26 +00001114inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00001115bool
1116operator>(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1117{
1118 return __x.base() > __y.base();
1119}
1120
1121template <class _Iter1, class _Iter2>
Marshall Clowb5f99122016-11-02 15:30:26 +00001122inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00001123bool
1124operator>=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1125{
1126 return __x.base() >= __y.base();
1127}
1128
1129template <class _Iter1, class _Iter2>
Marshall Clowb5f99122016-11-02 15:30:26 +00001130inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00001131bool
1132operator<=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1133{
1134 return __x.base() <= __y.base();
1135}
1136
Marshall Clow476d3f42016-07-18 13:19:00 +00001137#ifndef _LIBCPP_CXX03_LANG
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001138template <class _Iter1, class _Iter2>
Marshall Clowb5f99122016-11-02 15:30:26 +00001139inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001140auto
1141operator-(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1142-> decltype(__x.base() - __y.base())
1143{
1144 return __x.base() - __y.base();
1145}
1146#else
Howard Hinnantc51e1022010-05-11 19:42:16 +00001147template <class _Iter1, class _Iter2>
1148inline _LIBCPP_INLINE_VISIBILITY
1149typename move_iterator<_Iter1>::difference_type
1150operator-(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
1151{
1152 return __x.base() - __y.base();
1153}
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001154#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001155
1156template <class _Iter>
Marshall Clowb5f99122016-11-02 15:30:26 +00001157inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00001158move_iterator<_Iter>
1159operator+(typename move_iterator<_Iter>::difference_type __n, const move_iterator<_Iter>& __x)
1160{
1161 return move_iterator<_Iter>(__x.base() + __n);
1162}
1163
1164template <class _Iter>
Marshall Clowb5f99122016-11-02 15:30:26 +00001165inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00001166move_iterator<_Iter>
Marshall Clow84f90cf2013-08-27 13:03:03 +00001167make_move_iterator(_Iter __i)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001168{
1169 return move_iterator<_Iter>(__i);
1170}
1171
1172// __wrap_iter
1173
1174template <class _Iter> class __wrap_iter;
1175
1176template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001177_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001178bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001179operator==(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001180
1181template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001182_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001183bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001184operator<(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001185
1186template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001187_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001188bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001189operator!=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001190
1191template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001192_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001193bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001194operator>(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001195
1196template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001197_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001198bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001199operator>=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001200
1201template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001202_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001203bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001204operator<=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001205
Marshall Clow476d3f42016-07-18 13:19:00 +00001206#ifndef _LIBCPP_CXX03_LANG
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001207template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001208_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001209auto
Eric Fiselier873b8d32019-03-18 21:50:12 +00001210operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001211-> decltype(__x.base() - __y.base());
1212#else
Howard Hinnantc51e1022010-05-11 19:42:16 +00001213template <class _Iter1, class _Iter2>
Howard Hinnanta54386e2012-09-14 00:39:16 +00001214_LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001215typename __wrap_iter<_Iter1>::difference_type
Eric Fiselier873b8d32019-03-18 21:50:12 +00001216operator-(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001217#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001218
1219template <class _Iter>
Marshall Clowae4f8312018-07-13 16:35:26 +00001220_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001221__wrap_iter<_Iter>
Eric Fiselier873b8d32019-03-18 21:50:12 +00001222operator+(typename __wrap_iter<_Iter>::difference_type, __wrap_iter<_Iter>) _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001223
Louis Dionne65b433b2019-11-06 12:02:41 +00001224template <class _Ip, class _Op> _Op _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 copy(_Ip, _Ip, _Op);
1225template <class _B1, class _B2> _B2 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 copy_backward(_B1, _B1, _B2);
zoecarverd0279de2020-09-14 18:11:08 -04001226template <class _Ip, class _Op> _Op _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 move(_Ip, _Ip, _Op);
1227template <class _B1, class _B2> _B2 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 move_backward(_B1, _B1, _B2);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001228
Howard Hinnantc51e1022010-05-11 19:42:16 +00001229template <class _Iter>
1230class __wrap_iter
1231{
1232public:
1233 typedef _Iter iterator_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001234 typedef typename iterator_traits<iterator_type>::value_type value_type;
1235 typedef typename iterator_traits<iterator_type>::difference_type difference_type;
1236 typedef typename iterator_traits<iterator_type>::pointer pointer;
1237 typedef typename iterator_traits<iterator_type>::reference reference;
Arthur O'Dwyer1ac9f092021-01-15 12:59:56 -05001238 typedef typename iterator_traits<iterator_type>::iterator_category iterator_category;
1239#if _LIBCPP_STD_VER > 17
1240 typedef _If<__is_cpp17_contiguous_iterator<_Iter>::value,
1241 contiguous_iterator_tag, iterator_category> iterator_concept;
1242#endif
1243
Howard Hinnantc51e1022010-05-11 19:42:16 +00001244private:
1245 iterator_type __i;
1246public:
Eric Fiselier873b8d32019-03-18 21:50:12 +00001247 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter() _NOEXCEPT
Marshall Clow4e7b35b2013-08-07 20:48:48 +00001248#if _LIBCPP_STD_VER > 11
1249 : __i{}
1250#endif
Howard Hinnantc90aa632011-09-16 19:52:23 +00001251 {
Louis Dionneba400782020-10-02 15:02:52 -04001252#if _LIBCPP_DEBUG_LEVEL == 2
Howard Hinnantc90aa632011-09-16 19:52:23 +00001253 __get_db()->__insert_i(this);
1254#endif
1255 }
Marshall Clowae4f8312018-07-13 16:35:26 +00001256 template <class _Up> _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
1257 __wrap_iter(const __wrap_iter<_Up>& __u,
Bruce Mitchener170d8972020-11-24 12:53:53 -05001258 typename enable_if<is_convertible<_Up, iterator_type>::value>::type* = nullptr) _NOEXCEPT
Marshall Clowae4f8312018-07-13 16:35:26 +00001259 : __i(__u.base())
Howard Hinnant27e0e772011-09-14 18:33:51 +00001260 {
Louis Dionneba400782020-10-02 15:02:52 -04001261#if _LIBCPP_DEBUG_LEVEL == 2
Howard Hinnant27e0e772011-09-14 18:33:51 +00001262 __get_db()->__iterator_copy(this, &__u);
1263#endif
1264 }
Louis Dionneba400782020-10-02 15:02:52 -04001265#if _LIBCPP_DEBUG_LEVEL == 2
Marshall Clowae4f8312018-07-13 16:35:26 +00001266 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnant27e0e772011-09-14 18:33:51 +00001267 __wrap_iter(const __wrap_iter& __x)
1268 : __i(__x.base())
1269 {
1270 __get_db()->__iterator_copy(this, &__x);
1271 }
Marshall Clowae4f8312018-07-13 16:35:26 +00001272 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnant27e0e772011-09-14 18:33:51 +00001273 __wrap_iter& operator=(const __wrap_iter& __x)
1274 {
1275 if (this != &__x)
1276 {
1277 __get_db()->__iterator_copy(this, &__x);
1278 __i = __x.__i;
1279 }
1280 return *this;
1281 }
Marshall Clowae4f8312018-07-13 16:35:26 +00001282 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnant27e0e772011-09-14 18:33:51 +00001283 ~__wrap_iter()
1284 {
1285 __get_db()->__erase_i(this);
1286 }
1287#endif
Eric Fiselier873b8d32019-03-18 21:50:12 +00001288 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG reference operator*() const _NOEXCEPT
Howard Hinnant27e0e772011-09-14 18:33:51 +00001289 {
Louis Dionneba400782020-10-02 15:02:52 -04001290#if _LIBCPP_DEBUG_LEVEL == 2
Howard Hinnant27e0e772011-09-14 18:33:51 +00001291 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
1292 "Attempted to dereference a non-dereferenceable iterator");
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001293#endif
Howard Hinnant27e0e772011-09-14 18:33:51 +00001294 return *__i;
1295 }
Eric Fiselier873b8d32019-03-18 21:50:12 +00001296 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG pointer operator->() const _NOEXCEPT
Howard Hinnant76053d72013-06-27 19:35:32 +00001297 {
Louis Dionneba400782020-10-02 15:02:52 -04001298#if _LIBCPP_DEBUG_LEVEL == 2
Howard Hinnant76053d72013-06-27 19:35:32 +00001299 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
1300 "Attempted to dereference a non-dereferenceable iterator");
1301#endif
Marshall Clowd85a0562016-04-11 03:54:53 +00001302 return (pointer)_VSTD::addressof(*__i);
Howard Hinnant76053d72013-06-27 19:35:32 +00001303 }
Eric Fiselier873b8d32019-03-18 21:50:12 +00001304 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter& operator++() _NOEXCEPT
Howard Hinnant27e0e772011-09-14 18:33:51 +00001305 {
Louis Dionneba400782020-10-02 15:02:52 -04001306#if _LIBCPP_DEBUG_LEVEL == 2
Howard Hinnant27e0e772011-09-14 18:33:51 +00001307 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
1308 "Attempted to increment non-incrementable iterator");
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001309#endif
Howard Hinnant27e0e772011-09-14 18:33:51 +00001310 ++__i;
1311 return *this;
1312 }
Eric Fiselier873b8d32019-03-18 21:50:12 +00001313 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter operator++(int) _NOEXCEPT
Howard Hinnant27e0e772011-09-14 18:33:51 +00001314 {__wrap_iter __tmp(*this); ++(*this); return __tmp;}
Marshall Clow6d553a52018-07-14 03:06:11 +00001315
Eric Fiselier873b8d32019-03-18 21:50:12 +00001316 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter& operator--() _NOEXCEPT
Howard Hinnant27e0e772011-09-14 18:33:51 +00001317 {
Louis Dionneba400782020-10-02 15:02:52 -04001318#if _LIBCPP_DEBUG_LEVEL == 2
Howard Hinnant27e0e772011-09-14 18:33:51 +00001319 _LIBCPP_ASSERT(__get_const_db()->__decrementable(this),
1320 "Attempted to decrement non-decrementable iterator");
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001321#endif
Howard Hinnant27e0e772011-09-14 18:33:51 +00001322 --__i;
1323 return *this;
1324 }
Eric Fiselier873b8d32019-03-18 21:50:12 +00001325 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter operator--(int) _NOEXCEPT
Howard Hinnant27e0e772011-09-14 18:33:51 +00001326 {__wrap_iter __tmp(*this); --(*this); return __tmp;}
Eric Fiselier873b8d32019-03-18 21:50:12 +00001327 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter operator+ (difference_type __n) const _NOEXCEPT
Howard Hinnant27e0e772011-09-14 18:33:51 +00001328 {__wrap_iter __w(*this); __w += __n; return __w;}
Eric Fiselier873b8d32019-03-18 21:50:12 +00001329 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter& operator+=(difference_type __n) _NOEXCEPT
Howard Hinnant27e0e772011-09-14 18:33:51 +00001330 {
Louis Dionneba400782020-10-02 15:02:52 -04001331#if _LIBCPP_DEBUG_LEVEL == 2
Howard Hinnant27e0e772011-09-14 18:33:51 +00001332 _LIBCPP_ASSERT(__get_const_db()->__addable(this, __n),
1333 "Attempted to add/subtract iterator outside of valid range");
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001334#endif
Howard Hinnant27e0e772011-09-14 18:33:51 +00001335 __i += __n;
1336 return *this;
1337 }
Eric Fiselier873b8d32019-03-18 21:50:12 +00001338 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter operator- (difference_type __n) const _NOEXCEPT
Howard Hinnant27e0e772011-09-14 18:33:51 +00001339 {return *this + (-__n);}
Eric Fiselier873b8d32019-03-18 21:50:12 +00001340 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter& operator-=(difference_type __n) _NOEXCEPT
Howard Hinnant27e0e772011-09-14 18:33:51 +00001341 {*this += -__n; return *this;}
Eric Fiselier873b8d32019-03-18 21:50:12 +00001342 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG reference operator[](difference_type __n) const _NOEXCEPT
Howard Hinnant27e0e772011-09-14 18:33:51 +00001343 {
Louis Dionneba400782020-10-02 15:02:52 -04001344#if _LIBCPP_DEBUG_LEVEL == 2
Howard Hinnant27e0e772011-09-14 18:33:51 +00001345 _LIBCPP_ASSERT(__get_const_db()->__subscriptable(this, __n),
1346 "Attempted to subscript iterator outside of valid range");
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001347#endif
Howard Hinnant27e0e772011-09-14 18:33:51 +00001348 return __i[__n];
1349 }
Howard Hinnantc51e1022010-05-11 19:42:16 +00001350
Eric Fiselier873b8d32019-03-18 21:50:12 +00001351 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG iterator_type base() const _NOEXCEPT {return __i;}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001352
1353private:
Louis Dionneba400782020-10-02 15:02:52 -04001354#if _LIBCPP_DEBUG_LEVEL == 2
Marshall Clowae4f8312018-07-13 16:35:26 +00001355 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter(const void* __p, iterator_type __x) : __i(__x)
Howard Hinnant27e0e772011-09-14 18:33:51 +00001356 {
1357 __get_db()->__insert_ic(this, __p);
1358 }
Howard Hinnant8ea98242013-08-23 17:37:05 +00001359#else
Eric Fiselier873b8d32019-03-18 21:50:12 +00001360 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG __wrap_iter(iterator_type __x) _NOEXCEPT : __i(__x) {}
Howard Hinnant27e0e772011-09-14 18:33:51 +00001361#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001362
1363 template <class _Up> friend class __wrap_iter;
1364 template <class _CharT, class _Traits, class _Alloc> friend class basic_string;
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +00001365 template <class _Tp, class _Alloc> friend class _LIBCPP_TEMPLATE_VIS vector;
Marshall Clowcd6d8802019-02-27 00:32:16 +00001366 template <class _Tp, size_t> friend class _LIBCPP_TEMPLATE_VIS span;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001367
1368 template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001369 _LIBCPP_CONSTEXPR_IF_NODEBUG friend
Howard Hinnantc51e1022010-05-11 19:42:16 +00001370 bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001371 operator==(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001372
Howard Hinnantc51e1022010-05-11 19:42:16 +00001373 template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001374 _LIBCPP_CONSTEXPR_IF_NODEBUG friend
Howard Hinnantc51e1022010-05-11 19:42:16 +00001375 bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001376 operator<(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001377
Howard Hinnantc51e1022010-05-11 19:42:16 +00001378 template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001379 _LIBCPP_CONSTEXPR_IF_NODEBUG friend
Howard Hinnantc51e1022010-05-11 19:42:16 +00001380 bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001381 operator!=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001382
Howard Hinnantc51e1022010-05-11 19:42:16 +00001383 template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001384 _LIBCPP_CONSTEXPR_IF_NODEBUG friend
Howard Hinnantc51e1022010-05-11 19:42:16 +00001385 bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001386 operator>(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001387
Howard Hinnantc51e1022010-05-11 19:42:16 +00001388 template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001389 _LIBCPP_CONSTEXPR_IF_NODEBUG friend
Howard Hinnantc51e1022010-05-11 19:42:16 +00001390 bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001391 operator>=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001392
Howard Hinnantc51e1022010-05-11 19:42:16 +00001393 template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001394 _LIBCPP_CONSTEXPR_IF_NODEBUG friend
Howard Hinnantc51e1022010-05-11 19:42:16 +00001395 bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001396 operator<=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001397
Marshall Clow476d3f42016-07-18 13:19:00 +00001398#ifndef _LIBCPP_CXX03_LANG
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001399 template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001400 _LIBCPP_CONSTEXPR_IF_NODEBUG friend
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001401 auto
Eric Fiselier873b8d32019-03-18 21:50:12 +00001402 operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001403 -> decltype(__x.base() - __y.base());
1404#else
Howard Hinnantc51e1022010-05-11 19:42:16 +00001405 template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001406 _LIBCPP_CONSTEXPR_IF_NODEBUG friend
Howard Hinnantc51e1022010-05-11 19:42:16 +00001407 typename __wrap_iter<_Iter1>::difference_type
Eric Fiselier873b8d32019-03-18 21:50:12 +00001408 operator-(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001409#endif
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001410
Howard Hinnantc51e1022010-05-11 19:42:16 +00001411 template <class _Iter1>
Marshall Clowae4f8312018-07-13 16:35:26 +00001412 _LIBCPP_CONSTEXPR_IF_NODEBUG friend
Howard Hinnantc51e1022010-05-11 19:42:16 +00001413 __wrap_iter<_Iter1>
Eric Fiselier873b8d32019-03-18 21:50:12 +00001414 operator+(typename __wrap_iter<_Iter1>::difference_type, __wrap_iter<_Iter1>) _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001415
Louis Dionne65b433b2019-11-06 12:02:41 +00001416 template <class _Ip, class _Op> friend _LIBCPP_CONSTEXPR_AFTER_CXX17 _Op copy(_Ip, _Ip, _Op);
1417 template <class _B1, class _B2> friend _LIBCPP_CONSTEXPR_AFTER_CXX17 _B2 copy_backward(_B1, _B1, _B2);
zoecarverd0279de2020-09-14 18:11:08 -04001418 template <class _Ip, class _Op> friend _LIBCPP_CONSTEXPR_AFTER_CXX17 _Op move(_Ip, _Ip, _Op);
1419 template <class _B1, class _B2> friend _LIBCPP_CONSTEXPR_AFTER_CXX17 _B2 move_backward(_B1, _B1, _B2);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001420};
1421
Arthur O'Dwyer1ac9f092021-01-15 12:59:56 -05001422#if _LIBCPP_STD_VER <= 17
1423template <class _It>
1424struct __is_cpp17_contiguous_iterator<__wrap_iter<_It> > : __is_cpp17_contiguous_iterator<_It> {};
1425#endif
1426
1427template <class _Iter>
1428_LIBCPP_CONSTEXPR
1429_EnableIf<__is_cpp17_contiguous_iterator<_Iter>::value, decltype(_VSTD::__to_address(declval<_Iter>()))>
1430__to_address(__wrap_iter<_Iter> __w) _NOEXCEPT {
1431 return _VSTD::__to_address(__w.base());
1432}
1433
Howard Hinnantc51e1022010-05-11 19:42:16 +00001434template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001435inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001436bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001437operator==(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001438{
1439 return __x.base() == __y.base();
1440}
1441
1442template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001443inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001444bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001445operator<(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001446{
Louis Dionneba400782020-10-02 15:02:52 -04001447#if _LIBCPP_DEBUG_LEVEL == 2
Howard Hinnante6ff0b62013-08-02 00:26:35 +00001448 _LIBCPP_ASSERT(__get_const_db()->__less_than_comparable(&__x, &__y),
Howard Hinnant27e0e772011-09-14 18:33:51 +00001449 "Attempted to compare incomparable iterators");
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001450#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001451 return __x.base() < __y.base();
1452}
1453
1454template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001455inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001456bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001457operator!=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001458{
Howard Hinnant27e0e772011-09-14 18:33:51 +00001459 return !(__x == __y);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001460}
1461
1462template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001463inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001464bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001465operator>(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001466{
Howard Hinnant27e0e772011-09-14 18:33:51 +00001467 return __y < __x;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001468}
1469
1470template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001471inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001472bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001473operator>=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001474{
Howard Hinnant27e0e772011-09-14 18:33:51 +00001475 return !(__x < __y);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001476}
1477
1478template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001479inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001480bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001481operator<=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001482{
Howard Hinnant27e0e772011-09-14 18:33:51 +00001483 return !(__y < __x);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001484}
1485
Howard Hinnantf78e32c2012-10-02 19:45:42 +00001486template <class _Iter1>
Marshall Clowae4f8312018-07-13 16:35:26 +00001487inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantf78e32c2012-10-02 19:45:42 +00001488bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001489operator!=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT
Howard Hinnantf78e32c2012-10-02 19:45:42 +00001490{
1491 return !(__x == __y);
1492}
1493
1494template <class _Iter1>
Marshall Clowae4f8312018-07-13 16:35:26 +00001495inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantf78e32c2012-10-02 19:45:42 +00001496bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001497operator>(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT
Howard Hinnantf78e32c2012-10-02 19:45:42 +00001498{
1499 return __y < __x;
1500}
1501
1502template <class _Iter1>
Marshall Clowae4f8312018-07-13 16:35:26 +00001503inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantf78e32c2012-10-02 19:45:42 +00001504bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001505operator>=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT
Howard Hinnantf78e32c2012-10-02 19:45:42 +00001506{
1507 return !(__x < __y);
1508}
1509
1510template <class _Iter1>
Marshall Clowae4f8312018-07-13 16:35:26 +00001511inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantf78e32c2012-10-02 19:45:42 +00001512bool
Eric Fiselier873b8d32019-03-18 21:50:12 +00001513operator<=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter1>& __y) _NOEXCEPT
Howard Hinnantf78e32c2012-10-02 19:45:42 +00001514{
1515 return !(__y < __x);
1516}
1517
Marshall Clow476d3f42016-07-18 13:19:00 +00001518#ifndef _LIBCPP_CXX03_LANG
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001519template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001520inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001521auto
Eric Fiselier873b8d32019-03-18 21:50:12 +00001522operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001523-> decltype(__x.base() - __y.base())
1524{
Louis Dionneba400782020-10-02 15:02:52 -04001525#if _LIBCPP_DEBUG_LEVEL == 2
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001526 _LIBCPP_ASSERT(__get_const_db()->__less_than_comparable(&__x, &__y),
1527 "Attempted to subtract incompatible iterators");
1528#endif
1529 return __x.base() - __y.base();
1530}
1531#else
Howard Hinnantc51e1022010-05-11 19:42:16 +00001532template <class _Iter1, class _Iter2>
Marshall Clowae4f8312018-07-13 16:35:26 +00001533inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001534typename __wrap_iter<_Iter1>::difference_type
Eric Fiselier873b8d32019-03-18 21:50:12 +00001535operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001536{
Louis Dionneba400782020-10-02 15:02:52 -04001537#if _LIBCPP_DEBUG_LEVEL == 2
Howard Hinnante6ff0b62013-08-02 00:26:35 +00001538 _LIBCPP_ASSERT(__get_const_db()->__less_than_comparable(&__x, &__y),
Howard Hinnant27e0e772011-09-14 18:33:51 +00001539 "Attempted to subtract incompatible iterators");
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001540#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001541 return __x.base() - __y.base();
1542}
Marshall Clowf8fec4e2016-07-08 16:54:47 +00001543#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001544
1545template <class _Iter>
Marshall Clowae4f8312018-07-13 16:35:26 +00001546inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001547__wrap_iter<_Iter>
1548operator+(typename __wrap_iter<_Iter>::difference_type __n,
Eric Fiselier873b8d32019-03-18 21:50:12 +00001549 __wrap_iter<_Iter> __x) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001550{
Howard Hinnant27e0e772011-09-14 18:33:51 +00001551 __x += __n;
1552 return __x;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001553}
1554
Marshall Clow039b2f02016-01-13 21:54:34 +00001555template <class _Iter>
1556struct __libcpp_is_trivial_iterator
Marshall Clowb5f99122016-11-02 15:30:26 +00001557 : public _LIBCPP_BOOL_CONSTANT(is_pointer<_Iter>::value) {};
Louis Dionne173f29e2019-05-29 16:01:36 +00001558
Marshall Clow039b2f02016-01-13 21:54:34 +00001559template <class _Iter>
1560struct __libcpp_is_trivial_iterator<move_iterator<_Iter> >
Marshall Clowb5f99122016-11-02 15:30:26 +00001561 : public _LIBCPP_BOOL_CONSTANT(__libcpp_is_trivial_iterator<_Iter>::value) {};
Marshall Clow039b2f02016-01-13 21:54:34 +00001562
1563template <class _Iter>
1564struct __libcpp_is_trivial_iterator<reverse_iterator<_Iter> >
Marshall Clowb5f99122016-11-02 15:30:26 +00001565 : public _LIBCPP_BOOL_CONSTANT(__libcpp_is_trivial_iterator<_Iter>::value) {};
Marshall Clow039b2f02016-01-13 21:54:34 +00001566
1567template <class _Iter>
1568struct __libcpp_is_trivial_iterator<__wrap_iter<_Iter> >
Marshall Clowb5f99122016-11-02 15:30:26 +00001569 : public _LIBCPP_BOOL_CONSTANT(__libcpp_is_trivial_iterator<_Iter>::value) {};
Marshall Clow039b2f02016-01-13 21:54:34 +00001570
1571
Marshall Clow8411ebf2013-12-02 03:24:33 +00001572template <class _Tp, size_t _Np>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001573_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
Marshall Clow8411ebf2013-12-02 03:24:33 +00001574_Tp*
1575begin(_Tp (&__array)[_Np])
1576{
1577 return __array;
1578}
1579
1580template <class _Tp, size_t _Np>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001581_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
Marshall Clow8411ebf2013-12-02 03:24:33 +00001582_Tp*
1583end(_Tp (&__array)[_Np])
1584{
1585 return __array + _Np;
1586}
1587
Eric Fiselierc6f17cc2016-09-25 03:34:28 +00001588#if !defined(_LIBCPP_CXX03_LANG)
Marshall Clow037fcb72013-12-11 19:32:32 +00001589
Howard Hinnantc834c512011-11-29 18:15:50 +00001590template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001591_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00001592auto
Howard Hinnantc834c512011-11-29 18:15:50 +00001593begin(_Cp& __c) -> decltype(__c.begin())
Howard Hinnantc51e1022010-05-11 19:42:16 +00001594{
1595 return __c.begin();
1596}
1597
Howard Hinnantc834c512011-11-29 18:15:50 +00001598template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001599_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00001600auto
Howard Hinnantc834c512011-11-29 18:15:50 +00001601begin(const _Cp& __c) -> decltype(__c.begin())
Howard Hinnantc51e1022010-05-11 19:42:16 +00001602{
1603 return __c.begin();
1604}
1605
Howard Hinnantc834c512011-11-29 18:15:50 +00001606template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001607_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00001608auto
Howard Hinnantc834c512011-11-29 18:15:50 +00001609end(_Cp& __c) -> decltype(__c.end())
Howard Hinnantc51e1022010-05-11 19:42:16 +00001610{
1611 return __c.end();
1612}
1613
Howard Hinnantc834c512011-11-29 18:15:50 +00001614template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001615_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Howard Hinnantc51e1022010-05-11 19:42:16 +00001616auto
Howard Hinnantc834c512011-11-29 18:15:50 +00001617end(const _Cp& __c) -> decltype(__c.end())
Howard Hinnantc51e1022010-05-11 19:42:16 +00001618{
1619 return __c.end();
1620}
1621
Marshall Clowb278e9c2013-08-30 01:17:07 +00001622#if _LIBCPP_STD_VER > 11
1623
Marshall Clow8411ebf2013-12-02 03:24:33 +00001624template <class _Tp, size_t _Np>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001625_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clow8411ebf2013-12-02 03:24:33 +00001626reverse_iterator<_Tp*> rbegin(_Tp (&__array)[_Np])
1627{
1628 return reverse_iterator<_Tp*>(__array + _Np);
1629}
1630
1631template <class _Tp, size_t _Np>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001632_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clow8411ebf2013-12-02 03:24:33 +00001633reverse_iterator<_Tp*> rend(_Tp (&__array)[_Np])
1634{
1635 return reverse_iterator<_Tp*>(__array);
1636}
1637
1638template <class _Ep>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001639_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clow8411ebf2013-12-02 03:24:33 +00001640reverse_iterator<const _Ep*> rbegin(initializer_list<_Ep> __il)
1641{
1642 return reverse_iterator<const _Ep*>(__il.end());
1643}
1644
1645template <class _Ep>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001646_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clow8411ebf2013-12-02 03:24:33 +00001647reverse_iterator<const _Ep*> rend(initializer_list<_Ep> __il)
1648{
1649 return reverse_iterator<const _Ep*>(__il.begin());
1650}
1651
Marshall Clowb278e9c2013-08-30 01:17:07 +00001652template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001653_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
Marshall Clow3862f532016-08-10 20:04:46 +00001654auto cbegin(const _Cp& __c) -> decltype(_VSTD::begin(__c))
Marshall Clowb278e9c2013-08-30 01:17:07 +00001655{
Marshall Clow3862f532016-08-10 20:04:46 +00001656 return _VSTD::begin(__c);
Marshall Clowb278e9c2013-08-30 01:17:07 +00001657}
1658
1659template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001660_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
Marshall Clow3862f532016-08-10 20:04:46 +00001661auto cend(const _Cp& __c) -> decltype(_VSTD::end(__c))
Marshall Clowb278e9c2013-08-30 01:17:07 +00001662{
Marshall Clow3862f532016-08-10 20:04:46 +00001663 return _VSTD::end(__c);
Marshall Clowb278e9c2013-08-30 01:17:07 +00001664}
1665
1666template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001667_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clowb278e9c2013-08-30 01:17:07 +00001668auto rbegin(_Cp& __c) -> decltype(__c.rbegin())
1669{
1670 return __c.rbegin();
1671}
1672
1673template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001674_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clowb278e9c2013-08-30 01:17:07 +00001675auto rbegin(const _Cp& __c) -> decltype(__c.rbegin())
1676{
1677 return __c.rbegin();
1678}
1679
1680template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001681_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clowb278e9c2013-08-30 01:17:07 +00001682auto rend(_Cp& __c) -> decltype(__c.rend())
1683{
1684 return __c.rend();
1685}
1686
1687template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001688_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clowb278e9c2013-08-30 01:17:07 +00001689auto rend(const _Cp& __c) -> decltype(__c.rend())
1690{
1691 return __c.rend();
1692}
1693
1694template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001695_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clow3862f532016-08-10 20:04:46 +00001696auto crbegin(const _Cp& __c) -> decltype(_VSTD::rbegin(__c))
Marshall Clowb278e9c2013-08-30 01:17:07 +00001697{
Marshall Clow3862f532016-08-10 20:04:46 +00001698 return _VSTD::rbegin(__c);
Marshall Clowb278e9c2013-08-30 01:17:07 +00001699}
1700
1701template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001702_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
Marshall Clow3862f532016-08-10 20:04:46 +00001703auto crend(const _Cp& __c) -> decltype(_VSTD::rend(__c))
Marshall Clowb278e9c2013-08-30 01:17:07 +00001704{
Marshall Clow3862f532016-08-10 20:04:46 +00001705 return _VSTD::rend(__c);
Marshall Clowb278e9c2013-08-30 01:17:07 +00001706}
1707
1708#endif
1709
1710
Eric Fiselierc6f17cc2016-09-25 03:34:28 +00001711#else // defined(_LIBCPP_CXX03_LANG)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001712
Howard Hinnantc834c512011-11-29 18:15:50 +00001713template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001714_LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001715typename _Cp::iterator
1716begin(_Cp& __c)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001717{
1718 return __c.begin();
1719}
1720
Howard Hinnantc834c512011-11-29 18:15:50 +00001721template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001722_LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001723typename _Cp::const_iterator
1724begin(const _Cp& __c)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001725{
1726 return __c.begin();
1727}
1728
Howard Hinnantc834c512011-11-29 18:15:50 +00001729template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001730_LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001731typename _Cp::iterator
1732end(_Cp& __c)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001733{
1734 return __c.end();
1735}
1736
Howard Hinnantc834c512011-11-29 18:15:50 +00001737template <class _Cp>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001738_LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001739typename _Cp::const_iterator
1740end(const _Cp& __c)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001741{
1742 return __c.end();
1743}
1744
Louis Dionne2b1ceaa2021-04-20 12:03:32 -04001745#endif // !defined(_LIBCPP_CXX03_LANG)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001746
Marshall Clowef357272014-11-19 19:43:23 +00001747#if _LIBCPP_STD_VER > 14
Marshall Clow344c41d2017-11-16 17:55:41 +00001748
1749// #if _LIBCPP_STD_VER > 11
1750// template <>
1751// struct _LIBCPP_TEMPLATE_VIS plus<void>
1752// {
1753// template <class _T1, class _T2>
1754// _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
1755// auto operator()(_T1&& __t, _T2&& __u) const
1756// _NOEXCEPT_(noexcept(_VSTD::forward<_T1>(__t) + _VSTD::forward<_T2>(__u)))
1757// -> decltype (_VSTD::forward<_T1>(__t) + _VSTD::forward<_T2>(__u))
1758// { return _VSTD::forward<_T1>(__t) + _VSTD::forward<_T2>(__u); }
1759// typedef void is_transparent;
1760// };
1761// #endif
1762
Marshall Clowc4b4a342015-02-11 16:14:01 +00001763template <class _Cont>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001764_LIBCPP_INLINE_VISIBILITY
Marshall Clow344c41d2017-11-16 17:55:41 +00001765constexpr auto size(const _Cont& __c)
1766_NOEXCEPT_(noexcept(__c.size()))
1767-> decltype (__c.size())
1768{ return __c.size(); }
Marshall Clowef357272014-11-19 19:43:23 +00001769
Marshall Clowc4b4a342015-02-11 16:14:01 +00001770template <class _Tp, size_t _Sz>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001771_LIBCPP_INLINE_VISIBILITY
Eric Fiselier6003c772016-12-23 23:37:52 +00001772constexpr size_t size(const _Tp (&)[_Sz]) noexcept { return _Sz; }
Marshall Clowef357272014-11-19 19:43:23 +00001773
Marshall Clow3c5363e2019-02-27 02:58:56 +00001774#if _LIBCPP_STD_VER > 17
1775template <class _Cont>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001776_LIBCPP_INLINE_VISIBILITY
Marshall Clow3c5363e2019-02-27 02:58:56 +00001777constexpr auto ssize(const _Cont& __c)
1778_NOEXCEPT_(noexcept(static_cast<common_type_t<ptrdiff_t, make_signed_t<decltype(__c.size())>>>(__c.size())))
1779-> common_type_t<ptrdiff_t, make_signed_t<decltype(__c.size())>>
1780{ return static_cast<common_type_t<ptrdiff_t, make_signed_t<decltype(__c.size())>>>(__c.size()); }
1781
1782template <class _Tp, ptrdiff_t _Sz>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001783_LIBCPP_INLINE_VISIBILITY
Marshall Clow3c5363e2019-02-27 02:58:56 +00001784constexpr ptrdiff_t ssize(const _Tp (&)[_Sz]) noexcept { return _Sz; }
1785#endif
1786
Marshall Clowc4b4a342015-02-11 16:14:01 +00001787template <class _Cont>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001788_LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
Marshall Clow344c41d2017-11-16 17:55:41 +00001789constexpr auto empty(const _Cont& __c)
1790_NOEXCEPT_(noexcept(__c.empty()))
1791-> decltype (__c.empty())
1792{ return __c.empty(); }
Marshall Clowef357272014-11-19 19:43:23 +00001793
Marshall Clowc4b4a342015-02-11 16:14:01 +00001794template <class _Tp, size_t _Sz>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001795_LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
Eric Fiselier6003c772016-12-23 23:37:52 +00001796constexpr bool empty(const _Tp (&)[_Sz]) noexcept { return false; }
Marshall Clowef357272014-11-19 19:43:23 +00001797
1798template <class _Ep>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001799_LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
Marshall Clowef357272014-11-19 19:43:23 +00001800constexpr bool empty(initializer_list<_Ep> __il) noexcept { return __il.size() == 0; }
1801
Marshall Clowc4b4a342015-02-11 16:14:01 +00001802template <class _Cont> constexpr
Marshall Clow0bd662d2019-02-27 03:25:43 +00001803_LIBCPP_INLINE_VISIBILITY
Marshall Clow344c41d2017-11-16 17:55:41 +00001804auto data(_Cont& __c)
1805_NOEXCEPT_(noexcept(__c.data()))
1806-> decltype (__c.data())
1807{ return __c.data(); }
Marshall Clowef357272014-11-19 19:43:23 +00001808
Marshall Clowc4b4a342015-02-11 16:14:01 +00001809template <class _Cont> constexpr
Marshall Clow0bd662d2019-02-27 03:25:43 +00001810_LIBCPP_INLINE_VISIBILITY
Marshall Clow344c41d2017-11-16 17:55:41 +00001811auto data(const _Cont& __c)
1812_NOEXCEPT_(noexcept(__c.data()))
Louis Dionne173f29e2019-05-29 16:01:36 +00001813-> decltype (__c.data())
Marshall Clow344c41d2017-11-16 17:55:41 +00001814{ return __c.data(); }
Marshall Clowef357272014-11-19 19:43:23 +00001815
Marshall Clowc4b4a342015-02-11 16:14:01 +00001816template <class _Tp, size_t _Sz>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001817_LIBCPP_INLINE_VISIBILITY
Marshall Clowc4b4a342015-02-11 16:14:01 +00001818constexpr _Tp* data(_Tp (&__array)[_Sz]) noexcept { return __array; }
Marshall Clowef357272014-11-19 19:43:23 +00001819
1820template <class _Ep>
Marshall Clow0bd662d2019-02-27 03:25:43 +00001821_LIBCPP_INLINE_VISIBILITY
Marshall Clowef357272014-11-19 19:43:23 +00001822constexpr const _Ep* data(initializer_list<_Ep> __il) noexcept { return __il.begin(); }
1823#endif
1824
Arthur O'Dwyerb6738bd2021-03-21 16:53:09 -04001825template <class _Container, class _Predicate>
1826typename _Container::size_type
1827__libcpp_erase_if_container(_Container& __c, _Predicate& __pred) {
1828 typename _Container::size_type __old_size = __c.size();
1829
1830 const typename _Container::iterator __last = __c.end();
1831 for (typename _Container::iterator __iter = __c.begin(); __iter != __last;) {
1832 if (__pred(*__iter))
1833 __iter = __c.erase(__iter);
1834 else
1835 ++__iter;
1836 }
1837
1838 return __old_size - __c.size();
1839}
Marshall Clowef357272014-11-19 19:43:23 +00001840
Howard Hinnantc51e1022010-05-11 19:42:16 +00001841_LIBCPP_END_NAMESPACE_STD
1842
Louis Dionne2b1ceaa2021-04-20 12:03:32 -04001843#endif // _LIBCPP_ITERATOR