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