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