libstdc++
bits/stl_iterator.h
Go to the documentation of this file.
1// Iterators -*- C++ -*-
2
3// Copyright (C) 2001-2026 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/*
26 *
27 * Copyright (c) 1994
28 * Hewlett-Packard Company
29 *
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation. Hewlett-Packard Company makes no
35 * representations about the suitability of this software for any
36 * purpose. It is provided "as is" without express or implied warranty.
37 *
38 *
39 * Copyright (c) 1996-1998
40 * Silicon Graphics Computer Systems, Inc.
41 *
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation. Silicon Graphics makes no
47 * representations about the suitability of this software for any
48 * purpose. It is provided "as is" without express or implied warranty.
49 */
50
51/** @file bits/stl_iterator.h
52 * This is an internal header file, included by other library headers.
53 * Do not attempt to use it directly. @headername{iterator}
54 *
55 * This file implements reverse_iterator, back_insert_iterator,
56 * front_insert_iterator, insert_iterator, __normal_iterator, and their
57 * supporting functions and overloaded operators.
58 */
59
60#ifndef _STL_ITERATOR_H
61#define _STL_ITERATOR_H 1
62
63#include <bits/cpp_type_traits.h>
64#include <bits/stl_iterator_base_types.h>
65#include <ext/type_traits.h>
66#include <bits/move.h>
67#include <bits/ptr_traits.h>
68
69#if __cplusplus >= 201103L
70# include <type_traits>
71#endif
72
73#if __cplusplus >= 202002L
74# include <compare>
75# include <new>
76# include <bits/exception_defines.h>
77# include <bits/iterator_concepts.h>
78# include <bits/stl_construct.h>
79#endif
80
81#if __glibcxx_tuple_like // >= C++23
82# include <bits/utility.h> // for tuple_element_t
83#endif
84
85namespace std _GLIBCXX_VISIBILITY(default)
86{
87_GLIBCXX_BEGIN_NAMESPACE_VERSION
88
89 /**
90 * @addtogroup iterators
91 * @{
92 */
93
94#ifdef __glibcxx_concepts
95 /// @cond undocumented
96 namespace __detail
97 {
98 // Weaken iterator_category _Cat to _Limit if it is derived from that,
99 // otherwise use _Otherwise.
100 template<typename _Cat, typename _Limit, typename _Otherwise = _Cat>
101 using __clamp_iter_cat
102 = __conditional_t<derived_from<_Cat, _Limit>, _Limit, _Otherwise>;
103 }
104 /// @endcond
105#endif
106
107// Ignore warnings about std::iterator.
108#pragma GCC diagnostic push
109#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
110
111 // 24.4.1 Reverse iterators
112 /**
113 * Bidirectional and random access iterators have corresponding reverse
114 * %iterator adaptors that iterate through the data structure in the
115 * opposite direction. They have the same signatures as the corresponding
116 * iterators. The fundamental relation between a reverse %iterator and its
117 * corresponding %iterator @c i is established by the identity:
118 * @code
119 * &*(reverse_iterator(i)) == &*(i - 1)
120 * @endcode
121 *
122 * <em>This mapping is dictated by the fact that while there is always a
123 * pointer past the end of an array, there might not be a valid pointer
124 * before the beginning of an array.</em> [24.4.1]/1,2
125 *
126 * Reverse iterators can be tricky and surprising at first. Their
127 * semantics make sense, however, and the trickiness is a side effect of
128 * the requirement that the iterators must be safe.
129 */
130 template<typename _Iterator>
131 class reverse_iterator
132 : public iterator<typename iterator_traits<_Iterator>::iterator_category,
133 typename iterator_traits<_Iterator>::value_type,
134 typename iterator_traits<_Iterator>::difference_type,
135 typename iterator_traits<_Iterator>::pointer,
136 typename iterator_traits<_Iterator>::reference>
137 {
138 template<typename _Iter>
139 friend class reverse_iterator;
140
141#ifdef __glibcxx_concepts
142 // _GLIBCXX_RESOLVE_LIB_DEFECTS
143 // 3435. three_way_comparable_with<reverse_iterator<int*>, [...]>
144 template<typename _Iter>
145 static constexpr bool __convertible = !is_same_v<_Iter, _Iterator>
146 && convertible_to<const _Iter&, _Iterator>;
147#endif
148
149 protected:
150 _Iterator current;
151
152 typedef iterator_traits<_Iterator> __traits_type;
153
154 public:
155 typedef _Iterator iterator_type;
156 typedef typename __traits_type::pointer pointer;
157#ifndef __glibcxx_concepts
158 typedef typename __traits_type::difference_type difference_type;
159 typedef typename __traits_type::reference reference;
160#else
161 using iterator_concept
162 = __conditional_t<random_access_iterator<_Iterator>,
163 random_access_iterator_tag,
164 bidirectional_iterator_tag>;
165 using iterator_category
166 = __detail::__clamp_iter_cat<typename __traits_type::iterator_category,
167 random_access_iterator_tag>;
168 using value_type = iter_value_t<_Iterator>;
169 using difference_type = iter_difference_t<_Iterator>;
170 using reference = iter_reference_t<_Iterator>;
171#endif
172
173 /**
174 * The default constructor value-initializes member @p current.
175 * If it is a pointer, that means it is zero-initialized.
176 */
177 // _GLIBCXX_RESOLVE_LIB_DEFECTS
178 // 235 No specification of default ctor for reverse_iterator
179 // 1012. reverse_iterator default ctor should value initialize
180 _GLIBCXX17_CONSTEXPR
181 reverse_iterator()
182 _GLIBCXX_NOEXCEPT_IF(noexcept(_Iterator()))
183 : current()
184 { }
185
186 /**
187 * This %iterator will move in the opposite direction that @p x does.
188 */
189 explicit _GLIBCXX17_CONSTEXPR
190 reverse_iterator(iterator_type __x)
191 _GLIBCXX_NOEXCEPT_IF(noexcept(_Iterator(__x)))
192 : current(__x)
193 { }
194
195 /**
196 * The copy constructor is normal.
197 */
198 _GLIBCXX17_CONSTEXPR
199 reverse_iterator(const reverse_iterator& __x)
200 _GLIBCXX_NOEXCEPT_IF(noexcept(_Iterator(__x.current)))
201 : current(__x.current)
202 { }
203
204#if __cplusplus >= 201103L
205 reverse_iterator& operator=(const reverse_iterator&) = default;
206#endif
207
208 /**
209 * A %reverse_iterator across other types can be copied if the
210 * underlying %iterator can be converted to the type of @c current.
211 */
212 template<typename _Iter>
213#ifdef __glibcxx_concepts
214 requires __convertible<_Iter>
215#endif
216 _GLIBCXX17_CONSTEXPR
217 reverse_iterator(const reverse_iterator<_Iter>& __x)
218 _GLIBCXX_NOEXCEPT_IF(noexcept(_Iterator(__x.current)))
219 : current(__x.current)
220 { }
221
222#if __cplusplus >= 201103L
223 template<typename _Iter>
224# ifdef __glibcxx_concepts
225 requires __convertible<_Iter>
226 && assignable_from<_Iterator&, const _Iter&>
227# endif
228 _GLIBCXX17_CONSTEXPR
229 reverse_iterator&
230 operator=(const reverse_iterator<_Iter>& __x)
231 _GLIBCXX_NOEXCEPT_IF(noexcept(current = __x.current))
232 {
233 current = __x.current;
234 return *this;
235 }
236#endif // C++11
237
238 /**
239 * @return @c current, the %iterator used for underlying work.
240 */
241 _GLIBCXX_NODISCARD
242 _GLIBCXX17_CONSTEXPR iterator_type
243 base() const
244 _GLIBCXX_NOEXCEPT_IF(noexcept(_Iterator(current)))
245 { return current; }
246
247 /**
248 * @return A reference to the value at @c --current
249 *
250 * This requires that @c --current is dereferenceable.
251 *
252 * @warning This implementation requires that for an iterator of the
253 * underlying iterator type, @c x, a reference obtained by
254 * @c *x remains valid after @c x has been modified or
255 * destroyed. This is a bug: http://gcc.gnu.org/PR51823
256 */
257 _GLIBCXX_NODISCARD
258 _GLIBCXX17_CONSTEXPR reference
259 operator*() const
260 {
261 _Iterator __tmp = current;
262 return *--__tmp;
263 }
264
265 /**
266 * @return A pointer to the value at @c --current
267 *
268 * This requires that @c --current is dereferenceable.
269 */
270 _GLIBCXX_NODISCARD
271 _GLIBCXX17_CONSTEXPR pointer
272 operator->() const
273#ifdef __glibcxx_concepts
274 requires is_pointer_v<_Iterator>
275 || requires(const _Iterator __i) { __i.operator->(); }
276#endif
277 {
278 // _GLIBCXX_RESOLVE_LIB_DEFECTS
279 // 1052. operator-> should also support smart pointers
280 _Iterator __tmp = current;
281 --__tmp;
282 return _S_to_pointer(__tmp);
283 }
284
285 /**
286 * @return @c *this
287 *
288 * Decrements the underlying iterator.
289 */
290 _GLIBCXX17_CONSTEXPR reverse_iterator&
291 operator++()
292 {
293 --current;
294 return *this;
295 }
296
297 /**
298 * @return The original value of @c *this
299 *
300 * Decrements the underlying iterator.
301 */
302 _GLIBCXX17_CONSTEXPR reverse_iterator
303 operator++(int)
304 {
305 reverse_iterator __tmp = *this;
306 --current;
307 return __tmp;
308 }
309
310 /**
311 * @return @c *this
312 *
313 * Increments the underlying iterator.
314 */
315 _GLIBCXX17_CONSTEXPR reverse_iterator&
316 operator--()
317 {
318 ++current;
319 return *this;
320 }
321
322 /**
323 * @return A reverse_iterator with the previous value of @c *this
324 *
325 * Increments the underlying iterator.
326 */
327 _GLIBCXX17_CONSTEXPR reverse_iterator
328 operator--(int)
329 {
330 reverse_iterator __tmp = *this;
331 ++current;
332 return __tmp;
333 }
334
335 /**
336 * @return A reverse_iterator that refers to @c current - @a __n
337 *
338 * The underlying iterator must be a Random Access Iterator.
339 */
340 _GLIBCXX_NODISCARD
341 _GLIBCXX17_CONSTEXPR reverse_iterator
342 operator+(difference_type __n) const
343 { return reverse_iterator(current - __n); }
344
345 /**
346 * @return *this
347 *
348 * Moves the underlying iterator backwards @a __n steps.
349 * The underlying iterator must be a Random Access Iterator.
350 */
351 _GLIBCXX17_CONSTEXPR reverse_iterator&
352 operator+=(difference_type __n)
353 {
354 current -= __n;
355 return *this;
356 }
357
358 /**
359 * @return A reverse_iterator that refers to @c current - @a __n
360 *
361 * The underlying iterator must be a Random Access Iterator.
362 */
363 _GLIBCXX_NODISCARD
364 _GLIBCXX17_CONSTEXPR reverse_iterator
365 operator-(difference_type __n) const
366 { return reverse_iterator(current + __n); }
367
368 /**
369 * @return *this
370 *
371 * Moves the underlying iterator forwards @a __n steps.
372 * The underlying iterator must be a Random Access Iterator.
373 */
374 _GLIBCXX17_CONSTEXPR reverse_iterator&
375 operator-=(difference_type __n)
376 {
377 current += __n;
378 return *this;
379 }
380
381 /**
382 * @return The value at @c current - @a __n - 1
383 *
384 * The underlying iterator must be a Random Access Iterator.
385 */
386 _GLIBCXX_NODISCARD
387 _GLIBCXX17_CONSTEXPR reference
388 operator[](difference_type __n) const
389 { return *(*this + __n); }
390
391#ifdef __glibcxx_ranges
392 [[nodiscard]]
393 friend constexpr iter_rvalue_reference_t<_Iterator>
394 iter_move(const reverse_iterator& __i)
395 noexcept(is_nothrow_copy_constructible_v<_Iterator>
396 && noexcept(ranges::iter_move(--std::declval<_Iterator&>())))
397 {
398 auto __tmp = __i.base();
399 return ranges::iter_move(--__tmp);
400 }
401
402 template<indirectly_swappable<_Iterator> _Iter2>
403 friend constexpr void
404 iter_swap(const reverse_iterator& __x,
405 const reverse_iterator<_Iter2>& __y)
406 noexcept(is_nothrow_copy_constructible_v<_Iterator>
407 && is_nothrow_copy_constructible_v<_Iter2>
408 && noexcept(ranges::iter_swap(--std::declval<_Iterator&>(),
409 --std::declval<_Iter2&>())))
410 {
411 auto __xtmp = __x.base();
412 auto __ytmp = __y.base();
413 ranges::iter_swap(--__xtmp, --__ytmp);
414 }
415#endif // ranges
416
417 private:
418 template<typename _Tp>
419 static _GLIBCXX17_CONSTEXPR _Tp*
420 _S_to_pointer(_Tp* __p)
421 { return __p; }
422
423 template<typename _Tp>
424 static _GLIBCXX17_CONSTEXPR pointer
425 _S_to_pointer(_Tp __t)
426 { return __t.operator->(); }
427 };
428
429 ///@{
430 /**
431 * @param __x A %reverse_iterator.
432 * @param __y A %reverse_iterator.
433 * @return A simple bool.
434 *
435 * Reverse iterators forward comparisons to their underlying base()
436 * iterators.
437 *
438 */
439#ifndef __glibcxx_concepts
440 template<typename _Iterator>
441 _GLIBCXX_NODISCARD
442 inline _GLIBCXX17_CONSTEXPR bool
443 operator==(const reverse_iterator<_Iterator>& __x,
444 const reverse_iterator<_Iterator>& __y)
445 { return __x.base() == __y.base(); }
446
447 template<typename _Iterator>
448 _GLIBCXX_NODISCARD
449 inline _GLIBCXX17_CONSTEXPR bool
450 operator<(const reverse_iterator<_Iterator>& __x,
451 const reverse_iterator<_Iterator>& __y)
452 { return __y.base() < __x.base(); }
453
454 template<typename _Iterator>
455 _GLIBCXX_NODISCARD
456 inline _GLIBCXX17_CONSTEXPR bool
457 operator!=(const reverse_iterator<_Iterator>& __x,
458 const reverse_iterator<_Iterator>& __y)
459 { return !(__x == __y); }
460
461 template<typename _Iterator>
462 _GLIBCXX_NODISCARD
463 inline _GLIBCXX17_CONSTEXPR bool
464 operator>(const reverse_iterator<_Iterator>& __x,
465 const reverse_iterator<_Iterator>& __y)
466 { return __y < __x; }
467
468 template<typename _Iterator>
469 _GLIBCXX_NODISCARD
470 inline _GLIBCXX17_CONSTEXPR bool
471 operator<=(const reverse_iterator<_Iterator>& __x,
472 const reverse_iterator<_Iterator>& __y)
473 { return !(__y < __x); }
474
475 template<typename _Iterator>
476 _GLIBCXX_NODISCARD
477 inline _GLIBCXX17_CONSTEXPR bool
478 operator>=(const reverse_iterator<_Iterator>& __x,
479 const reverse_iterator<_Iterator>& __y)
480 { return !(__x < __y); }
481
482 // _GLIBCXX_RESOLVE_LIB_DEFECTS
483 // DR 280. Comparison of reverse_iterator to const reverse_iterator.
484
485 template<typename _IteratorL, typename _IteratorR>
486 _GLIBCXX_NODISCARD
487 inline _GLIBCXX17_CONSTEXPR bool
488 operator==(const reverse_iterator<_IteratorL>& __x,
489 const reverse_iterator<_IteratorR>& __y)
490 { return __x.base() == __y.base(); }
491
492 template<typename _IteratorL, typename _IteratorR>
493 _GLIBCXX_NODISCARD
494 inline _GLIBCXX17_CONSTEXPR bool
495 operator<(const reverse_iterator<_IteratorL>& __x,
496 const reverse_iterator<_IteratorR>& __y)
497 { return __x.base() > __y.base(); }
498
499 template<typename _IteratorL, typename _IteratorR>
500 _GLIBCXX_NODISCARD
501 inline _GLIBCXX17_CONSTEXPR bool
502 operator!=(const reverse_iterator<_IteratorL>& __x,
503 const reverse_iterator<_IteratorR>& __y)
504 { return __x.base() != __y.base(); }
505
506 template<typename _IteratorL, typename _IteratorR>
507 _GLIBCXX_NODISCARD
508 inline _GLIBCXX17_CONSTEXPR bool
509 operator>(const reverse_iterator<_IteratorL>& __x,
510 const reverse_iterator<_IteratorR>& __y)
511 { return __x.base() < __y.base(); }
512
513 template<typename _IteratorL, typename _IteratorR>
514 inline _GLIBCXX17_CONSTEXPR bool
515 operator<=(const reverse_iterator<_IteratorL>& __x,
516 const reverse_iterator<_IteratorR>& __y)
517 { return __x.base() >= __y.base(); }
518
519 template<typename _IteratorL, typename _IteratorR>
520 _GLIBCXX_NODISCARD
521 inline _GLIBCXX17_CONSTEXPR bool
522 operator>=(const reverse_iterator<_IteratorL>& __x,
523 const reverse_iterator<_IteratorR>& __y)
524 { return __x.base() <= __y.base(); }
525#else // C++20
526 template<typename _IteratorL, typename _IteratorR>
527 [[nodiscard]]
528 constexpr bool
529 operator==(const reverse_iterator<_IteratorL>& __x,
530 const reverse_iterator<_IteratorR>& __y)
531 requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
532 { return __x.base() == __y.base(); }
533
534 template<typename _IteratorL, typename _IteratorR>
535 [[nodiscard]]
536 constexpr bool
537 operator!=(const reverse_iterator<_IteratorL>& __x,
538 const reverse_iterator<_IteratorR>& __y)
539 requires requires { { __x.base() != __y.base() } -> convertible_to<bool>; }
540 { return __x.base() != __y.base(); }
541
542 template<typename _IteratorL, typename _IteratorR>
543 [[nodiscard]]
544 constexpr bool
545 operator<(const reverse_iterator<_IteratorL>& __x,
546 const reverse_iterator<_IteratorR>& __y)
547 requires requires { { __x.base() > __y.base() } -> convertible_to<bool>; }
548 { return __x.base() > __y.base(); }
549
550 template<typename _IteratorL, typename _IteratorR>
551 [[nodiscard]]
552 constexpr bool
553 operator>(const reverse_iterator<_IteratorL>& __x,
554 const reverse_iterator<_IteratorR>& __y)
555 requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
556 { return __x.base() < __y.base(); }
557
558 template<typename _IteratorL, typename _IteratorR>
559 [[nodiscard]]
560 constexpr bool
561 operator<=(const reverse_iterator<_IteratorL>& __x,
562 const reverse_iterator<_IteratorR>& __y)
563 requires requires { { __x.base() >= __y.base() } -> convertible_to<bool>; }
564 { return __x.base() >= __y.base(); }
565
566 template<typename _IteratorL, typename _IteratorR>
567 [[nodiscard]]
568 constexpr bool
569 operator>=(const reverse_iterator<_IteratorL>& __x,
570 const reverse_iterator<_IteratorR>& __y)
571 requires requires { { __x.base() <= __y.base() } -> convertible_to<bool>; }
572 { return __x.base() <= __y.base(); }
573
574 template<typename _IteratorL,
575 three_way_comparable_with<_IteratorL> _IteratorR>
576 [[nodiscard]]
577 constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
578 operator<=>(const reverse_iterator<_IteratorL>& __x,
579 const reverse_iterator<_IteratorR>& __y)
580 { return __y.base() <=> __x.base(); }
581
582 // Additional, non-standard overloads to avoid ambiguities with greedy,
583 // unconstrained overloads in associated namespaces.
584
585 template<typename _Iterator>
586 [[nodiscard]]
587 constexpr bool
588 operator==(const reverse_iterator<_Iterator>& __x,
589 const reverse_iterator<_Iterator>& __y)
590 requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
591 { return __x.base() == __y.base(); }
592
593 template<three_way_comparable _Iterator>
594 [[nodiscard]]
595 constexpr compare_three_way_result_t<_Iterator, _Iterator>
596 operator<=>(const reverse_iterator<_Iterator>& __x,
597 const reverse_iterator<_Iterator>& __y)
598 { return __y.base() <=> __x.base(); }
599#endif // C++20
600 ///@}
601
602#if __cplusplus < 201103L
603 template<typename _Iterator>
604 inline typename reverse_iterator<_Iterator>::difference_type
605 operator-(const reverse_iterator<_Iterator>& __x,
606 const reverse_iterator<_Iterator>& __y)
607 { return __y.base() - __x.base(); }
608
609 template<typename _IteratorL, typename _IteratorR>
610 inline typename reverse_iterator<_IteratorL>::difference_type
611 operator-(const reverse_iterator<_IteratorL>& __x,
612 const reverse_iterator<_IteratorR>& __y)
613 { return __y.base() - __x.base(); }
614#else
615 // _GLIBCXX_RESOLVE_LIB_DEFECTS
616 // DR 685. reverse_iterator/move_iterator difference has invalid signatures
617 template<typename _IteratorL, typename _IteratorR>
618 [[__nodiscard__]]
619 inline _GLIBCXX17_CONSTEXPR auto
620 operator-(const reverse_iterator<_IteratorL>& __x,
621 const reverse_iterator<_IteratorR>& __y)
622 -> decltype(__y.base() - __x.base())
623 { return __y.base() - __x.base(); }
624#endif
625
626 template<typename _Iterator>
627 _GLIBCXX_NODISCARD
628 inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
629 operator+(typename reverse_iterator<_Iterator>::difference_type __n,
630 const reverse_iterator<_Iterator>& __x)
631 { return reverse_iterator<_Iterator>(__x.base() - __n); }
632
633#if __cplusplus >= 201103L
634 // Same as C++14 make_reverse_iterator but used in C++11 mode too.
635 template<typename _Iterator>
636 inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
637 __make_reverse_iterator(_Iterator __i)
638 { return reverse_iterator<_Iterator>(__i); }
639
640# ifdef __glibcxx_make_reverse_iterator // C++ >= 14
641 // _GLIBCXX_RESOLVE_LIB_DEFECTS
642 // DR 2285. make_reverse_iterator
643 /// Generator function for reverse_iterator.
644 template<typename _Iterator>
645 [[__nodiscard__]]
646 inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
647 make_reverse_iterator(_Iterator __i)
648 { return reverse_iterator<_Iterator>(__i); }
649
650# ifdef __glibcxx_ranges
651 template<typename _Iterator1, typename _Iterator2>
652 requires (!sized_sentinel_for<_Iterator1, _Iterator2>)
653 inline constexpr bool
654 disable_sized_sentinel_for<reverse_iterator<_Iterator1>,
655 reverse_iterator<_Iterator2>> = true;
656# endif // C++20
657# endif // __glibcxx_make_reverse_iterator
658
659 template<typename _Iterator>
660 struct __is_move_iterator<reverse_iterator<_Iterator> >
661 : __is_move_iterator<_Iterator>
662 { };
663#endif // C++11
664
665 // 24.4.2.2.1 back_insert_iterator
666 /**
667 * @brief Turns assignment into insertion.
668 *
669 * These are output iterators, constructed from a container-of-T.
670 * Assigning a T to the iterator appends it to the container using
671 * push_back.
672 *
673 * Tip: Using the back_inserter function to create these iterators can
674 * save typing.
675 */
676 template<typename _Container>
677 class back_insert_iterator
678 : public iterator<output_iterator_tag, void, void, void, void>
679 {
680 protected:
681 _Container* container;
682
683 public:
684 /// A nested typedef for the type of whatever container you used.
685 typedef _Container container_type;
686#ifdef __glibcxx_ranges
687 using difference_type = ptrdiff_t;
688#endif
689
690 /// The only way to create this %iterator is with a container.
691 explicit _GLIBCXX20_CONSTEXPR
692 back_insert_iterator(_Container& __x)
693 : container(std::__addressof(__x)) { }
694
695 /**
696 * @param __value An instance of whatever type
697 * container_type::const_reference is; presumably a
698 * reference-to-const T for container<T>.
699 * @return This %iterator, for chained operations.
700 *
701 * This kind of %iterator doesn't really have a @a position in the
702 * container (you can think of the position as being permanently at
703 * the end, if you like). Assigning a value to the %iterator will
704 * always append the value to the end of the container.
705 */
706#if __cplusplus < 201103L
707 back_insert_iterator&
708 operator=(typename _Container::const_reference __value)
709 {
710 container->push_back(__value);
711 return *this;
712 }
713#else
714 _GLIBCXX20_CONSTEXPR
715 back_insert_iterator&
716 operator=(const typename _Container::value_type& __value)
717 {
718 container->push_back(__value);
719 return *this;
720 }
721
722 _GLIBCXX20_CONSTEXPR
723 back_insert_iterator&
724 operator=(typename _Container::value_type&& __value)
725 {
726 container->push_back(std::move(__value));
727 return *this;
728 }
729#endif
730
731 /// Simply returns *this.
732 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
733 back_insert_iterator&
734 operator*()
735 { return *this; }
736
737 /// Simply returns *this. (This %iterator does not @a move.)
738 _GLIBCXX20_CONSTEXPR
739 back_insert_iterator&
740 operator++()
741 { return *this; }
742
743 /// Simply returns *this. (This %iterator does not @a move.)
744 _GLIBCXX20_CONSTEXPR
745 back_insert_iterator
746 operator++(int)
747 { return *this; }
748 };
749
750 /**
751 * @param __x A container of arbitrary type.
752 * @return An instance of back_insert_iterator working on @p __x.
753 *
754 * This wrapper function helps in creating back_insert_iterator instances.
755 * Typing the name of the %iterator requires knowing the precise full
756 * type of the container, which can be tedious and impedes generic
757 * programming. Using this function lets you take advantage of automatic
758 * template parameter deduction, making the compiler match the correct
759 * types for you.
760 */
761 template<typename _Container>
762 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
763 inline back_insert_iterator<_Container>
764 back_inserter(_Container& __x)
765 { return back_insert_iterator<_Container>(__x); }
766
767 /**
768 * @brief Turns assignment into insertion.
769 *
770 * These are output iterators, constructed from a container-of-T.
771 * Assigning a T to the iterator prepends it to the container using
772 * push_front.
773 *
774 * Tip: Using the front_inserter function to create these iterators can
775 * save typing.
776 */
777 template<typename _Container>
778 class front_insert_iterator
779 : public iterator<output_iterator_tag, void, void, void, void>
780 {
781 protected:
782 _Container* container;
783
784 public:
785 /// A nested typedef for the type of whatever container you used.
786 typedef _Container container_type;
787#ifdef __glibcxx_ranges
788 using difference_type = ptrdiff_t;
789#endif
790
791 /// The only way to create this %iterator is with a container.
792 explicit _GLIBCXX20_CONSTEXPR
793 front_insert_iterator(_Container& __x)
794 : container(std::__addressof(__x)) { }
795
796 /**
797 * @param __value An instance of whatever type
798 * container_type::const_reference is; presumably a
799 * reference-to-const T for container<T>.
800 * @return This %iterator, for chained operations.
801 *
802 * This kind of %iterator doesn't really have a @a position in the
803 * container (you can think of the position as being permanently at
804 * the front, if you like). Assigning a value to the %iterator will
805 * always prepend the value to the front of the container.
806 */
807#if __cplusplus < 201103L
808 front_insert_iterator&
809 operator=(typename _Container::const_reference __value)
810 {
811 container->push_front(__value);
812 return *this;
813 }
814#else
815 _GLIBCXX20_CONSTEXPR
816 front_insert_iterator&
817 operator=(const typename _Container::value_type& __value)
818 {
819 container->push_front(__value);
820 return *this;
821 }
822
823 _GLIBCXX20_CONSTEXPR
824 front_insert_iterator&
825 operator=(typename _Container::value_type&& __value)
826 {
827 container->push_front(std::move(__value));
828 return *this;
829 }
830#endif
831
832 /// Simply returns *this.
833 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
834 front_insert_iterator&
835 operator*()
836 { return *this; }
837
838 /// Simply returns *this. (This %iterator does not @a move.)
839 _GLIBCXX20_CONSTEXPR
840 front_insert_iterator&
841 operator++()
842 { return *this; }
843
844 /// Simply returns *this. (This %iterator does not @a move.)
845 _GLIBCXX20_CONSTEXPR
846 front_insert_iterator
847 operator++(int)
848 { return *this; }
849 };
850
851 /**
852 * @param __x A container of arbitrary type.
853 * @return An instance of front_insert_iterator working on @p x.
854 *
855 * This wrapper function helps in creating front_insert_iterator instances.
856 * Typing the name of the %iterator requires knowing the precise full
857 * type of the container, which can be tedious and impedes generic
858 * programming. Using this function lets you take advantage of automatic
859 * template parameter deduction, making the compiler match the correct
860 * types for you.
861 */
862 template<typename _Container>
863 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
864 inline front_insert_iterator<_Container>
865 front_inserter(_Container& __x)
866 { return front_insert_iterator<_Container>(__x); }
867
868 /**
869 * @brief Turns assignment into insertion.
870 *
871 * These are output iterators, constructed from a container-of-T.
872 * Assigning a T to the iterator inserts it in the container at the
873 * %iterator's position, rather than overwriting the value at that
874 * position.
875 *
876 * (Sequences will actually insert a @e copy of the value before the
877 * %iterator's position.)
878 *
879 * Tip: Using the inserter function to create these iterators can
880 * save typing.
881 */
882 template<typename _Container>
883 class insert_iterator
884 : public iterator<output_iterator_tag, void, void, void, void>
885 {
886#ifdef __glibcxx_ranges
887 using _Iter = std::__detail::__range_iter_t<_Container>;
888#else
889 typedef typename _Container::iterator _Iter;
890#endif
891 protected:
892 _Container* container;
893 _Iter iter;
894
895 public:
896 /// A nested typedef for the type of whatever container you used.
897 typedef _Container container_type;
898
899#ifdef __glibcxx_ranges
900 using difference_type = ptrdiff_t;
901#endif
902
903 /**
904 * The only way to create this %iterator is with a container and an
905 * initial position (a normal %iterator into the container).
906 */
907 _GLIBCXX20_CONSTEXPR
908 insert_iterator(_Container& __x, _Iter __i)
909 : container(std::__addressof(__x)), iter(__i) {}
910
911 /**
912 * @param __value An instance of whatever type
913 * container_type::const_reference is; presumably a
914 * reference-to-const T for container<T>.
915 * @return This %iterator, for chained operations.
916 *
917 * This kind of %iterator maintains its own position in the
918 * container. Assigning a value to the %iterator will insert the
919 * value into the container at the place before the %iterator.
920 *
921 * The position is maintained such that subsequent assignments will
922 * insert values immediately after one another. For example,
923 * @code
924 * // vector v contains A and Z
925 *
926 * insert_iterator i (v, ++v.begin());
927 * i = 1;
928 * i = 2;
929 * i = 3;
930 *
931 * // vector v contains A, 1, 2, 3, and Z
932 * @endcode
933 */
934#if __cplusplus < 201103L
935 insert_iterator&
936 operator=(typename _Container::const_reference __value)
937 {
938 iter = container->insert(iter, __value);
939 ++iter;
940 return *this;
941 }
942#else
943 _GLIBCXX20_CONSTEXPR
944 insert_iterator&
945 operator=(const typename _Container::value_type& __value)
946 {
947 iter = container->insert(iter, __value);
948 ++iter;
949 return *this;
950 }
951
952 _GLIBCXX20_CONSTEXPR
953 insert_iterator&
954 operator=(typename _Container::value_type&& __value)
955 {
956 iter = container->insert(iter, std::move(__value));
957 ++iter;
958 return *this;
959 }
960#endif
961
962 /// Simply returns *this.
963 _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
964 insert_iterator&
965 operator*()
966 { return *this; }
967
968 /// Simply returns *this. (This %iterator does not @a move.)
969 _GLIBCXX20_CONSTEXPR
970 insert_iterator&
971 operator++()
972 { return *this; }
973
974 /// Simply returns *this. (This %iterator does not @a move.)
975 _GLIBCXX20_CONSTEXPR
976 insert_iterator&
977 operator++(int)
978 { return *this; }
979 };
980
981#pragma GCC diagnostic pop
982
983 /**
984 * @param __x A container of arbitrary type.
985 * @param __i An iterator into the container.
986 * @return An instance of insert_iterator working on @p __x.
987 *
988 * This wrapper function helps in creating insert_iterator instances.
989 * Typing the name of the %iterator requires knowing the precise full
990 * type of the container, which can be tedious and impedes generic
991 * programming. Using this function lets you take advantage of automatic
992 * template parameter deduction, making the compiler match the correct
993 * types for you.
994 */
995#ifdef __glibcxx_ranges
996 template<typename _Container>
997 [[nodiscard]]
998 constexpr insert_iterator<_Container>
999 inserter(_Container& __x, std::__detail::__range_iter_t<_Container> __i)
1000 { return insert_iterator<_Container>(__x, __i); }
1001#else
1002 template<typename _Container>
1003 _GLIBCXX_NODISCARD
1004 inline insert_iterator<_Container>
1005 inserter(_Container& __x, typename _Container::iterator __i)
1006 { return insert_iterator<_Container>(__x, __i); }
1007#endif
1008
1009 /// @} group iterators
1010
1011_GLIBCXX_END_NAMESPACE_VERSION
1012} // namespace
1013
1014namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
1015{
1016_GLIBCXX_BEGIN_NAMESPACE_VERSION
1017
1018 // This iterator adapter is @a normal in the sense that it does not
1019 // change the semantics of any of the operators of its iterator
1020 // parameter. Its primary purpose is to convert an iterator that is
1021 // not a class, e.g. a pointer, into an iterator that is a class.
1022 // The _Container parameter exists solely so that different containers
1023 // using this template can instantiate different types, even if the
1024 // _Iterator parameter is the same.
1025 template<typename _Iterator, typename _Container>
1026 class __normal_iterator
1027 {
1028 protected:
1029 _Iterator _M_current;
1030
1031 typedef std::iterator_traits<_Iterator> __traits_type;
1032
1033#if __cplusplus >= 201103L && ! defined __glibcxx_concepts
1034 template<typename _Iter>
1035 using __convertible_from
1036 = std::__enable_if_t<std::is_convertible<_Iter, _Iterator>::value>;
1037#endif
1038
1039 public:
1040 typedef _Iterator iterator_type;
1041 typedef typename __traits_type::iterator_category iterator_category;
1042 typedef typename __traits_type::value_type value_type;
1043 typedef typename __traits_type::difference_type difference_type;
1044 typedef typename __traits_type::reference reference;
1045 typedef typename __traits_type::pointer pointer;
1046
1047#ifdef __glibcxx_ranges
1048 using iterator_concept = std::__detail::__iter_concept<_Iterator>;
1049#endif
1050
1051 __attribute__((__always_inline__))
1052 _GLIBCXX_CONSTEXPR
1053 __normal_iterator() _GLIBCXX_NOEXCEPT
1054 : _M_current() { }
1055
1056 __attribute__((__always_inline__))
1057 explicit _GLIBCXX_CONSTEXPR
1058 __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT
1059 : _M_current(__i) { }
1060
1061 // Allow iterator to const_iterator conversion
1062#if __cplusplus >= 201103L
1063# ifdef __glibcxx_concepts
1064 template<typename _Iter> requires std::is_convertible_v<_Iter, _Iterator>
1065# else
1066 template<typename _Iter, typename = __convertible_from<_Iter>>
1067# endif
1068 [[__gnu__::__always_inline__]]
1069 constexpr
1070 __normal_iterator(const __normal_iterator<_Iter, _Container>& __i)
1071 noexcept
1072#else
1073 // N.B. _Container::pointer is not actually in container requirements,
1074 // but is present in std::vector and std::basic_string.
1075 template<typename _Iter>
1076 __attribute__((__always_inline__))
1077 __normal_iterator(const __normal_iterator<_Iter,
1078 typename __enable_if<
1079 (std::__are_same<_Iter, typename _Container::pointer>::__value),
1080 _Container>::__type>& __i)
1081#endif
1082 : _M_current(__i.base()) { }
1083
1084 // Forward iterator requirements
1085
1086 _GLIBCXX_NODISCARD __attribute__((__always_inline__))
1087 _GLIBCXX_CONSTEXPR
1088 reference
1089 operator*() const _GLIBCXX_NOEXCEPT
1090 { return *_M_current; }
1091
1092 _GLIBCXX_NODISCARD __attribute__((__always_inline__))
1093 _GLIBCXX_CONSTEXPR
1094 pointer
1095 operator->() const _GLIBCXX_NOEXCEPT
1096 { return _M_current; }
1097
1098 __attribute__((__always_inline__))
1099 _GLIBCXX14_CONSTEXPR
1100 __normal_iterator&
1101 operator++() _GLIBCXX_NOEXCEPT
1102 {
1103 ++_M_current;
1104 return *this;
1105 }
1106
1107 __attribute__((__always_inline__))
1108 _GLIBCXX14_CONSTEXPR
1109 __normal_iterator
1110 operator++(int) _GLIBCXX_NOEXCEPT
1111 { return __normal_iterator(_M_current++); }
1112
1113 // Bidirectional iterator requirements
1114
1115 __attribute__((__always_inline__))
1116 _GLIBCXX14_CONSTEXPR
1117 __normal_iterator&
1118 operator--() _GLIBCXX_NOEXCEPT
1119 {
1120 --_M_current;
1121 return *this;
1122 }
1123
1124 __attribute__((__always_inline__))
1125 _GLIBCXX14_CONSTEXPR
1126 __normal_iterator
1127 operator--(int) _GLIBCXX_NOEXCEPT
1128 { return __normal_iterator(_M_current--); }
1129
1130 // Random access iterator requirements
1131
1132 _GLIBCXX_NODISCARD __attribute__((__always_inline__))
1133 _GLIBCXX_CONSTEXPR
1134 reference
1135 operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
1136 { return _M_current[__n]; }
1137
1138 __attribute__((__always_inline__))
1139 _GLIBCXX14_CONSTEXPR
1140 __normal_iterator&
1141 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
1142 { _M_current += __n; return *this; }
1143
1144 _GLIBCXX_NODISCARD __attribute__((__always_inline__))
1145 _GLIBCXX_CONSTEXPR
1146 __normal_iterator
1147 operator+(difference_type __n) const _GLIBCXX_NOEXCEPT
1148 { return __normal_iterator(_M_current + __n); }
1149
1150 __attribute__((__always_inline__))
1151 _GLIBCXX14_CONSTEXPR
1152 __normal_iterator&
1153 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
1154 { _M_current -= __n; return *this; }
1155
1156 _GLIBCXX_NODISCARD __attribute__((__always_inline__))
1157 _GLIBCXX_CONSTEXPR
1158 __normal_iterator
1159 operator-(difference_type __n) const _GLIBCXX_NOEXCEPT
1160 { return __normal_iterator(_M_current - __n); }
1161
1162 _GLIBCXX_NODISCARD __attribute__((__always_inline__))
1163 _GLIBCXX_CONSTEXPR
1164 const _Iterator&
1165 base() const _GLIBCXX_NOEXCEPT
1166 { return _M_current; }
1167
1168 private:
1169 // Note: In what follows, the left- and right-hand-side iterators are
1170 // allowed to vary in types (conceptually in cv-qualification) so that
1171 // comparison between cv-qualified and non-cv-qualified iterators be
1172 // valid. However, the greedy and unfriendly operators in std::rel_ops
1173 // will make overload resolution ambiguous (when in scope) if we don't
1174 // provide overloads whose operands are of the same type. Can someone
1175 // remind me what generic programming is about? -- Gaby
1176
1177#ifdef __cpp_lib_three_way_comparison
1178 template<typename _Iter>
1179 [[nodiscard, __gnu__::__always_inline__]]
1180 friend
1181 constexpr bool
1182 operator==(const __normal_iterator& __lhs,
1183 const __normal_iterator<_Iter, _Container>& __rhs)
1184 noexcept(noexcept(__lhs.base() == __rhs.base()))
1185 requires requires {
1186 { __lhs.base() == __rhs.base() } -> std::convertible_to<bool>;
1187 }
1188 { return __lhs.base() == __rhs.base(); }
1189
1190 [[nodiscard, __gnu__::__always_inline__]]
1191 friend
1192 constexpr bool
1193 operator==(const __normal_iterator& __lhs, const __normal_iterator& __rhs)
1194 noexcept(noexcept(__lhs.base() == __rhs.base()))
1195 requires requires {
1196 { __lhs.base() == __rhs.base() } -> std::convertible_to<bool>;
1197 }
1198 { return __lhs.base() == __rhs.base(); }
1199
1200 template<typename _Iter>
1201 [[nodiscard, __gnu__::__always_inline__]]
1202 friend
1203 constexpr std::__detail::__synth3way_t<_Iterator, _Iter>
1204 operator<=>(const __normal_iterator& __lhs,
1205 const __normal_iterator<_Iter, _Container>& __rhs)
1206 noexcept(noexcept(std::__detail::__synth3way(__lhs.base(), __rhs.base())))
1207 requires requires {
1208 std::__detail::__synth3way(__lhs.base(), __rhs.base());
1209 }
1210 { return std::__detail::__synth3way(__lhs.base(), __rhs.base()); }
1211#else
1212 // Forward iterator requirements
1213 template<typename _Iter>
1214 _GLIBCXX_NODISCARD __attribute__((__always_inline__))
1215 friend
1216 _GLIBCXX_CONSTEXPR
1217 bool
1218 operator==(const __normal_iterator& __lhs,
1219 const __normal_iterator<_Iter, _Container>& __rhs)
1220 _GLIBCXX_NOEXCEPT
1221 { return __lhs.base() == __rhs.base(); }
1222
1223 _GLIBCXX_NODISCARD __attribute__((__always_inline__))
1224 friend
1225 _GLIBCXX_CONSTEXPR
1226 bool
1227 operator==(const __normal_iterator& __lhs, const __normal_iterator& __rhs)
1228 _GLIBCXX_NOEXCEPT
1229 { return __lhs.base() == __rhs.base(); }
1230
1231 template<typename _Iter>
1232 _GLIBCXX_NODISCARD __attribute__((__always_inline__))
1233 friend
1234 _GLIBCXX_CONSTEXPR
1235 bool
1236 operator!=(const __normal_iterator& __lhs,
1237 const __normal_iterator<_Iter, _Container>& __rhs)
1238 _GLIBCXX_NOEXCEPT
1239 { return __lhs.base() != __rhs.base(); }
1240
1241 _GLIBCXX_NODISCARD __attribute__((__always_inline__))
1242 friend
1243 _GLIBCXX_CONSTEXPR
1244 bool
1245 operator!=(const __normal_iterator& __lhs, const __normal_iterator& __rhs)
1246 _GLIBCXX_NOEXCEPT
1247 { return __lhs.base() != __rhs.base(); }
1248
1249 // Random access iterator requirements
1250 template<typename _Iter>
1251 _GLIBCXX_NODISCARD __attribute__((__always_inline__))
1252 friend
1253 _GLIBCXX_CONSTEXPR
1254 inline bool
1255 operator<(const __normal_iterator& __lhs,
1256 const __normal_iterator<_Iter, _Container>& __rhs)
1257 _GLIBCXX_NOEXCEPT
1258 { return __lhs.base() < __rhs.base(); }
1259
1260 _GLIBCXX_NODISCARD __attribute__((__always_inline__))
1261 friend
1262 _GLIBCXX20_CONSTEXPR
1263 bool
1264 operator<(const __normal_iterator& __lhs, const __normal_iterator& __rhs)
1265 _GLIBCXX_NOEXCEPT
1266 { return __lhs.base() < __rhs.base(); }
1267
1268 template<typename _Iter>
1269 _GLIBCXX_NODISCARD __attribute__((__always_inline__))
1270 friend
1271 _GLIBCXX_CONSTEXPR
1272 bool
1273 operator>(const __normal_iterator& __lhs,
1274 const __normal_iterator<_Iter, _Container>& __rhs)
1275 _GLIBCXX_NOEXCEPT
1276 { return __lhs.base() > __rhs.base(); }
1277
1278 _GLIBCXX_NODISCARD __attribute__((__always_inline__))
1279 friend
1280 _GLIBCXX_CONSTEXPR
1281 bool
1282 operator>(const __normal_iterator& __lhs, const __normal_iterator& __rhs)
1283 _GLIBCXX_NOEXCEPT
1284 { return __lhs.base() > __rhs.base(); }
1285
1286 template<typename _Iter>
1287 _GLIBCXX_NODISCARD __attribute__((__always_inline__))
1288 friend
1289 _GLIBCXX_CONSTEXPR
1290 bool
1291 operator<=(const __normal_iterator& __lhs,
1292 const __normal_iterator<_Iter, _Container>& __rhs)
1293 _GLIBCXX_NOEXCEPT
1294 { return __lhs.base() <= __rhs.base(); }
1295
1296 _GLIBCXX_NODISCARD __attribute__((__always_inline__))
1297 friend
1298 _GLIBCXX_CONSTEXPR
1299 bool
1300 operator<=(const __normal_iterator& __lhs, const __normal_iterator& __rhs)
1301 _GLIBCXX_NOEXCEPT
1302 { return __lhs.base() <= __rhs.base(); }
1303
1304 template<typename _Iter>
1305 _GLIBCXX_NODISCARD __attribute__((__always_inline__))
1306 friend
1307 _GLIBCXX_CONSTEXPR
1308 bool
1309 operator>=(const __normal_iterator& __lhs,
1310 const __normal_iterator<_Iter, _Container>& __rhs)
1311 _GLIBCXX_NOEXCEPT
1312 { return __lhs.base() >= __rhs.base(); }
1313
1314 _GLIBCXX_NODISCARD __attribute__((__always_inline__))
1315 friend
1316 _GLIBCXX_CONSTEXPR
1317 bool
1318 operator>=(const __normal_iterator& __lhs, const __normal_iterator& __rhs)
1319 _GLIBCXX_NOEXCEPT
1320 { return __lhs.base() >= __rhs.base(); }
1321#endif // three-way comparison
1322
1323 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1324 // 179. Comparison of const_iterators to iterators doesn't work
1325 // According to the resolution of DR179 not only the various comparison
1326 // operators but also operator- must accept mixed iterator/const_iterator
1327 // parameters.
1328 template<typename _Iter>
1329#if __cplusplus >= 201103L
1330 [[__nodiscard__, __gnu__::__always_inline__]]
1331 friend
1332 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1333 // 685. reverse_iterator/move_iterator difference has invalid signatures
1334 constexpr auto
1335 operator-(const __normal_iterator& __lhs,
1336 const __normal_iterator<_Iter, _Container>& __rhs) noexcept
1337 -> decltype(__lhs.base() - __rhs.base())
1338#else
1339 friend
1340 difference_type
1341 operator-(const __normal_iterator& __lhs,
1342 const __normal_iterator<_Iter, _Container>& __rhs)
1343#endif
1344 { return __lhs.base() - __rhs.base(); }
1345
1346 _GLIBCXX_NODISCARD __attribute__((__always_inline__))
1347 friend
1348 _GLIBCXX_CONSTEXPR
1349 difference_type
1350 operator-(const __normal_iterator& __lhs, const __normal_iterator& __rhs)
1351 _GLIBCXX_NOEXCEPT
1352 { return __lhs.base() - __rhs.base(); }
1353
1354 _GLIBCXX_NODISCARD __attribute__((__always_inline__))
1355 friend
1356 _GLIBCXX_CONSTEXPR
1357 __normal_iterator
1358 operator+(difference_type __n, const __normal_iterator& __i)
1359 _GLIBCXX_NOEXCEPT
1360 { return __normal_iterator(__i.base() + __n); }
1361 };
1362
1363_GLIBCXX_END_NAMESPACE_VERSION
1364} // namespace __gnu_cxx
1365
1366namespace std _GLIBCXX_VISIBILITY(default)
1367{
1368_GLIBCXX_BEGIN_NAMESPACE_VERSION
1369
1370#if __cplusplus >= 201103L
1371 /**
1372 * @addtogroup iterators
1373 * @{
1374 */
1375
1376#ifdef __glibcxx_ranges
1377 /// A sentinel adaptor for use with std::move_iterator.
1378 template<semiregular _Sent>
1379 class move_sentinel
1380 {
1381 public:
1382 constexpr
1383 move_sentinel()
1384 noexcept(is_nothrow_default_constructible_v<_Sent>)
1385 : _M_last() { }
1386
1387 constexpr explicit
1388 move_sentinel(_Sent __s)
1389 noexcept(is_nothrow_move_constructible_v<_Sent>)
1390 : _M_last(std::move(__s)) { }
1391
1392 template<typename _S2> requires convertible_to<const _S2&, _Sent>
1393 constexpr
1394 move_sentinel(const move_sentinel<_S2>& __s)
1395 noexcept(is_nothrow_constructible_v<_Sent, const _S2&>)
1396 : _M_last(__s.base())
1397 { }
1398
1399 template<typename _S2> requires assignable_from<_Sent&, const _S2&>
1400 constexpr move_sentinel&
1401 operator=(const move_sentinel<_S2>& __s)
1402 noexcept(is_nothrow_assignable_v<_Sent, const _S2&>)
1403 {
1404 _M_last = __s.base();
1405 return *this;
1406 }
1407
1408 [[nodiscard]]
1409 constexpr _Sent
1410 base() const
1411 noexcept(is_nothrow_copy_constructible_v<_Sent>)
1412 { return _M_last; }
1413
1414 private:
1415 _Sent _M_last;
1416 };
1417
1418 /// @cond undocumented
1419 namespace __detail
1420 {
1421 template<typename _Iterator>
1422 struct __move_iter_cat
1423 { };
1424
1425 template<typename _Iterator>
1426 requires requires { typename __iter_category_t<_Iterator>; }
1427 struct __move_iter_cat<_Iterator>
1428 {
1429 using iterator_category
1430 = __clamp_iter_cat<__iter_category_t<_Iterator>,
1431 random_access_iterator_tag>;
1432 };
1433 }
1434 /// @endcond
1435#endif // ranges
1436
1437 // 24.4.3 Move iterators
1438 /** @brief An iterator adaptor that yields an rvalue reference.
1439 *
1440 * Class template move_iterator is an iterator adapter with the same
1441 * behavior as the underlying iterator except that its dereference
1442 * operator implicitly converts the value returned by the underlying
1443 * iterator's dereference operator to an rvalue reference. Some
1444 * generic algorithms can be called with move iterators to replace
1445 * copying with moving.
1446 */
1447 template<typename _Iterator>
1448 class move_iterator
1449#ifdef __glibcxx_ranges
1450 : public __detail::__move_iter_cat<_Iterator>
1451#endif
1452 {
1453 _Iterator _M_current;
1454
1455 using __traits_type = iterator_traits<_Iterator>;
1456#ifndef __glibcxx_ranges
1457 using __base_ref = typename __traits_type::reference;
1458#endif
1459
1460 template<typename _Iter2>
1461 friend class move_iterator;
1462
1463#ifdef __glibcxx_concepts // C++20 && concepts
1464 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1465 // 3435. three_way_comparable_with<reverse_iterator<int*>, [...]>
1466 template<typename _Iter2>
1467 static constexpr bool __convertible = !is_same_v<_Iter2, _Iterator>
1468 && convertible_to<const _Iter2&, _Iterator>;
1469#endif
1470
1471#ifdef __glibcxx_ranges
1472 static auto
1473 _S_iter_concept()
1474 {
1475 if constexpr (random_access_iterator<_Iterator>)
1476 return random_access_iterator_tag{};
1477 else if constexpr (bidirectional_iterator<_Iterator>)
1478 return bidirectional_iterator_tag{};
1479 else if constexpr (forward_iterator<_Iterator>)
1480 return forward_iterator_tag{};
1481 else
1482 return input_iterator_tag{};
1483 }
1484#endif
1485
1486 public:
1487 using iterator_type = _Iterator;
1488
1489#ifdef __glibcxx_move_iterator_concept // C++ >= 20 && lib_concepts
1490 using iterator_concept = decltype(_S_iter_concept());
1491
1492 // iterator_category defined in __move_iter_cat
1493 using value_type = iter_value_t<_Iterator>;
1494 using difference_type = iter_difference_t<_Iterator>;
1495 using pointer = _Iterator;
1496 using reference = iter_rvalue_reference_t<_Iterator>;
1497#else
1498 typedef typename __traits_type::iterator_category iterator_category;
1499 typedef typename __traits_type::value_type value_type;
1500 typedef typename __traits_type::difference_type difference_type;
1501 // NB: DR 680.
1502 typedef _Iterator pointer;
1503 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1504 // 2106. move_iterator wrapping iterators returning prvalues
1505 using reference
1506 = __conditional_t<is_reference<__base_ref>::value,
1507 typename remove_reference<__base_ref>::type&&,
1508 __base_ref>;
1509#endif
1510
1511 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1512 // 4125. move_iterator's default constructor should be constrained
1513 _GLIBCXX17_CONSTEXPR
1514 move_iterator()
1515#ifdef __glibcxx_concepts
1516 requires default_initializable<_Iterator>
1517#endif
1518 : _M_current() { }
1519
1520 explicit _GLIBCXX17_CONSTEXPR
1521 move_iterator(iterator_type __i)
1522 : _M_current(std::move(__i)) { }
1523
1524 template<typename _Iter>
1525#ifdef __glibcxx_concepts
1526 requires __convertible<_Iter>
1527#endif
1528 _GLIBCXX17_CONSTEXPR
1529 move_iterator(const move_iterator<_Iter>& __i)
1530 : _M_current(__i._M_current) { }
1531
1532 template<typename _Iter>
1533#ifdef __glibcxx_concepts
1534 requires __convertible<_Iter>
1535 && assignable_from<_Iterator&, const _Iter&>
1536#endif
1537 _GLIBCXX17_CONSTEXPR
1538 move_iterator& operator=(const move_iterator<_Iter>& __i)
1539 {
1540 _M_current = __i._M_current;
1541 return *this;
1542 }
1543
1544#if __cplusplus <= 201703L
1545 [[__nodiscard__]]
1546 _GLIBCXX17_CONSTEXPR iterator_type
1547 base() const
1548 { return _M_current; }
1549#else
1550 [[nodiscard]]
1551 constexpr const iterator_type&
1552 base() const & noexcept
1553 { return _M_current; }
1554
1555 [[nodiscard]]
1556 constexpr iterator_type
1557 base() &&
1558 { return std::move(_M_current); }
1559#endif
1560
1561 [[__nodiscard__]]
1562 _GLIBCXX17_CONSTEXPR reference
1563 operator*() const
1564#ifdef __glibcxx_ranges
1565 { return ranges::iter_move(_M_current); }
1566#else
1567 { return static_cast<reference>(*_M_current); }
1568#endif
1569
1570 [[__nodiscard__]]
1571 _GLIBCXX17_CONSTEXPR pointer
1572 operator->() const
1573 { return _M_current; }
1574
1575 _GLIBCXX17_CONSTEXPR move_iterator&
1576 operator++()
1577 {
1578 ++_M_current;
1579 return *this;
1580 }
1581
1582 _GLIBCXX17_CONSTEXPR move_iterator
1583 operator++(int)
1584 {
1585 move_iterator __tmp = *this;
1586 ++_M_current;
1587 return __tmp;
1588 }
1589
1590#ifdef __glibcxx_concepts
1591 constexpr void
1592 operator++(int) requires (!forward_iterator<_Iterator>)
1593 { ++_M_current; }
1594#endif
1595
1596 _GLIBCXX17_CONSTEXPR move_iterator&
1597 operator--()
1598 {
1599 --_M_current;
1600 return *this;
1601 }
1602
1603 _GLIBCXX17_CONSTEXPR move_iterator
1604 operator--(int)
1605 {
1606 move_iterator __tmp = *this;
1607 --_M_current;
1608 return __tmp;
1609 }
1610
1611 [[__nodiscard__]]
1612 _GLIBCXX17_CONSTEXPR move_iterator
1613 operator+(difference_type __n) const
1614 { return move_iterator(_M_current + __n); }
1615
1616 _GLIBCXX17_CONSTEXPR move_iterator&
1617 operator+=(difference_type __n)
1618 {
1619 _M_current += __n;
1620 return *this;
1621 }
1622
1623 [[__nodiscard__]]
1624 _GLIBCXX17_CONSTEXPR move_iterator
1625 operator-(difference_type __n) const
1626 { return move_iterator(_M_current - __n); }
1627
1628 _GLIBCXX17_CONSTEXPR move_iterator&
1629 operator-=(difference_type __n)
1630 {
1631 _M_current -= __n;
1632 return *this;
1633 }
1634
1635 [[__nodiscard__]]
1636 _GLIBCXX17_CONSTEXPR reference
1637 operator[](difference_type __n) const
1638#ifdef __glibcxx_ranges
1639 { return ranges::iter_move(_M_current + __n); }
1640#else
1641 { return std::move(_M_current[__n]); }
1642#endif
1643
1644#ifdef __glibcxx_ranges
1645 template<sentinel_for<_Iterator> _Sent>
1646 [[nodiscard]]
1647 friend constexpr bool
1648 operator==(const move_iterator& __x, const move_sentinel<_Sent>& __y)
1649 { return __x.base() == __y.base(); }
1650
1651 template<sized_sentinel_for<_Iterator> _Sent>
1652 [[nodiscard]]
1653 friend constexpr iter_difference_t<_Iterator>
1654 operator-(const move_sentinel<_Sent>& __x, const move_iterator& __y)
1655 { return __x.base() - __y.base(); }
1656
1657 template<sized_sentinel_for<_Iterator> _Sent>
1658 [[nodiscard]]
1659 friend constexpr iter_difference_t<_Iterator>
1660 operator-(const move_iterator& __x, const move_sentinel<_Sent>& __y)
1661 { return __x.base() - __y.base(); }
1662
1663 [[nodiscard]]
1664 friend constexpr iter_rvalue_reference_t<_Iterator>
1665 iter_move(const move_iterator& __i)
1666 noexcept(noexcept(ranges::iter_move(__i._M_current)))
1667 { return ranges::iter_move(__i._M_current); }
1668
1669 template<indirectly_swappable<_Iterator> _Iter2>
1670 friend constexpr void
1671 iter_swap(const move_iterator& __x, const move_iterator<_Iter2>& __y)
1672 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1673 { return ranges::iter_swap(__x._M_current, __y._M_current); }
1674#endif // C++20
1675 };
1676
1677 template<typename _IteratorL, typename _IteratorR>
1678 [[__nodiscard__]]
1679 inline _GLIBCXX17_CONSTEXPR bool
1680 operator==(const move_iterator<_IteratorL>& __x,
1681 const move_iterator<_IteratorR>& __y)
1682#ifdef __glibcxx_concepts
1683 requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
1684#endif
1685 { return __x.base() == __y.base(); }
1686
1687#ifdef __cpp_lib_three_way_comparison
1688 template<typename _IteratorL,
1689 three_way_comparable_with<_IteratorL> _IteratorR>
1690 [[__nodiscard__]]
1691 constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
1692 operator<=>(const move_iterator<_IteratorL>& __x,
1693 const move_iterator<_IteratorR>& __y)
1694 { return __x.base() <=> __y.base(); }
1695#else
1696 template<typename _IteratorL, typename _IteratorR>
1697 [[__nodiscard__]]
1698 inline _GLIBCXX17_CONSTEXPR bool
1699 operator!=(const move_iterator<_IteratorL>& __x,
1700 const move_iterator<_IteratorR>& __y)
1701 { return !(__x == __y); }
1702#endif
1703
1704 template<typename _IteratorL, typename _IteratorR>
1705 [[__nodiscard__]]
1706 inline _GLIBCXX17_CONSTEXPR bool
1707 operator<(const move_iterator<_IteratorL>& __x,
1708 const move_iterator<_IteratorR>& __y)
1709#ifdef __glibcxx_concepts
1710 requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1711#endif
1712 { return __x.base() < __y.base(); }
1713
1714 template<typename _IteratorL, typename _IteratorR>
1715 [[__nodiscard__]]
1716 inline _GLIBCXX17_CONSTEXPR bool
1717 operator<=(const move_iterator<_IteratorL>& __x,
1718 const move_iterator<_IteratorR>& __y)
1719#ifdef __glibcxx_concepts
1720 requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1721#endif
1722 { return !(__y < __x); }
1723
1724 template<typename _IteratorL, typename _IteratorR>
1725 [[__nodiscard__]]
1726 inline _GLIBCXX17_CONSTEXPR bool
1727 operator>(const move_iterator<_IteratorL>& __x,
1728 const move_iterator<_IteratorR>& __y)
1729#ifdef __glibcxx_concepts
1730 requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1731#endif
1732 { return __y < __x; }
1733
1734 template<typename _IteratorL, typename _IteratorR>
1735 [[__nodiscard__]]
1736 inline _GLIBCXX17_CONSTEXPR bool
1737 operator>=(const move_iterator<_IteratorL>& __x,
1738 const move_iterator<_IteratorR>& __y)
1739#ifdef __glibcxx_concepts
1740 requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1741#endif
1742 { return !(__x < __y); }
1743
1744 // Note: See __normal_iterator operators note from Gaby to understand
1745 // why we have these extra overloads for some move_iterator operators.
1746
1747 template<typename _Iterator>
1748 [[__nodiscard__]]
1749 inline _GLIBCXX17_CONSTEXPR bool
1750 operator==(const move_iterator<_Iterator>& __x,
1751 const move_iterator<_Iterator>& __y)
1752 // N.B. No constraints, x.base() == y.base() is always well-formed.
1753 { return __x.base() == __y.base(); }
1754
1755#ifdef __cpp_lib_three_way_comparison
1756 template<three_way_comparable _Iterator>
1757 [[__nodiscard__]]
1758 constexpr compare_three_way_result_t<_Iterator>
1759 operator<=>(const move_iterator<_Iterator>& __x,
1760 const move_iterator<_Iterator>& __y)
1761 { return __x.base() <=> __y.base(); }
1762#else
1763 template<typename _Iterator>
1764 [[__nodiscard__]]
1765 inline _GLIBCXX17_CONSTEXPR bool
1766 operator!=(const move_iterator<_Iterator>& __x,
1767 const move_iterator<_Iterator>& __y)
1768 { return !(__x == __y); }
1769
1770 template<typename _Iterator>
1771 [[__nodiscard__]]
1772 inline _GLIBCXX17_CONSTEXPR bool
1773 operator<(const move_iterator<_Iterator>& __x,
1774 const move_iterator<_Iterator>& __y)
1775 { return __x.base() < __y.base(); }
1776
1777 template<typename _Iterator>
1778 [[__nodiscard__]]
1779 inline _GLIBCXX17_CONSTEXPR bool
1780 operator<=(const move_iterator<_Iterator>& __x,
1781 const move_iterator<_Iterator>& __y)
1782 { return !(__y < __x); }
1783
1784 template<typename _Iterator>
1785 [[__nodiscard__]]
1786 inline _GLIBCXX17_CONSTEXPR bool
1787 operator>(const move_iterator<_Iterator>& __x,
1788 const move_iterator<_Iterator>& __y)
1789 { return __y < __x; }
1790
1791 template<typename _Iterator>
1792 [[__nodiscard__]]
1793 inline _GLIBCXX17_CONSTEXPR bool
1794 operator>=(const move_iterator<_Iterator>& __x,
1795 const move_iterator<_Iterator>& __y)
1796 { return !(__x < __y); }
1797#endif // ! C++20
1798
1799 // DR 685.
1800 template<typename _IteratorL, typename _IteratorR>
1801 [[__nodiscard__]]
1802 inline _GLIBCXX17_CONSTEXPR auto
1803 operator-(const move_iterator<_IteratorL>& __x,
1804 const move_iterator<_IteratorR>& __y)
1805 -> decltype(__x.base() - __y.base())
1806 { return __x.base() - __y.base(); }
1807
1808 template<typename _Iterator>
1809 [[__nodiscard__]]
1810 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1811 operator+(typename move_iterator<_Iterator>::difference_type __n,
1812 const move_iterator<_Iterator>& __x)
1813#ifdef __glibcxx_concepts
1814 requires requires { { __x.base() + __n } -> same_as<_Iterator>; }
1815#endif
1816 { return __x + __n; }
1817
1818 template<typename _Iterator>
1819 [[__nodiscard__]]
1820 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1821 make_move_iterator(_Iterator __i)
1822 { return move_iterator<_Iterator>(std::move(__i)); }
1823
1824 template<typename _Iterator, typename _ReturnType
1825 = __conditional_t<__move_if_noexcept_cond
1826 <typename iterator_traits<_Iterator>::value_type>::value,
1827 _Iterator, move_iterator<_Iterator>>>
1828 [[__nodiscard__]]
1829 constexpr _ReturnType
1830 __make_move_if_noexcept_iterator(_Iterator __i)
1831 { return _ReturnType(__i); }
1832
1833 // Overload for pointers that matches std::move_if_noexcept more closely,
1834 // returning a constant iterator when we don't want to move.
1835 template<typename _Tp, typename _ReturnType
1836 = __conditional_t<__move_if_noexcept_cond<_Tp>::value,
1837 const _Tp*, move_iterator<_Tp*>>>
1838 [[__nodiscard__]]
1839 constexpr _ReturnType
1840 __make_move_if_noexcept_iterator(_Tp* __i)
1841 { return _ReturnType(__i); }
1842
1843 template<typename _Iterator>
1844 struct __is_move_iterator<move_iterator<_Iterator> >
1845 {
1846 enum { __value = 1 };
1847 typedef __true_type __type;
1848 };
1849
1850#define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
1851#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
1852 std::__make_move_if_noexcept_iterator(_Iter)
1853#else
1854#define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
1855#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
1856#endif // C++11
1857
1858#ifdef __glibcxx_ranges
1859 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1860 // 3736. move_iterator missing disable_sized_sentinel_for specialization
1861 template<typename _Iterator1, typename _Iterator2>
1862 requires (!sized_sentinel_for<_Iterator1, _Iterator2>)
1863 inline constexpr bool
1864 disable_sized_sentinel_for<move_iterator<_Iterator1>,
1865 move_iterator<_Iterator2>> = true;
1866
1867 // [iterators.common] Common iterators
1868
1869 /// @cond undocumented
1870 namespace __detail
1871 {
1872 template<typename _It>
1873 concept __common_iter_has_arrow = indirectly_readable<const _It>
1874 && (requires(const _It& __it) { __it.operator->(); }
1875 || is_reference_v<iter_reference_t<_It>>
1876 || constructible_from<iter_value_t<_It>, iter_reference_t<_It>>);
1877
1878 template<typename _It>
1879 concept __common_iter_use_postfix_proxy
1880 = (!requires (_It& __i) { { *__i++ } -> __can_reference; })
1881 && constructible_from<iter_value_t<_It>, iter_reference_t<_It>>
1882 && move_constructible<iter_value_t<_It>>;
1883 } // namespace __detail
1884 /// @endcond
1885
1886 /// An iterator/sentinel adaptor for representing a non-common range.
1887 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1888 requires (!same_as<_It, _Sent>) && copyable<_It>
1889 class common_iterator
1890 {
1891 template<typename _Tp, typename _Up>
1892 static constexpr bool
1893 _S_noexcept1()
1894 {
1895 if constexpr (is_trivially_default_constructible_v<_Tp>)
1896 return is_nothrow_assignable_v<_Tp&, _Up>;
1897 else
1898 return is_nothrow_constructible_v<_Tp, _Up>;
1899 }
1900
1901 template<typename _It2, typename _Sent2>
1902 static constexpr bool
1903 _S_noexcept()
1904 { return _S_noexcept1<_It, _It2>() && _S_noexcept1<_Sent, _Sent2>(); }
1905
1906 class __arrow_proxy
1907 {
1908 iter_value_t<_It> _M_keep;
1909
1910 constexpr
1911 __arrow_proxy(iter_reference_t<_It>&& __x)
1912 : _M_keep(std::move(__x)) { }
1913
1914 friend class common_iterator;
1915
1916 public:
1917 constexpr const iter_value_t<_It>*
1918 operator->() const noexcept
1919 { return std::__addressof(_M_keep); }
1920 };
1921
1922 class __postfix_proxy
1923 {
1924 iter_value_t<_It> _M_keep;
1925
1926 constexpr
1927 __postfix_proxy(iter_reference_t<_It>&& __x)
1928 : _M_keep(std::forward<iter_reference_t<_It>>(__x)) { }
1929
1930 friend class common_iterator;
1931
1932 public:
1933 constexpr const iter_value_t<_It>&
1934 operator*() const noexcept
1935 { return _M_keep; }
1936 };
1937
1938 public:
1939 constexpr
1940 common_iterator()
1941 noexcept(is_nothrow_default_constructible_v<_It>)
1942 requires default_initializable<_It>
1943 : _M_it(), _M_index(0)
1944 { }
1945
1946 constexpr
1947 common_iterator(_It __i)
1948 noexcept(is_nothrow_move_constructible_v<_It>)
1949 : _M_it(std::move(__i)), _M_index(0)
1950 { }
1951
1952 constexpr
1953 common_iterator(_Sent __s)
1954 noexcept(is_nothrow_move_constructible_v<_Sent>)
1955 : _M_sent(std::move(__s)), _M_index(1)
1956 { }
1957
1958 template<typename _It2, typename _Sent2>
1959 requires convertible_to<const _It2&, _It>
1960 && convertible_to<const _Sent2&, _Sent>
1961 constexpr
1962 common_iterator(const common_iterator<_It2, _Sent2>& __x)
1963 noexcept(_S_noexcept<const _It2&, const _Sent2&>())
1964 : _M_valueless(), _M_index(__x._M_index)
1965 {
1966 __glibcxx_assert(__x._M_has_value());
1967 if (_M_index == 0)
1968 {
1969 if constexpr (is_trivially_default_constructible_v<_It>)
1970 _M_it = std::move(__x._M_it);
1971 else
1972 std::construct_at(std::__addressof(_M_it), __x._M_it);
1973 }
1974 else if (_M_index == 1)
1975 {
1976 if constexpr (is_trivially_default_constructible_v<_Sent>)
1977 _M_sent = std::move(__x._M_sent);
1978 else
1979 std::construct_at(std::__addressof(_M_sent), __x._M_sent);
1980 }
1981 }
1982
1983 common_iterator(const common_iterator&) = default;
1984
1985 constexpr
1986 common_iterator(const common_iterator& __x)
1987 noexcept(_S_noexcept<const _It&, const _Sent&>())
1988 requires (!is_trivially_copyable_v<_It> || !is_trivially_copyable_v<_Sent>)
1989 : _M_valueless(), _M_index(__x._M_index)
1990 {
1991 if (_M_index == 0)
1992 {
1993 if constexpr (is_trivially_default_constructible_v<_It>)
1994 _M_it = __x._M_it;
1995 else
1996 std::construct_at(std::__addressof(_M_it), __x._M_it);
1997 }
1998 else if (_M_index == 1)
1999 {
2000 if constexpr (is_trivially_default_constructible_v<_Sent>)
2001 _M_sent = __x._M_sent;
2002 else
2003 std::construct_at(std::__addressof(_M_sent), __x._M_sent);
2004 }
2005 }
2006
2007 common_iterator(common_iterator&&) = default;
2008
2009 constexpr
2010 common_iterator(common_iterator&& __x)
2011 noexcept(_S_noexcept<_It, _Sent>())
2012 requires (!is_trivially_copyable_v<_It> || !is_trivially_copyable_v<_Sent>)
2013 : _M_valueless(), _M_index(__x._M_index)
2014 {
2015 if (_M_index == 0)
2016 {
2017 if constexpr (is_trivially_default_constructible_v<_It>)
2018 _M_it = std::move(__x._M_it);
2019 else
2020 std::construct_at(std::__addressof(_M_it), std::move(__x._M_it));
2021 }
2022 else if (_M_index == 1)
2023 {
2024 if constexpr (is_trivially_default_constructible_v<_Sent>)
2025 _M_sent = std::move(__x._M_sent);
2026 else
2027 std::construct_at(std::__addressof(_M_sent),
2028 std::move(__x._M_sent));
2029 }
2030 }
2031
2032 constexpr common_iterator&
2033 operator=(const common_iterator&) = default;
2034
2035 constexpr common_iterator&
2036 operator=(const common_iterator& __x)
2037 noexcept(is_nothrow_copy_assignable_v<_It>
2038 && is_nothrow_copy_assignable_v<_Sent>
2039 && is_nothrow_copy_constructible_v<_It>
2040 && is_nothrow_copy_constructible_v<_Sent>)
2041 requires (!is_trivially_copy_assignable_v<_It>
2042 || !is_trivially_copy_assignable_v<_Sent>)
2043 {
2044 _M_assign(__x);
2045 return *this;
2046 }
2047
2048 constexpr common_iterator&
2049 operator=(common_iterator&&) = default;
2050
2051 constexpr common_iterator&
2052 operator=(common_iterator&& __x)
2053 noexcept(is_nothrow_move_assignable_v<_It>
2054 && is_nothrow_move_assignable_v<_Sent>
2055 && is_nothrow_move_constructible_v<_It>
2056 && is_nothrow_move_constructible_v<_Sent>)
2057 requires (!is_trivially_move_assignable_v<_It>
2058 || !is_trivially_move_assignable_v<_Sent>)
2059 {
2060 _M_assign(std::move(__x));
2061 return *this;
2062 }
2063
2064 template<typename _It2, typename _Sent2>
2065 requires convertible_to<const _It2&, _It>
2066 && convertible_to<const _Sent2&, _Sent>
2067 && assignable_from<_It&, const _It2&>
2068 && assignable_from<_Sent&, const _Sent2&>
2069 constexpr common_iterator&
2070 operator=(const common_iterator<_It2, _Sent2>& __x)
2071 noexcept(is_nothrow_constructible_v<_It, const _It2&>
2072 && is_nothrow_constructible_v<_Sent, const _Sent2&>
2073 && is_nothrow_assignable_v<_It&, const _It2&>
2074 && is_nothrow_assignable_v<_Sent&, const _Sent2&>)
2075 {
2076 __glibcxx_assert(__x._M_has_value());
2077 _M_assign(__x);
2078 return *this;
2079 }
2080
2081#if __cpp_concepts >= 202002L // Constrained special member functions
2082 ~common_iterator() = default;
2083
2084 constexpr
2085 ~common_iterator()
2086 requires (!is_trivially_destructible_v<_It>
2087 || !is_trivially_destructible_v<_Sent>)
2088#else
2089 constexpr
2090 ~common_iterator()
2091#endif
2092 {
2093 if (_M_index == 0)
2094 _M_it.~_It();
2095 else if (_M_index == 1)
2096 _M_sent.~_Sent();
2097 }
2098
2099 [[nodiscard]]
2100 constexpr decltype(auto)
2101 operator*()
2102 {
2103 __glibcxx_assert(_M_index == 0);
2104 return *_M_it;
2105 }
2106
2107 [[nodiscard]]
2108 constexpr decltype(auto)
2109 operator*() const requires __detail::__dereferenceable<const _It>
2110 {
2111 __glibcxx_assert(_M_index == 0);
2112 return *_M_it;
2113 }
2114
2115 [[nodiscard]]
2116 constexpr auto
2117 operator->() const requires __detail::__common_iter_has_arrow<_It>
2118 {
2119 __glibcxx_assert(_M_index == 0);
2120 if constexpr (is_pointer_v<_It> || requires { _M_it.operator->(); })
2121 return _M_it;
2122 else if constexpr (is_reference_v<iter_reference_t<_It>>)
2123 {
2124 auto&& __tmp = *_M_it;
2125 return std::__addressof(__tmp);
2126 }
2127 else
2128 return __arrow_proxy{*_M_it};
2129 }
2130
2131 constexpr common_iterator&
2132 operator++()
2133 {
2134 __glibcxx_assert(_M_index == 0);
2135 ++_M_it;
2136 return *this;
2137 }
2138
2139 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2140 // 3953. iter_move for common_iterator and ... should return decltype(auto)
2141 constexpr decltype(auto)
2142 operator++(int)
2143 {
2144 __glibcxx_assert(_M_index == 0);
2145 if constexpr (forward_iterator<_It>)
2146 {
2147 common_iterator __tmp = *this;
2148 ++*this;
2149 return __tmp;
2150 }
2151 else if constexpr (!__detail::__common_iter_use_postfix_proxy<_It>)
2152 return _M_it++;
2153 else
2154 {
2155 __postfix_proxy __p(**this);
2156 ++*this;
2157 return __p;
2158 }
2159 }
2160
2161 template<typename _It2, sentinel_for<_It> _Sent2>
2162 requires sentinel_for<_Sent, _It2>
2163 friend constexpr bool
2164 operator== [[nodiscard]] (const common_iterator& __x,
2165 const common_iterator<_It2, _Sent2>& __y)
2166 {
2167 switch(__x._M_index << 2 | __y._M_index)
2168 {
2169 case 0b0000:
2170 case 0b0101:
2171 return true;
2172 case 0b0001:
2173 return __x._M_it == __y._M_sent;
2174 case 0b0100:
2175 return __x._M_sent == __y._M_it;
2176 default:
2177 __glibcxx_assert(__x._M_has_value());
2178 __glibcxx_assert(__y._M_has_value());
2179 __builtin_unreachable();
2180 }
2181 }
2182
2183 template<typename _It2, sentinel_for<_It> _Sent2>
2184 requires sentinel_for<_Sent, _It2> && equality_comparable_with<_It, _It2>
2185 friend constexpr bool
2186 operator== [[nodiscard]] (const common_iterator& __x,
2187 const common_iterator<_It2, _Sent2>& __y)
2188 {
2189 switch(__x._M_index << 2 | __y._M_index)
2190 {
2191 case 0b0101:
2192 return true;
2193 case 0b0000:
2194 return __x._M_it == __y._M_it;
2195 case 0b0001:
2196 return __x._M_it == __y._M_sent;
2197 case 0b0100:
2198 return __x._M_sent == __y._M_it;
2199 default:
2200 __glibcxx_assert(__x._M_has_value());
2201 __glibcxx_assert(__y._M_has_value());
2202 __builtin_unreachable();
2203 }
2204 }
2205
2206 template<sized_sentinel_for<_It> _It2, sized_sentinel_for<_It> _Sent2>
2207 requires sized_sentinel_for<_Sent, _It2>
2208 friend constexpr iter_difference_t<_It2>
2209 operator- [[nodiscard]] (const common_iterator& __x,
2210 const common_iterator<_It2, _Sent2>& __y)
2211 {
2212 switch(__x._M_index << 2 | __y._M_index)
2213 {
2214 case 0b0101:
2215 return 0;
2216 case 0b0000:
2217 return __x._M_it - __y._M_it;
2218 case 0b0001:
2219 return __x._M_it - __y._M_sent;
2220 case 0b0100:
2221 return __x._M_sent - __y._M_it;
2222 default:
2223 __glibcxx_assert(__x._M_has_value());
2224 __glibcxx_assert(__y._M_has_value());
2225 __builtin_unreachable();
2226 }
2227 }
2228
2229 [[nodiscard]]
2230 friend constexpr iter_rvalue_reference_t<_It>
2231 iter_move(const common_iterator& __i)
2232 noexcept(noexcept(ranges::iter_move(std::declval<const _It&>())))
2233 requires input_iterator<_It>
2234 {
2235 __glibcxx_assert(__i._M_index == 0);
2236 return ranges::iter_move(__i._M_it);
2237 }
2238
2239 template<indirectly_swappable<_It> _It2, typename _Sent2>
2240 friend constexpr void
2241 iter_swap(const common_iterator& __x,
2242 const common_iterator<_It2, _Sent2>& __y)
2243 noexcept(noexcept(ranges::iter_swap(std::declval<const _It&>(),
2244 std::declval<const _It2&>())))
2245 {
2246 __glibcxx_assert(__x._M_index == 0);
2247 __glibcxx_assert(__y._M_index == 0);
2248 return ranges::iter_swap(__x._M_it, __y._M_it);
2249 }
2250
2251 private:
2252 template<input_or_output_iterator _It2, sentinel_for<_It2> _Sent2>
2253 requires (!same_as<_It2, _Sent2>) && copyable<_It2>
2254 friend class common_iterator;
2255
2256 constexpr bool
2257 _M_has_value() const noexcept { return _M_index != _S_valueless; }
2258
2259 template<typename _CIt>
2260 constexpr void
2261 _M_assign(_CIt&& __x)
2262 {
2263 if (_M_index == __x._M_index)
2264 {
2265 if (_M_index == 0)
2266 _M_it = std::forward<_CIt>(__x)._M_it;
2267 else if (_M_index == 1)
2268 _M_sent = std::forward<_CIt>(__x)._M_sent;
2269 }
2270 else
2271 {
2272 if (_M_index == 0)
2273 _M_it.~_It();
2274 else if (_M_index == 1)
2275 _M_sent.~_Sent();
2276 _M_index = _S_valueless;
2277
2278 if (__x._M_index == 0)
2279 std::construct_at(std::__addressof(_M_it),
2280 std::forward<_CIt>(__x)._M_it);
2281 else if (__x._M_index == 1)
2282 std::construct_at(std::__addressof(_M_sent),
2283 std::forward<_CIt>(__x)._M_sent);
2284 _M_index = __x._M_index;
2285 }
2286 }
2287
2288 union
2289 {
2290 _It _M_it;
2291 _Sent _M_sent;
2292 unsigned char _M_valueless;
2293 };
2294 unsigned char _M_index; // 0 == _M_it, 1 == _M_sent, 2 == valueless
2295
2296 static constexpr unsigned char _S_valueless{2};
2297 };
2298
2299 template<typename _It, typename _Sent>
2300 struct incrementable_traits<common_iterator<_It, _Sent>>
2301 {
2302 using difference_type = iter_difference_t<_It>;
2303 };
2304
2305 namespace __detail
2306 {
2307 template<typename _It, typename _Sent>
2308 struct __common_iterator_iter_cat
2309 { };
2310
2311 template<typename _It, typename _Sent>
2312 requires integral<iter_difference_t<_It>>
2313 struct __common_iterator_iter_cat<_It, _Sent>
2314 {
2315 static auto
2316 _S_iter_cat()
2317 {
2318 if constexpr (requires { requires derived_from<__iter_category_t<_It>,
2319 forward_iterator_tag>; })
2320 return forward_iterator_tag{};
2321 else
2322 return input_iterator_tag{};
2323 }
2324
2325 using iterator_category = decltype(_S_iter_cat());
2326 };
2327 } // namespace __detail
2328
2329 template<input_iterator _It, typename _Sent>
2330 struct iterator_traits<common_iterator<_It, _Sent>>
2331 : __detail::__common_iterator_iter_cat<_It, _Sent>
2332 {
2333 private:
2334 template<typename _Iter>
2335 struct __ptr
2336 {
2337 using type = void;
2338 };
2339
2340 template<typename _Iter>
2341 requires __detail::__common_iter_has_arrow<_Iter>
2342 struct __ptr<_Iter>
2343 {
2344 using _CIter = common_iterator<_Iter, _Sent>;
2345 using type = decltype(std::declval<const _CIter&>().operator->());
2346 };
2347
2348 public:
2349 using iterator_concept = __conditional_t<forward_iterator<_It>,
2350 forward_iterator_tag,
2351 input_iterator_tag>;
2352 // iterator_category defined in base __common_iterator_iter_cat
2353 using value_type = iter_value_t<_It>;
2354 using difference_type = iter_difference_t<_It>;
2355 using pointer = typename __ptr<_It>::type;
2356 using reference = iter_reference_t<_It>;
2357 };
2358
2359 // [iterators.counted] Counted iterators
2360
2361 /// @cond undocumented
2362 namespace __detail
2363 {
2364 template<typename _It>
2365 struct __counted_iter_value_type
2366 { };
2367
2368 template<indirectly_readable _It>
2369 struct __counted_iter_value_type<_It>
2370 { using value_type = iter_value_t<_It>; };
2371
2372 template<typename _It>
2373 struct __counted_iter_concept
2374 { };
2375
2376 template<typename _It>
2377 requires requires { typename _It::iterator_concept; }
2378 struct __counted_iter_concept<_It>
2379 { using iterator_concept = typename _It::iterator_concept; };
2380
2381 template<typename _It>
2382 struct __counted_iter_cat
2383 { };
2384
2385 template<typename _It>
2386 requires requires { typename _It::iterator_category; }
2387 struct __counted_iter_cat<_It>
2388 { using iterator_category = typename _It::iterator_category; };
2389 }
2390 /// @endcond
2391
2392 /// An iterator adaptor that keeps track of the distance to the end.
2393 template<input_or_output_iterator _It>
2394 class counted_iterator
2395 : public __detail::__counted_iter_value_type<_It>,
2396 public __detail::__counted_iter_concept<_It>,
2397 public __detail::__counted_iter_cat<_It>
2398 {
2399 public:
2400 using iterator_type = _It;
2401 // value_type defined in __counted_iter_value_type
2402 using difference_type = iter_difference_t<_It>;
2403 // iterator_concept defined in __counted_iter_concept
2404 // iterator_category defined in __counted_iter_cat
2405
2406 constexpr counted_iterator() requires default_initializable<_It> = default;
2407
2408 constexpr
2409 counted_iterator(_It __i, iter_difference_t<_It> __n)
2410 : _M_current(std::move(__i)), _M_length(__n)
2411 { __glibcxx_assert(__n >= 0); }
2412
2413 template<typename _It2>
2414 requires convertible_to<const _It2&, _It>
2415 constexpr
2416 counted_iterator(const counted_iterator<_It2>& __x)
2417 : _M_current(__x._M_current), _M_length(__x._M_length)
2418 { }
2419
2420 template<typename _It2>
2421 requires assignable_from<_It&, const _It2&>
2422 constexpr counted_iterator&
2423 operator=(const counted_iterator<_It2>& __x)
2424 {
2425 _M_current = __x._M_current;
2426 _M_length = __x._M_length;
2427 return *this;
2428 }
2429
2430 [[nodiscard]]
2431 constexpr const _It&
2432 base() const & noexcept
2433 { return _M_current; }
2434
2435 [[nodiscard]]
2436 constexpr _It
2437 base() &&
2438 noexcept(is_nothrow_move_constructible_v<_It>)
2439 { return std::move(_M_current); }
2440
2441 [[nodiscard]]
2442 constexpr iter_difference_t<_It>
2443 count() const noexcept { return _M_length; }
2444
2445 [[nodiscard]]
2446 constexpr decltype(auto)
2447 operator*()
2448 noexcept(noexcept(*_M_current))
2449 {
2450 __glibcxx_assert( _M_length > 0 );
2451 return *_M_current;
2452 }
2453
2454 [[nodiscard]]
2455 constexpr decltype(auto)
2456 operator*() const
2457 noexcept(noexcept(*_M_current))
2458 requires __detail::__dereferenceable<const _It>
2459 {
2460 __glibcxx_assert( _M_length > 0 );
2461 return *_M_current;
2462 }
2463
2464 [[nodiscard]]
2465 constexpr auto
2466 operator->() const noexcept
2467 requires contiguous_iterator<_It>
2468 { return std::to_address(_M_current); }
2469
2470 constexpr counted_iterator&
2471 operator++()
2472 {
2473 __glibcxx_assert(_M_length > 0);
2474 ++_M_current;
2475 --_M_length;
2476 return *this;
2477 }
2478
2479 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2480 // 3953. iter_move for ... and counted_iterator should return decltype(auto)
2481 constexpr decltype(auto)
2482 operator++(int)
2483 {
2484 __glibcxx_assert(_M_length > 0);
2485 --_M_length;
2486 __try
2487 {
2488 return _M_current++;
2489 } __catch(...) {
2490 ++_M_length;
2491 __throw_exception_again;
2492 }
2493 }
2494
2495 constexpr counted_iterator
2496 operator++(int) requires forward_iterator<_It>
2497 {
2498 auto __tmp = *this;
2499 ++*this;
2500 return __tmp;
2501 }
2502
2503 constexpr counted_iterator&
2504 operator--() requires bidirectional_iterator<_It>
2505 {
2506 --_M_current;
2507 ++_M_length;
2508 return *this;
2509 }
2510
2511 constexpr counted_iterator
2512 operator--(int) requires bidirectional_iterator<_It>
2513 {
2514 auto __tmp = *this;
2515 --*this;
2516 return __tmp;
2517 }
2518
2519 [[nodiscard]]
2520 constexpr counted_iterator
2521 operator+(iter_difference_t<_It> __n) const
2522 requires random_access_iterator<_It>
2523 { return counted_iterator(_M_current + __n, _M_length - __n); }
2524
2525 [[nodiscard]]
2526 friend constexpr counted_iterator
2527 operator+(iter_difference_t<_It> __n, const counted_iterator& __x)
2528 requires random_access_iterator<_It>
2529 { return __x + __n; }
2530
2531 constexpr counted_iterator&
2532 operator+=(iter_difference_t<_It> __n)
2533 requires random_access_iterator<_It>
2534 {
2535 __glibcxx_assert(__n <= _M_length);
2536 _M_current += __n;
2537 _M_length -= __n;
2538 return *this;
2539 }
2540
2541 [[nodiscard]]
2542 constexpr counted_iterator
2543 operator-(iter_difference_t<_It> __n) const
2544 requires random_access_iterator<_It>
2545 { return counted_iterator(_M_current - __n, _M_length + __n); }
2546
2547 template<common_with<_It> _It2>
2548 [[nodiscard]]
2549 friend constexpr iter_difference_t<_It2>
2550 operator-(const counted_iterator& __x,
2551 const counted_iterator<_It2>& __y) noexcept
2552 { return __y._M_length - __x._M_length; }
2553
2554 [[nodiscard]]
2555 friend constexpr iter_difference_t<_It>
2556 operator-(const counted_iterator& __x, default_sentinel_t) noexcept
2557 { return -__x._M_length; }
2558
2559 [[nodiscard]]
2560 friend constexpr iter_difference_t<_It>
2561 operator-(default_sentinel_t, const counted_iterator& __y) noexcept
2562 { return __y._M_length; }
2563
2564 constexpr counted_iterator&
2565 operator-=(iter_difference_t<_It> __n)
2566 requires random_access_iterator<_It>
2567 {
2568 __glibcxx_assert(-__n <= _M_length);
2569 _M_current -= __n;
2570 _M_length += __n;
2571 return *this;
2572 }
2573
2574 [[nodiscard]]
2575 constexpr decltype(auto)
2576 operator[](iter_difference_t<_It> __n) const
2577 noexcept(noexcept(_M_current[__n]))
2578 requires random_access_iterator<_It>
2579 {
2580 __glibcxx_assert(__n < _M_length);
2581 return _M_current[__n];
2582 }
2583
2584 template<common_with<_It> _It2>
2585 [[nodiscard]]
2586 friend constexpr bool
2587 operator==(const counted_iterator& __x,
2588 const counted_iterator<_It2>& __y) noexcept
2589 { return __x._M_length == __y._M_length; }
2590
2591 [[nodiscard]]
2592 friend constexpr bool
2593 operator==(const counted_iterator& __x, default_sentinel_t) noexcept
2594 { return __x._M_length == 0; }
2595
2596 template<common_with<_It> _It2>
2597 [[nodiscard]]
2598 friend constexpr strong_ordering
2599 operator<=>(const counted_iterator& __x,
2600 const counted_iterator<_It2>& __y) noexcept
2601 { return __y._M_length <=> __x._M_length; }
2602
2603 [[nodiscard]]
2604 friend constexpr iter_rvalue_reference_t<_It>
2605 iter_move(const counted_iterator& __i)
2606 noexcept(noexcept(ranges::iter_move(__i._M_current)))
2607 requires input_iterator<_It>
2608 {
2609 __glibcxx_assert( __i._M_length > 0 );
2610 return ranges::iter_move(__i._M_current);
2611 }
2612
2613 template<indirectly_swappable<_It> _It2>
2614 friend constexpr void
2615 iter_swap(const counted_iterator& __x,
2616 const counted_iterator<_It2>& __y)
2617 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
2618 {
2619 __glibcxx_assert( __x._M_length > 0 && __y._M_length > 0 );
2620 ranges::iter_swap(__x._M_current, __y._M_current);
2621 }
2622
2623 private:
2624 template<input_or_output_iterator _It2> friend class counted_iterator;
2625
2626 _It _M_current = _It();
2627 iter_difference_t<_It> _M_length = 0;
2628 };
2629
2630 template<input_iterator _It>
2631 requires same_as<__detail::__iter_traits<_It>, iterator_traits<_It>>
2632 struct iterator_traits<counted_iterator<_It>> : iterator_traits<_It>
2633 {
2634 using pointer = __conditional_t<contiguous_iterator<_It>,
2635 add_pointer_t<iter_reference_t<_It>>,
2636 void>;
2637 };
2638
2639#ifdef __glibcxx_ranges_as_const // >= C++23
2640 template<indirectly_readable _It>
2641 using iter_const_reference_t
2642 = common_reference_t<const iter_value_t<_It>&&, iter_reference_t<_It>>;
2643
2644 template<input_iterator _It> class basic_const_iterator;
2645
2646 /// @cond undocumented
2647 namespace __detail
2648 {
2649 template<typename _It>
2650 concept __constant_iterator = input_iterator<_It>
2651 && same_as<iter_const_reference_t<_It>, iter_reference_t<_It>>;
2652
2653 template<typename _Tp>
2654 inline constexpr bool __is_const_iterator = false;
2655
2656 template<typename _It>
2657 inline constexpr bool __is_const_iterator<basic_const_iterator<_It>> = true;
2658
2659 template<typename _Tp>
2660 concept __not_a_const_iterator = !__is_const_iterator<_Tp>;
2661
2662 template<indirectly_readable _It>
2663 using __iter_const_rvalue_reference_t
2664 = common_reference_t<const iter_value_t<_It>&&, iter_rvalue_reference_t<_It>>;
2665
2666 template<typename _It>
2667 struct __basic_const_iterator_iter_cat
2668 { };
2669
2670 template<forward_iterator _It>
2671 struct __basic_const_iterator_iter_cat<_It>
2672 { using iterator_category = __iter_category_t<_It>; };
2673 } // namespace detail
2674 /// @endcond
2675
2676 template<input_iterator _It>
2677 using const_iterator
2678 = __conditional_t<__detail::__constant_iterator<_It>, _It, basic_const_iterator<_It>>;
2679
2680 /// @cond undocumented
2681 namespace __detail
2682 {
2683 template<typename _Sent>
2684 struct __const_sentinel
2685 { using type = _Sent; };
2686
2687 template<input_iterator _Sent>
2688 struct __const_sentinel<_Sent>
2689 { using type = const_iterator<_Sent>; };
2690 } // namespace __detail
2691 /// @endcond
2692
2693 template<semiregular _Sent>
2694 using const_sentinel = typename __detail::__const_sentinel<_Sent>::type;
2695
2696 template<input_iterator _It>
2697 class basic_const_iterator
2698 : public __detail::__basic_const_iterator_iter_cat<_It>
2699 {
2700 _It _M_current = _It();
2701 using __reference = iter_const_reference_t<_It>;
2702 using __rvalue_reference = __detail::__iter_const_rvalue_reference_t<_It>;
2703
2704 static auto
2705 _S_iter_concept()
2706 {
2707 if constexpr (contiguous_iterator<_It>)
2708 return contiguous_iterator_tag{};
2709 else if constexpr (random_access_iterator<_It>)
2710 return random_access_iterator_tag{};
2711 else if constexpr (bidirectional_iterator<_It>)
2712 return bidirectional_iterator_tag{};
2713 else if constexpr (forward_iterator<_It>)
2714 return forward_iterator_tag{};
2715 else
2716 return input_iterator_tag{};
2717 }
2718
2719 template<input_iterator _It2> friend class basic_const_iterator;
2720
2721 public:
2722 // _GLIBCXX_RESOLVE_LIB_DEFECTS
2723 // 4253. basic_const_iterator should provide iterator_type
2724 using iterator_type = _It;
2725 using iterator_concept = decltype(_S_iter_concept());
2726 using value_type = iter_value_t<_It>;
2727 using difference_type = iter_difference_t<_It>;
2728
2729 basic_const_iterator() requires default_initializable<_It> = default;
2730
2731 constexpr
2732 basic_const_iterator(_It __current)
2733 noexcept(is_nothrow_move_constructible_v<_It>)
2734 : _M_current(std::move(__current))
2735 { }
2736
2737 template<convertible_to<_It> _It2>
2738 constexpr
2739 basic_const_iterator(basic_const_iterator<_It2> __current)
2740 noexcept(is_nothrow_constructible_v<_It, _It2>)
2741 : _M_current(std::move(__current._M_current))
2742 { }
2743
2744 template<__detail::__different_from<basic_const_iterator> _Tp>
2745 requires convertible_to<_Tp, _It>
2746 constexpr
2747 basic_const_iterator(_Tp&& __current)
2748 noexcept(is_nothrow_constructible_v<_It, _Tp>)
2749 : _M_current(std::forward<_Tp>(__current))
2750 { }
2751
2752 constexpr const _It&
2753 base() const & noexcept
2754 { return _M_current; }
2755
2756 constexpr _It
2757 base() &&
2758 noexcept(is_nothrow_move_constructible_v<_It>)
2759 { return std::move(_M_current); }
2760
2761 constexpr __reference
2762 operator*() const
2763 noexcept(noexcept(static_cast<__reference>(*_M_current)))
2764 { return static_cast<__reference>(*_M_current); }
2765
2766 constexpr const auto*
2767 operator->() const
2768 noexcept(contiguous_iterator<_It> || noexcept(*_M_current))
2769 requires is_lvalue_reference_v<iter_reference_t<_It>>
2770 && same_as<remove_cvref_t<iter_reference_t<_It>>, value_type>
2771 {
2772 if constexpr (contiguous_iterator<_It>)
2773 return std::to_address(_M_current);
2774 else
2775 return std::__addressof(*_M_current);
2776 }
2777
2778 constexpr basic_const_iterator&
2779 operator++()
2780 noexcept(noexcept(++_M_current))
2781 {
2782 ++_M_current;
2783 return *this;
2784 }
2785
2786 constexpr void
2787 operator++(int)
2788 noexcept(noexcept(++_M_current))
2789 { ++_M_current; }
2790
2791 constexpr basic_const_iterator
2792 operator++(int)
2793 noexcept(noexcept(++*this) && is_nothrow_copy_constructible_v<basic_const_iterator>)
2794 requires forward_iterator<_It>
2795 {
2796 auto __tmp = *this;
2797 ++*this;
2798 return __tmp;
2799 }
2800
2801 constexpr basic_const_iterator&
2802 operator--()
2803 noexcept(noexcept(--_M_current))
2804 requires bidirectional_iterator<_It>
2805 {
2806 --_M_current;
2807 return *this;
2808 }
2809
2810 constexpr basic_const_iterator
2811 operator--(int)
2812 noexcept(noexcept(--*this) && is_nothrow_copy_constructible_v<basic_const_iterator>)
2813 requires bidirectional_iterator<_It>
2814 {
2815 auto __tmp = *this;
2816 --*this;
2817 return __tmp;
2818 }
2819
2820 constexpr basic_const_iterator&
2821 operator+=(difference_type __n)
2822 noexcept(noexcept(_M_current += __n))
2823 requires random_access_iterator<_It>
2824 {
2825 _M_current += __n;
2826 return *this;
2827 }
2828
2829 constexpr basic_const_iterator&
2830 operator-=(difference_type __n)
2831 noexcept(noexcept(_M_current -= __n))
2832 requires random_access_iterator<_It>
2833 {
2834 _M_current -= __n;
2835 return *this;
2836 }
2837
2838 constexpr __reference
2839 operator[](difference_type __n) const
2840 noexcept(noexcept(static_cast<__reference>(_M_current[__n])))
2841 requires random_access_iterator<_It>
2842 { return static_cast<__reference>(_M_current[__n]); }
2843
2844 template<sentinel_for<_It> _Sent>
2845 constexpr bool
2846 operator==(const _Sent& __s) const
2847 noexcept(noexcept(_M_current == __s))
2848 { return _M_current == __s; }
2849
2850 template<__detail::__not_a_const_iterator _CIt>
2851 requires __detail::__constant_iterator<_CIt> && convertible_to<_It, _CIt>
2852 constexpr
2853 operator _CIt() const&
2854 { return _M_current; }
2855
2856 template<__detail::__not_a_const_iterator _CIt>
2857 requires __detail::__constant_iterator<_CIt> && convertible_to<_It, _CIt>
2858 constexpr
2859 operator _CIt() &&
2860 { return std::move(_M_current); }
2861
2862 constexpr bool
2863 operator<(const basic_const_iterator& __y) const
2864 noexcept(noexcept(_M_current < __y._M_current))
2865 requires random_access_iterator<_It>
2866 { return _M_current < __y._M_current; }
2867
2868 constexpr bool
2869 operator>(const basic_const_iterator& __y) const
2870 noexcept(noexcept(_M_current > __y._M_current))
2871 requires random_access_iterator<_It>
2872 { return _M_current > __y._M_current; }
2873
2874 constexpr bool
2875 operator<=(const basic_const_iterator& __y) const
2876 noexcept(noexcept(_M_current <= __y._M_current))
2877 requires random_access_iterator<_It>
2878 { return _M_current <= __y._M_current; }
2879
2880 constexpr bool
2881 operator>=(const basic_const_iterator& __y) const
2882 noexcept(noexcept(_M_current >= __y._M_current))
2883 requires random_access_iterator<_It>
2884 { return _M_current >= __y._M_current; }
2885
2886 constexpr auto
2887 operator<=>(const basic_const_iterator& __y) const
2888 noexcept(noexcept(_M_current <=> __y._M_current))
2889 requires random_access_iterator<_It> && three_way_comparable<_It>
2890 { return _M_current <=> __y._M_current; }
2891
2892 template<__detail::__different_from<basic_const_iterator> _It2>
2893 constexpr bool
2894 operator<(const _It2& __y) const
2895 noexcept(noexcept(_M_current < __y))
2896 requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2897 { return _M_current < __y; }
2898
2899 template<__detail::__different_from<basic_const_iterator> _It2>
2900 constexpr bool
2901 operator>(const _It2& __y) const
2902 noexcept(noexcept(_M_current > __y))
2903 requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2904 { return _M_current > __y; }
2905
2906 template<__detail::__different_from<basic_const_iterator> _It2>
2907 constexpr bool
2908 operator<=(const _It2& __y) const
2909 noexcept(noexcept(_M_current <= __y))
2910 requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2911 { return _M_current <= __y; }
2912
2913 template<__detail::__different_from<basic_const_iterator> _It2>
2914 constexpr bool
2915 operator>=(const _It2& __y) const
2916 noexcept(noexcept(_M_current >= __y))
2917 requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2918 { return _M_current >= __y; }
2919
2920 template<__detail::__different_from<basic_const_iterator> _It2>
2921 constexpr auto
2922 operator<=>(const _It2& __y) const
2923 noexcept(noexcept(_M_current <=> __y))
2924 requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2925 && three_way_comparable_with<_It, _It2>
2926 { return _M_current <=> __y; }
2927
2928 template<__detail::__not_a_const_iterator _It2, same_as<_It> _It3>
2929 friend constexpr bool
2930 operator<(const _It2& __x, const basic_const_iterator<_It3>& __y)
2931 noexcept(noexcept(__x < __y._M_current))
2932 requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2933 { return __x < __y._M_current; }
2934
2935 template<__detail::__not_a_const_iterator _It2, same_as<_It> _It3>
2936 friend constexpr bool
2937 operator>(const _It2& __x, const basic_const_iterator<_It3>& __y)
2938 noexcept(noexcept(__x > __y._M_current))
2939 requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2940 { return __x > __y._M_current; }
2941
2942 template<__detail::__not_a_const_iterator _It2, same_as<_It> _It3>
2943 friend constexpr bool
2944 operator<=(const _It2& __x, const basic_const_iterator<_It3>& __y)
2945 noexcept(noexcept(__x <= __y._M_current))
2946 requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2947 { return __x <= __y._M_current; }
2948
2949 template<__detail::__not_a_const_iterator _It2, same_as<_It> _It3>
2950 friend constexpr bool
2951 operator>=(const _It2& __x, const basic_const_iterator<_It3>& __y)
2952 noexcept(noexcept(__x >= __y._M_current))
2953 requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2954 { return __x >= __y._M_current; }
2955
2956 friend constexpr basic_const_iterator
2957 operator+(const basic_const_iterator& __i, difference_type __n)
2958 noexcept(noexcept(basic_const_iterator(__i._M_current + __n)))
2959 requires random_access_iterator<_It>
2960 { return basic_const_iterator(__i._M_current + __n); }
2961
2962 friend constexpr basic_const_iterator
2963 operator+(difference_type __n, const basic_const_iterator& __i)
2964 noexcept(noexcept(basic_const_iterator(__i._M_current + __n)))
2965 requires random_access_iterator<_It>
2966 { return basic_const_iterator(__i._M_current + __n); }
2967
2968 friend constexpr basic_const_iterator
2969 operator-(const basic_const_iterator& __i, difference_type __n)
2970 noexcept(noexcept(basic_const_iterator(__i._M_current - __n)))
2971 requires random_access_iterator<_It>
2972 { return basic_const_iterator(__i._M_current - __n); }
2973
2974 template<sized_sentinel_for<_It> _Sent>
2975 constexpr difference_type
2976 operator-(const _Sent& __y) const
2977 noexcept(noexcept(_M_current - __y))
2978 { return _M_current - __y; }
2979
2980 template<__detail::__not_a_const_iterator _Sent, same_as<_It> _It2>
2981 requires sized_sentinel_for<_Sent, _It>
2982 friend constexpr difference_type
2983 operator-(const _Sent& __x, const basic_const_iterator<_It2>& __y)
2984 noexcept(noexcept(__x - __y._M_current))
2985 { return __x - __y._M_current; }
2986
2987 friend constexpr __rvalue_reference
2988 iter_move(const basic_const_iterator& __i)
2989 noexcept(noexcept(static_cast<__rvalue_reference>(ranges::iter_move(__i._M_current))))
2990 { return static_cast<__rvalue_reference>(ranges::iter_move(__i._M_current)); }
2991 };
2992
2993 template<typename _Tp, common_with<_Tp> _Up>
2994 requires input_iterator<common_type_t<_Tp, _Up>>
2995 struct common_type<basic_const_iterator<_Tp>, _Up>
2996 { using type = basic_const_iterator<common_type_t<_Tp, _Up>>; };
2997
2998 template<typename _Tp, common_with<_Tp> _Up>
2999 requires input_iterator<common_type_t<_Tp, _Up>>
3000 struct common_type<_Up, basic_const_iterator<_Tp>>
3001 { using type = basic_const_iterator<common_type_t<_Tp, _Up>>; };
3002
3003 template<typename _Tp, common_with<_Tp> _Up>
3004 requires input_iterator<common_type_t<_Tp, _Up>>
3005 struct common_type<basic_const_iterator<_Tp>, basic_const_iterator<_Up>>
3006 { using type = basic_const_iterator<common_type_t<_Tp, _Up>>; };
3007
3008 template<input_iterator _It>
3009 constexpr const_iterator<_It>
3010 make_const_iterator(_It __it)
3011 noexcept(is_nothrow_convertible_v<_It, const_iterator<_It>>)
3012 { return __it; }
3013
3014 template<semiregular _Sent>
3015 constexpr const_sentinel<_Sent>
3016 make_const_sentinel(_Sent __s)
3017 noexcept(is_nothrow_convertible_v<_Sent, const_sentinel<_Sent>>)
3018 { return __s; }
3019#endif // C++23 ranges_as_const
3020#endif // C++20 ranges
3021
3022 /// @} group iterators
3023
3024_GLIBCXX_END_NAMESPACE_VERSION
3025} // namespace std
3026
3027namespace __gnu_debug
3028{
3029 template<typename _Iterator, typename _Sequence, typename _Category>
3030 class _Safe_iterator;
3031}
3032
3033namespace std _GLIBCXX_VISIBILITY(default)
3034{
3035_GLIBCXX_BEGIN_NAMESPACE_VERSION
3036 /// @cond undocumented
3037
3038 // Unwrap a __normal_iterator to get the underlying iterator
3039 // (usually a pointer). See uses in std::copy, std::fill, etc.
3040 template<typename _Iterator, typename _Container>
3041 _GLIBCXX_NODISCARD __attribute__((__always_inline__))
3042 _GLIBCXX20_CONSTEXPR
3043 inline _Iterator
3044 __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
3045 _GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible<_Iterator>::value)
3046 { return __it.base(); }
3047
3048 // Fallback implementation used for iterators that can't be unwrapped.
3049 template<typename _Iterator>
3050 _GLIBCXX_NODISCARD __attribute__((__always_inline__))
3051 _GLIBCXX20_CONSTEXPR
3052 inline _Iterator
3053 __niter_base(_Iterator __it)
3054 _GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible<_Iterator>::value)
3055 { return __it; }
3056
3057 // Overload for _Safe_iterator needs to be declared before uses of
3058 // std::__niter_base because we call it qualified so isn't found by ADL.
3059#if __cplusplus < 201103L
3060 template<typename _Ite, typename _Seq>
3061 _Ite
3062 __niter_base(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq,
3063 std::random_access_iterator_tag>&);
3064
3065 template<typename _Ite, typename _Cont, typename _Seq>
3066 _Ite
3067 __niter_base(const ::__gnu_debug::_Safe_iterator<
3068 ::__gnu_cxx::__normal_iterator<_Ite, _Cont>, _Seq,
3069 std::random_access_iterator_tag>&);
3070#else
3071 template<typename _Ite, typename _Seq>
3072 _GLIBCXX20_CONSTEXPR
3073 decltype(std::__niter_base(std::declval<_Ite>()))
3074 __niter_base(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq,
3075 std::random_access_iterator_tag>&)
3076 noexcept(std::is_nothrow_copy_constructible<_Ite>::value);
3077#endif
3078
3079#if __cplusplus >= 201103L
3080 template<typename _Iterator>
3081 _GLIBCXX20_CONSTEXPR
3082 inline auto
3083 __niter_base(reverse_iterator<_Iterator> __it)
3084 -> decltype(__make_reverse_iterator(__niter_base(__it.base())))
3085 { return __make_reverse_iterator(__niter_base(__it.base())); }
3086
3087 template<typename _Iterator>
3088 _GLIBCXX20_CONSTEXPR
3089 inline auto
3090 __niter_base(move_iterator<_Iterator> __it)
3091 -> decltype(make_move_iterator(__niter_base(__it.base())))
3092 { return make_move_iterator(__niter_base(__it.base())); }
3093
3094 template<typename _Iterator>
3095 _GLIBCXX20_CONSTEXPR
3096 inline auto
3097 __miter_base(reverse_iterator<_Iterator> __it)
3098 -> decltype(__make_reverse_iterator(__miter_base(__it.base())))
3099 { return __make_reverse_iterator(__miter_base(__it.base())); }
3100
3101 template<typename _Iterator>
3102 _GLIBCXX20_CONSTEXPR
3103 inline auto
3104 __miter_base(move_iterator<_Iterator> __it)
3105 -> decltype(__miter_base(__it.base()))
3106 { return __miter_base(__it.base()); }
3107#endif
3108
3109 // Reverse the __niter_base transformation to get a __normal_iterator
3110 // back again (this assumes that __normal_iterator is only used to wrap
3111 // random access iterators, like pointers).
3112 // All overloads of std::__niter_base must be declared before this.
3113 template<typename _From, typename _To>
3114 _GLIBCXX_NODISCARD
3115 _GLIBCXX20_CONSTEXPR
3116 inline _From
3117 __niter_wrap(_From __from, _To __res)
3118 { return __from + (std::__niter_base(__res) - std::__niter_base(__from)); }
3119
3120 // No need to wrap, iterator already has the right type.
3121 template<typename _Iterator>
3122 _GLIBCXX_NODISCARD __attribute__((__always_inline__))
3123 _GLIBCXX20_CONSTEXPR
3124 inline _Iterator
3125 __niter_wrap(const _Iterator&, _Iterator __res)
3126 { return __res; }
3127
3128 /// @endcond
3129
3130#if __cpp_deduction_guides >= 201606
3131 // These helper traits are used for deduction guides
3132 // of associative containers.
3133
3134 // _GLIBCXX_RESOLVE_LIB_DEFECTS
3135 // 4223. Deduction guides for maps are mishandling tuples and references
3136 template<typename _InputIterator>
3137 using __iter_key_t = __remove_cvref_t<
3138#ifdef __glibcxx_tuple_like // >= C++23
3139 tuple_element_t<0, typename iterator_traits<_InputIterator>::value_type>>;
3140#else
3141 typename iterator_traits<_InputIterator>::value_type::first_type>;
3142#endif
3143
3144 template<typename _InputIterator>
3145 using __iter_val_t = __remove_cvref_t<
3146#ifdef __glibcxx_tuple_like // >= C++23
3147 tuple_element_t<1, typename iterator_traits<_InputIterator>::value_type>>;
3148#else
3149 typename iterator_traits<_InputIterator>::value_type::second_type>;
3150#endif
3151
3152 template<typename _T1, typename _T2>
3153 struct pair;
3154
3155 template<typename _InputIterator>
3156 using __iter_to_alloc_t
3157 = pair<const __iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>>;
3158#endif // __cpp_deduction_guides
3159
3160_GLIBCXX_END_NAMESPACE_VERSION
3161} // namespace
3162
3163#ifdef _GLIBCXX_DEBUG
3164# include <debug/stl_iterator.h>
3165#endif
3166
3167#endif
std::chrono::operator<=
constexpr bool operator<=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:865
std::chrono::operator>=
constexpr bool operator>=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:879
std::chrono::operator<
constexpr bool operator<(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:832
std::chrono::operator>
constexpr bool operator>(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:872
std::operator-
constexpr complex< _Tp > operator-(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x minus y.
Definition complex:404
std::operator+
constexpr complex< _Tp > operator+(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x plus y.
Definition complex:374
std::to_address
constexpr _Tp * to_address(_Tp *__ptr) noexcept
Obtain address referenced by a pointer to an object.
Definition ptr_traits.h:234
std::common_reference_t
typename common_reference< _Tp... >::type common_reference_t
Definition type_traits:4302
std::add_pointer_t
typename add_pointer< _Tp >::type add_pointer_t
Alias template for add_pointer.
Definition type_traits:2384
std::declval
auto declval() noexcept -> decltype(__declval< _Tp >(0))
Definition type_traits:2742
std::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition move.h:138
std::__addressof
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition move.h:52
std::forward
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Definition move.h:72
std::make_reverse_iterator
constexpr reverse_iterator< _Iterator > make_reverse_iterator(_Iterator __i)
Generator function for reverse_iterator.
Definition bits/stl_iterator.h:647
std::inserter
constexpr insert_iterator< _Container > inserter(_Container &__x, std::__detail::__range_iter_t< _Container > __i)
Definition bits/stl_iterator.h:999
std::front_inserter
constexpr front_insert_iterator< _Container > front_inserter(_Container &__x)
Definition bits/stl_iterator.h:865
std::back_inserter
constexpr back_insert_iterator< _Container > back_inserter(_Container &__x)
Definition bits/stl_iterator.h:764
std
ISO C++ entities toplevel namespace is std.
std::compare_three_way_result_t
typename __detail::__cmp3way_res_impl< _Tp, _Up >::type compare_three_way_result_t
[cmp.result], result of three-way comparison
Definition compare:547
std::iter_rvalue_reference_t
ranges::__imove::_IterMove::__type< _Tp & > iter_rvalue_reference_t
The result type of ranges::iter_move(std::declval<_Tp&>()).
Definition iterator_concepts.h:188
std::__detail
Implementation details not part of the namespace std interface.
__gnu_cxx
GNU extensions for public use.
__gnu_debug
GNU debug classes for public use.
Definition boost_concept_check.h:60
std::is_nothrow_copy_constructible
is_nothrow_copy_constructible
Definition type_traits:1362
std::common_type
common_type
Definition type_traits:2601
__gnu_debug::_Safe_iterator
Safe iterator wrapper.
Definition safe_iterator.h:133
std::iterator_traits
Traits class for iterators.
Definition stl_iterator_base_types.h:185
std::reverse_iterator::operator-=
constexpr reverse_iterator & operator-=(difference_type __n)
Definition bits/stl_iterator.h:373
std::reverse_iterator::operator+=
constexpr reverse_iterator & operator+=(difference_type __n)
Definition bits/stl_iterator.h:350
std::reverse_iterator::operator+
constexpr reverse_iterator operator+(difference_type __n) const
Definition bits/stl_iterator.h:340
std::reverse_iterator::base
constexpr iterator_type base() const noexcept(/*conditional */)
Definition bits/stl_iterator.h:241
std::reverse_iterator::operator[]
constexpr reference operator[](difference_type __n) const
Definition bits/stl_iterator.h:386
std::reverse_iterator::operator--
constexpr reverse_iterator & operator--()
Definition bits/stl_iterator.h:314
std::reverse_iterator::reverse_iterator
constexpr reverse_iterator() noexcept(/*conditional */)
Definition bits/stl_iterator.h:179
std::reverse_iterator::operator->
constexpr pointer operator->() const
Definition bits/stl_iterator.h:270
std::reverse_iterator::operator*
constexpr reference operator*() const
Definition bits/stl_iterator.h:257
std::reverse_iterator::operator-
constexpr reverse_iterator operator-(difference_type __n) const
Definition bits/stl_iterator.h:363
std::reverse_iterator::operator++
constexpr reverse_iterator & operator++()
Definition bits/stl_iterator.h:289
std::back_insert_iterator
Turns assignment into insertion.
Definition bits/stl_iterator.h:679
std::back_insert_iterator::operator++
constexpr back_insert_iterator operator++(int)
Simply returns *this. (This iterator does not move.).
Definition bits/stl_iterator.h:746
std::back_insert_iterator::container_type
_Container container_type
A nested typedef for the type of whatever container you used.
Definition bits/stl_iterator.h:685
std::back_insert_iterator::operator++
constexpr back_insert_iterator & operator++()
Simply returns *this. (This iterator does not move.).
Definition bits/stl_iterator.h:740
std::back_insert_iterator::operator=
constexpr back_insert_iterator & operator=(const typename _Container::value_type &__value)
Definition bits/stl_iterator.h:716
std::back_insert_iterator::back_insert_iterator
constexpr back_insert_iterator(_Container &__x)
The only way to create this iterator is with a container.
Definition bits/stl_iterator.h:692
std::back_insert_iterator::operator*
constexpr back_insert_iterator & operator*()
Simply returns *this.
Definition bits/stl_iterator.h:734
std::front_insert_iterator
Turns assignment into insertion.
Definition bits/stl_iterator.h:780
std::front_insert_iterator::container_type
_Container container_type
A nested typedef for the type of whatever container you used.
Definition bits/stl_iterator.h:786
std::front_insert_iterator::operator++
constexpr front_insert_iterator operator++(int)
Simply returns *this. (This iterator does not move.).
Definition bits/stl_iterator.h:847
std::front_insert_iterator::front_insert_iterator
constexpr front_insert_iterator(_Container &__x)
The only way to create this iterator is with a container.
Definition bits/stl_iterator.h:793
std::front_insert_iterator::operator++
constexpr front_insert_iterator & operator++()
Simply returns *this. (This iterator does not move.).
Definition bits/stl_iterator.h:841
std::front_insert_iterator::operator*
constexpr front_insert_iterator & operator*()
Simply returns *this.
Definition bits/stl_iterator.h:835
std::front_insert_iterator::operator=
constexpr front_insert_iterator & operator=(const typename _Container::value_type &__value)
Definition bits/stl_iterator.h:817
std::insert_iterator
Turns assignment into insertion.
Definition bits/stl_iterator.h:885
std::insert_iterator::operator++
constexpr insert_iterator & operator++(int)
Simply returns *this. (This iterator does not move.).
Definition bits/stl_iterator.h:977
std::insert_iterator::operator*
constexpr insert_iterator & operator*()
Simply returns *this.
Definition bits/stl_iterator.h:965
std::insert_iterator::container_type
_Container container_type
A nested typedef for the type of whatever container you used.
Definition bits/stl_iterator.h:897
std::insert_iterator::operator=
constexpr insert_iterator & operator=(const typename _Container::value_type &__value)
Definition bits/stl_iterator.h:945
std::insert_iterator::operator++
constexpr insert_iterator & operator++()
Simply returns *this. (This iterator does not move.).
Definition bits/stl_iterator.h:971
std::insert_iterator::insert_iterator
constexpr insert_iterator(_Container &__x, _Iter __i)
Definition bits/stl_iterator.h:908
std::move_sentinel
A sentinel adaptor for use with std::move_iterator.
Definition bits/stl_iterator.h:1380
std::move_iterator
An iterator adaptor that yields an rvalue reference.
Definition bits/stl_iterator.h:1452
std::common_iterator
An iterator/sentinel adaptor for representing a non-common range.
Definition bits/stl_iterator.h:1890
std::counted_iterator
An iterator adaptor that keeps track of the distance to the end.
Definition bits/stl_iterator.h:2398
std::pair
Struct holding two objects (or references) of arbitrary type.
Definition stl_pair.h:307
std::input_iterator_tag
Marking input iterators.
Definition stl_iterator_base_types.h:97
std::forward_iterator_tag
Forward iterators support a superset of input iterator operations.
Definition stl_iterator_base_types.h:103
std::bidirectional_iterator_tag
Bidirectional iterators support a superset of forward iterator operations.
Definition stl_iterator_base_types.h:107
std::random_access_iterator_tag
Random-access iterators support a superset of bidirectional iterator operations.
Definition stl_iterator_base_types.h:111
std::iterator
Common iterator class.
Definition stl_iterator_base_types.h:135
std::same_as
[concept.same], concept same_as
Definition concepts:65
std::convertible_to
[concept.convertible], concept convertible_to
Definition concepts:81
std::assignable_from
[concept.assignable], concept assignable_from
Definition concepts:149
std::default_initializable
[concept.defaultinitializable], concept default_initializable
Definition concepts:166