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