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