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 
88namespace 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 reverse_iterator(iterator_type __x) : current(__x) { } 
185 
186 /** 
187 * The copy constructor is normal. 
188 */ 
189 _GLIBCXX17_CONSTEXPR 
190 reverse_iterator(const reverse_iterator& __x) 
191 : 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 base() const 
229 { 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 operator*() const 
243 { 
244 _Iterator __tmp = current; 
245 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 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 _Iterator __tmp = current; 
263 --__tmp; 
264 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 operator++() 
274 { 
275 --current; 
276 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 operator++(int) 
286 { 
287 reverse_iterator __tmp = *this; 
288 --current; 
289 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 operator+(difference_type __n) const 
324 { 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 _S_to_pointer(_Tp __t) 
404 { 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 operator==(const reverse_iterator<_Iterator>& __x, 
421 const reverse_iterator<_Iterator>& __y) 
422 { 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 operator!=(const reverse_iterator<_Iterator>& __x, 
433 const reverse_iterator<_Iterator>& __y) 
434 { 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 operator-(const reverse_iterator<_IteratorL>& __x, 
578 const reverse_iterator<_IteratorR>& __y) 
579 -> decltype(__y.base() - __x.base()) 
580 { 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 __make_reverse_iterator(_Iterator __i) 
594 { 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 __niter_base(reverse_iterator<_Iterator> __it) 
620 -> decltype(__make_reverse_iterator(__niter_base(__it.base()))) 
621 { 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 back_insert_iterator(_Container& __x) 
666 : 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 operator=(const typename _Container::value_type& __value) 
690 { 
691 container->push_back(__value); 
692 return *this; 
693 } 
694 
695 _GLIBCXX20_CONSTEXPR 
696 back_insert_iterator& 
697 operator=(typename _Container::value_type&& __value) 
698 { 
699 container->push_back(std::move(__value)); 
700 return *this; 
701 } 
702#endif 
703 
704 /// Simply returns *this. 
705 _GLIBCXX20_CONSTEXPR 
706 back_insert_iterator& 
707 operator*() 
708 { return *this; } 
709 
710 /// Simply returns *this. (This %iterator does not @a move.) 
711 _GLIBCXX20_CONSTEXPR 
712 back_insert_iterator& 
713 operator++() 
714 { return *this; } 
715 
716 /// Simply returns *this. (This %iterator does not @a move.) 
717 _GLIBCXX20_CONSTEXPR 
718 back_insert_iterator 
719 operator++(int) 
720 { 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 back_inserter(_Container& __x) 
738 { 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 insert_iterator(_Container& __x, _Iter __i) 
891 : 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 operator=(const typename _Container::value_type& __value) 
928 { 
929 iter = container->insert(iter, __value); 
930 ++iter; 
931 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 operator*() 
948 { return *this; } 
949 
950 /// Simply returns *this. (This %iterator does not @a move.) 
951 _GLIBCXX20_CONSTEXPR 
952 insert_iterator& 
953 operator++() 
954 { 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 inserter(_Container& __x, typename _Container::iterator __i) 
984 { return insert_iterator<_Container>(__x, __i); } 
985#endif 
986 
987 /// @} group iterators 
988 
989_GLIBCXX_END_NAMESPACE_VERSION 
990} // namespace 
991 
992namespace __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 _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT 
1024 : _M_current(_Iterator()) { } 
1025 
1026 explicit _GLIBCXX20_CONSTEXPR 
1027 __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT 
1028 : _M_current(__i) { } 
1029 
1030 // Allow iterator to const_iterator conversion 
1031 template<typename _Iter> 
1032 _GLIBCXX20_CONSTEXPR 
1033 __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 : _M_current(__i.base()) { } 
1038 
1039 // Forward iterator requirements 
1040 _GLIBCXX20_CONSTEXPR 
1041 reference 
1042 operator*() const _GLIBCXX_NOEXCEPT 
1043 { return *_M_current; } 
1044 
1045 _GLIBCXX20_CONSTEXPR 
1046 pointer 
1047 operator->() const _GLIBCXX_NOEXCEPT 
1048 { return _M_current; } 
1049 
1050 _GLIBCXX20_CONSTEXPR 
1051 __normal_iterator& 
1052 operator++() _GLIBCXX_NOEXCEPT 
1053 { 
1054 ++_M_current; 
1055 return *this; 
1056 } 
1057 
1058 _GLIBCXX20_CONSTEXPR 
1059 __normal_iterator 
1060 operator++(int) _GLIBCXX_NOEXCEPT 
1061 { return __normal_iterator(_M_current++); } 
1062 
1063 // Bidirectional iterator requirements 
1064 _GLIBCXX20_CONSTEXPR 
1065 __normal_iterator& 
1066 operator--() _GLIBCXX_NOEXCEPT 
1067 { 
1068 --_M_current; 
1069 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 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT 
1086 { _M_current += __n; return *this; } 
1087 
1088 _GLIBCXX20_CONSTEXPR 
1089 __normal_iterator 
1090 operator+(difference_type __n) const _GLIBCXX_NOEXCEPT 
1091 { 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 operator-(difference_type __n) const _GLIBCXX_NOEXCEPT 
1101 { return __normal_iterator(_M_current - __n); } 
1102 
1103 _GLIBCXX20_CONSTEXPR 
1104 const _Iterator& 
1105 base() const _GLIBCXX_NOEXCEPT 
1106 { 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 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs, 
1156 const __normal_iterator<_IteratorR, _Container>& __rhs) 
1157 _GLIBCXX_NOEXCEPT 
1158 { return __lhs.base() == __rhs.base(); } 
1159 
1160 template<typename _Iterator, typename _Container> 
1161 _GLIBCXX20_CONSTEXPR 
1162 inline bool 
1163 operator==(const __normal_iterator<_Iterator, _Container>& __lhs, 
1164 const __normal_iterator<_Iterator, _Container>& __rhs) 
1165 _GLIBCXX_NOEXCEPT 
1166 { return __lhs.base() == __rhs.base(); } 
1167 
1168 template<typename _IteratorL, typename _IteratorR, typename _Container> 
1169 _GLIBCXX20_CONSTEXPR 
1170 inline bool 
1171 operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs, 
1172 const __normal_iterator<_IteratorR, _Container>& __rhs) 
1173 _GLIBCXX_NOEXCEPT 
1174 { return __lhs.base() != __rhs.base(); } 
1175 
1176 template<typename _Iterator, typename _Container> 
1177 _GLIBCXX20_CONSTEXPR 
1178 inline bool 
1179 operator!=(const __normal_iterator<_Iterator, _Container>& __lhs, 
1180 const __normal_iterator<_Iterator, _Container>& __rhs) 
1181 _GLIBCXX_NOEXCEPT 
1182 { 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 operator<(const __normal_iterator<_Iterator, _Container>& __lhs, 
1196 const __normal_iterator<_Iterator, _Container>& __rhs) 
1197 _GLIBCXX_NOEXCEPT 
1198 { 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 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 { 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 operator-(const __normal_iterator<_Iterator, _Container>& __lhs, 
1269 const __normal_iterator<_Iterator, _Container>& __rhs) 
1270 _GLIBCXX_NOEXCEPT 
1271 { 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 
1284namespace std _GLIBCXX_VISIBILITY(default) 
1285{ 
1286_GLIBCXX_BEGIN_NAMESPACE_VERSION 
1287 
1288 template<typename _Iterator, typename _Container> 
1289 _GLIBCXX20_CONSTEXPR 
1290 _Iterator 
1291 __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it) 
1292 _GLIBCXX_NOEXCEPT_IF(std::is_nothrow_copy_constructible<_Iterator>::value) 
1293 { 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 move_iterator(iterator_type __i) 
1440 : _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 base() const 
1465 { 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 operator*() const 
1478#if __cplusplus > 201703L && __cpp_lib_concepts 
1479 { return ranges::iter_move(_M_current); } 
1480#else 
1481 { 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 operator++() 
1490 { 
1491 ++_M_current; 
1492 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 operator==(const move_iterator<_Iterator>& __x, 
1649 const move_iterator<_Iterator>& __y) 
1650 { 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 operator!=(const move_iterator<_Iterator>& __x, 
1662 const move_iterator<_Iterator>& __y) 
1663 { 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 operator-(const move_iterator<_IteratorL>& __x, 
1694 const move_iterator<_IteratorR>& __y) 
1695 -> decltype(__x.base() - __y.base()) 
1696 { 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 make_move_iterator(_Iterator __i) 
1707 { 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 __make_move_if_noexcept_iterator(_Iterator __i) 
1715 { 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 __make_move_if_noexcept_iterator(_Tp* __i) 
1724 { 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 __miter_base(move_iterator<_Iterator> __it) 
2465 -> decltype(__miter_base(__it.base())) 
2466 { 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 
2504