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