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