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