1// -*- C++ -*-
2//===----------------------------------------------------------------------===//
3//
4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP_ITERATOR
11#define _LIBCPP_ITERATOR
12
13/*
14 iterator synopsis
15
16#include <concepts>
17
18namespace std
19{
20template<class> struct incrementable_traits; // since C++20
21template<class T>
22 using iter_difference_t = see below; // since C++20
23
24template<class> struct indirectly_readable_traits; // since C++20
25template<class T>
26 using iter_value_t = see below; // since C++20
27
28template<class Iterator>
29struct iterator_traits;
30
31template<class T>
32 requires is_object_v<T> // since C++20
33struct iterator_traits<T*>;
34
35template<dereferenceable T>
36 using iter_reference_t = decltype(*declval<T&>());
37
38namespace ranges::inline unspecified {
39 inline constexpr unspecified iter_move = unspecified; // since C++20, nodiscard as an extension
40}}
41
42template<dereferenceable T>
43 requires ...
44using iter_rvalue_reference_t = decltype(ranges::iter_move(declval<T&>())); // since C++20
45
46// [iterator.concepts], iterator concepts
47// [iterator.concept.readable], concept indirectly_readable
48template<class In>
49 concept indirectly_readable = see below; // since C++20
50
51template<indirectly_readable T>
52 using iter_common_reference_t =
53 common_reference_t<iter_reference_t<T>, iter_value_t<T>&>; // since C++20
54
55// [iterator.concept.writable], concept indirectly_writable
56template<class Out, class T>
57 concept indirectly_writable = see below; // since C++20
58
59// [iterator.concept.winc], concept weakly_incrementable
60template<class I>
61 concept weakly_incrementable = see below; // since C++20
62
63// [iterator.concept.inc], concept incrementable
64template<class I>
65 concept incrementable = see below; // since C++20
66
67// [iterator.concept.iterator], concept input_or_output_iterator
68 template<class I>
69 concept input_or_output_iterator = see below; // since C++20
70
71// [iterator.concept.sentinel], concept sentinel_for
72template<class S, class I>
73 concept sentinel_for = see below; // since C++20
74
75// [iterator.concept.sizedsentinel], concept sized_sentinel_for
76template<class S, class I>
77 inline constexpr bool disable_sized_sentinel_for = false;
78
79template<class S, class I>
80 concept sized_sentinel_for = see below;
81
82// [iterator.concept.input], concept input_iterator
83template<class I>
84 concept input_iterator = see below; // since C++20
85
86// [iterator.concept.output], concept output_iterator
87template<class I, class T>
88 concept output_iterator = see below; // since C++20
89
90// [iterator.concept.forward], concept forward_iterator
91template<class I>
92 concept forward_iterator = see below; // since C++20
93
94// [iterator.concept.bidir], concept bidirectional_iterator
95template<class I>
96 concept bidirectional_iterator = see below; // since C++20
97
98// [iterator.concept.random.access], concept random_access_iterator
99template<class I>
100 concept random_access_iterator = see below; // since C++20
101
102// [indirectcallable]
103// [indirectcallable.indirectinvocable]
104template<class F, class I>
105 concept indirectly_unary_invocable = see below; // since C++20
106
107template<class F, class I>
108 concept indirectly_regular_unary_invocable = see below; // since C++20
109
110template<class F, class I>
111 concept indirect_unary_predicate = see below; // since C++20
112
113template<class F, class I1, class I2>
114 concept indirect_binary_predicate = see below; // since C++20
115
116template<class F, class I1, class I2 = I1>
117 concept indirect_equivalence_relation = see below; // since C++20
118
119template<class F, class I1, class I2 = I1>
120 concept indirect_strict_weak_order = see below; // since C++20
121
122template<class F, class... Is>
123 using indirect_result_t = see below; // since C++20
124
125// [projected], projected
126template<indirectly_readable I, indirectly_regular_unary_invocable<I> Proj>
127 struct projected; // since C++20
128
129template<weakly_incrementable I, indirectly_regular_unary_invocable<I> Proj>
130 struct incrementable_traits<projected<I, Proj>>; // since C++20
131
132// [alg.req.ind.move], concept indirectly_movable
133template<class In, class Out>
134 concept indirectly_movable = see below; // since C++20
135
136template<class In, class Out>
137 concept indirectly_movable_storable = see below; // since C++20
138
139// [alg.req.ind.copy], concept indirectly_copyable
140template<class In, class Out>
141 concept indirectly_copyable = see below; // since C++20
142
143template<class In, class Out>
144 concept indirectly_copyable_storable = see below; // since C++20
145
146// [alg.req.ind.swap], concept indirectly_swappable
147template<class I1, class I2 = I1>
148 concept indirectly_swappable = see below; // since C++20
149
150template<class I1, class I2, class R, class P1 = identity,
151 class P2 = identity>
152 concept indirectly_comparable =
153 indirect_binary_predicate<R, projected<I1, P1>, projected<I2, P2>>; // since C++20
154
155// [alg.req.permutable], concept permutable
156template<class I>
157 concept permutable = see below; // since C++20
158
159 // [alg.req.mergeable], concept mergeable
160template<class I1, class I2, class Out,
161 class R = ranges::less, class P1 = identity, class P2 = identity>
162 concept mergeable = see below; // since C++20
163
164// [alg.req.sortable], concept sortable
165template<class I, class R = ranges::less, class P = identity>
166 concept sortable = see below; // since C++20
167
168template<input_or_output_iterator I, sentinel_for<I> S>
169 requires (!same_as<I, S> && copyable<I>)
170class common_iterator; // since C++20
171
172template<class Category, class T, class Distance = ptrdiff_t,
173 class Pointer = T*, class Reference = T&>
174struct iterator // deprecated in C++17
175{
176 typedef T value_type;
177 typedef Distance difference_type;
178 typedef Pointer pointer;
179 typedef Reference reference;
180 typedef Category iterator_category;
181};
182
183struct input_iterator_tag {};
184struct output_iterator_tag {};
185struct forward_iterator_tag : public input_iterator_tag {};
186struct bidirectional_iterator_tag : public forward_iterator_tag {};
187struct random_access_iterator_tag : public bidirectional_iterator_tag {};
188struct contiguous_iterator_tag : public random_access_iterator_tag {};
189
190// 27.4.3, iterator operations
191template <class InputIterator, class Distance> // constexpr in C++17
192 constexpr void advance(InputIterator& i, Distance n);
193
194template <class InputIterator> // constexpr in C++17
195 constexpr typename iterator_traits<InputIterator>::difference_type
196 distance(InputIterator first, InputIterator last);
197
198template <class InputIterator> // constexpr in C++17
199 constexpr InputIterator next(InputIterator x,
200typename iterator_traits<InputIterator>::difference_type n = 1);
201
202template <class BidirectionalIterator> // constexpr in C++17
203 constexpr BidirectionalIterator prev(BidirectionalIterator x,
204 typename iterator_traits<BidirectionalIterator>::difference_type n = 1);
205
206// [range.iter.ops], range iterator operations
207namespace ranges {
208 // [range.iter.op.advance], ranges::advance
209 template<input_or_output_iterator I>
210 constexpr void advance(I& i, iter_difference_t<I> n); // since C++20
211 template<input_or_output_iterator I, sentinel_for<I> S>
212 constexpr void advance(I& i, S bound); // since C++20
213 template<input_or_output_iterator I, sentinel_for<I> S>
214 constexpr iter_difference_t<I> advance(I& i, iter_difference_t<I> n, S bound); // since C++20
215}
216
217template <class Iterator>
218class reverse_iterator
219 : public iterator<typename iterator_traits<Iterator>::iterator_category, // until C++17
220 typename iterator_traits<Iterator>::value_type,
221 typename iterator_traits<Iterator>::difference_type,
222 typename iterator_traits<Iterator>::pointer,
223 typename iterator_traits<Iterator>::reference>
224{
225protected:
226 Iterator current;
227public:
228 using iterator_type = Iterator;
229 using iterator_concept = see below; // since C++20
230 using iterator_category = typename iterator_traits<Iterator>::iterator_category; // since C++17, until C++20
231 using iterator_category = see below; // since C++20
232 using value_type = typename iterator_traits<Iterator>::value_type; // since C++17, until C++20
233 using value_type = iter_value_t<Iterator>; // since C++20
234 using difference_type = typename iterator_traits<Iterator>::difference_type; // until C++20
235 using difference_type = iter_difference_t<Iterator>; // since C++20
236 using pointer = typename iterator_traits<Iterator>::pointer;
237 using reference = typename iterator_traits<Iterator>::reference; // until C++20
238 using reference = iter_reference_t<Iterator>; // since C++20
239
240 constexpr reverse_iterator();
241 constexpr explicit reverse_iterator(Iterator x);
242 template <class U> constexpr reverse_iterator(const reverse_iterator<U>& u);
243 template <class U> constexpr reverse_iterator& operator=(const reverse_iterator<U>& u);
244 constexpr Iterator base() const;
245 constexpr reference operator*() const;
246 constexpr pointer operator->() const; // until C++20
247 constexpr pointer operator->() const requires see below; // since C++20
248 constexpr reverse_iterator& operator++();
249 constexpr reverse_iterator operator++(int);
250 constexpr reverse_iterator& operator--();
251 constexpr reverse_iterator operator--(int);
252 constexpr reverse_iterator operator+ (difference_type n) const;
253 constexpr reverse_iterator& operator+=(difference_type n);
254 constexpr reverse_iterator operator- (difference_type n) const;
255 constexpr reverse_iterator& operator-=(difference_type n);
256 constexpr unspecified operator[](difference_type n) const;
257
258 friend constexpr iter_rvalue_reference_t<Iterator>
259 iter_move(const reverse_iterator& i) noexcept(see below);
260 template<indirectly_swappable<Iterator> Iterator2>
261 friend constexpr void
262 iter_swap(const reverse_iterator& x,
263 const reverse_iterator<Iterator2>& y) noexcept(see below);
264};
265
266template <class Iterator1, class Iterator2>
267constexpr bool // constexpr in C++17
268operator==(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
269
270template <class Iterator1, class Iterator2>
271constexpr bool // constexpr in C++17
272operator!=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
273
274template <class Iterator1, class Iterator2>
275constexpr bool // constexpr in C++17
276operator<(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
277
278template <class Iterator1, class Iterator2>
279constexpr bool // constexpr in C++17
280operator>(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
281
282template <class Iterator1, class Iterator2>
283constexpr bool // constexpr in C++17
284operator<=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
285
286template <class Iterator1, class Iterator2>
287constexpr bool // constexpr in C++17
288operator>=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
289
290template<class Iterator1, three_way_comparable_with<Iterator1> Iterator2>
291 constexpr compare_three_way_result_t<Iterator1, Iterator2>
292 operator<=>(const reverse_iterator<Iterator1>& x,
293 const reverse_iterator<Iterator2>& y);
294
295template <class Iterator1, class Iterator2>
296constexpr auto
297operator-(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y)
298-> decltype(__y.base() - __x.base()); // constexpr in C++17
299
300template <class Iterator>
301constexpr reverse_iterator<Iterator>
302operator+(typename reverse_iterator<Iterator>::difference_type n,
303 const reverse_iterator<Iterator>& x); // constexpr in C++17
304
305template <class Iterator>
306constexpr reverse_iterator<Iterator> make_reverse_iterator(Iterator i); // C++14, constexpr in C++17
307
308template<class Iterator1, class Iterator2>
309 requires (!sized_sentinel_for<Iterator1, Iterator2>)
310 inline constexpr bool disable_sized_sentinel_for<reverse_iterator<Iterator1>,
311 reverse_iterator<Iterator2>> = true;
312
313template <class Container>
314class back_insert_iterator
315 : public iterator<output_iterator_tag, void, void, void, void> // until C++17
316{
317protected:
318 Container* container;
319public:
320 typedef Container container_type;
321 typedef void value_type;
322 typedef void difference_type; // until C++20
323 typedef ptrdiff_t difference_type; // since C++20
324 typedef void reference;
325 typedef void pointer;
326
327 explicit back_insert_iterator(Container& x); // constexpr in C++20
328 back_insert_iterator& operator=(const typename Container::value_type& value); // constexpr in C++20
329 back_insert_iterator& operator*(); // constexpr in C++20
330 back_insert_iterator& operator++(); // constexpr in C++20
331 back_insert_iterator operator++(int); // constexpr in C++20
332};
333
334template <class Container> back_insert_iterator<Container> back_inserter(Container& x); // constexpr in C++20
335
336template <class Container>
337class front_insert_iterator
338 : public iterator<output_iterator_tag, void, void, void, void> // until C++17
339{
340protected:
341 Container* container;
342public:
343 typedef Container container_type;
344 typedef void value_type;
345 typedef void difference_type; // until C++20
346 typedef ptrdiff_t difference_type; // since C++20
347 typedef void reference;
348 typedef void pointer;
349
350 explicit front_insert_iterator(Container& x); // constexpr in C++20
351 front_insert_iterator& operator=(const typename Container::value_type& value); // constexpr in C++20
352 front_insert_iterator& operator*(); // constexpr in C++20
353 front_insert_iterator& operator++(); // constexpr in C++20
354 front_insert_iterator operator++(int); // constexpr in C++20
355};
356
357template <class Container> front_insert_iterator<Container> front_inserter(Container& x); // constexpr in C++20
358
359template <class Container>
360class insert_iterator
361 : public iterator<output_iterator_tag, void, void, void, void> // until C++17
362{
363protected:
364 Container* container;
365 typename Container::iterator iter;
366public:
367 typedef Container container_type;
368 typedef void value_type;
369 typedef void difference_type; // until C++20
370 typedef ptrdiff_t difference_type; // since C++20
371 typedef void reference;
372 typedef void pointer;
373
374 insert_iterator(Container& x, typename Container::iterator i); // constexpr in C++20
375 insert_iterator& operator=(const typename Container::value_type& value); // constexpr in C++20
376 insert_iterator& operator*(); // constexpr in C++20
377 insert_iterator& operator++(); // constexpr in C++20
378 insert_iterator& operator++(int); // constexpr in C++20
379};
380
381template <class Container>
382insert_iterator<Container> inserter(Container& x, typename Container::iterator i); // until C++20
383template <class Container>
384constexpr insert_iterator<Container> inserter(Container& x, ranges::iterator_t<Container> i); // since C++20
385
386template <class Iterator>
387class move_iterator {
388public:
389 using iterator_type = Iterator;
390 using iterator_concept = see below; // From C++20
391 using iterator_category = see below; // not always present starting from C++20
392 using value_type = iter_value_t<Iterator>; // Until C++20, iterator_traits<Iterator>::value_type
393 using difference_type = iter_difference_t<Iterator>; // Until C++20, iterator_traits<Iterator>::difference_type;
394 using pointer = Iterator;
395 using reference = iter_rvalue_reference_t<Iterator>; // Until C++20, value_type&&
396
397 constexpr move_iterator(); // all the constexprs are in C++17
398 constexpr explicit move_iterator(Iterator i);
399 template <class U>
400 constexpr move_iterator(const move_iterator<U>& u);
401 template <class U>
402 constexpr move_iterator& operator=(const move_iterator<U>& u);
403
404 constexpr iterator_type base() const; // Until C++20
405 constexpr const Iterator& base() const & noexcept; // From C++20
406 constexpr Iterator base() &&; // From C++20
407
408 constexpr reference operator*() const;
409 constexpr pointer operator->() const; // Deprecated in C++20
410 constexpr move_iterator& operator++();
411 constexpr auto operator++(int); // Return type was move_iterator until C++20
412 constexpr move_iterator& operator--();
413 constexpr move_iterator operator--(int);
414 constexpr move_iterator operator+(difference_type n) const;
415 constexpr move_iterator& operator+=(difference_type n);
416 constexpr move_iterator operator-(difference_type n) const;
417 constexpr move_iterator& operator-=(difference_type n);
418 constexpr reference operator[](difference_type n) const; // Return type unspecified until C++20
419
420 template<sentinel_for<Iterator> S>
421 friend constexpr bool
422 operator==(const move_iterator& x, const move_sentinel<S>& y); // Since C++20
423 template<sized_sentinel_for<Iterator> S>
424 friend constexpr iter_difference_t<Iterator>
425 operator-(const move_sentinel<S>& x, const move_iterator& y); // Since C++20
426 template<sized_sentinel_for<Iterator> S>
427 friend constexpr iter_difference_t<Iterator>
428 operator-(const move_iterator& x, const move_sentinel<S>& y); // Since C++20
429 friend constexpr iter_rvalue_reference_t<Iterator>
430 iter_move(const move_iterator& i)
431 noexcept(noexcept(ranges::iter_move(i.current))); // Since C++20
432 template<indirectly_swappable<Iterator> Iterator2>
433 friend constexpr void
434 iter_swap(const move_iterator& x, const move_iterator<Iterator2>& y)
435 noexcept(noexcept(ranges::iter_swap(x.current, y.current))); // Since C++20
436
437private:
438 Iterator current; // exposition only
439};
440
441template <class Iterator1, class Iterator2>
442constexpr bool // constexpr in C++17
443operator==(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
444
445template <class Iterator1, class Iterator2>
446constexpr bool // constexpr in C++17
447operator!=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
448
449template <class Iterator1, class Iterator2>
450constexpr bool // constexpr in C++17
451operator<(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
452
453template <class Iterator1, class Iterator2>
454constexpr bool // constexpr in C++17
455operator<=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
456
457template <class Iterator1, class Iterator2>
458constexpr bool // constexpr in C++17
459operator>(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
460
461template <class Iterator1, class Iterator2>
462constexpr bool // constexpr in C++17
463operator>=(const move_iterator<Iterator1>& x, const move_iterator<Iterator2>& y);
464
465template <class Iterator1, class Iterator2>
466constexpr auto // constexpr in C++17
467operator-(const move_iterator<Iterator1>& x,
468 const move_iterator<Iterator2>& y) -> decltype(x.base() - y.base());
469
470template <class Iterator>
471constexpr move_iterator<Iterator> operator+( // constexpr in C++17
472 typename move_iterator<Iterator>::difference_type n,
473 const move_iterator<Iterator>& x);
474
475template <class Iterator> // constexpr in C++17
476constexpr move_iterator<Iterator> make_move_iterator(const Iterator& i);
477
478template<class Iterator1, class Iterator2>
479 requires (!sized_sentinel_for<Iterator1, Iterator2>)
480 inline constexpr bool disable_sized_sentinel_for<move_iterator<Iterator1>, // since C++20
481 move_iterator<Iterator2>> = true;
482
483template<semiregular S>
484class move_sentinel {
485public:
486 constexpr move_sentinel();
487 constexpr explicit move_sentinel(S s);
488 template<class S2>
489 requires convertible_to<const S2&, S>
490 constexpr move_sentinel(const move_sentinel<S2>& s);
491 template<class S2>
492 requires assignable_from<S&, const S2&>
493 constexpr move_sentinel& operator=(const move_sentinel<S2>& s);
494
495 constexpr S base() const;
496private:
497 S last; // exposition only
498};
499
500// [default.sentinel], default sentinel
501struct default_sentinel_t;
502inline constexpr default_sentinel_t default_sentinel{};
503
504// [iterators.counted], counted iterators
505template<input_or_output_iterator I> class counted_iterator;
506
507template<input_iterator I>
508 requires see below
509 struct iterator_traits<counted_iterator<I>>;
510
511// [unreachable.sentinel], unreachable sentinel
512struct unreachable_sentinel_t;
513inline constexpr unreachable_sentinel_t unreachable_sentinel{};
514
515template <class T, class charT = char, class traits = char_traits<charT>, class Distance = ptrdiff_t>
516class istream_iterator
517 : public iterator<input_iterator_tag, T, Distance, const T*, const T&> // until C++17
518{
519public:
520 typedef input_iterator_tag iterator_category;
521 typedef T value_type;
522 typedef Distance difference_type;
523 typedef const T* pointer;
524 typedef const T& reference;
525
526 typedef charT char_type;
527 typedef traits traits_type;
528 typedef basic_istream<charT, traits> istream_type;
529
530 istream_iterator(); // constexpr since C++11
531 constexpr istream_iterator(default_sentinel_t); // since C++20
532 istream_iterator(istream_type& s);
533 istream_iterator(const istream_iterator& x);
534 ~istream_iterator();
535
536 const T& operator*() const;
537 const T* operator->() const;
538 istream_iterator& operator++();
539 istream_iterator operator++(int);
540 friend bool operator==(const istream_iterator& i, default_sentinel_t); // since C++20
541};
542
543template <class T, class charT, class traits, class Distance>
544bool operator==(const istream_iterator<T,charT,traits,Distance>& x,
545 const istream_iterator<T,charT,traits,Distance>& y);
546template <class T, class charT, class traits, class Distance>
547bool operator!=(const istream_iterator<T,charT,traits,Distance>& x,
548 const istream_iterator<T,charT,traits,Distance>& y); // until C++20
549
550template <class T, class charT = char, class traits = char_traits<charT> >
551class ostream_iterator
552 : public iterator<output_iterator_tag, void, void, void, void> // until C++17
553{
554public:
555 typedef output_iterator_tag iterator_category;
556 typedef void value_type;
557 typedef void difference_type; // until C++20
558 typedef ptrdiff_t difference_type; // since C++20
559 typedef void pointer;
560 typedef void reference;
561
562 typedef charT char_type;
563 typedef traits traits_type;
564 typedef basic_ostream<charT,traits> ostream_type;
565
566 ostream_iterator(ostream_type& s);
567 ostream_iterator(ostream_type& s, const charT* delimiter);
568 ostream_iterator(const ostream_iterator& x);
569 ~ostream_iterator();
570 ostream_iterator& operator=(const T& value);
571
572 ostream_iterator& operator*();
573 ostream_iterator& operator++();
574 ostream_iterator& operator++(int);
575};
576
577template<class charT, class traits = char_traits<charT> >
578class istreambuf_iterator
579 : public iterator<input_iterator_tag, charT, traits::off_type, unspecified, charT> // until C++17
580{
581public:
582 typedef input_iterator_tag iterator_category;
583 typedef charT value_type;
584 typedef traits::off_type difference_type;
585 typedef unspecified pointer;
586 typedef charT reference;
587
588 typedef charT char_type;
589 typedef traits traits_type;
590 typedef traits::int_type int_type;
591 typedef basic_streambuf<charT, traits> streambuf_type;
592 typedef basic_istream<charT, traits> istream_type;
593
594 istreambuf_iterator() noexcept; // constexpr since C++11
595 constexpr istreambuf_iterator(default_sentinel_t) noexcept; // since C++20
596 istreambuf_iterator(istream_type& s) noexcept;
597 istreambuf_iterator(streambuf_type* s) noexcept;
598 istreambuf_iterator(a-private-type) noexcept;
599
600 charT operator*() const;
601 pointer operator->() const;
602 istreambuf_iterator& operator++();
603 a-private-type operator++(int);
604
605 bool equal(const istreambuf_iterator& b) const;
606 friend bool operator==(const istreambuf_iterator& i, default_sentinel_t s); // since C++20
607};
608
609template <class charT, class traits>
610bool operator==(const istreambuf_iterator<charT,traits>& a,
611 const istreambuf_iterator<charT,traits>& b);
612template <class charT, class traits>
613bool operator!=(const istreambuf_iterator<charT,traits>& a,
614 const istreambuf_iterator<charT,traits>& b); // until C++20
615
616template <class charT, class traits = char_traits<charT> >
617class ostreambuf_iterator
618 : public iterator<output_iterator_tag, void, void, void, void> // until C++17
619{
620public:
621 typedef output_iterator_tag iterator_category;
622 typedef void value_type;
623 typedef void difference_type; // until C++20
624 typedef ptrdiff_t difference_type; // since C++20
625 typedef void pointer;
626 typedef void reference;
627
628 typedef charT char_type;
629 typedef traits traits_type;
630 typedef basic_streambuf<charT, traits> streambuf_type;
631 typedef basic_ostream<charT, traits> ostream_type;
632
633 ostreambuf_iterator(ostream_type& s) noexcept;
634 ostreambuf_iterator(streambuf_type* s) noexcept;
635 ostreambuf_iterator& operator=(charT c);
636 ostreambuf_iterator& operator*();
637 ostreambuf_iterator& operator++();
638 ostreambuf_iterator& operator++(int);
639 bool failed() const noexcept;
640};
641
642template <class C> constexpr auto begin(C& c) -> decltype(c.begin()); // constexpr since C++17
643template <class C> constexpr auto begin(const C& c) -> decltype(c.begin()); // constexpr since C++17
644template <class C> constexpr auto end(C& c) -> decltype(c.end()); // constexpr since C++17
645template <class C> constexpr auto end(const C& c) -> decltype(c.end()); // constexpr since C++17
646template <class T, size_t N> constexpr T* begin(T (&array)[N]) noexcept;
647template <class T, size_t N> constexpr T* end(T (&array)[N]) noexcept;
648
649template <class C> constexpr auto cbegin(const C& c) noexcept(see-below) -> decltype(std::begin(c)); // C++14
650template <class C> constexpr auto cend(const C& c) noexcept(see-below) -> decltype(std::end(c)); // C++14
651template <class C> constexpr auto rbegin(C& c) -> decltype(c.rbegin()); // C++14, constexpr since C++17
652template <class C> constexpr auto rbegin(const C& c) -> decltype(c.rbegin()); // C++14, constexpr since C++17
653template <class C> constexpr auto rend(C& c) -> decltype(c.rend()); // C++14, constexpr since C++17
654template <class C> constexpr auto rend(const C& c) -> decltype(c.rend()); // C++14, constexpr since C++17
655template <class E> constexpr reverse_iterator<const E*> rbegin(initializer_list<E> il); // C++14, constexpr since C++17
656template <class E> constexpr reverse_iterator<const E*> rend(initializer_list<E> il); // C++14, constexpr since C++17
657template <class T, size_t N> constexpr reverse_iterator<T*> rbegin(T (&array)[N]); // C++14, constexpr since C++17
658template <class T, size_t N> constexpr reverse_iterator<T*> rend(T (&array)[N]); // C++14, constexpr since C++17
659template <class C> constexpr auto crbegin(const C& c) -> decltype(std::rbegin(c)); // C++14, constexpr since C++17
660template <class C> constexpr auto crend(const C& c) -> decltype(std::rend(c)); // C++14, constexpr since C++17
661
662// 24.8, container access:
663template <class C> constexpr auto size(const C& c) -> decltype(c.size()); // C++17
664template <class T, size_t N> constexpr size_t size(const T (&array)[N]) noexcept; // C++17
665
666template <class C> constexpr auto ssize(const C& c)
667 -> common_type_t<ptrdiff_t, make_signed_t<decltype(c.size())>>; // C++20
668template <class T, ptrdiff_t> constexpr ptrdiff_t ssize(const T (&array)[N]) noexcept; // C++20
669
670template <class C> constexpr auto empty(const C& c) -> decltype(c.empty()); // C++17
671template <class T, size_t N> constexpr bool empty(const T (&array)[N]) noexcept; // C++17
672template <class E> constexpr bool empty(initializer_list<E> il) noexcept; // C++17
673template <class C> constexpr auto data(C& c) -> decltype(c.data()); // C++17
674template <class C> constexpr auto data(const C& c) -> decltype(c.data()); // C++17
675template <class T, size_t N> constexpr T* data(T (&array)[N]) noexcept; // C++17
676template <class E> constexpr const E* data(initializer_list<E> il) noexcept; // C++17
677
678} // std
679
680*/
681
682#include <__config>
683#include <__iterator/access.h>
684#include <__iterator/advance.h>
685#include <__iterator/back_insert_iterator.h>
686#include <__iterator/distance.h>
687#include <__iterator/front_insert_iterator.h>
688#include <__iterator/insert_iterator.h>
689#include <__iterator/istream_iterator.h>
690#include <__iterator/istreambuf_iterator.h>
691#include <__iterator/iterator.h>
692#include <__iterator/iterator_traits.h>
693#include <__iterator/move_iterator.h>
694#include <__iterator/next.h>
695#include <__iterator/ostream_iterator.h>
696#include <__iterator/ostreambuf_iterator.h>
697#include <__iterator/prev.h>
698#include <__iterator/reverse_iterator.h>
699#include <__iterator/wrap_iter.h>
700
701#if _LIBCPP_STD_VER >= 14
702# include <__iterator/reverse_access.h>
703#endif
704
705#if _LIBCPP_STD_VER >= 17
706# include <__iterator/data.h>
707# include <__iterator/empty.h>
708# include <__iterator/size.h>
709#endif
710
711#if _LIBCPP_STD_VER >= 20
712# include <__iterator/common_iterator.h>
713# include <__iterator/concepts.h>
714# include <__iterator/counted_iterator.h>
715# include <__iterator/default_sentinel.h>
716# include <__iterator/incrementable_traits.h>
717# include <__iterator/indirectly_comparable.h>
718# include <__iterator/iter_move.h>
719# include <__iterator/iter_swap.h>
720# include <__iterator/mergeable.h>
721# include <__iterator/move_sentinel.h>
722# include <__iterator/permutable.h>
723# include <__iterator/projected.h>
724# include <__iterator/readable_traits.h>
725# include <__iterator/sortable.h>
726# include <__iterator/unreachable_sentinel.h>
727#endif
728
729#include <version>
730
731// standard-mandated includes
732
733// [iterator.synopsis]
734#include <compare>
735#include <concepts>
736
737#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
738# pragma GCC system_header
739#endif
740
741#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 17
742# include <variant>
743#endif
744
745#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
746# include <cstdlib>
747# include <exception>
748# include <new>
749# include <type_traits>
750# include <typeinfo>
751# include <utility>
752#endif
753
754#endif // _LIBCPP_ITERATOR
755