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