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