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
63#include <bits/cpp_type_traits.h>
64#include <bits/stl_iterator_base_types.h>
65#include <ext/type_traits.h>
66#include <bits/move.h>
67#include <bits/ptr_traits.h>
68
69#if __cplusplus >= 201103L
70# include <type_traits>
71#endif
72
73#if __cplusplus > 201703L
74# define __cpp_lib_array_constexpr 201811L
75# define __cpp_lib_constexpr_iterator 201811L
76#elif __cplusplus == 201703L
77# define __cpp_lib_array_constexpr 201803L
78#endif
79
80#if __cplusplus >= 202002L
81# include <compare>
82# include <new>
83# include <bits/exception_defines.h>
84# include <bits/iterator_concepts.h>
85# include <bits/stl_construct.h>
86#endif
87
88namespace std _GLIBCXX_VISIBILITY(default)
89{
90_GLIBCXX_BEGIN_NAMESPACE_VERSION
91
92 /**
93 * @addtogroup iterators
94 * @{
95 */
96
97#if __cpp_lib_concepts
98 namespace __detail
99 {
100 // Weaken iterator_category _Cat to _Limit if it is derived from that,
101 // otherwise use _Otherwise.
102 template<typename _Cat, typename _Limit, typename _Otherwise = _Cat>
103 using __clamp_iter_cat
104 = conditional_t<derived_from<_Cat, _Limit>, _Limit, _Otherwise>;
105 }
106#endif
107
108 // 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>
128 class reverse_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
149 typedef iterator_traits<_Iterator> __traits_type;
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
159 = conditional_t<random_access_iterator<_Iterator>,
160 random_access_iterator_tag,
161 bidirectional_iterator_tag>;
162 using iterator_category
163 = __detail::__clamp_iter_cat<typename __traits_type::iterator_category,
164 random_access_iterator_tag>;
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
190 reverse_iterator(const reverse_iterator& __x)
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
206 reverse_iterator(const reverse_iterator<_Iter>& __x)
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
216 reverse_iterator&
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
254 operator->() const
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&
273 operator++()
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
285 operator++(int)
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&
298 operator--()
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
310 operator--(int)
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,
421 const reverse_iterator<_Iterator>& __y)
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>
604 make_reverse_iterator(_Iterator __i)
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>
648 class back_insert_iterator
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
680 back_insert_iterator&
681 operator=(typename _Container::const_reference __value)
682 {
683 container->push_back(__value);
684 return *this;
685 }
686#else
687 _GLIBCXX20_CONSTEXPR
688 back_insert_iterator&
689 operator=(const typename _Container::value_type& __value)
690 {
691 container->push_back(__value);
692 return *this;
693 }
694
695 _GLIBCXX20_CONSTEXPR
696 back_insert_iterator&
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
706 back_insert_iterator&
707 operator*()
708 { return *this; }
709
710 /// Simply returns *this. (This %iterator does not @a move.)
711 _GLIBCXX20_CONSTEXPR
712 back_insert_iterator&
713 operator++()
714 { return *this; }
715
716 /// Simply returns *this. (This %iterator does not @a move.)
717 _GLIBCXX20_CONSTEXPR
718 back_insert_iterator
719 operator++(int)
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>
751 class front_insert_iterator
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
783 front_insert_iterator&
784 operator=(typename _Container::const_reference __value)
785 {
786 container->push_front(__value);
787 return *this;
788 }
789#else
790 _GLIBCXX20_CONSTEXPR
791 front_insert_iterator&
792 operator=(const typename _Container::value_type& __value)
793 {
794 container->push_front(__value);
795 return *this;
796 }
797
798 _GLIBCXX20_CONSTEXPR
799 front_insert_iterator&
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
809 front_insert_iterator&
810 operator*()
811 { return *this; }
812
813 /// Simply returns *this. (This %iterator does not @a move.)
814 _GLIBCXX20_CONSTEXPR
815 front_insert_iterator&
816 operator++()
817 { return *this; }
818
819 /// Simply returns *this. (This %iterator does not @a move.)
820 _GLIBCXX20_CONSTEXPR
821 front_insert_iterator
822 operator++(int)
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>
858 class insert_iterator
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
917 insert_iterator&
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
926 insert_iterator&
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
935 insert_iterator&
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
946 insert_iterator&
947 operator*()
948 { return *this; }
949
950 /// Simply returns *this. (This %iterator does not @a move.)
951 _GLIBCXX20_CONSTEXPR
952 insert_iterator&
953 operator++()
954 { return *this; }
955
956 /// Simply returns *this. (This %iterator does not @a move.)
957 _GLIBCXX20_CONSTEXPR
958 insert_iterator&
959 operator++(int)
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)
1292 _GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible<_Iterator>::value)
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>
1370 class move_iterator
1371#if __cplusplus > 201703L && __cpp_lib_concepts
1372 : public __detail::__move_iter_cat<_Iterator>
1373#endif
1374 {
1375 _Iterator _M_current;
1376
1377 using __traits_type = iterator_traits<_Iterator>;
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#if __cplusplus > 201703L && __cpp_lib_concepts
1394 static auto
1395 _S_iter_concept()
1396 {
1397 if constexpr (random_access_iterator<_Iterator>)
1398 return random_access_iterator_tag{};
1399 else if constexpr (bidirectional_iterator<_Iterator>)
1400 return bidirectional_iterator_tag{};
1401 else if constexpr (forward_iterator<_Iterator>)
1402 return forward_iterator_tag{};
1403 else
1404 return input_iterator_tag{};
1405 }
1406#endif
1407
1408 public:
1409 using iterator_type = _Iterator;
1410
1411#if __cplusplus > 201703L && __cpp_lib_concepts
1412 // This is P2520R0, a C++23 change, but we treat it as a DR against C++20.
1413# define __cpp_lib_move_iterator_concept 202207L
1414 using iterator_concept = decltype(_S_iter_concept());
1415
1416 // iterator_category defined in __move_iter_cat
1417 using value_type = iter_value_t<_Iterator>;
1418 using difference_type = iter_difference_t<_Iterator>;
1419 using pointer = _Iterator;
1420 using reference = iter_rvalue_reference_t<_Iterator>;
1421#else
1422 typedef typename __traits_type::iterator_category iterator_category;
1423 typedef typename __traits_type::value_type value_type;
1424 typedef typename __traits_type::difference_type difference_type;
1425 // NB: DR 680.
1426 typedef _Iterator pointer;
1427 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1428 // 2106. move_iterator wrapping iterators returning prvalues
1429 typedef typename conditional<is_reference<__base_ref>::value,
1430 typename remove_reference<__base_ref>::type&&,
1431 __base_ref>::type reference;
1432#endif
1433
1434 _GLIBCXX17_CONSTEXPR
1435 move_iterator()
1436 : _M_current() { }
1437
1438 explicit _GLIBCXX17_CONSTEXPR
1439 move_iterator(iterator_type __i)
1440 : _M_current(std::move(__i)) { }
1441
1442 template<typename _Iter>
1443#if __cpp_lib_concepts
1444 requires __convertible<_Iter>
1445#endif
1446 _GLIBCXX17_CONSTEXPR
1447 move_iterator(const move_iterator<_Iter>& __i)
1448 : _M_current(__i._M_current) { }
1449
1450 template<typename _Iter>
1451#if __cpp_lib_concepts
1452 requires __convertible<_Iter>
1453 && assignable_from<_Iterator&, const _Iter&>
1454#endif
1455 _GLIBCXX17_CONSTEXPR
1456 move_iterator& operator=(const move_iterator<_Iter>& __i)
1457 {
1458 _M_current = __i._M_current;
1459 return *this;
1460 }
1461
1462#if __cplusplus <= 201703L
1463 _GLIBCXX17_CONSTEXPR iterator_type
1464 base() const
1465 { return _M_current; }
1466#else
1467 constexpr const iterator_type&
1468 base() const & noexcept
1469 { return _M_current; }
1470
1471 constexpr iterator_type
1472 base() &&
1473 { return std::move(_M_current); }
1474#endif
1475
1476 _GLIBCXX17_CONSTEXPR reference
1477 operator*() const
1478#if __cplusplus > 201703L && __cpp_lib_concepts
1479 { return ranges::iter_move(_M_current); }
1480#else
1481 { return static_cast<reference>(*_M_current); }
1482#endif
1483
1484 _GLIBCXX17_CONSTEXPR pointer
1485 operator->() const
1486 { return _M_current; }
1487
1488 _GLIBCXX17_CONSTEXPR move_iterator&
1489 operator++()
1490 {
1491 ++_M_current;
1492 return *this;
1493 }
1494
1495 _GLIBCXX17_CONSTEXPR move_iterator
1496 operator++(int)
1497 {
1498 move_iterator __tmp = *this;
1499 ++_M_current;
1500 return __tmp;
1501 }
1502
1503#if __cpp_lib_concepts
1504 constexpr void
1505 operator++(int) requires (!forward_iterator<_Iterator>)
1506 { ++_M_current; }
1507#endif
1508
1509 _GLIBCXX17_CONSTEXPR move_iterator&
1510 operator--()
1511 {
1512 --_M_current;
1513 return *this;
1514 }
1515
1516 _GLIBCXX17_CONSTEXPR move_iterator
1517 operator--(int)
1518 {
1519 move_iterator __tmp = *this;
1520 --_M_current;
1521 return __tmp;
1522 }
1523
1524 _GLIBCXX17_CONSTEXPR move_iterator
1525 operator+(difference_type __n) const
1526 { return move_iterator(_M_current + __n); }
1527
1528 _GLIBCXX17_CONSTEXPR move_iterator&
1529 operator+=(difference_type __n)
1530 {
1531 _M_current += __n;
1532 return *this;
1533 }
1534
1535 _GLIBCXX17_CONSTEXPR move_iterator
1536 operator-(difference_type __n) const
1537 { return move_iterator(_M_current - __n); }
1538
1539 _GLIBCXX17_CONSTEXPR move_iterator&
1540 operator-=(difference_type __n)
1541 {
1542 _M_current -= __n;
1543 return *this;
1544 }
1545
1546 _GLIBCXX17_CONSTEXPR reference
1547 operator[](difference_type __n) const
1548#if __cplusplus > 201703L && __cpp_lib_concepts
1549 { return ranges::iter_move(_M_current + __n); }
1550#else
1551 { return std::move(_M_current[__n]); }
1552#endif
1553
1554#if __cplusplus > 201703L && __cpp_lib_concepts
1555 template<sentinel_for<_Iterator> _Sent>
1556 friend constexpr bool
1557 operator==(const move_iterator& __x, const move_sentinel<_Sent>& __y)
1558 { return __x.base() == __y.base(); }
1559
1560 template<sized_sentinel_for<_Iterator> _Sent>
1561 friend constexpr iter_difference_t<_Iterator>
1562 operator-(const move_sentinel<_Sent>& __x, const move_iterator& __y)
1563 { return __x.base() - __y.base(); }
1564
1565 template<sized_sentinel_for<_Iterator> _Sent>
1566 friend constexpr iter_difference_t<_Iterator>
1567 operator-(const move_iterator& __x, const move_sentinel<_Sent>& __y)
1568 { return __x.base() - __y.base(); }
1569
1570 friend constexpr iter_rvalue_reference_t<_Iterator>
1571 iter_move(const move_iterator& __i)
1572 noexcept(noexcept(ranges::iter_move(__i._M_current)))
1573 { return ranges::iter_move(__i._M_current); }
1574
1575 template<indirectly_swappable<_Iterator> _Iter2>
1576 friend constexpr void
1577 iter_swap(const move_iterator& __x, const move_iterator<_Iter2>& __y)
1578 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1579 { return ranges::iter_swap(__x._M_current, __y._M_current); }
1580#endif // C++20
1581 };
1582
1583 template<typename _IteratorL, typename _IteratorR>
1584 inline _GLIBCXX17_CONSTEXPR bool
1585 operator==(const move_iterator<_IteratorL>& __x,
1586 const move_iterator<_IteratorR>& __y)
1587#if __cplusplus > 201703L && __cpp_lib_concepts
1588 requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
1589#endif
1590 { return __x.base() == __y.base(); }
1591
1592#if __cpp_lib_three_way_comparison
1593 template<typename _IteratorL,
1594 three_way_comparable_with<_IteratorL> _IteratorR>
1595 constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
1596 operator<=>(const move_iterator<_IteratorL>& __x,
1597 const move_iterator<_IteratorR>& __y)
1598 { return __x.base() <=> __y.base(); }
1599#else
1600 template<typename _IteratorL, typename _IteratorR>
1601 inline _GLIBCXX17_CONSTEXPR bool
1602 operator!=(const move_iterator<_IteratorL>& __x,
1603 const move_iterator<_IteratorR>& __y)
1604 { return !(__x == __y); }
1605#endif
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 { { __x.base() < __y.base() } -> convertible_to<bool>; }
1613#endif
1614 { return __x.base() < __y.base(); }
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 { { __y.base() < __x.base() } -> convertible_to<bool>; }
1622#endif
1623 { return !(__y < __x); }
1624
1625 template<typename _IteratorL, typename _IteratorR>
1626 inline _GLIBCXX17_CONSTEXPR bool
1627 operator>(const move_iterator<_IteratorL>& __x,
1628 const move_iterator<_IteratorR>& __y)
1629#if __cplusplus > 201703L && __cpp_lib_concepts
1630 requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1631#endif
1632 { return __y < __x; }
1633
1634 template<typename _IteratorL, typename _IteratorR>
1635 inline _GLIBCXX17_CONSTEXPR bool
1636 operator>=(const move_iterator<_IteratorL>& __x,
1637 const move_iterator<_IteratorR>& __y)
1638#if __cplusplus > 201703L && __cpp_lib_concepts
1639 requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1640#endif
1641 { return !(__x < __y); }
1642
1643 // Note: See __normal_iterator operators note from Gaby to understand
1644 // why we have these extra overloads for some move_iterator operators.
1645
1646 template<typename _Iterator>
1647 inline _GLIBCXX17_CONSTEXPR bool
1648 operator==(const move_iterator<_Iterator>& __x,
1649 const move_iterator<_Iterator>& __y)
1650 { return __x.base() == __y.base(); }
1651
1652#if __cpp_lib_three_way_comparison
1653 template<three_way_comparable _Iterator>
1654 constexpr compare_three_way_result_t<_Iterator>
1655 operator<=>(const move_iterator<_Iterator>& __x,
1656 const move_iterator<_Iterator>& __y)
1657 { return __x.base() <=> __y.base(); }
1658#else
1659 template<typename _Iterator>
1660 inline _GLIBCXX17_CONSTEXPR bool
1661 operator!=(const move_iterator<_Iterator>& __x,
1662 const move_iterator<_Iterator>& __y)
1663 { return !(__x == __y); }
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.base() < __y.base(); }
1670
1671 template<typename _Iterator>
1672 inline _GLIBCXX17_CONSTEXPR bool
1673 operator<=(const move_iterator<_Iterator>& __x,
1674 const move_iterator<_Iterator>& __y)
1675 { return !(__y < __x); }
1676
1677 template<typename _Iterator>
1678 inline _GLIBCXX17_CONSTEXPR bool
1679 operator>(const move_iterator<_Iterator>& __x,
1680 const move_iterator<_Iterator>& __y)
1681 { return __y < __x; }
1682
1683 template<typename _Iterator>
1684 inline _GLIBCXX17_CONSTEXPR bool
1685 operator>=(const move_iterator<_Iterator>& __x,
1686 const move_iterator<_Iterator>& __y)
1687 { return !(__x < __y); }
1688#endif // ! C++20
1689
1690 // DR 685.
1691 template<typename _IteratorL, typename _IteratorR>
1692 inline _GLIBCXX17_CONSTEXPR auto
1693 operator-(const move_iterator<_IteratorL>& __x,
1694 const move_iterator<_IteratorR>& __y)
1695 -> decltype(__x.base() - __y.base())
1696 { return __x.base() - __y.base(); }
1697
1698 template<typename _Iterator>
1699 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1700 operator+(typename move_iterator<_Iterator>::difference_type __n,
1701 const move_iterator<_Iterator>& __x)
1702 { return __x + __n; }
1703
1704 template<typename _Iterator>
1705 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1706 make_move_iterator(_Iterator __i)
1707 { return move_iterator<_Iterator>(std::move(__i)); }
1708
1709 template<typename _Iterator, typename _ReturnType
1710 = typename conditional<__move_if_noexcept_cond
1711 <typename iterator_traits<_Iterator>::value_type>::value,
1712 _Iterator, move_iterator<_Iterator>>::type>
1713 inline _GLIBCXX17_CONSTEXPR _ReturnType
1714 __make_move_if_noexcept_iterator(_Iterator __i)
1715 { return _ReturnType(__i); }
1716
1717 // Overload for pointers that matches std::move_if_noexcept more closely,
1718 // returning a constant iterator when we don't want to move.
1719 template<typename _Tp, typename _ReturnType
1720 = typename conditional<__move_if_noexcept_cond<_Tp>::value,
1721 const _Tp*, move_iterator<_Tp*>>::type>
1722 inline _GLIBCXX17_CONSTEXPR _ReturnType
1723 __make_move_if_noexcept_iterator(_Tp* __i)
1724 { return _ReturnType(__i); }
1725
1726#if __cplusplus > 201703L && __cpp_lib_concepts
1727 // [iterators.common] Common iterators
1728
1729 namespace __detail
1730 {
1731 template<typename _It>
1732 concept __common_iter_has_arrow = indirectly_readable<const _It>
1733 && (requires(const _It& __it) { __it.operator->(); }
1734 || is_reference_v<iter_reference_t<_It>>
1735 || constructible_from<iter_value_t<_It>, iter_reference_t<_It>>);
1736
1737 template<typename _It>
1738 concept __common_iter_use_postfix_proxy
1739 = (!requires (_It& __i) { { *__i++ } -> __can_reference; })
1740 && constructible_from<iter_value_t<_It>, iter_reference_t<_It>>
1741 && move_constructible<iter_value_t<_It>>;
1742 } // namespace __detail
1743
1744 /// An iterator/sentinel adaptor for representing a non-common range.
1745 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1746 requires (!same_as<_It, _Sent>) && copyable<_It>
1747 class common_iterator
1748 {
1749 template<typename _Tp, typename _Up>
1750 static constexpr bool
1751 _S_noexcept1()
1752 {
1753 if constexpr (is_trivially_default_constructible_v<_Tp>)
1754 return is_nothrow_assignable_v<_Tp&, _Up>;
1755 else
1756 return is_nothrow_constructible_v<_Tp, _Up>;
1757 }
1758
1759 template<typename _It2, typename _Sent2>
1760 static constexpr bool
1761 _S_noexcept()
1762 { return _S_noexcept1<_It, _It2>() && _S_noexcept1<_Sent, _Sent2>(); }
1763
1764 class __arrow_proxy
1765 {
1766 iter_value_t<_It> _M_keep;
1767
1768 constexpr
1769 __arrow_proxy(iter_reference_t<_It>&& __x)
1770 : _M_keep(std::move(__x)) { }
1771
1772 friend class common_iterator;
1773
1774 public:
1775 constexpr const iter_value_t<_It>*
1776 operator->() const noexcept
1777 { return std::__addressof(_M_keep); }
1778 };
1779
1780 class __postfix_proxy
1781 {
1782 iter_value_t<_It> _M_keep;
1783
1784 constexpr
1785 __postfix_proxy(iter_reference_t<_It>&& __x)
1786 : _M_keep(std::forward<iter_reference_t<_It>>(__x)) { }
1787
1788 friend class common_iterator;
1789
1790 public:
1791 constexpr const iter_value_t<_It>&
1792 operator*() const noexcept
1793 { return _M_keep; }
1794 };
1795
1796 public:
1797 constexpr
1798 common_iterator()
1799 noexcept(is_nothrow_default_constructible_v<_It>)
1800 requires default_initializable<_It>
1801 : _M_it(), _M_index(0)
1802 { }
1803
1804 constexpr
1805 common_iterator(_It __i)
1806 noexcept(is_nothrow_move_constructible_v<_It>)
1807 : _M_it(std::move(__i)), _M_index(0)
1808 { }
1809
1810 constexpr
1811 common_iterator(_Sent __s)
1812 noexcept(is_nothrow_move_constructible_v<_Sent>)
1813 : _M_sent(std::move(__s)), _M_index(1)
1814 { }
1815
1816 template<typename _It2, typename _Sent2>
1817 requires convertible_to<const _It2&, _It>
1818 && convertible_to<const _Sent2&, _Sent>
1819 constexpr
1820 common_iterator(const common_iterator<_It2, _Sent2>& __x)
1821 noexcept(_S_noexcept<const _It2&, const _Sent2&>())
1822 : _M_valueless(), _M_index(__x._M_index)
1823 {
1824 __glibcxx_assert(__x._M_has_value());
1825 if (_M_index == 0)
1826 {
1827 if constexpr (is_trivially_default_constructible_v<_It>)
1828 _M_it = std::move(__x._M_it);
1829 else
1830 std::construct_at(std::__addressof(_M_it), __x._M_it);
1831 }
1832 else if (_M_index == 1)
1833 {
1834 if constexpr (is_trivially_default_constructible_v<_Sent>)
1835 _M_sent = std::move(__x._M_sent);
1836 else
1837 std::construct_at(std::__addressof(_M_sent), __x._M_sent);
1838 }
1839 }
1840
1841 constexpr
1842 common_iterator(const common_iterator& __x)
1843 noexcept(_S_noexcept<const _It&, const _Sent&>())
1844 : _M_valueless(), _M_index(__x._M_index)
1845 {
1846 if (_M_index == 0)
1847 {
1848 if constexpr (is_trivially_default_constructible_v<_It>)
1849 _M_it = __x._M_it;
1850 else
1851 std::construct_at(std::__addressof(_M_it), __x._M_it);
1852 }
1853 else if (_M_index == 1)
1854 {
1855 if constexpr (is_trivially_default_constructible_v<_Sent>)
1856 _M_sent = __x._M_sent;
1857 else
1858 std::construct_at(std::__addressof(_M_sent), __x._M_sent);
1859 }
1860 }
1861
1862 constexpr
1863 common_iterator(common_iterator&& __x)
1864 noexcept(_S_noexcept<_It, _Sent>())
1865 : _M_valueless(), _M_index(__x._M_index)
1866 {
1867 if (_M_index == 0)
1868 {
1869 if constexpr (is_trivially_default_constructible_v<_It>)
1870 _M_it = std::move(__x._M_it);
1871 else
1872 std::construct_at(std::__addressof(_M_it), std::move(__x._M_it));
1873 }
1874 else if (_M_index == 1)
1875 {
1876 if constexpr (is_trivially_default_constructible_v<_Sent>)
1877 _M_sent = std::move(__x._M_sent);
1878 else
1879 std::construct_at(std::__addressof(_M_sent),
1880 std::move(__x._M_sent));
1881 }
1882 }
1883
1884 constexpr common_iterator&
1885 operator=(const common_iterator&) = default;
1886
1887 constexpr common_iterator&
1888 operator=(const common_iterator& __x)
1889 noexcept(is_nothrow_copy_assignable_v<_It>
1890 && is_nothrow_copy_assignable_v<_Sent>
1891 && is_nothrow_copy_constructible_v<_It>
1892 && is_nothrow_copy_constructible_v<_Sent>)
1893 requires (!is_trivially_copy_assignable_v<_It>
1894 || !is_trivially_copy_assignable_v<_Sent>)
1895 {
1896 _M_assign(__x);
1897 return *this;
1898 }
1899
1900 constexpr common_iterator&
1901 operator=(common_iterator&&) = default;
1902
1903 constexpr common_iterator&
1904 operator=(common_iterator&& __x)
1905 noexcept(is_nothrow_move_assignable_v<_It>
1906 && is_nothrow_move_assignable_v<_Sent>
1907 && is_nothrow_move_constructible_v<_It>
1908 && is_nothrow_move_constructible_v<_Sent>)
1909 requires (!is_trivially_move_assignable_v<_It>
1910 || !is_trivially_move_assignable_v<_Sent>)
1911 {
1912 _M_assign(std::move(__x));
1913 return *this;
1914 }
1915
1916 template<typename _It2, typename _Sent2>
1917 requires convertible_to<const _It2&, _It>
1918 && convertible_to<const _Sent2&, _Sent>
1919 && assignable_from<_It&, const _It2&>
1920 && assignable_from<_Sent&, const _Sent2&>
1921 constexpr common_iterator&
1922 operator=(const common_iterator<_It2, _Sent2>& __x)
1923 noexcept(is_nothrow_constructible_v<_It, const _It2&>
1924 && is_nothrow_constructible_v<_Sent, const _Sent2&>
1925 && is_nothrow_assignable_v<_It&, const _It2&>
1926 && is_nothrow_assignable_v<_Sent&, const _Sent2&>)
1927 {
1928 __glibcxx_assert(__x._M_has_value());
1929 _M_assign(__x);
1930 return *this;
1931 }
1932
1933 constexpr
1934 ~common_iterator()
1935 {
1936 if (_M_index == 0)
1937 _M_it.~_It();
1938 else if (_M_index == 1)
1939 _M_sent.~_Sent();
1940 }
1941
1942 [[nodiscard]]
1943 constexpr decltype(auto)
1944 operator*()
1945 {
1946 __glibcxx_assert(_M_index == 0);
1947 return *_M_it;
1948 }
1949
1950 [[nodiscard]]
1951 constexpr decltype(auto)
1952 operator*() const requires __detail::__dereferenceable<const _It>
1953 {
1954 __glibcxx_assert(_M_index == 0);
1955 return *_M_it;
1956 }
1957
1958 [[nodiscard]]
1959 constexpr auto
1960 operator->() const requires __detail::__common_iter_has_arrow<_It>
1961 {
1962 __glibcxx_assert(_M_index == 0);
1963 if constexpr (is_pointer_v<_It> || requires { _M_it.operator->(); })
1964 return _M_it;
1965 else if constexpr (is_reference_v<iter_reference_t<_It>>)
1966 {
1967 auto&& __tmp = *_M_it;
1968 return std::__addressof(__tmp);
1969 }
1970 else
1971 return __arrow_proxy{*_M_it};
1972 }
1973
1974 constexpr common_iterator&
1975 operator++()
1976 {
1977 __glibcxx_assert(_M_index == 0);
1978 ++_M_it;
1979 return *this;
1980 }
1981
1982 constexpr decltype(auto)
1983 operator++(int)
1984 {
1985 __glibcxx_assert(_M_index == 0);
1986 if constexpr (forward_iterator<_It>)
1987 {
1988 common_iterator __tmp = *this;
1989 ++*this;
1990 return __tmp;
1991 }
1992 else if constexpr (!__detail::__common_iter_use_postfix_proxy<_It>)
1993 return _M_it++;
1994 else
1995 {
1996 __postfix_proxy __p(**this);
1997 ++*this;
1998 return __p;
1999 }
2000 }
2001
2002 template<typename _It2, sentinel_for<_It> _Sent2>
2003 requires sentinel_for<_Sent, _It2>
2004 friend constexpr bool
2005 operator== [[nodiscard]] (const common_iterator& __x,
2006 const common_iterator<_It2, _Sent2>& __y)
2007 {
2008 switch(__x._M_index << 2 | __y._M_index)
2009 {
2010 case 0b0000:
2011 case 0b0101:
2012 return true;
2013 case 0b0001:
2014 return __x._M_it == __y._M_sent;
2015 case 0b0100:
2016 return __x._M_sent == __y._M_it;
2017 default:
2018 __glibcxx_assert(__x._M_has_value());
2019 __glibcxx_assert(__y._M_has_value());
2020 __builtin_unreachable();
2021 }
2022 }
2023
2024 template<typename _It2, sentinel_for<_It> _Sent2>
2025 requires sentinel_for<_Sent, _It2> && equality_comparable_with<_It, _It2>
2026 friend constexpr bool
2027 operator== [[nodiscard]] (const common_iterator& __x,
2028 const common_iterator<_It2, _Sent2>& __y)
2029 {
2030 switch(__x._M_index << 2 | __y._M_index)
2031 {
2032 case 0b0101:
2033 return true;
2034 case 0b0000:
2035 return __x._M_it == __y._M_it;
2036 case 0b0001:
2037 return __x._M_it == __y._M_sent;
2038 case 0b0100:
2039 return __x._M_sent == __y._M_it;
2040 default:
2041 __glibcxx_assert(__x._M_has_value());
2042 __glibcxx_assert(__y._M_has_value());
2043 __builtin_unreachable();
2044 }
2045 }
2046
2047 template<sized_sentinel_for<_It> _It2, sized_sentinel_for<_It> _Sent2>
2048 requires sized_sentinel_for<_Sent, _It2>
2049 friend constexpr iter_difference_t<_It2>
2050 operator- [[nodiscard]] (const common_iterator& __x,
2051 const common_iterator<_It2, _Sent2>& __y)
2052 {
2053 switch(__x._M_index << 2 | __y._M_index)
2054 {
2055 case 0b0101:
2056 return 0;
2057 case 0b0000:
2058 return __x._M_it - __y._M_it;
2059 case 0b0001:
2060 return __x._M_it - __y._M_sent;
2061 case 0b0100:
2062 return __x._M_sent - __y._M_it;
2063 default:
2064 __glibcxx_assert(__x._M_has_value());
2065 __glibcxx_assert(__y._M_has_value());
2066 __builtin_unreachable();
2067 }
2068 }
2069
2070 [[nodiscard]]
2071 friend constexpr iter_rvalue_reference_t<_It>
2072 iter_move(const common_iterator& __i)
2073 noexcept(noexcept(ranges::iter_move(std::declval<const _It&>())))
2074 requires input_iterator<_It>
2075 {
2076 __glibcxx_assert(__i._M_index == 0);
2077 return ranges::iter_move(__i._M_it);
2078 }
2079
2080 template<indirectly_swappable<_It> _It2, typename _Sent2>
2081 friend constexpr void
2082 iter_swap(const common_iterator& __x,
2083 const common_iterator<_It2, _Sent2>& __y)
2084 noexcept(noexcept(ranges::iter_swap(std::declval<const _It&>(),
2085 std::declval<const _It2&>())))
2086 {
2087 __glibcxx_assert(__x._M_index == 0);
2088 __glibcxx_assert(__y._M_index == 0);
2089 return ranges::iter_swap(__x._M_it, __y._M_it);
2090 }
2091
2092 private:
2093 template<input_or_output_iterator _It2, sentinel_for<_It2> _Sent2>
2094 requires (!same_as<_It2, _Sent2>) && copyable<_It2>
2095 friend class common_iterator;
2096
2097 constexpr bool
2098 _M_has_value() const noexcept { return _M_index != _S_valueless; }
2099
2100 template<typename _CIt>
2101 constexpr void
2102 _M_assign(_CIt&& __x)
2103 {
2104 if (_M_index == __x._M_index)
2105 {
2106 if (_M_index == 0)
2107 _M_it = std::forward<_CIt>(__x)._M_it;
2108 else if (_M_index == 1)
2109 _M_sent = std::forward<_CIt>(__x)._M_sent;
2110 }
2111 else
2112 {
2113 if (_M_index == 0)
2114 _M_it.~_It();
2115 else if (_M_index == 1)
2116 _M_sent.~_Sent();
2117 _M_index = _S_valueless;
2118
2119 if (__x._M_index == 0)
2120 std::construct_at(std::__addressof(_M_it),
2121 std::forward<_CIt>(__x)._M_it);
2122 else if (__x._M_index == 1)
2123 std::construct_at(std::__addressof(_M_sent),
2124 std::forward<_CIt>(__x)._M_sent);
2125 _M_index = __x._M_index;
2126 }
2127 }
2128
2129 union
2130 {
2131 _It _M_it;
2132 _Sent _M_sent;
2133 unsigned char _M_valueless;
2134 };
2135 unsigned char _M_index; // 0 == _M_it, 1 == _M_sent, 2 == valueless
2136
2137 static constexpr unsigned char _S_valueless{2};
2138 };
2139
2140 template<typename _It, typename _Sent>
2141 struct incrementable_traits<common_iterator<_It, _Sent>>
2142 {
2143 using difference_type = iter_difference_t<_It>;
2144 };
2145
2146 template<input_iterator _It, typename _Sent>
2147 struct iterator_traits<common_iterator<_It, _Sent>>
2148 {
2149 private:
2150 template<typename _Iter>
2151 struct __ptr
2152 {
2153 using type = void;
2154 };
2155
2156 template<typename _Iter>
2157 requires __detail::__common_iter_has_arrow<_Iter>
2158 struct __ptr<_Iter>
2159 {
2160 using _CIter = common_iterator<_Iter, _Sent>;
2161 using type = decltype(std::declval<const _CIter&>().operator->());
2162 };
2163
2164 static auto
2165 _S_iter_cat()
2166 {
2167 using _Traits = iterator_traits<_It>;
2168 if constexpr (requires { requires derived_from<typename _Traits::iterator_category,
2169 forward_iterator_tag>; })
2170 return forward_iterator_tag{};
2171 else
2172 return input_iterator_tag{};
2173 }
2174
2175 public:
2176 using iterator_concept = conditional_t<forward_iterator<_It>,
2177 forward_iterator_tag, input_iterator_tag>;
2178 using iterator_category = decltype(_S_iter_cat());
2179 using value_type = iter_value_t<_It>;
2180 using difference_type = iter_difference_t<_It>;
2181 using pointer = typename __ptr<_It>::type;
2182 using reference = iter_reference_t<_It>;
2183 };
2184
2185 // [iterators.counted] Counted iterators
2186
2187 namespace __detail
2188 {
2189 template<typename _It>
2190 struct __counted_iter_value_type
2191 { };
2192
2193 template<indirectly_readable _It>
2194 struct __counted_iter_value_type<_It>
2195 { using value_type = iter_value_t<_It>; };
2196
2197 template<typename _It>
2198 struct __counted_iter_concept
2199 { };
2200
2201 template<typename _It>
2202 requires requires { typename _It::iterator_concept; }
2203 struct __counted_iter_concept<_It>
2204 { using iterator_concept = typename _It::iterator_concept; };
2205
2206 template<typename _It>
2207 struct __counted_iter_cat
2208 { };
2209
2210 template<typename _It>
2211 requires requires { typename _It::iterator_category; }
2212 struct __counted_iter_cat<_It>
2213 { using iterator_category = typename _It::iterator_category; };
2214 }
2215
2216 /// An iterator adaptor that keeps track of the distance to the end.
2217 template<input_or_output_iterator _It>
2218 class counted_iterator
2219 : public __detail::__counted_iter_value_type<_It>,
2220 public __detail::__counted_iter_concept<_It>,
2221 public __detail::__counted_iter_cat<_It>
2222 {
2223 public:
2224 using iterator_type = _It;
2225 // value_type defined in __counted_iter_value_type
2226 using difference_type = iter_difference_t<_It>;
2227 // iterator_concept defined in __counted_iter_concept
2228 // iterator_category defined in __counted_iter_cat
2229
2230 constexpr counted_iterator() requires default_initializable<_It> = default;
2231
2232 constexpr
2233 counted_iterator(_It __i, iter_difference_t<_It> __n)
2234 : _M_current(std::move(__i)), _M_length(__n)
2235 { __glibcxx_assert(__n >= 0); }
2236
2237 template<typename _It2>
2238 requires convertible_to<const _It2&, _It>
2239 constexpr
2240 counted_iterator(const counted_iterator<_It2>& __x)
2241 : _M_current(__x._M_current), _M_length(__x._M_length)
2242 { }
2243
2244 template<typename _It2>
2245 requires assignable_from<_It&, const _It2&>
2246 constexpr counted_iterator&
2247 operator=(const counted_iterator<_It2>& __x)
2248 {
2249 _M_current = __x._M_current;
2250 _M_length = __x._M_length;
2251 return *this;
2252 }
2253
2254 constexpr const _It&
2255 base() const & noexcept
2256 { return _M_current; }
2257
2258 constexpr _It
2259 base() &&
2260 noexcept(is_nothrow_move_constructible_v<_It>)
2261 { return std::move(_M_current); }
2262
2263 constexpr iter_difference_t<_It>
2264 count() const noexcept { return _M_length; }
2265
2266 constexpr decltype(auto)
2267 operator*()
2268 noexcept(noexcept(*_M_current))
2269 {
2270 __glibcxx_assert( _M_length > 0 );
2271 return *_M_current;
2272 }
2273
2274 constexpr decltype(auto)
2275 operator*() const
2276 noexcept(noexcept(*_M_current))
2277 requires __detail::__dereferenceable<const _It>
2278 {
2279 __glibcxx_assert( _M_length > 0 );
2280 return *_M_current;
2281 }
2282
2283 constexpr auto
2284 operator->() const noexcept
2285 requires contiguous_iterator<_It>
2286 { return std::to_address(_M_current); }
2287
2288 constexpr counted_iterator&
2289 operator++()
2290 {
2291 __glibcxx_assert(_M_length > 0);
2292 ++_M_current;
2293 --_M_length;
2294 return *this;
2295 }
2296
2297 constexpr decltype(auto)
2298 operator++(int)
2299 {
2300 __glibcxx_assert(_M_length > 0);
2301 --_M_length;
2302 __try
2303 {
2304 return _M_current++;
2305 } __catch(...) {
2306 ++_M_length;
2307 __throw_exception_again;
2308 }
2309 }
2310
2311 constexpr counted_iterator
2312 operator++(int) requires forward_iterator<_It>
2313 {
2314 auto __tmp = *this;
2315 ++*this;
2316 return __tmp;
2317 }
2318
2319 constexpr counted_iterator&
2320 operator--() requires bidirectional_iterator<_It>
2321 {
2322 --_M_current;
2323 ++_M_length;
2324 return *this;
2325 }
2326
2327 constexpr counted_iterator
2328 operator--(int) requires bidirectional_iterator<_It>
2329 {
2330 auto __tmp = *this;
2331 --*this;
2332 return __tmp;
2333 }
2334
2335 constexpr counted_iterator
2336 operator+(iter_difference_t<_It> __n) const
2337 requires random_access_iterator<_It>
2338 { return counted_iterator(_M_current + __n, _M_length - __n); }
2339
2340 friend constexpr counted_iterator
2341 operator+(iter_difference_t<_It> __n, const counted_iterator& __x)
2342 requires random_access_iterator<_It>
2343 { return __x + __n; }
2344
2345 constexpr counted_iterator&
2346 operator+=(iter_difference_t<_It> __n)
2347 requires random_access_iterator<_It>
2348 {
2349 __glibcxx_assert(__n <= _M_length);
2350 _M_current += __n;
2351 _M_length -= __n;
2352 return *this;
2353 }
2354
2355 constexpr counted_iterator
2356 operator-(iter_difference_t<_It> __n) const
2357 requires random_access_iterator<_It>
2358 { return counted_iterator(_M_current - __n, _M_length + __n); }
2359
2360 template<common_with<_It> _It2>
2361 friend constexpr iter_difference_t<_It2>
2362 operator-(const counted_iterator& __x,
2363 const counted_iterator<_It2>& __y)
2364 { return __y._M_length - __x._M_length; }
2365
2366 friend constexpr iter_difference_t<_It>
2367 operator-(const counted_iterator& __x, default_sentinel_t)
2368 { return -__x._M_length; }
2369
2370 friend constexpr iter_difference_t<_It>
2371 operator-(default_sentinel_t, const counted_iterator& __y)
2372 { return __y._M_length; }
2373
2374 constexpr counted_iterator&
2375 operator-=(iter_difference_t<_It> __n)
2376 requires random_access_iterator<_It>
2377 {
2378 __glibcxx_assert(-__n <= _M_length);
2379 _M_current -= __n;
2380 _M_length += __n;
2381 return *this;
2382 }
2383
2384 constexpr decltype(auto)
2385 operator[](iter_difference_t<_It> __n) const
2386 noexcept(noexcept(_M_current[__n]))
2387 requires random_access_iterator<_It>
2388 {
2389 __glibcxx_assert(__n < _M_length);
2390 return _M_current[__n];
2391 }
2392
2393 template<common_with<_It> _It2>
2394 friend constexpr bool
2395 operator==(const counted_iterator& __x,
2396 const counted_iterator<_It2>& __y)
2397 { return __x._M_length == __y._M_length; }
2398
2399 friend constexpr bool
2400 operator==(const counted_iterator& __x, default_sentinel_t)
2401 { return __x._M_length == 0; }
2402
2403 template<common_with<_It> _It2>
2404 friend constexpr strong_ordering
2405 operator<=>(const counted_iterator& __x,
2406 const counted_iterator<_It2>& __y)
2407 { return __y._M_length <=> __x._M_length; }
2408
2409 friend constexpr iter_rvalue_reference_t<_It>
2410 iter_move(const counted_iterator& __i)
2411 noexcept(noexcept(ranges::iter_move(__i._M_current)))
2412 requires input_iterator<_It>
2413 {
2414 __glibcxx_assert( __i._M_length > 0 );
2415 return ranges::iter_move(__i._M_current);
2416 }
2417
2418 template<indirectly_swappable<_It> _It2>
2419 friend constexpr void
2420 iter_swap(const counted_iterator& __x,
2421 const counted_iterator<_It2>& __y)
2422 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
2423 {
2424 __glibcxx_assert( __x._M_length > 0 && __y._M_length > 0 );
2425 ranges::iter_swap(__x._M_current, __y._M_current);
2426 }
2427
2428 private:
2429 template<input_or_output_iterator _It2> friend class counted_iterator;
2430
2431 _It _M_current = _It();
2432 iter_difference_t<_It> _M_length = 0;
2433 };
2434
2435 template<input_iterator _It>
2436 requires same_as<__detail::__iter_traits<_It>, iterator_traits<_It>>
2437 struct iterator_traits<counted_iterator<_It>> : iterator_traits<_It>
2438 {
2439 using pointer = conditional_t<contiguous_iterator<_It>,
2440 add_pointer_t<iter_reference_t<_It>>,
2441 void>;
2442 };
2443#endif // C++20
2444
2445 /// @} group iterators
2446
2447 template<typename _Iterator>
2448 _GLIBCXX20_CONSTEXPR
2449 auto
2450 __niter_base(move_iterator<_Iterator> __it)
2451 -> decltype(make_move_iterator(__niter_base(__it.base())))
2452 { return make_move_iterator(__niter_base(__it.base())); }
2453
2454 template<typename _Iterator>
2455 struct __is_move_iterator<move_iterator<_Iterator> >
2456 {
2457 enum { __value = 1 };
2458 typedef __true_type __type;
2459 };
2460
2461 template<typename _Iterator>
2462 _GLIBCXX20_CONSTEXPR
2463 auto
2464 __miter_base(move_iterator<_Iterator> __it)
2465 -> decltype(__miter_base(__it.base()))
2466 { return __miter_base(__it.base()); }
2467
2468#define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
2469#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
2470 std::__make_move_if_noexcept_iterator(_Iter)
2471#else
2472#define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
2473#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
2474#endif // C++11
2475
2476#if __cpp_deduction_guides >= 201606
2477 // These helper traits are used for deduction guides
2478 // of associative containers.
2479 template<typename _InputIterator>
2480 using __iter_key_t = remove_const_t<
2481 typename iterator_traits<_InputIterator>::value_type::first_type>;
2482
2483 template<typename _InputIterator>
2484 using __iter_val_t =
2485 typename iterator_traits<_InputIterator>::value_type::second_type;
2486
2487 template<typename _T1, typename _T2>
2488 struct pair;
2489
2490 template<typename _InputIterator>
2491 using __iter_to_alloc_t =
2492 pair<add_const_t<__iter_key_t<_InputIterator>>,
2493 __iter_val_t<_InputIterator>>;
2494#endif // __cpp_deduction_guides
2495
2496_GLIBCXX_END_NAMESPACE_VERSION
2497} // namespace
2498
2499#ifdef _GLIBCXX_DEBUG
2500# include <debug/stl_iterator.h>
2501#endif
2502
2503#endif
2504

source code of include/c++/11/bits/stl_iterator.h