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