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