libstdc++
bits/stl_iterator.h
Go to the documentation of this file.
1// Iterators -*- C++ -*-
2
3// Copyright (C) 2001-2025 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 _GLIBCXX17_CONSTEXPR
1512 move_iterator()
1513 : _M_current() { }
1514
1515 explicit _GLIBCXX17_CONSTEXPR
1516 move_iterator(iterator_type __i)
1517 : _M_current(std::move(__i)) { }
1518
1519 template<typename _Iter>
1520#ifdef __glibcxx_concepts
1521 requires __convertible<_Iter>
1522#endif
1523 _GLIBCXX17_CONSTEXPR
1524 move_iterator(const move_iterator<_Iter>& __i)
1525 : _M_current(__i._M_current) { }
1526
1527 template<typename _Iter>
1528#ifdef __glibcxx_concepts
1529 requires __convertible<_Iter>
1530 && assignable_from<_Iterator&, const _Iter&>
1531#endif
1532 _GLIBCXX17_CONSTEXPR
1533 move_iterator& operator=(const move_iterator<_Iter>& __i)
1534 {
1535 _M_current = __i._M_current;
1536 return *this;
1537 }
1538
1539#if __cplusplus <= 201703L
1540 [[__nodiscard__]]
1541 _GLIBCXX17_CONSTEXPR iterator_type
1542 base() const
1543 { return _M_current; }
1544#else
1545 [[nodiscard]]
1546 constexpr const iterator_type&
1547 base() const & noexcept
1548 { return _M_current; }
1549
1550 [[nodiscard]]
1551 constexpr iterator_type
1552 base() &&
1553 { return std::move(_M_current); }
1554#endif
1555
1556 [[__nodiscard__]]
1557 _GLIBCXX17_CONSTEXPR reference
1558 operator*() const
1559#ifdef __glibcxx_ranges
1560 { return ranges::iter_move(_M_current); }
1561#else
1562 { return static_cast<reference>(*_M_current); }
1563#endif
1564
1565 [[__nodiscard__]]
1566 _GLIBCXX17_CONSTEXPR pointer
1567 operator->() const
1568 { return _M_current; }
1569
1570 _GLIBCXX17_CONSTEXPR move_iterator&
1571 operator++()
1572 {
1573 ++_M_current;
1574 return *this;
1575 }
1576
1577 _GLIBCXX17_CONSTEXPR move_iterator
1578 operator++(int)
1579 {
1580 move_iterator __tmp = *this;
1581 ++_M_current;
1582 return __tmp;
1583 }
1584
1585#ifdef __glibcxx_concepts
1586 constexpr void
1587 operator++(int) requires (!forward_iterator<_Iterator>)
1588 { ++_M_current; }
1589#endif
1590
1591 _GLIBCXX17_CONSTEXPR move_iterator&
1592 operator--()
1593 {
1594 --_M_current;
1595 return *this;
1596 }
1597
1598 _GLIBCXX17_CONSTEXPR move_iterator
1599 operator--(int)
1600 {
1601 move_iterator __tmp = *this;
1602 --_M_current;
1603 return __tmp;
1604 }
1605
1606 [[__nodiscard__]]
1607 _GLIBCXX17_CONSTEXPR move_iterator
1608 operator+(difference_type __n) const
1609 { return move_iterator(_M_current + __n); }
1610
1611 _GLIBCXX17_CONSTEXPR move_iterator&
1612 operator+=(difference_type __n)
1613 {
1614 _M_current += __n;
1615 return *this;
1616 }
1617
1618 [[__nodiscard__]]
1619 _GLIBCXX17_CONSTEXPR move_iterator
1620 operator-(difference_type __n) const
1621 { return move_iterator(_M_current - __n); }
1622
1623 _GLIBCXX17_CONSTEXPR move_iterator&
1624 operator-=(difference_type __n)
1625 {
1626 _M_current -= __n;
1627 return *this;
1628 }
1629
1630 [[__nodiscard__]]
1631 _GLIBCXX17_CONSTEXPR reference
1632 operator[](difference_type __n) const
1633#ifdef __glibcxx_ranges
1634 { return ranges::iter_move(_M_current + __n); }
1635#else
1636 { return std::move(_M_current[__n]); }
1637#endif
1638
1639#ifdef __glibcxx_ranges
1640 template<sentinel_for<_Iterator> _Sent>
1641 [[nodiscard]]
1642 friend constexpr bool
1643 operator==(const move_iterator& __x, const move_sentinel<_Sent>& __y)
1644 { return __x.base() == __y.base(); }
1645
1646 template<sized_sentinel_for<_Iterator> _Sent>
1647 [[nodiscard]]
1648 friend constexpr iter_difference_t<_Iterator>
1649 operator-(const move_sentinel<_Sent>& __x, const move_iterator& __y)
1650 { return __x.base() - __y.base(); }
1651
1652 template<sized_sentinel_for<_Iterator> _Sent>
1653 [[nodiscard]]
1654 friend constexpr iter_difference_t<_Iterator>
1655 operator-(const move_iterator& __x, const move_sentinel<_Sent>& __y)
1656 { return __x.base() - __y.base(); }
1657
1658 [[nodiscard]]
1659 friend constexpr iter_rvalue_reference_t<_Iterator>
1660 iter_move(const move_iterator& __i)
1661 noexcept(noexcept(ranges::iter_move(__i._M_current)))
1662 { return ranges::iter_move(__i._M_current); }
1663
1664 template<indirectly_swappable<_Iterator> _Iter2>
1665 friend constexpr void
1666 iter_swap(const move_iterator& __x, const move_iterator<_Iter2>& __y)
1667 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
1668 { return ranges::iter_swap(__x._M_current, __y._M_current); }
1669#endif // C++20
1670 };
1671
1672 template<typename _IteratorL, typename _IteratorR>
1673 [[__nodiscard__]]
1674 inline _GLIBCXX17_CONSTEXPR bool
1675 operator==(const move_iterator<_IteratorL>& __x,
1676 const move_iterator<_IteratorR>& __y)
1677#ifdef __glibcxx_concepts
1678 requires requires { { __x.base() == __y.base() } -> convertible_to<bool>; }
1679#endif
1680 { return __x.base() == __y.base(); }
1681
1682#ifdef __cpp_lib_three_way_comparison
1683 template<typename _IteratorL,
1684 three_way_comparable_with<_IteratorL> _IteratorR>
1685 [[__nodiscard__]]
1686 constexpr compare_three_way_result_t<_IteratorL, _IteratorR>
1687 operator<=>(const move_iterator<_IteratorL>& __x,
1688 const move_iterator<_IteratorR>& __y)
1689 { return __x.base() <=> __y.base(); }
1690#else
1691 template<typename _IteratorL, typename _IteratorR>
1692 [[__nodiscard__]]
1693 inline _GLIBCXX17_CONSTEXPR bool
1694 operator!=(const move_iterator<_IteratorL>& __x,
1695 const move_iterator<_IteratorR>& __y)
1696 { return !(__x == __y); }
1697#endif
1698
1699 template<typename _IteratorL, typename _IteratorR>
1700 [[__nodiscard__]]
1701 inline _GLIBCXX17_CONSTEXPR bool
1702 operator<(const move_iterator<_IteratorL>& __x,
1703 const move_iterator<_IteratorR>& __y)
1704#ifdef __glibcxx_concepts
1705 requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1706#endif
1707 { return __x.base() < __y.base(); }
1708
1709 template<typename _IteratorL, typename _IteratorR>
1710 [[__nodiscard__]]
1711 inline _GLIBCXX17_CONSTEXPR bool
1712 operator<=(const move_iterator<_IteratorL>& __x,
1713 const move_iterator<_IteratorR>& __y)
1714#ifdef __glibcxx_concepts
1715 requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1716#endif
1717 { return !(__y < __x); }
1718
1719 template<typename _IteratorL, typename _IteratorR>
1720 [[__nodiscard__]]
1721 inline _GLIBCXX17_CONSTEXPR bool
1722 operator>(const move_iterator<_IteratorL>& __x,
1723 const move_iterator<_IteratorR>& __y)
1724#ifdef __glibcxx_concepts
1725 requires requires { { __y.base() < __x.base() } -> convertible_to<bool>; }
1726#endif
1727 { return __y < __x; }
1728
1729 template<typename _IteratorL, typename _IteratorR>
1730 [[__nodiscard__]]
1731 inline _GLIBCXX17_CONSTEXPR bool
1732 operator>=(const move_iterator<_IteratorL>& __x,
1733 const move_iterator<_IteratorR>& __y)
1734#ifdef __glibcxx_concepts
1735 requires requires { { __x.base() < __y.base() } -> convertible_to<bool>; }
1736#endif
1737 { return !(__x < __y); }
1738
1739 // Note: See __normal_iterator operators note from Gaby to understand
1740 // why we have these extra overloads for some move_iterator operators.
1741
1742 template<typename _Iterator>
1743 [[__nodiscard__]]
1744 inline _GLIBCXX17_CONSTEXPR bool
1745 operator==(const move_iterator<_Iterator>& __x,
1746 const move_iterator<_Iterator>& __y)
1747 // N.B. No contraints, x.base() == y.base() is always well-formed.
1748 { return __x.base() == __y.base(); }
1749
1750#ifdef __cpp_lib_three_way_comparison
1751 template<three_way_comparable _Iterator>
1752 [[__nodiscard__]]
1753 constexpr compare_three_way_result_t<_Iterator>
1754 operator<=>(const move_iterator<_Iterator>& __x,
1755 const move_iterator<_Iterator>& __y)
1756 { return __x.base() <=> __y.base(); }
1757#else
1758 template<typename _Iterator>
1759 [[__nodiscard__]]
1760 inline _GLIBCXX17_CONSTEXPR bool
1761 operator!=(const move_iterator<_Iterator>& __x,
1762 const move_iterator<_Iterator>& __y)
1763 { return !(__x == __y); }
1764
1765 template<typename _Iterator>
1766 [[__nodiscard__]]
1767 inline _GLIBCXX17_CONSTEXPR bool
1768 operator<(const move_iterator<_Iterator>& __x,
1769 const move_iterator<_Iterator>& __y)
1770 { return __x.base() < __y.base(); }
1771
1772 template<typename _Iterator>
1773 [[__nodiscard__]]
1774 inline _GLIBCXX17_CONSTEXPR bool
1775 operator<=(const move_iterator<_Iterator>& __x,
1776 const move_iterator<_Iterator>& __y)
1777 { return !(__y < __x); }
1778
1779 template<typename _Iterator>
1780 [[__nodiscard__]]
1781 inline _GLIBCXX17_CONSTEXPR bool
1782 operator>(const move_iterator<_Iterator>& __x,
1783 const move_iterator<_Iterator>& __y)
1784 { return __y < __x; }
1785
1786 template<typename _Iterator>
1787 [[__nodiscard__]]
1788 inline _GLIBCXX17_CONSTEXPR bool
1789 operator>=(const move_iterator<_Iterator>& __x,
1790 const move_iterator<_Iterator>& __y)
1791 { return !(__x < __y); }
1792#endif // ! C++20
1793
1794 // DR 685.
1795 template<typename _IteratorL, typename _IteratorR>
1796 [[__nodiscard__]]
1797 inline _GLIBCXX17_CONSTEXPR auto
1798 operator-(const move_iterator<_IteratorL>& __x,
1799 const move_iterator<_IteratorR>& __y)
1800 -> decltype(__x.base() - __y.base())
1801 { return __x.base() - __y.base(); }
1802
1803 template<typename _Iterator>
1804 [[__nodiscard__]]
1805 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1806 operator+(typename move_iterator<_Iterator>::difference_type __n,
1807 const move_iterator<_Iterator>& __x)
1808#ifdef __glibcxx_concepts
1809 requires requires { { __x.base() + __n } -> same_as<_Iterator>; }
1810#endif
1811 { return __x + __n; }
1812
1813 template<typename _Iterator>
1814 [[__nodiscard__]]
1815 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1816 make_move_iterator(_Iterator __i)
1817 { return move_iterator<_Iterator>(std::move(__i)); }
1818
1819 template<typename _Iterator, typename _ReturnType
1820 = __conditional_t<__move_if_noexcept_cond
1821 <typename iterator_traits<_Iterator>::value_type>::value,
1822 _Iterator, move_iterator<_Iterator>>>
1823 [[__nodiscard__]]
1824 constexpr _ReturnType
1825 __make_move_if_noexcept_iterator(_Iterator __i)
1826 { return _ReturnType(__i); }
1827
1828 // Overload for pointers that matches std::move_if_noexcept more closely,
1829 // returning a constant iterator when we don't want to move.
1830 template<typename _Tp, typename _ReturnType
1831 = __conditional_t<__move_if_noexcept_cond<_Tp>::value,
1832 const _Tp*, move_iterator<_Tp*>>>
1833 [[__nodiscard__]]
1834 constexpr _ReturnType
1835 __make_move_if_noexcept_iterator(_Tp* __i)
1836 { return _ReturnType(__i); }
1837
1838 template<typename _Iterator>
1839 struct __is_move_iterator<move_iterator<_Iterator> >
1840 {
1841 enum { __value = 1 };
1842 typedef __true_type __type;
1843 };
1844
1845#define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
1846#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
1847 std::__make_move_if_noexcept_iterator(_Iter)
1848#else
1849#define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
1850#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
1851#endif // C++11
1852
1853#ifdef __glibcxx_ranges
1854 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1855 // 3736. move_iterator missing disable_sized_sentinel_for specialization
1856 template<typename _Iterator1, typename _Iterator2>
1857 requires (!sized_sentinel_for<_Iterator1, _Iterator2>)
1858 inline constexpr bool
1859 disable_sized_sentinel_for<move_iterator<_Iterator1>,
1860 move_iterator<_Iterator2>> = true;
1861
1862 // [iterators.common] Common iterators
1863
1864 /// @cond undocumented
1865 namespace __detail
1866 {
1867 template<typename _It>
1868 concept __common_iter_has_arrow = indirectly_readable<const _It>
1869 && (requires(const _It& __it) { __it.operator->(); }
1870 || is_reference_v<iter_reference_t<_It>>
1871 || constructible_from<iter_value_t<_It>, iter_reference_t<_It>>);
1872
1873 template<typename _It>
1874 concept __common_iter_use_postfix_proxy
1875 = (!requires (_It& __i) { { *__i++ } -> __can_reference; })
1876 && constructible_from<iter_value_t<_It>, iter_reference_t<_It>>
1877 && move_constructible<iter_value_t<_It>>;
1878 } // namespace __detail
1879 /// @endcond
1880
1881 /// An iterator/sentinel adaptor for representing a non-common range.
1882 template<input_or_output_iterator _It, sentinel_for<_It> _Sent>
1883 requires (!same_as<_It, _Sent>) && copyable<_It>
1884 class common_iterator
1885 {
1886 template<typename _Tp, typename _Up>
1887 static constexpr bool
1888 _S_noexcept1()
1889 {
1890 if constexpr (is_trivially_default_constructible_v<_Tp>)
1891 return is_nothrow_assignable_v<_Tp&, _Up>;
1892 else
1893 return is_nothrow_constructible_v<_Tp, _Up>;
1894 }
1895
1896 template<typename _It2, typename _Sent2>
1897 static constexpr bool
1898 _S_noexcept()
1899 { return _S_noexcept1<_It, _It2>() && _S_noexcept1<_Sent, _Sent2>(); }
1900
1901 class __arrow_proxy
1902 {
1903 iter_value_t<_It> _M_keep;
1904
1905 constexpr
1906 __arrow_proxy(iter_reference_t<_It>&& __x)
1907 : _M_keep(std::move(__x)) { }
1908
1909 friend class common_iterator;
1910
1911 public:
1912 constexpr const iter_value_t<_It>*
1913 operator->() const noexcept
1914 { return std::__addressof(_M_keep); }
1915 };
1916
1917 class __postfix_proxy
1918 {
1919 iter_value_t<_It> _M_keep;
1920
1921 constexpr
1922 __postfix_proxy(iter_reference_t<_It>&& __x)
1923 : _M_keep(std::forward<iter_reference_t<_It>>(__x)) { }
1924
1925 friend class common_iterator;
1926
1927 public:
1928 constexpr const iter_value_t<_It>&
1929 operator*() const noexcept
1930 { return _M_keep; }
1931 };
1932
1933 public:
1934 constexpr
1935 common_iterator()
1936 noexcept(is_nothrow_default_constructible_v<_It>)
1937 requires default_initializable<_It>
1938 : _M_it(), _M_index(0)
1939 { }
1940
1941 constexpr
1942 common_iterator(_It __i)
1943 noexcept(is_nothrow_move_constructible_v<_It>)
1944 : _M_it(std::move(__i)), _M_index(0)
1945 { }
1946
1947 constexpr
1948 common_iterator(_Sent __s)
1949 noexcept(is_nothrow_move_constructible_v<_Sent>)
1950 : _M_sent(std::move(__s)), _M_index(1)
1951 { }
1952
1953 template<typename _It2, typename _Sent2>
1954 requires convertible_to<const _It2&, _It>
1955 && convertible_to<const _Sent2&, _Sent>
1956 constexpr
1957 common_iterator(const common_iterator<_It2, _Sent2>& __x)
1958 noexcept(_S_noexcept<const _It2&, const _Sent2&>())
1959 : _M_valueless(), _M_index(__x._M_index)
1960 {
1961 __glibcxx_assert(__x._M_has_value());
1962 if (_M_index == 0)
1963 {
1964 if constexpr (is_trivially_default_constructible_v<_It>)
1965 _M_it = std::move(__x._M_it);
1966 else
1967 std::construct_at(std::__addressof(_M_it), __x._M_it);
1968 }
1969 else if (_M_index == 1)
1970 {
1971 if constexpr (is_trivially_default_constructible_v<_Sent>)
1972 _M_sent = std::move(__x._M_sent);
1973 else
1974 std::construct_at(std::__addressof(_M_sent), __x._M_sent);
1975 }
1976 }
1977
1978 common_iterator(const common_iterator&) = default;
1979
1980 constexpr
1981 common_iterator(const common_iterator& __x)
1982 noexcept(_S_noexcept<const _It&, const _Sent&>())
1983 requires (!is_trivially_copyable_v<_It> || !is_trivially_copyable_v<_Sent>)
1984 : _M_valueless(), _M_index(__x._M_index)
1985 {
1986 if (_M_index == 0)
1987 {
1988 if constexpr (is_trivially_default_constructible_v<_It>)
1989 _M_it = __x._M_it;
1990 else
1991 std::construct_at(std::__addressof(_M_it), __x._M_it);
1992 }
1993 else if (_M_index == 1)
1994 {
1995 if constexpr (is_trivially_default_constructible_v<_Sent>)
1996 _M_sent = __x._M_sent;
1997 else
1998 std::construct_at(std::__addressof(_M_sent), __x._M_sent);
1999 }
2000 }
2001
2002 common_iterator(common_iterator&&) = default;
2003
2004 constexpr
2005 common_iterator(common_iterator&& __x)
2006 noexcept(_S_noexcept<_It, _Sent>())
2007 requires (!is_trivially_copyable_v<_It> || !is_trivially_copyable_v<_Sent>)
2008 : _M_valueless(), _M_index(__x._M_index)
2009 {
2010 if (_M_index == 0)
2011 {
2012 if constexpr (is_trivially_default_constructible_v<_It>)
2013 _M_it = std::move(__x._M_it);
2014 else
2015 std::construct_at(std::__addressof(_M_it), std::move(__x._M_it));
2016 }
2017 else if (_M_index == 1)
2018 {
2019 if constexpr (is_trivially_default_constructible_v<_Sent>)
2020 _M_sent = std::move(__x._M_sent);
2021 else
2022 std::construct_at(std::__addressof(_M_sent),
2023 std::move(__x._M_sent));
2024 }
2025 }
2026
2027 constexpr common_iterator&
2028 operator=(const common_iterator&) = default;
2029
2030 constexpr common_iterator&
2031 operator=(const common_iterator& __x)
2032 noexcept(is_nothrow_copy_assignable_v<_It>
2033 && is_nothrow_copy_assignable_v<_Sent>
2034 && is_nothrow_copy_constructible_v<_It>
2035 && is_nothrow_copy_constructible_v<_Sent>)
2036 requires (!is_trivially_copy_assignable_v<_It>
2037 || !is_trivially_copy_assignable_v<_Sent>)
2038 {
2039 _M_assign(__x);
2040 return *this;
2041 }
2042
2043 constexpr common_iterator&
2044 operator=(common_iterator&&) = default;
2045
2046 constexpr common_iterator&
2047 operator=(common_iterator&& __x)
2048 noexcept(is_nothrow_move_assignable_v<_It>
2049 && is_nothrow_move_assignable_v<_Sent>
2050 && is_nothrow_move_constructible_v<_It>
2051 && is_nothrow_move_constructible_v<_Sent>)
2052 requires (!is_trivially_move_assignable_v<_It>
2053 || !is_trivially_move_assignable_v<_Sent>)
2054 {
2055 _M_assign(std::move(__x));
2056 return *this;
2057 }
2058
2059 template<typename _It2, typename _Sent2>
2060 requires convertible_to<const _It2&, _It>
2061 && convertible_to<const _Sent2&, _Sent>
2062 && assignable_from<_It&, const _It2&>
2063 && assignable_from<_Sent&, const _Sent2&>
2064 constexpr common_iterator&
2065 operator=(const common_iterator<_It2, _Sent2>& __x)
2066 noexcept(is_nothrow_constructible_v<_It, const _It2&>
2067 && is_nothrow_constructible_v<_Sent, const _Sent2&>
2068 && is_nothrow_assignable_v<_It&, const _It2&>
2069 && is_nothrow_assignable_v<_Sent&, const _Sent2&>)
2070 {
2071 __glibcxx_assert(__x._M_has_value());
2072 _M_assign(__x);
2073 return *this;
2074 }
2075
2076#if __cpp_concepts >= 202002L // Constrained special member functions
2077 ~common_iterator() = default;
2078
2079 constexpr
2080 ~common_iterator()
2081 requires (!is_trivially_destructible_v<_It>
2082 || !is_trivially_destructible_v<_Sent>)
2083#else
2084 constexpr
2085 ~common_iterator()
2086#endif
2087 {
2088 if (_M_index == 0)
2089 _M_it.~_It();
2090 else if (_M_index == 1)
2091 _M_sent.~_Sent();
2092 }
2093
2094 [[nodiscard]]
2095 constexpr decltype(auto)
2096 operator*()
2097 {
2098 __glibcxx_assert(_M_index == 0);
2099 return *_M_it;
2100 }
2101
2102 [[nodiscard]]
2103 constexpr decltype(auto)
2104 operator*() const requires __detail::__dereferenceable<const _It>
2105 {
2106 __glibcxx_assert(_M_index == 0);
2107 return *_M_it;
2108 }
2109
2110 [[nodiscard]]
2111 constexpr auto
2112 operator->() const requires __detail::__common_iter_has_arrow<_It>
2113 {
2114 __glibcxx_assert(_M_index == 0);
2115 if constexpr (is_pointer_v<_It> || requires { _M_it.operator->(); })
2116 return _M_it;
2117 else if constexpr (is_reference_v<iter_reference_t<_It>>)
2118 {
2119 auto&& __tmp = *_M_it;
2120 return std::__addressof(__tmp);
2121 }
2122 else
2123 return __arrow_proxy{*_M_it};
2124 }
2125
2126 constexpr common_iterator&
2127 operator++()
2128 {
2129 __glibcxx_assert(_M_index == 0);
2130 ++_M_it;
2131 return *this;
2132 }
2133
2134 constexpr decltype(auto)
2135 operator++(int)
2136 {
2137 __glibcxx_assert(_M_index == 0);
2138 if constexpr (forward_iterator<_It>)
2139 {
2140 common_iterator __tmp = *this;
2141 ++*this;
2142 return __tmp;
2143 }
2144 else if constexpr (!__detail::__common_iter_use_postfix_proxy<_It>)
2145 return _M_it++;
2146 else
2147 {
2148 __postfix_proxy __p(**this);
2149 ++*this;
2150 return __p;
2151 }
2152 }
2153
2154 template<typename _It2, sentinel_for<_It> _Sent2>
2155 requires sentinel_for<_Sent, _It2>
2156 friend constexpr bool
2157 operator== [[nodiscard]] (const common_iterator& __x,
2158 const common_iterator<_It2, _Sent2>& __y)
2159 {
2160 switch(__x._M_index << 2 | __y._M_index)
2161 {
2162 case 0b0000:
2163 case 0b0101:
2164 return true;
2165 case 0b0001:
2166 return __x._M_it == __y._M_sent;
2167 case 0b0100:
2168 return __x._M_sent == __y._M_it;
2169 default:
2170 __glibcxx_assert(__x._M_has_value());
2171 __glibcxx_assert(__y._M_has_value());
2172 __builtin_unreachable();
2173 }
2174 }
2175
2176 template<typename _It2, sentinel_for<_It> _Sent2>
2177 requires sentinel_for<_Sent, _It2> && equality_comparable_with<_It, _It2>
2178 friend constexpr bool
2179 operator== [[nodiscard]] (const common_iterator& __x,
2180 const common_iterator<_It2, _Sent2>& __y)
2181 {
2182 switch(__x._M_index << 2 | __y._M_index)
2183 {
2184 case 0b0101:
2185 return true;
2186 case 0b0000:
2187 return __x._M_it == __y._M_it;
2188 case 0b0001:
2189 return __x._M_it == __y._M_sent;
2190 case 0b0100:
2191 return __x._M_sent == __y._M_it;
2192 default:
2193 __glibcxx_assert(__x._M_has_value());
2194 __glibcxx_assert(__y._M_has_value());
2195 __builtin_unreachable();
2196 }
2197 }
2198
2199 template<sized_sentinel_for<_It> _It2, sized_sentinel_for<_It> _Sent2>
2200 requires sized_sentinel_for<_Sent, _It2>
2201 friend constexpr iter_difference_t<_It2>
2202 operator- [[nodiscard]] (const common_iterator& __x,
2203 const common_iterator<_It2, _Sent2>& __y)
2204 {
2205 switch(__x._M_index << 2 | __y._M_index)
2206 {
2207 case 0b0101:
2208 return 0;
2209 case 0b0000:
2210 return __x._M_it - __y._M_it;
2211 case 0b0001:
2212 return __x._M_it - __y._M_sent;
2213 case 0b0100:
2214 return __x._M_sent - __y._M_it;
2215 default:
2216 __glibcxx_assert(__x._M_has_value());
2217 __glibcxx_assert(__y._M_has_value());
2218 __builtin_unreachable();
2219 }
2220 }
2221
2222 [[nodiscard]]
2223 friend constexpr iter_rvalue_reference_t<_It>
2224 iter_move(const common_iterator& __i)
2225 noexcept(noexcept(ranges::iter_move(std::declval<const _It&>())))
2226 requires input_iterator<_It>
2227 {
2228 __glibcxx_assert(__i._M_index == 0);
2229 return ranges::iter_move(__i._M_it);
2230 }
2231
2232 template<indirectly_swappable<_It> _It2, typename _Sent2>
2233 friend constexpr void
2234 iter_swap(const common_iterator& __x,
2235 const common_iterator<_It2, _Sent2>& __y)
2236 noexcept(noexcept(ranges::iter_swap(std::declval<const _It&>(),
2237 std::declval<const _It2&>())))
2238 {
2239 __glibcxx_assert(__x._M_index == 0);
2240 __glibcxx_assert(__y._M_index == 0);
2241 return ranges::iter_swap(__x._M_it, __y._M_it);
2242 }
2243
2244 private:
2245 template<input_or_output_iterator _It2, sentinel_for<_It2> _Sent2>
2246 requires (!same_as<_It2, _Sent2>) && copyable<_It2>
2247 friend class common_iterator;
2248
2249 constexpr bool
2250 _M_has_value() const noexcept { return _M_index != _S_valueless; }
2251
2252 template<typename _CIt>
2253 constexpr void
2254 _M_assign(_CIt&& __x)
2255 {
2256 if (_M_index == __x._M_index)
2257 {
2258 if (_M_index == 0)
2259 _M_it = std::forward<_CIt>(__x)._M_it;
2260 else if (_M_index == 1)
2261 _M_sent = std::forward<_CIt>(__x)._M_sent;
2262 }
2263 else
2264 {
2265 if (_M_index == 0)
2266 _M_it.~_It();
2267 else if (_M_index == 1)
2268 _M_sent.~_Sent();
2269 _M_index = _S_valueless;
2270
2271 if (__x._M_index == 0)
2272 std::construct_at(std::__addressof(_M_it),
2273 std::forward<_CIt>(__x)._M_it);
2274 else if (__x._M_index == 1)
2275 std::construct_at(std::__addressof(_M_sent),
2276 std::forward<_CIt>(__x)._M_sent);
2277 _M_index = __x._M_index;
2278 }
2279 }
2280
2281 union
2282 {
2283 _It _M_it;
2284 _Sent _M_sent;
2285 unsigned char _M_valueless;
2286 };
2287 unsigned char _M_index; // 0 == _M_it, 1 == _M_sent, 2 == valueless
2288
2289 static constexpr unsigned char _S_valueless{2};
2290 };
2291
2292 template<typename _It, typename _Sent>
2293 struct incrementable_traits<common_iterator<_It, _Sent>>
2294 {
2295 using difference_type = iter_difference_t<_It>;
2296 };
2297
2298 template<input_iterator _It, typename _Sent>
2299 struct iterator_traits<common_iterator<_It, _Sent>>
2300 {
2301 private:
2302 template<typename _Iter>
2303 struct __ptr
2304 {
2305 using type = void;
2306 };
2307
2308 template<typename _Iter>
2309 requires __detail::__common_iter_has_arrow<_Iter>
2310 struct __ptr<_Iter>
2311 {
2312 using _CIter = common_iterator<_Iter, _Sent>;
2313 using type = decltype(std::declval<const _CIter&>().operator->());
2314 };
2315
2316 static auto
2317 _S_iter_cat()
2318 {
2319 if constexpr (requires { requires derived_from<__iter_category_t<_It>,
2320 forward_iterator_tag>; })
2321 return forward_iterator_tag{};
2322 else
2323 return input_iterator_tag{};
2324 }
2325
2326 public:
2327 using iterator_concept = __conditional_t<forward_iterator<_It>,
2328 forward_iterator_tag,
2329 input_iterator_tag>;
2330 using iterator_category = decltype(_S_iter_cat());
2331 using value_type = iter_value_t<_It>;
2332 using difference_type = iter_difference_t<_It>;
2333 using pointer = typename __ptr<_It>::type;
2334 using reference = iter_reference_t<_It>;
2335 };
2336
2337 // [iterators.counted] Counted iterators
2338
2339 /// @cond undocumented
2340 namespace __detail
2341 {
2342 template<typename _It>
2343 struct __counted_iter_value_type
2344 { };
2345
2346 template<indirectly_readable _It>
2347 struct __counted_iter_value_type<_It>
2348 { using value_type = iter_value_t<_It>; };
2349
2350 template<typename _It>
2351 struct __counted_iter_concept
2352 { };
2353
2354 template<typename _It>
2355 requires requires { typename _It::iterator_concept; }
2356 struct __counted_iter_concept<_It>
2357 { using iterator_concept = typename _It::iterator_concept; };
2358
2359 template<typename _It>
2360 struct __counted_iter_cat
2361 { };
2362
2363 template<typename _It>
2364 requires requires { typename _It::iterator_category; }
2365 struct __counted_iter_cat<_It>
2366 { using iterator_category = typename _It::iterator_category; };
2367 }
2368 /// @endcond
2369
2370 /// An iterator adaptor that keeps track of the distance to the end.
2371 template<input_or_output_iterator _It>
2372 class counted_iterator
2373 : public __detail::__counted_iter_value_type<_It>,
2374 public __detail::__counted_iter_concept<_It>,
2375 public __detail::__counted_iter_cat<_It>
2376 {
2377 public:
2378 using iterator_type = _It;
2379 // value_type defined in __counted_iter_value_type
2380 using difference_type = iter_difference_t<_It>;
2381 // iterator_concept defined in __counted_iter_concept
2382 // iterator_category defined in __counted_iter_cat
2383
2384 constexpr counted_iterator() requires default_initializable<_It> = default;
2385
2386 constexpr
2387 counted_iterator(_It __i, iter_difference_t<_It> __n)
2388 : _M_current(std::move(__i)), _M_length(__n)
2389 { __glibcxx_assert(__n >= 0); }
2390
2391 template<typename _It2>
2392 requires convertible_to<const _It2&, _It>
2393 constexpr
2394 counted_iterator(const counted_iterator<_It2>& __x)
2395 : _M_current(__x._M_current), _M_length(__x._M_length)
2396 { }
2397
2398 template<typename _It2>
2399 requires assignable_from<_It&, const _It2&>
2400 constexpr counted_iterator&
2401 operator=(const counted_iterator<_It2>& __x)
2402 {
2403 _M_current = __x._M_current;
2404 _M_length = __x._M_length;
2405 return *this;
2406 }
2407
2408 [[nodiscard]]
2409 constexpr const _It&
2410 base() const & noexcept
2411 { return _M_current; }
2412
2413 [[nodiscard]]
2414 constexpr _It
2415 base() &&
2416 noexcept(is_nothrow_move_constructible_v<_It>)
2417 { return std::move(_M_current); }
2418
2419 [[nodiscard]]
2420 constexpr iter_difference_t<_It>
2421 count() const noexcept { return _M_length; }
2422
2423 [[nodiscard]]
2424 constexpr decltype(auto)
2425 operator*()
2426 noexcept(noexcept(*_M_current))
2427 {
2428 __glibcxx_assert( _M_length > 0 );
2429 return *_M_current;
2430 }
2431
2432 [[nodiscard]]
2433 constexpr decltype(auto)
2434 operator*() const
2435 noexcept(noexcept(*_M_current))
2436 requires __detail::__dereferenceable<const _It>
2437 {
2438 __glibcxx_assert( _M_length > 0 );
2439 return *_M_current;
2440 }
2441
2442 [[nodiscard]]
2443 constexpr auto
2444 operator->() const noexcept
2445 requires contiguous_iterator<_It>
2446 { return std::to_address(_M_current); }
2447
2448 constexpr counted_iterator&
2449 operator++()
2450 {
2451 __glibcxx_assert(_M_length > 0);
2452 ++_M_current;
2453 --_M_length;
2454 return *this;
2455 }
2456
2457 constexpr decltype(auto)
2458 operator++(int)
2459 {
2460 __glibcxx_assert(_M_length > 0);
2461 --_M_length;
2462 __try
2463 {
2464 return _M_current++;
2465 } __catch(...) {
2466 ++_M_length;
2467 __throw_exception_again;
2468 }
2469 }
2470
2471 constexpr counted_iterator
2472 operator++(int) requires forward_iterator<_It>
2473 {
2474 auto __tmp = *this;
2475 ++*this;
2476 return __tmp;
2477 }
2478
2479 constexpr counted_iterator&
2480 operator--() requires bidirectional_iterator<_It>
2481 {
2482 --_M_current;
2483 ++_M_length;
2484 return *this;
2485 }
2486
2487 constexpr counted_iterator
2488 operator--(int) requires bidirectional_iterator<_It>
2489 {
2490 auto __tmp = *this;
2491 --*this;
2492 return __tmp;
2493 }
2494
2495 [[nodiscard]]
2496 constexpr counted_iterator
2497 operator+(iter_difference_t<_It> __n) const
2498 requires random_access_iterator<_It>
2499 { return counted_iterator(_M_current + __n, _M_length - __n); }
2500
2501 [[nodiscard]]
2502 friend constexpr counted_iterator
2503 operator+(iter_difference_t<_It> __n, const counted_iterator& __x)
2504 requires random_access_iterator<_It>
2505 { return __x + __n; }
2506
2507 constexpr counted_iterator&
2508 operator+=(iter_difference_t<_It> __n)
2509 requires random_access_iterator<_It>
2510 {
2511 __glibcxx_assert(__n <= _M_length);
2512 _M_current += __n;
2513 _M_length -= __n;
2514 return *this;
2515 }
2516
2517 [[nodiscard]]
2518 constexpr counted_iterator
2519 operator-(iter_difference_t<_It> __n) const
2520 requires random_access_iterator<_It>
2521 { return counted_iterator(_M_current - __n, _M_length + __n); }
2522
2523 template<common_with<_It> _It2>
2524 [[nodiscard]]
2525 friend constexpr iter_difference_t<_It2>
2526 operator-(const counted_iterator& __x,
2527 const counted_iterator<_It2>& __y) noexcept
2528 { return __y._M_length - __x._M_length; }
2529
2530 [[nodiscard]]
2531 friend constexpr iter_difference_t<_It>
2532 operator-(const counted_iterator& __x, default_sentinel_t) noexcept
2533 { return -__x._M_length; }
2534
2535 [[nodiscard]]
2536 friend constexpr iter_difference_t<_It>
2537 operator-(default_sentinel_t, const counted_iterator& __y) noexcept
2538 { return __y._M_length; }
2539
2540 constexpr counted_iterator&
2541 operator-=(iter_difference_t<_It> __n)
2542 requires random_access_iterator<_It>
2543 {
2544 __glibcxx_assert(-__n <= _M_length);
2545 _M_current -= __n;
2546 _M_length += __n;
2547 return *this;
2548 }
2549
2550 [[nodiscard]]
2551 constexpr decltype(auto)
2552 operator[](iter_difference_t<_It> __n) const
2553 noexcept(noexcept(_M_current[__n]))
2554 requires random_access_iterator<_It>
2555 {
2556 __glibcxx_assert(__n < _M_length);
2557 return _M_current[__n];
2558 }
2559
2560 template<common_with<_It> _It2>
2561 [[nodiscard]]
2562 friend constexpr bool
2563 operator==(const counted_iterator& __x,
2564 const counted_iterator<_It2>& __y) noexcept
2565 { return __x._M_length == __y._M_length; }
2566
2567 [[nodiscard]]
2568 friend constexpr bool
2569 operator==(const counted_iterator& __x, default_sentinel_t) noexcept
2570 { return __x._M_length == 0; }
2571
2572 template<common_with<_It> _It2>
2573 [[nodiscard]]
2574 friend constexpr strong_ordering
2575 operator<=>(const counted_iterator& __x,
2576 const counted_iterator<_It2>& __y) noexcept
2577 { return __y._M_length <=> __x._M_length; }
2578
2579 [[nodiscard]]
2580 friend constexpr iter_rvalue_reference_t<_It>
2581 iter_move(const counted_iterator& __i)
2582 noexcept(noexcept(ranges::iter_move(__i._M_current)))
2583 requires input_iterator<_It>
2584 {
2585 __glibcxx_assert( __i._M_length > 0 );
2586 return ranges::iter_move(__i._M_current);
2587 }
2588
2589 template<indirectly_swappable<_It> _It2>
2590 friend constexpr void
2591 iter_swap(const counted_iterator& __x,
2592 const counted_iterator<_It2>& __y)
2593 noexcept(noexcept(ranges::iter_swap(__x._M_current, __y._M_current)))
2594 {
2595 __glibcxx_assert( __x._M_length > 0 && __y._M_length > 0 );
2596 ranges::iter_swap(__x._M_current, __y._M_current);
2597 }
2598
2599 private:
2600 template<input_or_output_iterator _It2> friend class counted_iterator;
2601
2602 _It _M_current = _It();
2603 iter_difference_t<_It> _M_length = 0;
2604 };
2605
2606 template<input_iterator _It>
2607 requires same_as<__detail::__iter_traits<_It>, iterator_traits<_It>>
2608 struct iterator_traits<counted_iterator<_It>> : iterator_traits<_It>
2609 {
2610 using pointer = __conditional_t<contiguous_iterator<_It>,
2611 add_pointer_t<iter_reference_t<_It>>,
2612 void>;
2613 };
2614
2615#ifdef __glibcxx_ranges_as_const // >= C++23
2616 template<indirectly_readable _It>
2617 using iter_const_reference_t
2618 = common_reference_t<const iter_value_t<_It>&&, iter_reference_t<_It>>;
2619
2620 template<input_iterator _It> class basic_const_iterator;
2621
2622 namespace __detail
2623 {
2624 template<typename _It>
2625 concept __constant_iterator = input_iterator<_It>
2626 && same_as<iter_const_reference_t<_It>, iter_reference_t<_It>>;
2627
2628 template<typename _Tp>
2629 inline constexpr bool __is_const_iterator = false;
2630
2631 template<typename _It>
2632 inline constexpr bool __is_const_iterator<basic_const_iterator<_It>> = true;
2633
2634 template<typename _Tp>
2635 concept __not_a_const_iterator = !__is_const_iterator<_Tp>;
2636
2637 template<indirectly_readable _It>
2638 using __iter_const_rvalue_reference_t
2639 = common_reference_t<const iter_value_t<_It>&&, iter_rvalue_reference_t<_It>>;
2640
2641 template<typename _It>
2642 struct __basic_const_iterator_iter_cat
2643 { };
2644
2645 template<forward_iterator _It>
2646 struct __basic_const_iterator_iter_cat<_It>
2647 { using iterator_category = __iter_category_t<_It>; };
2648 } // namespace detail
2649
2650 template<input_iterator _It>
2651 using const_iterator
2652 = __conditional_t<__detail::__constant_iterator<_It>, _It, basic_const_iterator<_It>>;
2653
2654 namespace __detail
2655 {
2656 template<typename _Sent>
2657 struct __const_sentinel
2658 { using type = _Sent; };
2659
2660 template<input_iterator _Sent>
2661 struct __const_sentinel<_Sent>
2662 { using type = const_iterator<_Sent>; };
2663 } // namespace __detail
2664
2665 template<semiregular _Sent>
2666 using const_sentinel = typename __detail::__const_sentinel<_Sent>::type;
2667
2668 template<input_iterator _It>
2669 class basic_const_iterator
2670 : public __detail::__basic_const_iterator_iter_cat<_It>
2671 {
2672 _It _M_current = _It();
2673 using __reference = iter_const_reference_t<_It>;
2674 using __rvalue_reference = __detail::__iter_const_rvalue_reference_t<_It>;
2675
2676 static auto
2677 _S_iter_concept()
2678 {
2679 if constexpr (contiguous_iterator<_It>)
2680 return contiguous_iterator_tag{};
2681 else if constexpr (random_access_iterator<_It>)
2682 return random_access_iterator_tag{};
2683 else if constexpr (bidirectional_iterator<_It>)
2684 return bidirectional_iterator_tag{};
2685 else if constexpr (forward_iterator<_It>)
2686 return forward_iterator_tag{};
2687 else
2688 return input_iterator_tag{};
2689 }
2690
2691 template<input_iterator _It2> friend class basic_const_iterator;
2692
2693 public:
2694 using iterator_concept = decltype(_S_iter_concept());
2695 using value_type = iter_value_t<_It>;
2696 using difference_type = iter_difference_t<_It>;
2697
2698 basic_const_iterator() requires default_initializable<_It> = default;
2699
2700 constexpr
2701 basic_const_iterator(_It __current)
2702 noexcept(is_nothrow_move_constructible_v<_It>)
2703 : _M_current(std::move(__current))
2704 { }
2705
2706 template<convertible_to<_It> _It2>
2707 constexpr
2708 basic_const_iterator(basic_const_iterator<_It2> __current)
2709 noexcept(is_nothrow_constructible_v<_It, _It2>)
2710 : _M_current(std::move(__current._M_current))
2711 { }
2712
2713 template<__detail::__different_from<basic_const_iterator> _Tp>
2714 requires convertible_to<_Tp, _It>
2715 constexpr
2716 basic_const_iterator(_Tp&& __current)
2717 noexcept(is_nothrow_constructible_v<_It, _Tp>)
2718 : _M_current(std::forward<_Tp>(__current))
2719 { }
2720
2721 constexpr const _It&
2722 base() const & noexcept
2723 { return _M_current; }
2724
2725 constexpr _It
2726 base() &&
2727 noexcept(is_nothrow_move_constructible_v<_It>)
2728 { return std::move(_M_current); }
2729
2730 constexpr __reference
2731 operator*() const
2732 noexcept(noexcept(static_cast<__reference>(*_M_current)))
2733 { return static_cast<__reference>(*_M_current); }
2734
2735 constexpr const auto*
2736 operator->() const
2737 noexcept(contiguous_iterator<_It> || noexcept(*_M_current))
2738 requires is_lvalue_reference_v<iter_reference_t<_It>>
2739 && same_as<remove_cvref_t<iter_reference_t<_It>>, value_type>
2740 {
2741 if constexpr (contiguous_iterator<_It>)
2742 return std::to_address(_M_current);
2743 else
2744 return std::__addressof(*_M_current);
2745 }
2746
2747 constexpr basic_const_iterator&
2748 operator++()
2749 noexcept(noexcept(++_M_current))
2750 {
2751 ++_M_current;
2752 return *this;
2753 }
2754
2755 constexpr void
2756 operator++(int)
2757 noexcept(noexcept(++_M_current))
2758 { ++_M_current; }
2759
2760 constexpr basic_const_iterator
2761 operator++(int)
2762 noexcept(noexcept(++*this) && is_nothrow_copy_constructible_v<basic_const_iterator>)
2763 requires forward_iterator<_It>
2764 {
2765 auto __tmp = *this;
2766 ++*this;
2767 return __tmp;
2768 }
2769
2770 constexpr basic_const_iterator&
2771 operator--()
2772 noexcept(noexcept(--_M_current))
2773 requires bidirectional_iterator<_It>
2774 {
2775 --_M_current;
2776 return *this;
2777 }
2778
2779 constexpr basic_const_iterator
2780 operator--(int)
2781 noexcept(noexcept(--*this) && is_nothrow_copy_constructible_v<basic_const_iterator>)
2782 requires bidirectional_iterator<_It>
2783 {
2784 auto __tmp = *this;
2785 --*this;
2786 return __tmp;
2787 }
2788
2789 constexpr basic_const_iterator&
2790 operator+=(difference_type __n)
2791 noexcept(noexcept(_M_current += __n))
2792 requires random_access_iterator<_It>
2793 {
2794 _M_current += __n;
2795 return *this;
2796 }
2797
2798 constexpr basic_const_iterator&
2799 operator-=(difference_type __n)
2800 noexcept(noexcept(_M_current -= __n))
2801 requires random_access_iterator<_It>
2802 {
2803 _M_current -= __n;
2804 return *this;
2805 }
2806
2807 constexpr __reference
2808 operator[](difference_type __n) const
2809 noexcept(noexcept(static_cast<__reference>(_M_current[__n])))
2810 requires random_access_iterator<_It>
2811 { return static_cast<__reference>(_M_current[__n]); }
2812
2813 template<sentinel_for<_It> _Sent>
2814 constexpr bool
2815 operator==(const _Sent& __s) const
2816 noexcept(noexcept(_M_current == __s))
2817 { return _M_current == __s; }
2818
2819 template<__detail::__not_a_const_iterator _CIt>
2820 requires __detail::__constant_iterator<_CIt> && convertible_to<_It, _CIt>
2821 constexpr
2822 operator _CIt() const&
2823 { return _M_current; }
2824
2825 template<__detail::__not_a_const_iterator _CIt>
2826 requires __detail::__constant_iterator<_CIt> && convertible_to<_It, _CIt>
2827 constexpr
2828 operator _CIt() &&
2829 { return std::move(_M_current); }
2830
2831 constexpr bool
2832 operator<(const basic_const_iterator& __y) const
2833 noexcept(noexcept(_M_current < __y._M_current))
2834 requires random_access_iterator<_It>
2835 { return _M_current < __y._M_current; }
2836
2837 constexpr bool
2838 operator>(const basic_const_iterator& __y) const
2839 noexcept(noexcept(_M_current > __y._M_current))
2840 requires random_access_iterator<_It>
2841 { return _M_current > __y._M_current; }
2842
2843 constexpr bool
2844 operator<=(const basic_const_iterator& __y) const
2845 noexcept(noexcept(_M_current <= __y._M_current))
2846 requires random_access_iterator<_It>
2847 { return _M_current <= __y._M_current; }
2848
2849 constexpr bool
2850 operator>=(const basic_const_iterator& __y) const
2851 noexcept(noexcept(_M_current >= __y._M_current))
2852 requires random_access_iterator<_It>
2853 { return _M_current >= __y._M_current; }
2854
2855 constexpr auto
2856 operator<=>(const basic_const_iterator& __y) const
2857 noexcept(noexcept(_M_current <=> __y._M_current))
2858 requires random_access_iterator<_It> && three_way_comparable<_It>
2859 { return _M_current <=> __y._M_current; }
2860
2861 template<__detail::__different_from<basic_const_iterator> _It2>
2862 constexpr bool
2863 operator<(const _It2& __y) const
2864 noexcept(noexcept(_M_current < __y))
2865 requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2866 { return _M_current < __y; }
2867
2868 template<__detail::__different_from<basic_const_iterator> _It2>
2869 constexpr bool
2870 operator>(const _It2& __y) const
2871 noexcept(noexcept(_M_current > __y))
2872 requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2873 { return _M_current > __y; }
2874
2875 template<__detail::__different_from<basic_const_iterator> _It2>
2876 constexpr bool
2877 operator<=(const _It2& __y) const
2878 noexcept(noexcept(_M_current <= __y))
2879 requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2880 { return _M_current <= __y; }
2881
2882 template<__detail::__different_from<basic_const_iterator> _It2>
2883 constexpr bool
2884 operator>=(const _It2& __y) const
2885 noexcept(noexcept(_M_current >= __y))
2886 requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2887 { return _M_current >= __y; }
2888
2889 template<__detail::__different_from<basic_const_iterator> _It2>
2890 constexpr auto
2891 operator<=>(const _It2& __y) const
2892 noexcept(noexcept(_M_current <=> __y))
2893 requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2894 && three_way_comparable_with<_It, _It2>
2895 { return _M_current <=> __y; }
2896
2897 template<__detail::__not_a_const_iterator _It2, same_as<_It> _It3>
2898 friend constexpr bool
2899 operator<(const _It2& __x, const basic_const_iterator<_It3>& __y)
2900 noexcept(noexcept(__x < __y._M_current))
2901 requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2902 { return __x < __y._M_current; }
2903
2904 template<__detail::__not_a_const_iterator _It2, same_as<_It> _It3>
2905 friend constexpr bool
2906 operator>(const _It2& __x, const basic_const_iterator<_It3>& __y)
2907 noexcept(noexcept(__x > __y._M_current))
2908 requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2909 { return __x > __y._M_current; }
2910
2911 template<__detail::__not_a_const_iterator _It2, same_as<_It> _It3>
2912 friend constexpr bool
2913 operator<=(const _It2& __x, const basic_const_iterator<_It3>& __y)
2914 noexcept(noexcept(__x <= __y._M_current))
2915 requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2916 { return __x <= __y._M_current; }
2917
2918 template<__detail::__not_a_const_iterator _It2, same_as<_It> _It3>
2919 friend constexpr bool
2920 operator>=(const _It2& __x, const basic_const_iterator<_It3>& __y)
2921 noexcept(noexcept(__x >= __y._M_current))
2922 requires random_access_iterator<_It> && totally_ordered_with<_It, _It2>
2923 { return __x >= __y._M_current; }
2924
2925 friend constexpr basic_const_iterator
2926 operator+(const basic_const_iterator& __i, difference_type __n)
2927 noexcept(noexcept(basic_const_iterator(__i._M_current + __n)))
2928 requires random_access_iterator<_It>
2929 { return basic_const_iterator(__i._M_current + __n); }
2930
2931 friend constexpr basic_const_iterator
2932 operator+(difference_type __n, const basic_const_iterator& __i)
2933 noexcept(noexcept(basic_const_iterator(__i._M_current + __n)))
2934 requires random_access_iterator<_It>
2935 { return basic_const_iterator(__i._M_current + __n); }
2936
2937 friend constexpr basic_const_iterator
2938 operator-(const basic_const_iterator& __i, difference_type __n)
2939 noexcept(noexcept(basic_const_iterator(__i._M_current - __n)))
2940 requires random_access_iterator<_It>
2941 { return basic_const_iterator(__i._M_current - __n); }
2942
2943 template<sized_sentinel_for<_It> _Sent>
2944 constexpr difference_type
2945 operator-(const _Sent& __y) const
2946 noexcept(noexcept(_M_current - __y))
2947 { return _M_current - __y; }
2948
2949 template<__detail::__not_a_const_iterator _Sent, same_as<_It> _It2>
2950 requires sized_sentinel_for<_Sent, _It>
2951 friend constexpr difference_type
2952 operator-(const _Sent& __x, const basic_const_iterator<_It2>& __y)
2953 noexcept(noexcept(__x - __y._M_current))
2954 { return __x - __y._M_current; }
2955
2956 friend constexpr __rvalue_reference
2957 iter_move(const basic_const_iterator& __i)
2958 noexcept(noexcept(static_cast<__rvalue_reference>(ranges::iter_move(__i._M_current))))
2959 { return static_cast<__rvalue_reference>(ranges::iter_move(__i._M_current)); }
2960 };
2961
2962 template<typename _Tp, common_with<_Tp> _Up>
2963 requires input_iterator<common_type_t<_Tp, _Up>>
2964 struct common_type<basic_const_iterator<_Tp>, _Up>
2965 { using type = basic_const_iterator<common_type_t<_Tp, _Up>>; };
2966
2967 template<typename _Tp, common_with<_Tp> _Up>
2968 requires input_iterator<common_type_t<_Tp, _Up>>
2969 struct common_type<_Up, basic_const_iterator<_Tp>>
2970 { using type = basic_const_iterator<common_type_t<_Tp, _Up>>; };
2971
2972 template<typename _Tp, common_with<_Tp> _Up>
2973 requires input_iterator<common_type_t<_Tp, _Up>>
2974 struct common_type<basic_const_iterator<_Tp>, basic_const_iterator<_Up>>
2975 { using type = basic_const_iterator<common_type_t<_Tp, _Up>>; };
2976
2977 template<input_iterator _It>
2978 constexpr const_iterator<_It>
2979 make_const_iterator(_It __it)
2980 noexcept(is_nothrow_convertible_v<_It, const_iterator<_It>>)
2981 { return __it; }
2982
2983 template<semiregular _Sent>
2984 constexpr const_sentinel<_Sent>
2985 make_const_sentinel(_Sent __s)
2986 noexcept(is_nothrow_convertible_v<_Sent, const_sentinel<_Sent>>)
2987 { return __s; }
2988#endif // C++23 ranges_as_const
2989#endif // C++20 ranges
2990
2991 /// @} group iterators
2992
2993_GLIBCXX_END_NAMESPACE_VERSION
2994} // namespace std
2995
2996namespace __gnu_debug
2997{
2998 template<typename _Iterator, typename _Sequence, typename _Category>
2999 class _Safe_iterator;
3000}
3001
3002namespace std _GLIBCXX_VISIBILITY(default)
3003{
3004_GLIBCXX_BEGIN_NAMESPACE_VERSION
3005 /// @cond undocumented
3006
3007 // Unwrap a __normal_iterator to get the underlying iterator
3008 // (usually a pointer). See uses in std::copy, std::fill, etc.
3009 template<typename _Iterator, typename _Container>
3010 _GLIBCXX_NODISCARD __attribute__((__always_inline__))
3011 _GLIBCXX20_CONSTEXPR
3012 inline _Iterator
3013 __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
3014 _GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible<_Iterator>::value)
3015 { return __it.base(); }
3016
3017 // Fallback implementation used for iterators that can't be unwrapped.
3018 template<typename _Iterator>
3019 _GLIBCXX_NODISCARD __attribute__((__always_inline__))
3020 _GLIBCXX20_CONSTEXPR
3021 inline _Iterator
3022 __niter_base(_Iterator __it)
3023 _GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible<_Iterator>::value)
3024 { return __it; }
3025
3026 // Overload for _Safe_iterator needs to be declared before uses of
3027 // std::__niter_base because we call it qualified so isn't found by ADL.
3028#if __cplusplus < 201103L
3029 template<typename _Ite, typename _Seq>
3030 _Ite
3031 __niter_base(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq,
3032 std::random_access_iterator_tag>&);
3033
3034 template<typename _Ite, typename _Cont, typename _Seq>
3035 _Ite
3036 __niter_base(const ::__gnu_debug::_Safe_iterator<
3037 ::__gnu_cxx::__normal_iterator<_Ite, _Cont>, _Seq,
3038 std::random_access_iterator_tag>&);
3039#else
3040 template<typename _Ite, typename _Seq>
3041 _GLIBCXX20_CONSTEXPR
3042 decltype(std::__niter_base(std::declval<_Ite>()))
3043 __niter_base(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq,
3044 std::random_access_iterator_tag>&)
3045 noexcept(std::is_nothrow_copy_constructible<_Ite>::value);
3046#endif
3047
3048#if __cplusplus >= 201103L
3049 template<typename _Iterator>
3050 _GLIBCXX20_CONSTEXPR
3051 inline auto
3052 __niter_base(reverse_iterator<_Iterator> __it)
3053 -> decltype(__make_reverse_iterator(__niter_base(__it.base())))
3054 { return __make_reverse_iterator(__niter_base(__it.base())); }
3055
3056 template<typename _Iterator>
3057 _GLIBCXX20_CONSTEXPR
3058 inline auto
3059 __niter_base(move_iterator<_Iterator> __it)
3060 -> decltype(make_move_iterator(__niter_base(__it.base())))
3061 { return make_move_iterator(__niter_base(__it.base())); }
3062
3063 template<typename _Iterator>
3064 _GLIBCXX20_CONSTEXPR
3065 inline auto
3066 __miter_base(reverse_iterator<_Iterator> __it)
3067 -> decltype(__make_reverse_iterator(__miter_base(__it.base())))
3068 { return __make_reverse_iterator(__miter_base(__it.base())); }
3069
3070 template<typename _Iterator>
3071 _GLIBCXX20_CONSTEXPR
3072 inline auto
3073 __miter_base(move_iterator<_Iterator> __it)
3074 -> decltype(__miter_base(__it.base()))
3075 { return __miter_base(__it.base()); }
3076#endif
3077
3078 // Reverse the __niter_base transformation to get a __normal_iterator
3079 // back again (this assumes that __normal_iterator is only used to wrap
3080 // random access iterators, like pointers).
3081 // All overloads of std::__niter_base must be declared before this.
3082 template<typename _From, typename _To>
3083 _GLIBCXX_NODISCARD
3084 _GLIBCXX20_CONSTEXPR
3085 inline _From
3086 __niter_wrap(_From __from, _To __res)
3087 { return __from + (std::__niter_base(__res) - std::__niter_base(__from)); }
3088
3089 // No need to wrap, iterator already has the right type.
3090 template<typename _Iterator>
3091 _GLIBCXX_NODISCARD __attribute__((__always_inline__))
3092 _GLIBCXX20_CONSTEXPR
3093 inline _Iterator
3094 __niter_wrap(const _Iterator&, _Iterator __res)
3095 { return __res; }
3096
3097 /// @endcond
3098
3099#if __cpp_deduction_guides >= 201606
3100 // These helper traits are used for deduction guides
3101 // of associative containers.
3102
3103 // _GLIBCXX_RESOLVE_LIB_DEFECTS
3104 // 4223. Deduction guides for maps are mishandling tuples and references
3105 template<typename _InputIterator>
3106 using __iter_key_t = __remove_cvref_t<
3107#ifdef __glibcxx_tuple_like // >= C++23
3108 tuple_element_t<0, typename iterator_traits<_InputIterator>::value_type>>;
3109#else
3110 typename iterator_traits<_InputIterator>::value_type::first_type>;
3111#endif
3112
3113 template<typename _InputIterator>
3114 using __iter_val_t = __remove_cvref_t<
3115#ifdef __glibcxx_tuple_like // >= C++23
3116 tuple_element_t<1, typename iterator_traits<_InputIterator>::value_type>>;
3117#else
3118 typename iterator_traits<_InputIterator>::value_type::second_type>;
3119#endif
3120
3121 template<typename _T1, typename _T2>
3122 struct pair;
3123
3124 template<typename _InputIterator>
3125 using __iter_to_alloc_t
3126 = pair<const __iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>>;
3127#endif // __cpp_deduction_guides
3128
3129_GLIBCXX_END_NAMESPACE_VERSION
3130} // namespace
3131
3132#ifdef _GLIBCXX_DEBUG
3133# include <debug/stl_iterator.h>
3134#endif
3135
3136#endif
std::chrono::operator<=
constexpr bool operator<=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:859
std::chrono::operator>=
constexpr bool operator>=(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:873
std::chrono::operator<
constexpr bool operator<(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:826
std::chrono::operator>
constexpr bool operator>(const duration< _Rep1, _Period1 > &__lhs, const duration< _Rep2, _Period2 > &__rhs)
Definition chrono.h:866
std::operator*
constexpr complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
Definition complex:434
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:232
std::common_reference_t
typename common_reference< _Tp... >::type common_reference_t
Definition type_traits:4195
std::add_pointer_t
typename add_pointer< _Tp >::type add_pointer_t
Alias template for add_pointer.
Definition type_traits:2312
std::declval
auto declval() noexcept -> decltype(__declval< _Tp >(0))
Definition type_traits:2670
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:548
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:1290
std::common_type
common_type
Definition type_traits:2529
__gnu_debug::_Safe_iterator
Safe iterator wrapper.
Definition safe_iterator.h:133
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::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:1885
std::counted_iterator
An iterator adaptor that keeps track of the distance to the end.
Definition bits/stl_iterator.h:2376
std::pair
Struct holding two objects of arbitrary type.
Definition stl_pair.h:304
std::input_iterator_tag
Marking input iterators.
Definition stl_iterator_base_types.h:95
std::forward_iterator_tag
Forward iterators support a superset of input iterator operations.
Definition stl_iterator_base_types.h:101
std::bidirectional_iterator_tag
Bidirectional iterators support a superset of forward iterator operations.
Definition stl_iterator_base_types.h:105
std::random_access_iterator_tag
Random-access iterators support a superset of bidirectional iterator operations.
Definition stl_iterator_base_types.h:109
std::iterator
Common iterator class.
Definition stl_iterator_base_types.h:130
std::iterator_traits
Traits class for iterators.
Definition stl_iterator_base_types.h:180