1// Iterators -*- C++ -*-
2
3// Copyright (C) 2001-2022 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/*
26 *
27 * Copyright (c) 1994
28 * Hewlett-Packard Company
29 *
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation. Hewlett-Packard Company makes no
35 * representations about the suitability of this software for any
36 * purpose. It is provided "as is" without express or implied warranty.
37 *
38 *
39 * Copyright (c) 1996-1998
40 * Silicon Graphics Computer Systems, Inc.
41 *
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation. Silicon Graphics makes no
47 * representations about the suitability of this software for any
48 * purpose. It is provided "as is" without express or implied warranty.
49 */
50
51/** @file bits/stl_iterator.h
52 * This is an internal header file, included by other library headers.
53 * Do not attempt to use it directly. @headername{iterator}
54 *
55 * This file implements reverse_iterator, back_insert_iterator,
56 * front_insert_iterator, insert_iterator, __normal_iterator, and their
57 * supporting functions and overloaded operators.
58 */
59
60#ifndef _STL_ITERATOR_H
61#define _STL_ITERATOR_H 1
62
63#include <bits/cpp_type_traits.h>
64#include <bits/stl_iterator_base_types.h>
65#include <ext/type_traits.h>
66#include <bits/move.h>
67#include <bits/ptr_traits.h>
68
69#if __cplusplus >= 201103L
70# include <type_traits>
71#endif
72
73#if __cplusplus > 201703L
74# define __cpp_lib_array_constexpr 201811L
75# define __cpp_lib_constexpr_iterator 201811L
76#elif __cplusplus == 201703L
77# define __cpp_lib_array_constexpr 201803L
78#endif
79
80#if __cplusplus >= 202002L
81# include <compare>
82# include <new>
83# include <bits/exception_defines.h>
84# include <bits/iterator_concepts.h>
85# include <bits/stl_construct.h>
86#endif
87
88namespace std _GLIBCXX_VISIBILITY(default)
89{
90_GLIBCXX_BEGIN_NAMESPACE_VERSION
91
92 /**
93 * @addtogroup iterators
94 * @{
95 */
96
97#if __cpp_lib_concepts
98 namespace __detail
99 {
100 // Weaken iterator_category _Cat to _Limit if it is derived from that,
101 // otherwise use _Otherwise.
102 template<typename _Cat, typename _Limit, typename _Otherwise = _Cat>
103 using __clamp_iter_cat
104 = __conditional_t<derived_from<_Cat, _Limit>, _Limit, _Otherwise>;
105 }
106#endif
107
108// Ignore warnings about std::iterator.
109#pragma GCC diagnostic push
110#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
111
112 // 24.4.1 Reverse iterators
113 /**
114 * Bidirectional and random access iterators have corresponding reverse
115 * %iterator adaptors that iterate through the data structure in the
116 * opposite direction. They have the same signatures as the corresponding
117 * iterators. The fundamental relation between a reverse %iterator and its
118 * corresponding %iterator @c i is established by the identity:
119 * @code
120 * &*(reverse_iterator(i)) == &*(i - 1)
121 * @endcode
122 *
123 * <em>This mapping is dictated by the fact that while there is always a
124 * pointer past the end of an array, there might not be a valid pointer
125 * before the beginning of an array.</em> [24.4.1]/1,2
126 *
127 * Reverse iterators can be tricky and surprising at first. Their
128 * semantics make sense, however, and the trickiness is a side effect of
129 * the requirement that the iterators must be safe.
130 */
131 template<typename _Iterator>
132 class reverse_iterator
133 : public iterator<typename iterator_traits<_Iterator>::iterator_category,
134 typename iterator_traits<_Iterator>::value_type,
135 typename iterator_traits<_Iterator>::difference_type,
136 typename iterator_traits<_Iterator>::pointer,
137 typename iterator_traits<_Iterator>::reference>
138 {
139 template<typename _Iter>
140 friend class reverse_iterator;
141
142#if __cpp_lib_concepts
143 // _GLIBCXX_RESOLVE_LIB_DEFECTS
144 // 3435. three_way_comparable_with<reverse_iterator<int*>, [...]>
145 template<typename _Iter>
146 static constexpr bool __convertible = !is_same_v<_Iter, _Iterator>
147 && convertible_to<const _Iter&, _Iterator>;
148#endif
149
150 protected:
151 _Iterator current;
152
153 typedef iterator_traits<_Iterator> __traits_type;
154
155 public:
156 typedef _Iterator iterator_type;
157 typedef typename __traits_type::pointer pointer;
158#if ! __cpp_lib_concepts
159 typedef typename __traits_type::difference_type difference_type;
160 typedef typename __traits_type::reference reference;
161#else
162 using iterator_concept
163 = __conditional_t<random_access_iterator<_Iterator>,
164 random_access_iterator_tag,
165 bidirectional_iterator_tag>;
166 using iterator_category
167 = __detail::__clamp_iter_cat<typename __traits_type::iterator_category,
168 random_access_iterator_tag>;
169 using value_type = iter_value_t<_Iterator>;
170 using difference_type = iter_difference_t<_Iterator>;
171 using reference = iter_reference_t<_Iterator>;
172#endif
173
174 /**
175 * The default constructor value-initializes member @p current.
176 * If it is a pointer, that means it is zero-initialized.
177 */
178 // _GLIBCXX_RESOLVE_LIB_DEFECTS
179 // 235 No specification of default ctor for reverse_iterator
180 // 1012. reverse_iterator default ctor should value initialize
181 _GLIBCXX17_CONSTEXPR
182 reverse_iterator()
183 _GLIBCXX_NOEXCEPT_IF(noexcept(_Iterator()))
184 : current()
185 { }
186
187 /**
188 * This %iterator will move in the opposite direction that @p x does.
189 */
190 explicit _GLIBCXX17_CONSTEXPR
191 reverse_iterator(iterator_type __x)
192 _GLIBCXX_NOEXCEPT_IF(noexcept(_Iterator(__x)))
193 : current(__x)
194 { }
195
196 /**
197 * The copy constructor is normal.
198 */
199 _GLIBCXX17_CONSTEXPR
200 reverse_iterator(const reverse_iterator& __x)
201 _GLIBCXX_NOEXCEPT_IF(noexcept(_Iterator(__x.current)))
202 : current(__x.current)
203 { }
204
205#if __cplusplus >= 201103L
206 reverse_iterator& operator=(const reverse_iterator&) = default;
207#endif
208
209 /**
210 * A %reverse_iterator across other types can be copied if the
211 * underlying %iterator can be converted to the type of @c current.
212 */
213 template<typename _Iter>
214#if __cpp_lib_concepts
215 requires __convertible<_Iter>
216#endif
217 _GLIBCXX17_CONSTEXPR
218 reverse_iterator(const reverse_iterator<_Iter>& __x)
219 _GLIBCXX_NOEXCEPT_IF(noexcept(_Iterator(__x.current)))
220 : current(__x.current)
221 { }
222
223#if __cplusplus >= 201103L
224 template<typename _Iter>
225#if __cpp_lib_concepts
226 requires __convertible<_Iter>
227 && assignable_from<_Iterator&, const _Iter&>
228#endif
229 _GLIBCXX17_CONSTEXPR
230 reverse_iterator&
231 operator=(const reverse_iterator<_Iter>& __x)
232 _GLIBCXX_NOEXCEPT_IF(noexcept(current = __x.current))
233 {
234 current = __x.current;
235 return *this;
236 }
237#endif
238
239 /**
240 * @return @c current, the %iterator used for underlying work.
241 */
242 _GLIBCXX_NODISCARD
243 _GLIBCXX17_CONSTEXPR iterator_type
244 base() const
245 _GLIBCXX_NOEXCEPT_IF(noexcept(_Iterator(current)))
246 { return current; }
247
248 /**
249 * @return A reference to the value at @c --current
250 *
251 * This requires that @c --current is dereferenceable.
252 *
253 * @warning This implementation requires that for an iterator of the
254 * underlying iterator type, @c x, a reference obtained by
255 * @c *x remains valid after @c x has been modified or
256 * destroyed. This is a bug: http://gcc.gnu.org/PR51823
257 */
258 _GLIBCXX_NODISCARD
259 _GLIBCXX17_CONSTEXPR reference
260 operator*() const
261 {
262 _Iterator __tmp = current;
263 return *--__tmp;
264 }
265
266 /**
267 * @return A pointer to the value at @c --current
268 *
269 * This requires that @c --current is dereferenceable.
270 */
271 _GLIBCXX_NODISCARD
272 _GLIBCXX17_CONSTEXPR pointer
273 operator->() const
274#if __cplusplus > 201703L && __cpp_concepts >= 201907L
275 requires is_pointer_v<_Iterator>
276 || requires(const _Iterator __i) { __i.operator->(); }
277#endif
278 {
279 // _GLIBCXX_RESOLVE_LIB_DEFECTS
280 // 1052. operator-> should also support smart pointers
281 _Iterator __tmp = current;
282 --__tmp;
283 return _S_to_pointer(__tmp);
284 }
285
286 /**
287 * @return @c *this
288 *
289 * Decrements the underlying iterator.
290 */
291 _GLIBCXX17_CONSTEXPR reverse_iterator&
292 operator++()
293 {
294 --current;
295 return *this;
296 }
297
298 /**
299 * @return The original value of @c *this
300 *
301 * Decrements the underlying iterator.
302 */
303 _GLIBCXX17_CONSTEXPR reverse_iterator
304 operator++(int)
305 {
306 reverse_iterator __tmp = *this;
307 --current;
308 return __tmp;
309 }
310
311 /**
312 * @return @c *this
313 *
314 * Increments the underlying iterator.
315 */
316 _GLIBCXX17_CONSTEXPR reverse_iterator&
317 operator--()
318 {
319 ++current;
320 return *this;
321 }
322
323 /**
324 * @return A reverse_iterator with the previous value of @c *this
325 *
326 * Increments the underlying iterator.
327 */
328 _GLIBCXX17_CONSTEXPR reverse_iterator
329 operator--(int)
330 {
331 reverse_iterator __tmp = *this;
332 ++current;
333 return __tmp;
334 }
335
336 /**
337 * @return A reverse_iterator that refers to @c current - @a __n
338 *
339 * The underlying iterator must be a Random Access Iterator.
340 */
341 _GLIBCXX_NODISCARD
342 _GLIBCXX17_CONSTEXPR reverse_iterator
343 operator+(difference_type __n) const
344 { return reverse_iterator(current - __n); }
345
346 /**
347 * @return *this
348 *
349 * Moves the underlying iterator backwards @a __n steps.
350 * The underlying iterator must be a Random Access Iterator.
351 */
352 _GLIBCXX17_CONSTEXPR reverse_iterator&
353 operator+=(difference_type __n)
354 {
355 current -= __n;
356 return *this;
357 }
358
359 /**
360 * @return A reverse_iterator that refers to @c current - @a __n
361 *
362 * The underlying iterator must be a Random Access Iterator.
363 */
364 _GLIBCXX_NODISCARD
365 _GLIBCXX17_CONSTEXPR reverse_iterator
366 operator-(difference_type __n) const
367 { return reverse_iterator(current + __n); }
368
369 /**
370 * @return *this
371 *
372 * Moves the underlying iterator forwards @a __n steps.
373 * The underlying iterator must be a Random Access Iterator.
374 */
375 _GLIBCXX17_CONSTEXPR reverse_iterator&
376 operator-=(difference_type __n)
377 {
378 current += __n;
379 return *this;
380 }
381
382 /**
383 * @return The value at @c current - @a __n - 1
384 *
385 * The underlying iterator must be a Random Access Iterator.
386 */
387 _GLIBCXX_NODISCARD
388 _GLIBCXX17_CONSTEXPR reference
389 operator[](difference_type __n) const
390 { return *(*this + __n); }
391
392#if __cplusplus > 201703L && __cpp_lib_concepts
393 [[nodiscard]]
394 friend constexpr iter_rvalue_reference_t<_Iterator>
395 iter_move(const reverse_iterator& __i)
396 noexcept(is_nothrow_copy_constructible_v<_Iterator>
397 && noexcept(ranges::iter_move(--std::declval<_Iterator&>())))
398 {
399 auto __tmp = __i.base();
400 return ranges::iter_move(--__tmp);
401 }
402
403 template<indirectly_swappable<_Iterator> _Iter2>
404 friend constexpr void
405 iter_swap(const reverse_iterator& __x,
406 const reverse_iterator<_Iter2>& __y)
407 noexcept(is_nothrow_copy_constructible_v<_Iterator>
408 && is_nothrow_copy_constructible_v<_Iter2>
409 && noexcept(ranges::iter_swap(--std::declval<_Iterator&>(),
410 --std::declval<_Iter2&>())))
411 {
412 auto __xtmp = __x.base();
413 auto __ytmp = __y.base();
414 ranges::iter_swap(--__xtmp, --__ytmp);
415 }
416#endif
417
418 private:
419 template<typename _Tp>
420 static _GLIBCXX17_CONSTEXPR _Tp*
421 _S_to_pointer(_Tp* __p)
422 { return __p; }
423
424 template<typename _Tp>
425 static _GLIBCXX17_CONSTEXPR pointer
426 _S_to_pointer(_Tp __t)
427 { return __t.operator->(); }
428 };
429
430 ///@{
431 /**
432 * @param __x A %reverse_iterator.
433 * @param __y A %reverse_iterator.
434 * @return A simple bool.
435 *
436 * Reverse iterators forward comparisons to their underlying base()
437 * iterators.
438 *
439 */
440#if __cplusplus <= 201703L || ! defined __cpp_lib_concepts
441 template<typename _Iterator>
442 _GLIBCXX_NODISCARD
443 inline _GLIBCXX17_CONSTEXPR bool
444 operator==(const reverse_iterator<_Iterator>& __x,
445 const reverse_iterator<_Iterator>& __y)
446 { return __x.base() == __y.base(); }
447
448 template<typename _Iterator>
449 _GLIBCXX_NODISCARD
450 inline _GLIBCXX17_CONSTEXPR bool
451 operator<(const reverse_iterator<_Iterator>& __x,
452 const reverse_iterator<_Iterator>& __y)
453 { return __y.base() < __x.base(); }
454
455 template<typename _Iterator>
456 _GLIBCXX_NODISCARD
457 inline _GLIBCXX17_CONSTEXPR bool
458 operator!=(const reverse_iterator<_Iterator>& __x,
459 const reverse_iterator<_Iterator>& __y)
460 { return !(__x == __y); }
461
462 template<typename _Iterator>
463 _GLIBCXX_NODISCARD
464 inline _GLIBCXX17_CONSTEXPR bool
465 operator>(const reverse_iterator<_Iterator>& __x,
466 const reverse_iterator<_Iterator>& __y)
467 { return __y < __x; }
468
469 template<typename _Iterator>
470 _GLIBCXX_NODISCARD
471 inline _GLIBCXX17_CONSTEXPR bool
472 operator<=(const reverse_iterator<_Iterator>& __x,
473 const reverse_iterator<_Iterator>& __y)
474 { return !(__y < __x); }
475
476 template<typename _Iterator>
477 _GLIBCXX_NODISCARD
478 inline _GLIBCXX17_CONSTEXPR bool
479 operator>=(const reverse_iterator<_Iterator>& __x,
480 const reverse_iterator<_Iterator>& __y)
481 { return !(__x < __y); }
482
483 // _GLIBCXX_RESOLVE_LIB_DEFECTS
484 // DR 280. Comparison of reverse_iterator to const reverse_iterator.
485
486 template<typename _IteratorL, typename _IteratorR>
487 _GLIBCXX_NODISCARD
488 inline _GLIBCXX17_CONSTEXPR bool
489 operator==(const reverse_iterator<_IteratorL>& __x,
490 const reverse_iterator<_IteratorR>& __y)
491 { return __x.base() == __y.base(); }
492
493 template<typename _IteratorL, typename _IteratorR>
494 _GLIBCXX_NODISCARD
495 inline _GLIBCXX17_CONSTEXPR bool
496 operator<(const reverse_iterator<_IteratorL>& __x,
497 const reverse_iterator<_IteratorR>& __y)
498 { return __x.base() > __y.base(); }
499
500 template<typename _IteratorL, typename _IteratorR>
501 _GLIBCXX_NODISCARD
502 inline _GLIBCXX17_CONSTEXPR bool
503 operator!=(const reverse_iterator<_IteratorL>& __x,
504 const reverse_iterator<_IteratorR>& __y)
505 { return __x.base() != __y.base(); }
506
507 template<typename _IteratorL, typename _IteratorR>
508 _GLIBCXX_NODISCARD
509 inline _GLIBCXX17_CONSTEXPR bool
510 operator>(const reverse_iterator<_IteratorL>& __x,
511 const reverse_iterator<_IteratorR>& __y)
512 { return __x.base() < __y.base(); }
513
514 template<typename _IteratorL, typename _IteratorR>
515 inline _GLIBCXX17_CONSTEXPR bool
516 operator<=(const reverse_iterator<_IteratorL>& __x,
517 const reverse_iterator<_IteratorR>& __y)
518 { return __x.base() >= __y.base(); }
519
520 template<typename _IteratorL, typename _IteratorR>
521 _GLIBCXX_NODISCARD
522 inline _GLIBCXX17_CONSTEXPR bool
523 operator>=(const reverse_iterator<_IteratorL>& __x,
524 const reverse_iterator<_IteratorR>& __y)
525 { return __x.base() <= __y.base(); }
526#else // C++20
527 template<typename _IteratorL, typename _IteratorR>
528 [[nodiscard]]
529 constexpr bool
530 operator==(const reverse_iterator<_IteratorL>& __x,
531 const reverse_iterator<_IteratorR>& __y)
532 requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
533 { return __x.base() == __y.base(); }
534
535 template<typename _IteratorL, typename _IteratorR>
536 [[nodiscard]]
537 constexpr bool
538 operator!=(const reverse_iterator<_IteratorL>& __x,
539 const reverse_iterator<_IteratorR>& __y)
540 requires requires { { __x.base() != __y.base() } -> convertible_to<bool>; }
541 { return __x.base() != __y.base(); }
542
543 template<typename _IteratorL, typename _IteratorR>
544 [[nodiscard]]
545 constexpr bool
546 operator<(const reverse_iterator<_IteratorL>& __x,
547 const reverse_iterator<_IteratorR>& __y)
548 requires requires { { __x.base() > __y.base() } -> convertible_to<bool>; }
549 { return __x.base() > __y.base(); }
550
551 template<typename _IteratorL, typename _IteratorR>
552 [[nodiscard]]
553 constexpr bool
554 operator>(const reverse_iterator<_IteratorL>& __x,
555 const reverse_iterator<_IteratorR>& __y)
556 requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
557 { return __x.base() < __y.base(); }
558
559 template<typename _IteratorL, typename _IteratorR>
560 [[nodiscard]]
561 constexpr bool
562 operator<=(const reverse_iterator<_IteratorL>& __x,
563 const reverse_iterator<_IteratorR>& __y)
564 requires requires { { __x.base() >= __y.base() } -> convertible_to<bool>; }
565 { return __x.base() >= __y.base(); }
566
567 template<typename _IteratorL, typename _IteratorR>
568 [[nodiscard]]
569 constexpr bool
570 operator>=(const reverse_iterator<_IteratorL>& __x,
571 const reverse_iterator<_IteratorR>& __y)
572 requires requires { { __x.base() <= __y.base() } -> convertible_to<bool>; }
573 { return __x.base() <= __y.base(); }
574
575 template<typename _IteratorL,
576 three_way_comparable_with<_IteratorL> _IteratorR>
577 [[nodiscard]]
578 constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
579 operator<=>(const reverse_iterator<_IteratorL>& __x,
580 const reverse_iterator<_IteratorR>& __y)
581 { return __y.base() <=> __x.base(); }
582
583 // Additional, non-standard overloads to avoid ambiguities with greedy,
584 // unconstrained overloads in associated namespaces.
585
586 template<typename _Iterator>
587 [[nodiscard]]
588 constexpr bool
589 operator==(const reverse_iterator<_Iterator>& __x,
590 const reverse_iterator<_Iterator>& __y)
591 requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
592 { return __x.base() == __y.base(); }
593
594 template<three_way_comparable _Iterator>
595 [[nodiscard]]
596 constexpr compare_three_way_result_t<_Iterator, _Iterator>
597 operator<=>(const reverse_iterator<_Iterator>& __x,
598 const reverse_iterator<_Iterator>& __y)
599 { return __y.base() <=> __x.base(); }
600#endif // C++20
601 ///@}
602
603#if __cplusplus < 201103L
604 template<typename _Iterator>
605 inline typename reverse_iterator<_Iterator>::difference_type
606 operator-(const reverse_iterator<_Iterator>& __x,
607 const reverse_iterator<_Iterator>& __y)
608 { return __y.base() - __x.base(); }
609
610 template<typename _IteratorL, typename _IteratorR>
611 inline typename reverse_iterator<_IteratorL>::difference_type
612 operator-(const reverse_iterator<_IteratorL>& __x,
613 const reverse_iterator<_IteratorR>& __y)
614 { return __y.base() - __x.base(); }
615#else
616 // _GLIBCXX_RESOLVE_LIB_DEFECTS
617 // DR 685. reverse_iterator/move_iterator difference has invalid signatures
618 template<typename _IteratorL, typename _IteratorR>
619 [[__nodiscard__]]
620 inline _GLIBCXX17_CONSTEXPR auto
621 operator-(const reverse_iterator<_IteratorL>& __x,
622 const reverse_iterator<_IteratorR>& __y)
623 -> decltype(__y.base() - __x.base())
624 { return __y.base() - __x.base(); }
625#endif
626
627 template<typename _Iterator>
628 _GLIBCXX_NODISCARD
629 inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
630 operator+(typename reverse_iterator<_Iterator>::difference_type __n,
631 const reverse_iterator<_Iterator>& __x)
632 { return reverse_iterator<_Iterator>(__x.base() - __n); }
633
634#if __cplusplus >= 201103L
635 // Same as C++14 make_reverse_iterator but used in C++11 mode too.
636 template<typename _Iterator>
637 inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
638 __make_reverse_iterator(_Iterator __i)
639 { return reverse_iterator<_Iterator>(__i); }
640
641# if __cplusplus >= 201402L
642# define __cpp_lib_make_reverse_iterator 201402L
643
644 // _GLIBCXX_RESOLVE_LIB_DEFECTS
645 // DR 2285. make_reverse_iterator
646 /// Generator function for reverse_iterator.
647 template<typename _Iterator>
648 [[__nodiscard__]]
649 inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
650 make_reverse_iterator(_Iterator __i)
651 { return reverse_iterator<_Iterator>(__i); }
652
653# if __cplusplus > 201703L && defined __cpp_lib_concepts
654 template<typename _Iterator1, typename _Iterator2>
655 requires (!sized_sentinel_for<_Iterator1, _Iterator2>)
656 inline constexpr bool
657 disable_sized_sentinel_for<reverse_iterator<_Iterator1>,
658 reverse_iterator<_Iterator2>> = true;
659# endif // C++20
660# endif // C++14
661
662 template<typename _Iterator>
663 _GLIBCXX20_CONSTEXPR
664 auto
665 __niter_base(reverse_iterator<_Iterator> __it)
666 -> decltype(__make_reverse_iterator(__niter_base(__it.base())))
667 { return __make_reverse_iterator(__niter_base(__it.base())); }
668
669 template<typename _Iterator>
670 struct __is_move_iterator<reverse_iterator<_Iterator> >
671 : __is_move_iterator<_Iterator>
672 { };
673
674 template<typename _Iterator>
675 _GLIBCXX20_CONSTEXPR
676 auto
677 __miter_base(reverse_iterator<_Iterator> __it)
678 -> decltype(__make_reverse_iterator(__miter_base(__it.base())))
679 { return __make_reverse_iterator(__miter_base(__it.base())); }
680#endif // C++11
681
682 // 24.4.2.2.1 back_insert_iterator
683 /**
684 * @brief Turns assignment into insertion.
685 *
686 * These are output iterators, constructed from a container-of-T.
687 * Assigning a T to the iterator appends it to the container using
688 * push_back.
689 *
690 * Tip: Using the back_inserter function to create these iterators can
691 * save typing.
692 */
693 template<typename _Container>
694 class back_insert_iterator
695 : public iterator<output_iterator_tag, void, void, void, void>
696 {
697 protected:
698 _Container* container;
699
700 public:
701 /// A nested typedef for the type of whatever container you used.
702 typedef _Container container_type;
703#if __cplusplus > 201703L
704 using difference_type = ptrdiff_t;
705#endif
706
707 /// The only way to create this %iterator is with a container.
708 explicit _GLIBCXX20_CONSTEXPR
709 back_insert_iterator(_Container& __x)
710 : container(std::__addressof(__x)) { }
711
712 /**
713 * @param __value An instance of whatever type
714 * container_type::const_reference is; presumably a
715 * reference-to-const T for container<T>.
716 * @return This %iterator, for chained operations.
717 *
718 * This kind of %iterator doesn't really have a @a position in the
719 * container (you can think of the position as being permanently at
720 * the end, if you like). Assigning a value to the %iterator will
721 * always append the value to the end of the container.
722 */
723#if __cplusplus < 201103L
724 back_insert_iterator&
725 operator=(typename _Container::const_reference __value)
726 {
727 container->push_back(__value);
728 return *this;
729 }
730#else
731 _GLIBCXX20_CONSTEXPR
732 back_insert_iterator&
733 operator=(const typename _Container::value_type& __value)
734 {
735 container->push_back(__value);
736 return *this;
737 }
738
739 _GLIBCXX20_CONSTEXPR
740 back_insert_iterator&
741 operator=(typename _Container::value_type&& __value)
742 {
743 container->push_back(std::move(__value));
744 return *this;
745 }
746#endif
747
748 /// Simply returns *this.
749 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
750 back_insert_iterator&
751 operator*()
752 { return *this; }
753
754 /// Simply returns *this. (This %iterator does not @a move.)
755 _GLIBCXX20_CONSTEXPR
756 back_insert_iterator&
757 operator++()
758 { return *this; }
759
760 /// Simply returns *this. (This %iterator does not @a move.)
761 _GLIBCXX20_CONSTEXPR
762 back_insert_iterator
763 operator++(int)
764 { return *this; }
765 };
766
767 /**
768 * @param __x A container of arbitrary type.
769 * @return An instance of back_insert_iterator working on @p __x.
770 *
771 * This wrapper function helps in creating back_insert_iterator instances.
772 * Typing the name of the %iterator requires knowing the precise full
773 * type of the container, which can be tedious and impedes generic
774 * programming. Using this function lets you take advantage of automatic
775 * template parameter deduction, making the compiler match the correct
776 * types for you.
777 */
778 template<typename _Container>
779 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
780 inline back_insert_iterator<_Container>
781 back_inserter(_Container& __x)
782 { return back_insert_iterator<_Container>(__x); }
783
784 /**
785 * @brief Turns assignment into insertion.
786 *
787 * These are output iterators, constructed from a container-of-T.
788 * Assigning a T to the iterator prepends it to the container using
789 * push_front.
790 *
791 * Tip: Using the front_inserter function to create these iterators can
792 * save typing.
793 */
794 template<typename _Container>
795 class front_insert_iterator
796 : public iterator<output_iterator_tag, void, void, void, void>
797 {
798 protected:
799 _Container* container;
800
801 public:
802 /// A nested typedef for the type of whatever container you used.
803 typedef _Container container_type;
804#if __cplusplus > 201703L
805 using difference_type = ptrdiff_t;
806#endif
807
808 /// The only way to create this %iterator is with a container.
809 explicit _GLIBCXX20_CONSTEXPR
810 front_insert_iterator(_Container& __x)
811 : container(std::__addressof(__x)) { }
812
813 /**
814 * @param __value An instance of whatever type
815 * container_type::const_reference is; presumably a
816 * reference-to-const T for container<T>.
817 * @return This %iterator, for chained operations.
818 *
819 * This kind of %iterator doesn't really have a @a position in the
820 * container (you can think of the position as being permanently at
821 * the front, if you like). Assigning a value to the %iterator will
822 * always prepend the value to the front of the container.
823 */
824#if __cplusplus < 201103L
825 front_insert_iterator&
826 operator=(typename _Container::const_reference __value)
827 {
828 container->push_front(__value);
829 return *this;
830 }
831#else
832 _GLIBCXX20_CONSTEXPR
833 front_insert_iterator&
834 operator=(const typename _Container::value_type& __value)
835 {
836 container->push_front(__value);
837 return *this;
838 }
839
840 _GLIBCXX20_CONSTEXPR
841 front_insert_iterator&
842 operator=(typename _Container::value_type&& __value)
843 {
844 container->push_front(std::move(__value));
845 return *this;
846 }
847#endif
848
849 /// Simply returns *this.
850 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
851 front_insert_iterator&
852 operator*()
853 { return *this; }
854
855 /// Simply returns *this. (This %iterator does not @a move.)
856 _GLIBCXX20_CONSTEXPR
857 front_insert_iterator&
858 operator++()
859 { return *this; }
860
861 /// Simply returns *this. (This %iterator does not @a move.)
862 _GLIBCXX20_CONSTEXPR
863 front_insert_iterator
864 operator++(int)
865 { return *this; }
866 };
867
868 /**
869 * @param __x A container of arbitrary type.
870 * @return An instance of front_insert_iterator working on @p x.
871 *
872 * This wrapper function helps in creating front_insert_iterator instances.
873 * Typing the name of the %iterator requires knowing the precise full
874 * type of the container, which can be tedious and impedes generic
875 * programming. Using this function lets you take advantage of automatic
876 * template parameter deduction, making the compiler match the correct
877 * types for you.
878 */
879 template<typename _Container>
880 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
881 inline front_insert_iterator<_Container>
882 front_inserter(_Container& __x)
883 { return front_insert_iterator<_Container>(__x); }
884
885 /**
886 * @brief Turns assignment into insertion.
887 *
888 * These are output iterators, constructed from a container-of-T.
889 * Assigning a T to the iterator inserts it in the container at the
890 * %iterator's position, rather than overwriting the value at that
891 * position.
892 *
893 * (Sequences will actually insert a @e copy of the value before the
894 * %iterator's position.)
895 *
896 * Tip: Using the inserter function to create these iterators can
897 * save typing.
898 */
899 template<typename _Container>
900 class insert_iterator
901 : public iterator<output_iterator_tag, void, void, void, void>
902 {
903#if __cplusplus > 201703L && defined __cpp_lib_concepts
904 using _Iter = std::__detail::__range_iter_t<_Container>;
905#else
906 typedef typename _Container::iterator _Iter;
907#endif
908 protected:
909 _Container* container;
910 _Iter iter;
911
912 public:
913 /// A nested typedef for the type of whatever container you used.
914 typedef _Container container_type;
915
916#if __cplusplus > 201703L && defined __cpp_lib_concepts
917 using difference_type = ptrdiff_t;
918#endif
919
920 /**
921 * The only way to create this %iterator is with a container and an
922 * initial position (a normal %iterator into the container).
923 */
924 _GLIBCXX20_CONSTEXPR
925 insert_iterator(_Container& __x, _Iter __i)
926 : container(std::__addressof(__x)), iter(__i) {}
927
928 /**
929 * @param __value An instance of whatever type
930 * container_type::const_reference is; presumably a
931 * reference-to-const T for container<T>.
932 * @return This %iterator, for chained operations.
933 *
934 * This kind of %iterator maintains its own position in the
935 * container. Assigning a value to the %iterator will insert the
936 * value into the container at the place before the %iterator.
937 *
938 * The position is maintained such that subsequent assignments will
939 * insert values immediately after one another. For example,
940 * @code
941 * // vector v contains A and Z
942 *
943 * insert_iterator i (v, ++v.begin());
944 * i = 1;
945 * i = 2;
946 * i = 3;
947 *
948 * // vector v contains A, 1, 2, 3, and Z
949 * @endcode
950 */
951#if __cplusplus < 201103L
952 insert_iterator&
953 operator=(typename _Container::const_reference __value)
954 {
955 iter = container->insert(iter, __value);
956 ++iter;
957 return *this;
958 }
959#else
960 _GLIBCXX20_CONSTEXPR
961 insert_iterator&
962 operator=(const typename _Container::value_type& __value)
963 {
964 iter = container->insert(iter, __value);
965 ++iter;
966 return *this;
967 }
968
969 _GLIBCXX20_CONSTEXPR
970 insert_iterator&
971 operator=(typename _Container::value_type&& __value)
972 {
973 iter = container->insert(iter, std::move(__value));
974 ++iter;
975 return *this;
976 }
977#endif
978
979 /// Simply returns *this.
980 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
981 insert_iterator&
982 operator*()
983 { return *this; }
984
985 /// Simply returns *this. (This %iterator does not @a move.)
986 _GLIBCXX20_CONSTEXPR
987 insert_iterator&
988 operator++()
989 { return *this; }
990
991 /// Simply returns *this. (This %iterator does not @a move.)
992 _GLIBCXX20_CONSTEXPR
993 insert_iterator&
994 operator++(int)
995 { return *this; }
996 };
997
998#pragma GCC diagnostic pop
999
1000 /**
1001 * @param __x A container of arbitrary type.
1002 * @param __i An iterator into the container.
1003 * @return An instance of insert_iterator working on @p __x.
1004 *
1005 * This wrapper function helps in creating insert_iterator instances.
1006 * Typing the name of the %iterator requires knowing the precise full
1007 * type of the container, which can be tedious and impedes generic
1008 * programming. Using this function lets you take advantage of automatic
1009 * template parameter deduction, making the compiler match the correct
1010 * types for you.
1011 */
1012#if __cplusplus > 201703L && defined __cpp_lib_concepts
1013 template<typename _Container>
1014 [[nodiscard]]
1015 constexpr insert_iterator<_Container>
1016 inserter(_Container& __x, std::__detail::__range_iter_t<_Container> __i)
1017 { return insert_iterator<_Container>(__x, __i); }
1018#else
1019 template<typename _Container>
1020 _GLIBCXX_NODISCARD
1021 inline insert_iterator<_Container>
1022 inserter(_Container& __x, typename _Container::iterator __i)
1023 { return insert_iterator<_Container>(__x, __i); }
1024#endif
1025
1026 /// @} group iterators
1027
1028_GLIBCXX_END_NAMESPACE_VERSION
1029} // namespace
1030
1031namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
1032{
1033_GLIBCXX_BEGIN_NAMESPACE_VERSION
1034
1035 // This iterator adapter is @a normal in the sense that it does not
1036 // change the semantics of any of the operators of its iterator
1037 // parameter. Its primary purpose is to convert an iterator that is
1038 // not a class, e.g. a pointer, into an iterator that is a class.
1039 // The _Container parameter exists solely so that different containers
1040 // using this template can instantiate different types, even if the
1041 // _Iterator parameter is the same.
1042 template<typename _Iterator, typename _Container>
1043 class __normal_iterator
1044 {
1045 protected:
1046 _Iterator _M_current;
1047
1048 typedef std::iterator_traits<_Iterator> __traits_type;
1049
1050#if __cplusplus >= 201103L
1051 template<typename _Iter>
1052 using __convertible_from
1053 = std::__enable_if_t<std::is_convertible<_Iter, _Iterator>::value>;
1054#endif
1055
1056 public:
1057 typedef _Iterator iterator_type;
1058 typedef typename __traits_type::iterator_category iterator_category;
1059 typedef typename __traits_type::value_type value_type;
1060 typedef typename __traits_type::difference_type difference_type;
1061 typedef typename __traits_type::reference reference;
1062 typedef typename __traits_type::pointer pointer;
1063
1064#if __cplusplus > 201703L && __cpp_lib_concepts
1065 using iterator_concept = std::__detail::__iter_concept<_Iterator>;
1066#endif
1067
1068 _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT
1069 : _M_current(_Iterator()) { }
1070
1071 explicit _GLIBCXX20_CONSTEXPR
1072 __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT
1073 : _M_current(__i) { }
1074
1075 // Allow iterator to const_iterator conversion
1076#if __cplusplus >= 201103L
1077 template<typename _Iter, typename = __convertible_from<_Iter>>
1078 _GLIBCXX20_CONSTEXPR
1079 __normal_iterator(const __normal_iterator<_Iter, _Container>& __i)
1080 noexcept
1081#else
1082 // N.B. _Container::pointer is not actually in container requirements,
1083 // but is present in std::vector and std::basic_string.
1084 template<typename _Iter>
1085 __normal_iterator(const __normal_iterator<_Iter,
1086 typename __enable_if<
1087 (std::__are_same<_Iter, typename _Container::pointer>::__value),
1088 _Container>::__type>& __i)
1089#endif
1090 : _M_current(__i.base()) { }
1091
1092 // Forward iterator requirements
1093 _GLIBCXX20_CONSTEXPR
1094 reference
1095 operator*() const _GLIBCXX_NOEXCEPT
1096 { return *_M_current; }
1097
1098 _GLIBCXX20_CONSTEXPR
1099 pointer
1100 operator->() const _GLIBCXX_NOEXCEPT
1101 { return _M_current; }
1102
1103 _GLIBCXX20_CONSTEXPR
1104 __normal_iterator&
1105 operator++() _GLIBCXX_NOEXCEPT
1106 {
1107 ++_M_current;
1108 return *this;
1109 }
1110
1111 _GLIBCXX20_CONSTEXPR
1112 __normal_iterator
1113 operator++(int) _GLIBCXX_NOEXCEPT
1114 { return __normal_iterator(_M_current++); }
1115
1116 // Bidirectional iterator requirements
1117 _GLIBCXX20_CONSTEXPR
1118 __normal_iterator&
1119 operator--() _GLIBCXX_NOEXCEPT
1120 {
1121 --_M_current;
1122 return *this;
1123 }
1124
1125 _GLIBCXX20_CONSTEXPR
1126 __normal_iterator
1127 operator--(int) _GLIBCXX_NOEXCEPT
1128 { return __normal_iterator(_M_current--); }
1129
1130 // Random access iterator requirements
1131 _GLIBCXX20_CONSTEXPR
1132 reference
1133 operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
1134 { return _M_current[__n]; }
1135
1136 _GLIBCXX20_CONSTEXPR
1137 __normal_iterator&
1138 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
1139 { _M_current += __n; return *this; }
1140
1141 _GLIBCXX20_CONSTEXPR
1142 __normal_iterator
1143 operator+(difference_type __n) const _GLIBCXX_NOEXCEPT
1144 { return __normal_iterator(_M_current + __n); }
1145
1146 _GLIBCXX20_CONSTEXPR
1147 __normal_iterator&
1148 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
1149 { _M_current -= __n; return *this; }
1150
1151 _GLIBCXX20_CONSTEXPR
1152 __normal_iterator
1153 operator-(difference_type __n) const _GLIBCXX_NOEXCEPT
1154 { return __normal_iterator(_M_current - __n); }
1155
1156 _GLIBCXX20_CONSTEXPR
1157 const _Iterator&
1158 base() const _GLIBCXX_NOEXCEPT
1159 { return _M_current; }
1160 };
1161
1162 // Note: In what follows, the left- and right-hand-side iterators are
1163 // allowed to vary in types (conceptually in cv-qualification) so that
1164 // comparison between cv-qualified and non-cv-qualified iterators be
1165 // valid. However, the greedy and unfriendly operators in std::rel_ops
1166 // will make overload resolution ambiguous (when in scope) if we don't
1167 // provide overloads whose operands are of the same type. Can someone
1168 // remind me what generic programming is about? -- Gaby
1169
1170#if __cpp_lib_three_way_comparison
1171 template<typename _IteratorL, typename _IteratorR, typename _Container>
1172 [[nodiscard]]
1173 constexpr bool
1174 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
1175 const __normal_iterator<_IteratorR, _Container>& __rhs)
1176 noexcept(noexcept(__lhs.base() == __rhs.base()))
1177 requires requires {
1178 { __lhs.base() == __rhs.base() } -> std::convertible_to<bool>;
1179 }
1180 { return __lhs.base() == __rhs.base(); }
1181
1182 template<typename _IteratorL, typename _IteratorR, typename _Container>
1183 [[nodiscard]]
1184 constexpr std::__detail::__synth3way_t<_IteratorR, _IteratorL>
1185 operator<=>(const __normal_iterator<_IteratorL, _Container>& __lhs,
1186 const __normal_iterator<_IteratorR, _Container>& __rhs)
1187 noexcept(noexcept(std::__detail::__synth3way(__lhs.base(), __rhs.base())))
1188 { return std::__detail::__synth3way(__lhs.base(), __rhs.base()); }
1189
1190 template<typename _Iterator, typename _Container>
1191 [[nodiscard]]
1192 constexpr bool
1193 operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
1194 const __normal_iterator<_Iterator, _Container>& __rhs)
1195 noexcept(noexcept(__lhs.base() == __rhs.base()))
1196 requires requires {
1197 { __lhs.base() == __rhs.base() } -> std::convertible_to<bool>;
1198 }
1199 { return __lhs.base() == __rhs.base(); }
1200
1201 template<typename _Iterator, typename _Container>
1202 [[nodiscard]]
1203 constexpr std::__detail::__synth3way_t<_Iterator>
1204 operator<=>(const __normal_iterator<_Iterator, _Container>& __lhs,
1205 const __normal_iterator<_Iterator, _Container>& __rhs)
1206 noexcept(noexcept(std::__detail::__synth3way(__lhs.base(), __rhs.base())))
1207 { return std::__detail::__synth3way(__lhs.base(), __rhs.base()); }
1208#else
1209 // Forward iterator requirements
1210 template<typename _IteratorL, typename _IteratorR, typename _Container>
1211 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1212 inline bool
1213 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
1214 const __normal_iterator<_IteratorR, _Container>& __rhs)
1215 _GLIBCXX_NOEXCEPT
1216 { return __lhs.base() == __rhs.base(); }
1217
1218 template<typename _Iterator, typename _Container>
1219 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1220 inline bool
1221 operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
1222 const __normal_iterator<_Iterator, _Container>& __rhs)
1223 _GLIBCXX_NOEXCEPT
1224 { return __lhs.base() == __rhs.base(); }
1225
1226 template<typename _IteratorL, typename _IteratorR, typename _Container>
1227 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1228 inline bool
1229 operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
1230 const __normal_iterator<_IteratorR, _Container>& __rhs)
1231 _GLIBCXX_NOEXCEPT
1232 { return __lhs.base() != __rhs.base(); }
1233
1234 template<typename _Iterator, typename _Container>
1235 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1236 inline bool
1237 operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
1238 const __normal_iterator<_Iterator, _Container>& __rhs)
1239 _GLIBCXX_NOEXCEPT
1240 { return __lhs.base() != __rhs.base(); }
1241
1242 // Random access iterator requirements
1243 template<typename _IteratorL, typename _IteratorR, typename _Container>
1244 _GLIBCXX_NODISCARD
1245 inline bool
1246 operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
1247 const __normal_iterator<_IteratorR, _Container>& __rhs)
1248 _GLIBCXX_NOEXCEPT
1249 { return __lhs.base() < __rhs.base(); }
1250
1251 template<typename _Iterator, typename _Container>
1252 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1253 inline bool
1254 operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
1255 const __normal_iterator<_Iterator, _Container>& __rhs)
1256 _GLIBCXX_NOEXCEPT
1257 { return __lhs.base() < __rhs.base(); }
1258
1259 template<typename _IteratorL, typename _IteratorR, typename _Container>
1260 _GLIBCXX_NODISCARD
1261 inline bool
1262 operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
1263 const __normal_iterator<_IteratorR, _Container>& __rhs)
1264 _GLIBCXX_NOEXCEPT
1265 { return __lhs.base() > __rhs.base(); }
1266
1267 template<typename _Iterator, typename _Container>
1268 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1269 inline bool
1270 operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
1271 const __normal_iterator<_Iterator, _Container>& __rhs)
1272 _GLIBCXX_NOEXCEPT
1273 { return __lhs.base() > __rhs.base(); }
1274
1275 template<typename _IteratorL, typename _IteratorR, typename _Container>
1276 _GLIBCXX_NODISCARD
1277 inline bool
1278 operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
1279 const __normal_iterator<_IteratorR, _Container>& __rhs)
1280 _GLIBCXX_NOEXCEPT
1281 { return __lhs.base() <= __rhs.base(); }
1282
1283 template<typename _Iterator, typename _Container>
1284 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1285 inline bool
1286 operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
1287 const __normal_iterator<_Iterator, _Container>& __rhs)
1288 _GLIBCXX_NOEXCEPT
1289 { return __lhs.base() <= __rhs.base(); }
1290
1291 template<typename _IteratorL, typename _IteratorR, typename _Container>
1292 _GLIBCXX_NODISCARD
1293 inline bool
1294 operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
1295 const __normal_iterator<_IteratorR, _Container>& __rhs)
1296 _GLIBCXX_NOEXCEPT
1297 { return __lhs.base() >= __rhs.base(); }
1298
1299 template<typename _Iterator, typename _Container>
1300 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1301 inline bool
1302 operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
1303 const __normal_iterator<_Iterator, _Container>& __rhs)
1304 _GLIBCXX_NOEXCEPT
1305 { return __lhs.base() >= __rhs.base(); }
1306#endif // three-way comparison
1307
1308 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1309 // According to the resolution of DR179 not only the various comparison
1310 // operators but also operator- must accept mixed iterator/const_iterator
1311 // parameters.
1312 template<typename _IteratorL, typename _IteratorR, typename _Container>
1313#if __cplusplus >= 201103L
1314 // DR 685.
1315 [[__nodiscard__]] _GLIBCXX20_CONSTEXPR
1316 inline auto
1317 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
1318 const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept
1319 -> decltype(__lhs.base() - __rhs.base())
1320#else
1321 inline typename __normal_iterator<_IteratorL, _Container>::difference_type
1322 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
1323 const __normal_iterator<_IteratorR, _Container>& __rhs)
1324#endif
1325 { return __lhs.base() - __rhs.base(); }
1326
1327 template<typename _Iterator, typename _Container>
1328 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1329 inline typename __normal_iterator<_Iterator, _Container>::difference_type
1330 operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
1331 const __normal_iterator<_Iterator, _Container>& __rhs)
1332 _GLIBCXX_NOEXCEPT
1333 { return __lhs.base() - __rhs.base(); }
1334
1335 template<typename _Iterator, typename _Container>
1336 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
1337 inline __normal_iterator<_Iterator, _Container>
1338 operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
1339 __n, const __normal_iterator<_Iterator, _Container>& __i)
1340 _GLIBCXX_NOEXCEPT
1341 { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
1342
1343_GLIBCXX_END_NAMESPACE_VERSION
1344} // namespace
1345
1346namespace std _GLIBCXX_VISIBILITY(default)
1347{
1348_GLIBCXX_BEGIN_NAMESPACE_VERSION
1349
1350 template<typename _Iterator, typename _Container>
1351 _GLIBCXX20_CONSTEXPR
1352 _Iterator
1353 __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
1354 _GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible<_Iterator>::value)
1355 { return __it.base(); }
1356
1357#if __cplusplus >= 201103L
1358
1359#if __cplusplus <= 201703L
1360 // Need to overload __to_address because the pointer_traits primary template
1361 // will deduce element_type of __normal_iterator<T*, C> as T* rather than T.
1362 template<typename _Iterator, typename _Container>
1363 constexpr auto
1364 __to_address(const __gnu_cxx::__normal_iterator<_Iterator,
1365 _Container>& __it) noexcept
1366 -> decltype(std::__to_address(__it.base()))
1367 { return std::__to_address(__it.base()); }
1368#endif
1369
1370 /**
1371 * @addtogroup iterators
1372 * @{
1373 */
1374
1375#if __cplusplus > 201703L && __cpp_lib_concepts
1376 template<semiregular _Sent>
1377 class move_sentinel
1378 {
1379 public:
1380 constexpr
1381 move_sentinel()
1382 noexcept(is_nothrow_default_constructible_v<_Sent>)
1383 : _M_last() { }
1384
1385 constexpr explicit
1386 move_sentinel(_Sent __s)
1387 noexcept(is_nothrow_move_constructible_v<_Sent>)
1388 : _M_last(std::move(__s)) { }
1389
1390 template<typename _S2> requires convertible_to<const _S2&, _Sent>
1391 constexpr
1392 move_sentinel(const move_sentinel<_S2>& __s)
1393 noexcept(is_nothrow_constructible_v<_Sent, const _S2&>)
1394 : _M_last(__s.base())
1395 { }
1396
1397 template<typename _S2> requires assignable_from<_Sent&, const _S2&>
1398 constexpr move_sentinel&
1399 operator=(const move_sentinel<_S2>& __s)
1400 noexcept(is_nothrow_assignable_v<_Sent, const _S2&>)
1401 {
1402 _M_last = __s.base();
1403 return *this;
1404 }
1405
1406 [[nodiscard]]
1407 constexpr _Sent
1408 base() const
1409 noexcept(is_nothrow_copy_constructible_v<_Sent>)
1410 { return _M_last; }
1411
1412 private:
1413 _Sent _M_last;
1414 };
1415#endif // C++20
1416
1417 namespace __detail
1418 {
1419#if __cplusplus > 201703L && __cpp_lib_concepts
1420 template<typename _Iterator>
1421 struct __move_iter_cat
1422 { };
1423
1424 template<typename _Iterator>
1425 requires requires { typename iterator_traits<_Iterator>::iterator_category; }
1426 struct __move_iter_cat<_Iterator>
1427 {
1428 using iterator_category
1429 = __clamp_iter_cat<typename iterator_traits<_Iterator>::iterator_category,
1430 random_access_iterator_tag>;
1431 };
1432#endif
1433 }
1434
1435 // 24.4.3 Move iterators
1436 /**
1437 * Class template move_iterator is an iterator adapter with the same
1438 * behavior as the underlying iterator except that its dereference
1439 * operator implicitly converts the value returned by the underlying
1440 * iterator's dereference operator to an rvalue reference. Some
1441 * generic algorithms can be called with move iterators to replace
1442 * copying with moving.
1443 */
1444 template<typename _Iterator>
1445 class move_iterator
1446#if __cplusplus > 201703L && __cpp_lib_concepts
1447 : public __detail::__move_iter_cat<_Iterator>
1448#endif
1449 {
1450 _Iterator _M_current;
1451
1452 using __traits_type = iterator_traits<_Iterator>;
1453#if ! (__cplusplus > 201703L && __cpp_lib_concepts)
1454 using __base_ref = typename __traits_type::reference;
1455#endif
1456
1457 template<typename _Iter2>
1458 friend class move_iterator;
1459
1460#if __cpp_lib_concepts
1461 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1462 // 3435. three_way_comparable_with<reverse_iterator<int*>, [...]>
1463 template<typename _Iter2>
1464 static constexpr bool __convertible = !is_same_v<_Iter2, _Iterator>
1465 && convertible_to<const _Iter2&, _Iterator>;
1466#endif
1467
1468#if __cplusplus > 201703L && __cpp_lib_concepts
1469 static auto
1470 _S_iter_concept()
1471 {
1472 if constexpr (random_access_iterator<_Iterator>)
1473 return random_access_iterator_tag{};
1474 else if constexpr (bidirectional_iterator<_Iterator>)
1475 return bidirectional_iterator_tag{};
1476 else if constexpr (forward_iterator<_Iterator>)
1477 return forward_iterator_tag{};
1478 else
1479 return input_iterator_tag{};
1480 }
1481#endif
1482
1483 public:
1484 using iterator_type = _Iterator;
1485
1486#if __cplusplus > 201703L && __cpp_lib_concepts
1487 // This is P2520R0, a C++23 change, but we treat it as a DR against C++20.
1488# define __cpp_lib_move_iterator_concept 202207L
1489 using iterator_concept = decltype(_S_iter_concept());
1490
1491 // iterator_category defined in __move_iter_cat
1492 using value_type = iter_value_t<_Iterator>;
1493 using difference_type = iter_difference_t<_Iterator>;
1494 using pointer = _Iterator;
1495 using reference = iter_rvalue_reference_t<_Iterator>;
1496#else
1497 typedef typename __traits_type::iterator_category iterator_category;
1498 typedef typename __traits_type::value_type value_type;
1499 typedef typename __traits_type::difference_type difference_type;
1500 // NB: DR 680.
1501 typedef _Iterator pointer;
1502 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1503 // 2106. move_iterator wrapping iterators returning prvalues
1504 using reference
1505 = __conditional_t<is_reference<__base_ref>::value,
1506 typename remove_reference<__base_ref>::type&&,
1507 __base_ref>;
1508#endif
1509
1510 _GLIBCXX17_CONSTEXPR
1511 move_iterator()
1512 : _M_current() { }
1513
1514 explicit _GLIBCXX17_CONSTEXPR
1515 move_iterator(iterator_type __i)
1516 : _M_current(std::move(__i)) { }
1517
1518 template<typename _Iter>
1519#if __cpp_lib_concepts
1520 requires __convertible<_Iter>
1521#endif
1522 _GLIBCXX17_CONSTEXPR
1523 move_iterator(const move_iterator<_Iter>& __i)
1524 : _M_current(__i._M_current) { }
1525
1526 template<typename _Iter>
1527#if __cpp_lib_concepts
1528 requires __convertible<_Iter>
1529 && assignable_from<_Iterator&, const _Iter&>
1530#endif
1531 _GLIBCXX17_CONSTEXPR
1532 move_iterator& operator=(const move_iterator<_Iter>& __i)
1533 {
1534 _M_current = __i._M_current;
1535 return *this;
1536 }
1537
1538#if __cplusplus <= 201703L
1539 [[__nodiscard__]]
1540 _GLIBCXX17_CONSTEXPR iterator_type
1541 base() const
1542 { return _M_current; }
1543#else
1544 [[nodiscard]]
1545 constexpr const iterator_type&
1546 base() const & noexcept
1547 { return _M_current; }
1548
1549 [[nodiscard]]
1550 constexpr iterator_type
1551 base() &&
1552 { return std::move(_M_current); }
1553#endif
1554
1555 [[__nodiscard__]]
1556 _GLIBCXX17_CONSTEXPR reference
1557 operator*() const
1558#if __cplusplus > 201703L && __cpp_lib_concepts
1559 { return ranges::iter_move(_M_current); }
1560#else
1561 { return static_cast<reference>(*_M_current); }
1562#endif
1563
1564 [[__nodiscard__]]
1565 _GLIBCXX17_CONSTEXPR pointer
1566 operator->() const
1567 { return _M_current; }
1568
1569 _GLIBCXX17_CONSTEXPR move_iterator&
1570 operator++()
1571 {
1572 ++_M_current;
1573 return *this;
1574 }
1575
1576 _GLIBCXX17_CONSTEXPR move_iterator
1577 operator++(int)
1578 {
1579 move_iterator __tmp = *this;
1580 ++_M_current;
1581 return __tmp;
1582 }
1583
1584#if __cpp_lib_concepts
1585 constexpr void
1586 operator++(int) requires (!forward_iterator<_Iterator>)
1587 { ++_M_current; }
1588#endif
1589
1590 _GLIBCXX17_CONSTEXPR move_iterator&
1591 operator--()
1592 {
1593 --_M_current;
1594 return *this;
1595 }
1596
1597 _GLIBCXX17_CONSTEXPR move_iterator
1598 operator--(int)
1599 {
1600 move_iterator __tmp = *this;
1601 --_M_current;
1602 return __tmp;
1603 }
1604
1605 [[__nodiscard__]]
1606 _GLIBCXX17_CONSTEXPR move_iterator
1607 operator+(difference_type __n) const
1608 { return move_iterator(_M_current + __n); }
1609
1610 _GLIBCXX17_CONSTEXPR move_iterator&
1611 operator+=(difference_type __n)
1612 {
1613 _M_current += __n;
1614 return *this;
1615 }
1616
1617 [[__nodiscard__]]
1618 _GLIBCXX17_CONSTEXPR move_iterator
1619 operator-(difference_type __n) const
1620 { return move_iterator(_M_current - __n); }
1621
1622 _GLIBCXX17_CONSTEXPR move_iterator&
1623 operator-=(difference_type __n)
1624 {
1625 _M_current -= __n;
1626 return *this;
1627 }
1628
1629 [[__nodiscard__]]
1630 _GLIBCXX17_CONSTEXPR reference
1631 operator[](difference_type __n) const
1632#if __cplusplus > 201703L && __cpp_lib_concepts
1633 { return ranges::iter_move(_M_current + __n); }
1634#else
1635 { return std::move(_M_current[__n]); }
1636#endif
1637
1638#if __cplusplus > 201703L && __cpp_lib_concepts
1639 template<sentinel_for<_Iterator> _Sent>
1640 [[nodiscard]]
1641 friend constexpr bool
1642 operator==(const move_iterator& __x, const move_sentinel<_Sent>& __y)
1643 { return __x.base() == __y.base(); }
1644
1645 template<sized_sentinel_for<_Iterator> _Sent>
1646 [[nodiscard]]
1647 friend constexpr iter_difference_t<_Iterator>
1648 operator-(const move_sentinel<_Sent>& __x, const move_iterator& __y)
1649 { return __x.base() - __y.base(); }
1650
1651 template<sized_sentinel_for<_Iterator> _Sent>
1652 [[nodiscard]]
1653 friend constexpr iter_difference_t<_Iterator>
1654 operator-(const move_iterator& __x, const move_sentinel<_Sent>& __y)
1655 { return __x.base() - __y.base(); }
1656
1657 [[nodiscard]]
1658 friend constexpr iter_rvalue_reference_t<_Iterator>
1659 iter_move(const move_iterator& __i)
1660 noexcept(noexcept(ranges::iter_move(__i._M_current)))
1661 { return ranges::iter_move(__i._M_current); }
1662
1663 template<indirectly_swappable<_Iterator> _Iter2>
1664 friend constexpr void
1665 iter_swap(const move_iterator& __x, const move_iterator<_Iter2>& __y)
1666 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1667 { return ranges::iter_swap(__x._M_current, __y._M_current); }
1668#endif // C++20
1669 };
1670
1671 template<typename _IteratorL, typename _IteratorR>
1672 [[__nodiscard__]]
1673 inline _GLIBCXX17_CONSTEXPR bool
1674 operator==(const move_iterator<_IteratorL>& __x,
1675 const move_iterator<_IteratorR>& __y)
1676#if __cplusplus > 201703L && __cpp_lib_concepts
1677 requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
1678#endif
1679 { return __x.base() == __y.base(); }
1680
1681#if __cpp_lib_three_way_comparison
1682 template<typename _IteratorL,
1683 three_way_comparable_with<_IteratorL> _IteratorR>
1684 [[__nodiscard__]]
1685 constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
1686 operator<=>(const move_iterator<_IteratorL>& __x,
1687 const move_iterator<_IteratorR>& __y)
1688 { return __x.base() <=> __y.base(); }
1689#else
1690 template<typename _IteratorL, typename _IteratorR>
1691 [[__nodiscard__]]
1692 inline _GLIBCXX17_CONSTEXPR bool
1693 operator!=(const move_iterator<_IteratorL>& __x,
1694 const move_iterator<_IteratorR>& __y)
1695 { return !(__x == __y); }
1696#endif
1697
1698 template<typename _IteratorL, typename _IteratorR>
1699 [[__nodiscard__]]
1700 inline _GLIBCXX17_CONSTEXPR bool
1701 operator<(const move_iterator<_IteratorL>& __x,
1702 const move_iterator<_IteratorR>& __y)
1703#if __cplusplus > 201703L && __cpp_lib_concepts
1704 requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1705#endif
1706 { return __x.base() < __y.base(); }
1707
1708 template<typename _IteratorL, typename _IteratorR>
1709 [[__nodiscard__]]
1710 inline _GLIBCXX17_CONSTEXPR bool
1711 operator<=(const move_iterator<_IteratorL>& __x,
1712 const move_iterator<_IteratorR>& __y)
1713#if __cplusplus > 201703L && __cpp_lib_concepts
1714 requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1715#endif
1716 { return !(__y < __x); }
1717
1718 template<typename _IteratorL, typename _IteratorR>
1719 [[__nodiscard__]]
1720 inline _GLIBCXX17_CONSTEXPR bool
1721 operator>(const move_iterator<_IteratorL>& __x,
1722 const move_iterator<_IteratorR>& __y)
1723#if __cplusplus > 201703L && __cpp_lib_concepts
1724 requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1725#endif
1726 { return __y < __x; }
1727
1728 template<typename _IteratorL, typename _IteratorR>
1729 [[__nodiscard__]]
1730 inline _GLIBCXX17_CONSTEXPR bool
1731 operator>=(const move_iterator<_IteratorL>& __x,
1732 const move_iterator<_IteratorR>& __y)
1733#if __cplusplus > 201703L && __cpp_lib_concepts
1734 requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1735#endif
1736 { return !(__x < __y); }
1737
1738 // Note: See __normal_iterator operators note from Gaby to understand
1739 // why we have these extra overloads for some move_iterator operators.
1740
1741 template<typename _Iterator>
1742 [[__nodiscard__]]
1743 inline _GLIBCXX17_CONSTEXPR bool
1744 operator==(const move_iterator<_Iterator>& __x,
1745 const move_iterator<_Iterator>& __y)
1746 { return __x.base() == __y.base(); }
1747
1748#if __cpp_lib_three_way_comparison
1749 template<three_way_comparable _Iterator>
1750 [[__nodiscard__]]
1751 constexpr compare_three_way_result_t<_Iterator>
1752 operator<=>(const move_iterator<_Iterator>& __x,
1753 const move_iterator<_Iterator>& __y)
1754 { return __x.base() <=> __y.base(); }
1755#else
1756 template<typename _Iterator>
1757 [[__nodiscard__]]
1758 inline _GLIBCXX17_CONSTEXPR bool
1759 operator!=(const move_iterator<_Iterator>& __x,
1760 const move_iterator<_Iterator>& __y)
1761 { return !(__x == __y); }
1762
1763 template<typename _Iterator>
1764 [[__nodiscard__]]
1765 inline _GLIBCXX17_CONSTEXPR bool
1766 operator<(const move_iterator<_Iterator>& __x,
1767 const move_iterator<_Iterator>& __y)
1768 { return __x.base() < __y.base(); }
1769
1770 template<typename _Iterator>
1771 [[__nodiscard__]]
1772 inline _GLIBCXX17_CONSTEXPR bool
1773 operator<=(const move_iterator<_Iterator>& __x,
1774 const move_iterator<_Iterator>& __y)
1775 { return !(__y < __x); }
1776
1777 template<typename _Iterator>
1778 [[__nodiscard__]]
1779 inline _GLIBCXX17_CONSTEXPR bool
1780 operator>(const move_iterator<_Iterator>& __x,
1781 const move_iterator<_Iterator>& __y)
1782 { return __y < __x; }
1783
1784 template<typename _Iterator>
1785 [[__nodiscard__]]
1786 inline _GLIBCXX17_CONSTEXPR bool
1787 operator>=(const move_iterator<_Iterator>& __x,
1788 const move_iterator<_Iterator>& __y)
1789 { return !(__x < __y); }
1790#endif // ! C++20
1791
1792 // DR 685.
1793 template<typename _IteratorL, typename _IteratorR>
1794 [[__nodiscard__]]
1795 inline _GLIBCXX17_CONSTEXPR auto
1796 operator-(const move_iterator<_IteratorL>& __x,
1797 const move_iterator<_IteratorR>& __y)
1798 -> decltype(__x.base() - __y.base())
1799 { return __x.base() - __y.base(); }
1800
1801 template<typename _Iterator>
1802 [[__nodiscard__]]
1803 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1804 operator+(typename move_iterator<_Iterator>::difference_type __n,
1805 const move_iterator<_Iterator>& __x)
1806 { return __x + __n; }
1807
1808 template<typename _Iterator>
1809 [[__nodiscard__]]
1810 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1811 make_move_iterator(_Iterator __i)
1812 { return move_iterator<_Iterator>(std::move(__i)); }
1813
1814 template<typename _Iterator, typename _ReturnType
1815 = __conditional_t<__move_if_noexcept_cond
1816 <typename iterator_traits<_Iterator>::value_type>::value,
1817 _Iterator, move_iterator<_Iterator>>>
1818 inline _GLIBCXX17_CONSTEXPR _ReturnType
1819 __make_move_if_noexcept_iterator(_Iterator __i)
1820 { return _ReturnType(__i); }
1821
1822 // Overload for pointers that matches std::move_if_noexcept more closely,
1823 // returning a constant iterator when we don't want to move.
1824 template<typename _Tp, typename _ReturnType
1825 = __conditional_t<__move_if_noexcept_cond<_Tp>::value,
1826 const _Tp*, move_iterator<_Tp*>>>
1827 inline _GLIBCXX17_CONSTEXPR _ReturnType
1828 __make_move_if_noexcept_iterator(_Tp* __i)
1829 { return _ReturnType(__i); }
1830
1831#if __cplusplus > 201703L && __cpp_lib_concepts
1832 // [iterators.common] Common iterators
1833
1834 namespace __detail
1835 {
1836 template<typename _It>
1837 concept __common_iter_has_arrow = indirectly_readable<const _It>
1838 && (requires(const _It& __it) { __it.operator->(); }
1839 || is_reference_v<iter_reference_t<_It>>
1840 || constructible_from<iter_value_t<_It>, iter_reference_t<_It>>);
1841
1842 template<typename _It>
1843 concept __common_iter_use_postfix_proxy
1844 = (!requires (_It& __i) { { *__i++ } -> __can_reference; })
1845 && constructible_from<iter_value_t<_It>, iter_reference_t<_It>>
1846 && move_constructible<iter_value_t<_It>>;
1847 } // namespace __detail
1848
1849 /// An iterator/sentinel adaptor for representing a non-common range.
1850 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1851 requires (!same_as<_It, _Sent>) && copyable<_It>
1852 class common_iterator
1853 {
1854 template<typename _Tp, typename _Up>
1855 static constexpr bool
1856 _S_noexcept1()
1857 {
1858 if constexpr (is_trivially_default_constructible_v<_Tp>)
1859 return is_nothrow_assignable_v<_Tp&, _Up>;
1860 else
1861 return is_nothrow_constructible_v<_Tp, _Up>;
1862 }
1863
1864 template<typename _It2, typename _Sent2>
1865 static constexpr bool
1866 _S_noexcept()
1867 { return _S_noexcept1<_It, _It2>() && _S_noexcept1<_Sent, _Sent2>(); }
1868
1869 class __arrow_proxy
1870 {
1871 iter_value_t<_It> _M_keep;
1872
1873 constexpr
1874 __arrow_proxy(iter_reference_t<_It>&& __x)
1875 : _M_keep(std::move(__x)) { }
1876
1877 friend class common_iterator;
1878
1879 public:
1880 constexpr const iter_value_t<_It>*
1881 operator->() const noexcept
1882 { return std::__addressof(_M_keep); }
1883 };
1884
1885 class __postfix_proxy
1886 {
1887 iter_value_t<_It> _M_keep;
1888
1889 constexpr
1890 __postfix_proxy(iter_reference_t<_It>&& __x)
1891 : _M_keep(std::forward<iter_reference_t<_It>>(__x)) { }
1892
1893 friend class common_iterator;
1894
1895 public:
1896 constexpr const iter_value_t<_It>&
1897 operator*() const noexcept
1898 { return _M_keep; }
1899 };
1900
1901 public:
1902 constexpr
1903 common_iterator()
1904 noexcept(is_nothrow_default_constructible_v<_It>)
1905 requires default_initializable<_It>
1906 : _M_it(), _M_index(0)
1907 { }
1908
1909 constexpr
1910 common_iterator(_It __i)
1911 noexcept(is_nothrow_move_constructible_v<_It>)
1912 : _M_it(std::move(__i)), _M_index(0)
1913 { }
1914
1915 constexpr
1916 common_iterator(_Sent __s)
1917 noexcept(is_nothrow_move_constructible_v<_Sent>)
1918 : _M_sent(std::move(__s)), _M_index(1)
1919 { }
1920
1921 template<typename _It2, typename _Sent2>
1922 requires convertible_to<const _It2&, _It>
1923 && convertible_to<const _Sent2&, _Sent>
1924 constexpr
1925 common_iterator(const common_iterator<_It2, _Sent2>& __x)
1926 noexcept(_S_noexcept<const _It2&, const _Sent2&>())
1927 : _M_valueless(), _M_index(__x._M_index)
1928 {
1929 __glibcxx_assert(__x._M_has_value());
1930 if (_M_index == 0)
1931 {
1932 if constexpr (is_trivially_default_constructible_v<_It>)
1933 _M_it = std::move(__x._M_it);
1934 else
1935 std::construct_at(std::__addressof(_M_it), __x._M_it);
1936 }
1937 else if (_M_index == 1)
1938 {
1939 if constexpr (is_trivially_default_constructible_v<_Sent>)
1940 _M_sent = std::move(__x._M_sent);
1941 else
1942 std::construct_at(std::__addressof(_M_sent), __x._M_sent);
1943 }
1944 }
1945
1946 constexpr
1947 common_iterator(const common_iterator& __x)
1948 noexcept(_S_noexcept<const _It&, const _Sent&>())
1949 : _M_valueless(), _M_index(__x._M_index)
1950 {
1951 if (_M_index == 0)
1952 {
1953 if constexpr (is_trivially_default_constructible_v<_It>)
1954 _M_it = __x._M_it;
1955 else
1956 std::construct_at(std::__addressof(_M_it), __x._M_it);
1957 }
1958 else if (_M_index == 1)
1959 {
1960 if constexpr (is_trivially_default_constructible_v<_Sent>)
1961 _M_sent = __x._M_sent;
1962 else
1963 std::construct_at(std::__addressof(_M_sent), __x._M_sent);
1964 }
1965 }
1966
1967 constexpr
1968 common_iterator(common_iterator&& __x)
1969 noexcept(_S_noexcept<_It, _Sent>())
1970 : _M_valueless(), _M_index(__x._M_index)
1971 {
1972 if (_M_index == 0)
1973 {
1974 if constexpr (is_trivially_default_constructible_v<_It>)
1975 _M_it = std::move(__x._M_it);
1976 else
1977 std::construct_at(std::__addressof(_M_it), std::move(__x._M_it));
1978 }
1979 else if (_M_index == 1)
1980 {
1981 if constexpr (is_trivially_default_constructible_v<_Sent>)
1982 _M_sent = std::move(__x._M_sent);
1983 else
1984 std::construct_at(std::__addressof(_M_sent),
1985 std::move(__x._M_sent));
1986 }
1987 }
1988
1989 constexpr common_iterator&
1990 operator=(const common_iterator&) = default;
1991
1992 constexpr common_iterator&
1993 operator=(const common_iterator& __x)
1994 noexcept(is_nothrow_copy_assignable_v<_It>
1995 && is_nothrow_copy_assignable_v<_Sent>
1996 && is_nothrow_copy_constructible_v<_It>
1997 && is_nothrow_copy_constructible_v<_Sent>)
1998 requires (!is_trivially_copy_assignable_v<_It>
1999 || !is_trivially_copy_assignable_v<_Sent>)
2000 {
2001 _M_assign(__x);
2002 return *this;
2003 }
2004
2005 constexpr common_iterator&
2006 operator=(common_iterator&&) = default;
2007
2008 constexpr common_iterator&
2009 operator=(common_iterator&& __x)
2010 noexcept(is_nothrow_move_assignable_v<_It>
2011 && is_nothrow_move_assignable_v<_Sent>
2012 && is_nothrow_move_constructible_v<_It>
2013 && is_nothrow_move_constructible_v<_Sent>)
2014 requires (!is_trivially_move_assignable_v<_It>
2015 || !is_trivially_move_assignable_v<_Sent>)
2016 {
2017 _M_assign(std::move(__x));
2018 return *this;
2019 }
2020
2021 template<typename _It2, typename _Sent2>
2022 requires convertible_to<const _It2&, _It>
2023 && convertible_to<const _Sent2&, _Sent>
2024 && assignable_from<_It&, const _It2&>
2025 && assignable_from<_Sent&, const _Sent2&>
2026 constexpr common_iterator&
2027 operator=(const common_iterator<_It2, _Sent2>& __x)
2028 noexcept(is_nothrow_constructible_v<_It, const _It2&>
2029 && is_nothrow_constructible_v<_Sent, const _Sent2&>
2030 && is_nothrow_assignable_v<_It&, const _It2&>
2031 && is_nothrow_assignable_v<_Sent&, const _Sent2&>)
2032 {
2033 __glibcxx_assert(__x._M_has_value());
2034 _M_assign(__x);
2035 return *this;
2036 }
2037
2038 constexpr
2039 ~common_iterator()
2040 {
2041 if (_M_index == 0)
2042 _M_it.~_It();
2043 else if (_M_index == 1)
2044 _M_sent.~_Sent();
2045 }
2046
2047 [[nodiscard]]
2048 constexpr decltype(auto)
2049 operator*()
2050 {
2051 __glibcxx_assert(_M_index == 0);
2052 return *_M_it;
2053 }
2054
2055 [[nodiscard]]
2056 constexpr decltype(auto)
2057 operator*() const requires __detail::__dereferenceable<const _It>
2058 {
2059 __glibcxx_assert(_M_index == 0);
2060 return *_M_it;
2061 }
2062
2063 [[nodiscard]]
2064 constexpr auto
2065 operator->() const requires __detail::__common_iter_has_arrow<_It>
2066 {
2067 __glibcxx_assert(_M_index == 0);
2068 if constexpr (is_pointer_v<_It> || requires { _M_it.operator->(); })
2069 return _M_it;
2070 else if constexpr (is_reference_v<iter_reference_t<_It>>)
2071 {
2072 auto&& __tmp = *_M_it;
2073 return std::__addressof(__tmp);
2074 }
2075 else
2076 return __arrow_proxy{*_M_it};
2077 }
2078
2079 constexpr common_iterator&
2080 operator++()
2081 {
2082 __glibcxx_assert(_M_index == 0);
2083 ++_M_it;
2084 return *this;
2085 }
2086
2087 constexpr decltype(auto)
2088 operator++(int)
2089 {
2090 __glibcxx_assert(_M_index == 0);
2091 if constexpr (forward_iterator<_It>)
2092 {
2093 common_iterator __tmp = *this;
2094 ++*this;
2095 return __tmp;
2096 }
2097 else if constexpr (!__detail::__common_iter_use_postfix_proxy<_It>)
2098 return _M_it++;
2099 else
2100 {
2101 __postfix_proxy __p(**this);
2102 ++*this;
2103 return __p;
2104 }
2105 }
2106
2107 template<typename _It2, sentinel_for<_It> _Sent2>
2108 requires sentinel_for<_Sent, _It2>
2109 friend constexpr bool
2110 operator== [[nodiscard]] (const common_iterator& __x,
2111 const common_iterator<_It2, _Sent2>& __y)
2112 {
2113 switch(__x._M_index << 2 | __y._M_index)
2114 {
2115 case 0b0000:
2116 case 0b0101:
2117 return true;
2118 case 0b0001:
2119 return __x._M_it == __y._M_sent;
2120 case 0b0100:
2121 return __x._M_sent == __y._M_it;
2122 default:
2123 __glibcxx_assert(__x._M_has_value());
2124 __glibcxx_assert(__y._M_has_value());
2125 __builtin_unreachable();
2126 }
2127 }
2128
2129 template<typename _It2, sentinel_for<_It> _Sent2>
2130 requires sentinel_for<_Sent, _It2> && equality_comparable_with<_It, _It2>
2131 friend constexpr bool
2132 operator== [[nodiscard]] (const common_iterator& __x,
2133 const common_iterator<_It2, _Sent2>& __y)
2134 {
2135 switch(__x._M_index << 2 | __y._M_index)
2136 {
2137 case 0b0101:
2138 return true;
2139 case 0b0000:
2140 return __x._M_it == __y._M_it;
2141 case 0b0001:
2142 return __x._M_it == __y._M_sent;
2143 case 0b0100:
2144 return __x._M_sent == __y._M_it;
2145 default:
2146 __glibcxx_assert(__x._M_has_value());
2147 __glibcxx_assert(__y._M_has_value());
2148 __builtin_unreachable();
2149 }
2150 }
2151
2152 template<sized_sentinel_for<_It> _It2, sized_sentinel_for<_It> _Sent2>
2153 requires sized_sentinel_for<_Sent, _It2>
2154 friend constexpr iter_difference_t<_It2>
2155 operator- [[nodiscard]] (const common_iterator& __x,
2156 const common_iterator<_It2, _Sent2>& __y)
2157 {
2158 switch(__x._M_index << 2 | __y._M_index)
2159 {
2160 case 0b0101:
2161 return 0;
2162 case 0b0000:
2163 return __x._M_it - __y._M_it;
2164 case 0b0001:
2165 return __x._M_it - __y._M_sent;
2166 case 0b0100:
2167 return __x._M_sent - __y._M_it;
2168 default:
2169 __glibcxx_assert(__x._M_has_value());
2170 __glibcxx_assert(__y._M_has_value());
2171 __builtin_unreachable();
2172 }
2173 }
2174
2175 [[nodiscard]]
2176 friend constexpr iter_rvalue_reference_t<_It>
2177 iter_move(const common_iterator& __i)
2178 noexcept(noexcept(ranges::iter_move(std::declval<const _It&>())))
2179 requires input_iterator<_It>
2180 {
2181 __glibcxx_assert(__i._M_index == 0);
2182 return ranges::iter_move(__i._M_it);
2183 }
2184
2185 template<indirectly_swappable<_It> _It2, typename _Sent2>
2186 friend constexpr void
2187 iter_swap(const common_iterator& __x,
2188 const common_iterator<_It2, _Sent2>& __y)
2189 noexcept(noexcept(ranges::iter_swap(std::declval<const _It&>(),
2190 std::declval<const _It2&>())))
2191 {
2192 __glibcxx_assert(__x._M_index == 0);
2193 __glibcxx_assert(__y._M_index == 0);
2194 return ranges::iter_swap(__x._M_it, __y._M_it);
2195 }
2196
2197 private:
2198 template<input_or_output_iterator _It2, sentinel_for<_It2> _Sent2>
2199 requires (!same_as<_It2, _Sent2>) && copyable<_It2>
2200 friend class common_iterator;
2201
2202 constexpr bool
2203 _M_has_value() const noexcept { return _M_index != _S_valueless; }
2204
2205 template<typename _CIt>
2206 constexpr void
2207 _M_assign(_CIt&& __x)
2208 {
2209 if (_M_index == __x._M_index)
2210 {
2211 if (_M_index == 0)
2212 _M_it = std::forward<_CIt>(__x)._M_it;
2213 else if (_M_index == 1)
2214 _M_sent = std::forward<_CIt>(__x)._M_sent;
2215 }
2216 else
2217 {
2218 if (_M_index == 0)
2219 _M_it.~_It();
2220 else if (_M_index == 1)
2221 _M_sent.~_Sent();
2222 _M_index = _S_valueless;
2223
2224 if (__x._M_index == 0)
2225 std::construct_at(std::__addressof(_M_it),
2226 std::forward<_CIt>(__x)._M_it);
2227 else if (__x._M_index == 1)
2228 std::construct_at(std::__addressof(_M_sent),
2229 std::forward<_CIt>(__x)._M_sent);
2230 _M_index = __x._M_index;
2231 }
2232 }
2233
2234 union
2235 {
2236 _It _M_it;
2237 _Sent _M_sent;
2238 unsigned char _M_valueless;
2239 };
2240 unsigned char _M_index; // 0 == _M_it, 1 == _M_sent, 2 == valueless
2241
2242 static constexpr unsigned char _S_valueless{2};
2243 };
2244
2245 template<typename _It, typename _Sent>
2246 struct incrementable_traits<common_iterator<_It, _Sent>>
2247 {
2248 using difference_type = iter_difference_t<_It>;
2249 };
2250
2251 template<input_iterator _It, typename _Sent>
2252 struct iterator_traits<common_iterator<_It, _Sent>>
2253 {
2254 private:
2255 template<typename _Iter>
2256 struct __ptr
2257 {
2258 using type = void;
2259 };
2260
2261 template<typename _Iter>
2262 requires __detail::__common_iter_has_arrow<_Iter>
2263 struct __ptr<_Iter>
2264 {
2265 using _CIter = common_iterator<_Iter, _Sent>;
2266 using type = decltype(std::declval<const _CIter&>().operator->());
2267 };
2268
2269 static auto
2270 _S_iter_cat()
2271 {
2272 using _Traits = iterator_traits<_It>;
2273 if constexpr (requires { requires derived_from<typename _Traits::iterator_category,
2274 forward_iterator_tag>; })
2275 return forward_iterator_tag{};
2276 else
2277 return input_iterator_tag{};
2278 }
2279
2280 public:
2281 using iterator_concept = __conditional_t<forward_iterator<_It>,
2282 forward_iterator_tag,
2283 input_iterator_tag>;
2284 using iterator_category = decltype(_S_iter_cat());
2285 using value_type = iter_value_t<_It>;
2286 using difference_type = iter_difference_t<_It>;
2287 using pointer = typename __ptr<_It>::type;
2288 using reference = iter_reference_t<_It>;
2289 };
2290
2291 // [iterators.counted] Counted iterators
2292
2293 namespace __detail
2294 {
2295 template<typename _It>
2296 struct __counted_iter_value_type
2297 { };
2298
2299 template<indirectly_readable _It>
2300 struct __counted_iter_value_type<_It>
2301 { using value_type = iter_value_t<_It>; };
2302
2303 template<typename _It>
2304 struct __counted_iter_concept
2305 { };
2306
2307 template<typename _It>
2308 requires requires { typename _It::iterator_concept; }
2309 struct __counted_iter_concept<_It>
2310 { using iterator_concept = typename _It::iterator_concept; };
2311
2312 template<typename _It>
2313 struct __counted_iter_cat
2314 { };
2315
2316 template<typename _It>
2317 requires requires { typename _It::iterator_category; }
2318 struct __counted_iter_cat<_It>
2319 { using iterator_category = typename _It::iterator_category; };
2320 }
2321
2322 /// An iterator adaptor that keeps track of the distance to the end.
2323 template<input_or_output_iterator _It>
2324 class counted_iterator
2325 : public __detail::__counted_iter_value_type<_It>,
2326 public __detail::__counted_iter_concept<_It>,
2327 public __detail::__counted_iter_cat<_It>
2328 {
2329 public:
2330 using iterator_type = _It;
2331 // value_type defined in __counted_iter_value_type
2332 using difference_type = iter_difference_t<_It>;
2333 // iterator_concept defined in __counted_iter_concept
2334 // iterator_category defined in __counted_iter_cat
2335
2336 constexpr counted_iterator() requires default_initializable<_It> = default;
2337
2338 constexpr
2339 counted_iterator(_It __i, iter_difference_t<_It> __n)
2340 : _M_current(std::move(__i)), _M_length(__n)
2341 { __glibcxx_assert(__n >= 0); }
2342
2343 template<typename _It2>
2344 requires convertible_to<const _It2&, _It>
2345 constexpr
2346 counted_iterator(const counted_iterator<_It2>& __x)
2347 : _M_current(__x._M_current), _M_length(__x._M_length)
2348 { }
2349
2350 template<typename _It2>
2351 requires assignable_from<_It&, const _It2&>
2352 constexpr counted_iterator&
2353 operator=(const counted_iterator<_It2>& __x)
2354 {
2355 _M_current = __x._M_current;
2356 _M_length = __x._M_length;
2357 return *this;
2358 }
2359
2360 [[nodiscard]]
2361 constexpr const _It&
2362 base() const & noexcept
2363 { return _M_current; }
2364
2365 [[nodiscard]]
2366 constexpr _It
2367 base() &&
2368 noexcept(is_nothrow_move_constructible_v<_It>)
2369 { return std::move(_M_current); }
2370
2371 [[nodiscard]]
2372 constexpr iter_difference_t<_It>
2373 count() const noexcept { return _M_length; }
2374
2375 [[nodiscard]]
2376 constexpr decltype(auto)
2377 operator*()
2378 noexcept(noexcept(*_M_current))
2379 {
2380 __glibcxx_assert( _M_length > 0 );
2381 return *_M_current;
2382 }
2383
2384 [[nodiscard]]
2385 constexpr decltype(auto)
2386 operator*() const
2387 noexcept(noexcept(*_M_current))
2388 requires __detail::__dereferenceable<const _It>
2389 {
2390 __glibcxx_assert( _M_length > 0 );
2391 return *_M_current;
2392 }
2393
2394 [[nodiscard]]
2395 constexpr auto
2396 operator->() const noexcept
2397 requires contiguous_iterator<_It>
2398 { return std::to_address(_M_current); }
2399
2400 constexpr counted_iterator&
2401 operator++()
2402 {
2403 __glibcxx_assert(_M_length > 0);
2404 ++_M_current;
2405 --_M_length;
2406 return *this;
2407 }
2408
2409 constexpr decltype(auto)
2410 operator++(int)
2411 {
2412 __glibcxx_assert(_M_length > 0);
2413 --_M_length;
2414 __try
2415 {
2416 return _M_current++;
2417 } __catch(...) {
2418 ++_M_length;
2419 __throw_exception_again;
2420 }
2421 }
2422
2423 constexpr counted_iterator
2424 operator++(int) requires forward_iterator<_It>
2425 {
2426 auto __tmp = *this;
2427 ++*this;
2428 return __tmp;
2429 }
2430
2431 constexpr counted_iterator&
2432 operator--() requires bidirectional_iterator<_It>
2433 {
2434 --_M_current;
2435 ++_M_length;
2436 return *this;
2437 }
2438
2439 constexpr counted_iterator
2440 operator--(int) requires bidirectional_iterator<_It>
2441 {
2442 auto __tmp = *this;
2443 --*this;
2444 return __tmp;
2445 }
2446
2447 [[nodiscard]]
2448 constexpr counted_iterator
2449 operator+(iter_difference_t<_It> __n) const
2450 requires random_access_iterator<_It>
2451 { return counted_iterator(_M_current + __n, _M_length - __n); }
2452
2453 [[nodiscard]]
2454 friend constexpr counted_iterator
2455 operator+(iter_difference_t<_It> __n, const counted_iterator& __x)
2456 requires random_access_iterator<_It>
2457 { return __x + __n; }
2458
2459 constexpr counted_iterator&
2460 operator+=(iter_difference_t<_It> __n)
2461 requires random_access_iterator<_It>
2462 {
2463 __glibcxx_assert(__n <= _M_length);
2464 _M_current += __n;
2465 _M_length -= __n;
2466 return *this;
2467 }
2468
2469 [[nodiscard]]
2470 constexpr counted_iterator
2471 operator-(iter_difference_t<_It> __n) const
2472 requires random_access_iterator<_It>
2473 { return counted_iterator(_M_current - __n, _M_length + __n); }
2474
2475 template<common_with<_It> _It2>
2476 [[nodiscard]]
2477 friend constexpr iter_difference_t<_It2>
2478 operator-(const counted_iterator& __x,
2479 const counted_iterator<_It2>& __y)
2480 { return __y._M_length - __x._M_length; }
2481
2482 [[nodiscard]]
2483 friend constexpr iter_difference_t<_It>
2484 operator-(const counted_iterator& __x, default_sentinel_t)
2485 { return -__x._M_length; }
2486
2487 [[nodiscard]]
2488 friend constexpr iter_difference_t<_It>
2489 operator-(default_sentinel_t, const counted_iterator& __y)
2490 { return __y._M_length; }
2491
2492 constexpr counted_iterator&
2493 operator-=(iter_difference_t<_It> __n)
2494 requires random_access_iterator<_It>
2495 {
2496 __glibcxx_assert(-__n <= _M_length);
2497 _M_current -= __n;
2498 _M_length += __n;
2499 return *this;
2500 }
2501
2502 [[nodiscard]]
2503 constexpr decltype(auto)
2504 operator[](iter_difference_t<_It> __n) const
2505 noexcept(noexcept(_M_current[__n]))
2506 requires random_access_iterator<_It>
2507 {
2508 __glibcxx_assert(__n < _M_length);
2509 return _M_current[__n];
2510 }
2511
2512 template<common_with<_It> _It2>
2513 [[nodiscard]]
2514 friend constexpr bool
2515 operator==(const counted_iterator& __x,
2516 const counted_iterator<_It2>& __y)
2517 { return __x._M_length == __y._M_length; }
2518
2519 [[nodiscard]]
2520 friend constexpr bool
2521 operator==(const counted_iterator& __x, default_sentinel_t)
2522 { return __x._M_length == 0; }
2523
2524 template<common_with<_It> _It2>
2525 [[nodiscard]]
2526 friend constexpr strong_ordering
2527 operator<=>(const counted_iterator& __x,
2528 const counted_iterator<_It2>& __y)
2529 { return __y._M_length <=> __x._M_length; }
2530
2531 [[nodiscard]]
2532 friend constexpr iter_rvalue_reference_t<_It>
2533 iter_move(const counted_iterator& __i)
2534 noexcept(noexcept(ranges::iter_move(__i._M_current)))
2535 requires input_iterator<_It>
2536 {
2537 __glibcxx_assert( __i._M_length > 0 );
2538 return ranges::iter_move(__i._M_current);
2539 }
2540
2541 template<indirectly_swappable<_It> _It2>
2542 friend constexpr void
2543 iter_swap(const counted_iterator& __x,
2544 const counted_iterator<_It2>& __y)
2545 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
2546 {
2547 __glibcxx_assert( __x._M_length > 0 && __y._M_length > 0 );
2548 ranges::iter_swap(__x._M_current, __y._M_current);
2549 }
2550
2551 private:
2552 template<input_or_output_iterator _It2> friend class counted_iterator;
2553
2554 _It _M_current = _It();
2555 iter_difference_t<_It> _M_length = 0;
2556 };
2557
2558 template<input_iterator _It>
2559 requires same_as<__detail::__iter_traits<_It>, iterator_traits<_It>>
2560 struct iterator_traits<counted_iterator<_It>> : iterator_traits<_It>
2561 {
2562 using pointer = __conditional_t<contiguous_iterator<_It>,
2563 add_pointer_t<iter_reference_t<_It>>,
2564 void>;
2565 };
2566#endif // C++20
2567
2568 /// @} group iterators
2569
2570 template<typename _Iterator>
2571 _GLIBCXX20_CONSTEXPR
2572 auto
2573 __niter_base(move_iterator<_Iterator> __it)
2574 -> decltype(make_move_iterator(__niter_base(__it.base())))
2575 { return make_move_iterator(__niter_base(__it.base())); }
2576
2577 template<typename _Iterator>
2578 struct __is_move_iterator<move_iterator<_Iterator> >
2579 {
2580 enum { __value = 1 };
2581 typedef __true_type __type;
2582 };
2583
2584 template<typename _Iterator>
2585 _GLIBCXX20_CONSTEXPR
2586 auto
2587 __miter_base(move_iterator<_Iterator> __it)
2588 -> decltype(__miter_base(__it.base()))
2589 { return __miter_base(__it.base()); }
2590
2591#define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
2592#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
2593 std::__make_move_if_noexcept_iterator(_Iter)
2594#else
2595#define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
2596#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
2597#endif // C++11
2598
2599#if __cpp_deduction_guides >= 201606
2600 // These helper traits are used for deduction guides
2601 // of associative containers.
2602 template<typename _InputIterator>
2603 using __iter_key_t = remove_const_t<
2604 typename iterator_traits<_InputIterator>::value_type::first_type>;
2605
2606 template<typename _InputIterator>
2607 using __iter_val_t =
2608 typename iterator_traits<_InputIterator>::value_type::second_type;
2609
2610 template<typename _T1, typename _T2>
2611 struct pair;
2612
2613 template<typename _InputIterator>
2614 using __iter_to_alloc_t =
2615 pair<add_const_t<__iter_key_t<_InputIterator>>,
2616 __iter_val_t<_InputIterator>>;
2617#endif // __cpp_deduction_guides
2618
2619_GLIBCXX_END_NAMESPACE_VERSION
2620} // namespace
2621
2622#ifdef _GLIBCXX_DEBUG
2623# include <debug/stl_iterator.h>
2624#endif
2625
2626#endif
2627