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