1// Iterators -*- C++ -*-
2
3// Copyright (C) 2001-2018 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 > 201402L
69# define __cpp_lib_array_constexpr 201603
70#endif
71
72namespace std _GLIBCXX_VISIBILITY(default)
73{
74_GLIBCXX_BEGIN_NAMESPACE_VERSION
75
76 /**
77 * @addtogroup iterators
78 * @{
79 */
80
81 // 24.4.1 Reverse iterators
82 /**
83 * Bidirectional and random access iterators have corresponding reverse
84 * %iterator adaptors that iterate through the data structure in the
85 * opposite direction. They have the same signatures as the corresponding
86 * iterators. The fundamental relation between a reverse %iterator and its
87 * corresponding %iterator @c i is established by the identity:
88 * @code
89 * &*(reverse_iterator(i)) == &*(i - 1)
90 * @endcode
91 *
92 * <em>This mapping is dictated by the fact that while there is always a
93 * pointer past the end of an array, there might not be a valid pointer
94 * before the beginning of an array.</em> [24.4.1]/1,2
95 *
96 * Reverse iterators can be tricky and surprising at first. Their
97 * semantics make sense, however, and the trickiness is a side effect of
98 * the requirement that the iterators must be safe.
99 */
100 template<typename _Iterator>
101 class reverse_iterator
102 : public iterator<typename iterator_traits<_Iterator>::iterator_category,
103 typename iterator_traits<_Iterator>::value_type,
104 typename iterator_traits<_Iterator>::difference_type,
105 typename iterator_traits<_Iterator>::pointer,
106 typename iterator_traits<_Iterator>::reference>
107 {
108 protected:
109 _Iterator current;
110
111 typedef iterator_traits<_Iterator> __traits_type;
112
113 public:
114 typedef _Iterator iterator_type;
115 typedef typename __traits_type::difference_type difference_type;
116 typedef typename __traits_type::pointer pointer;
117 typedef typename __traits_type::reference reference;
118
119 /**
120 * The default constructor value-initializes member @p current.
121 * If it is a pointer, that means it is zero-initialized.
122 */
123 // _GLIBCXX_RESOLVE_LIB_DEFECTS
124 // 235 No specification of default ctor for reverse_iterator
125 _GLIBCXX17_CONSTEXPR
126 reverse_iterator() : current() { }
127
128 /**
129 * This %iterator will move in the opposite direction that @p x does.
130 */
131 explicit _GLIBCXX17_CONSTEXPR
132 reverse_iterator(iterator_type __x) : current(__x) { }
133
134 /**
135 * The copy constructor is normal.
136 */
137 _GLIBCXX17_CONSTEXPR
138 reverse_iterator(const reverse_iterator& __x)
139 : current(__x.current) { }
140
141 /**
142 * A %reverse_iterator across other types can be copied if the
143 * underlying %iterator can be converted to the type of @c current.
144 */
145 template<typename _Iter>
146 _GLIBCXX17_CONSTEXPR
147 reverse_iterator(const reverse_iterator<_Iter>& __x)
148 : current(__x.base()) { }
149
150 /**
151 * @return @c current, the %iterator used for underlying work.
152 */
153 _GLIBCXX17_CONSTEXPR iterator_type
154 base() const
155 { return current; }
156
157 /**
158 * @return A reference to the value at @c --current
159 *
160 * This requires that @c --current is dereferenceable.
161 *
162 * @warning This implementation requires that for an iterator of the
163 * underlying iterator type, @c x, a reference obtained by
164 * @c *x remains valid after @c x has been modified or
165 * destroyed. This is a bug: http://gcc.gnu.org/PR51823
166 */
167 _GLIBCXX17_CONSTEXPR reference
168 operator*() const
169 {
170 _Iterator __tmp = current;
171 return *--__tmp;
172 }
173
174 /**
175 * @return A pointer to the value at @c --current
176 *
177 * This requires that @c --current is dereferenceable.
178 */
179 _GLIBCXX17_CONSTEXPR pointer
180 operator->() const
181 { return &(operator*()); }
182
183 /**
184 * @return @c *this
185 *
186 * Decrements the underlying iterator.
187 */
188 _GLIBCXX17_CONSTEXPR reverse_iterator&
189 operator++()
190 {
191 --current;
192 return *this;
193 }
194
195 /**
196 * @return The original value of @c *this
197 *
198 * Decrements the underlying iterator.
199 */
200 _GLIBCXX17_CONSTEXPR reverse_iterator
201 operator++(int)
202 {
203 reverse_iterator __tmp = *this;
204 --current;
205 return __tmp;
206 }
207
208 /**
209 * @return @c *this
210 *
211 * Increments the underlying iterator.
212 */
213 _GLIBCXX17_CONSTEXPR reverse_iterator&
214 operator--()
215 {
216 ++current;
217 return *this;
218 }
219
220 /**
221 * @return A reverse_iterator with the previous value of @c *this
222 *
223 * Increments the underlying iterator.
224 */
225 _GLIBCXX17_CONSTEXPR reverse_iterator
226 operator--(int)
227 {
228 reverse_iterator __tmp = *this;
229 ++current;
230 return __tmp;
231 }
232
233 /**
234 * @return A reverse_iterator that refers to @c current - @a __n
235 *
236 * The underlying iterator must be a Random Access Iterator.
237 */
238 _GLIBCXX17_CONSTEXPR reverse_iterator
239 operator+(difference_type __n) const
240 { return reverse_iterator(current - __n); }
241
242 /**
243 * @return *this
244 *
245 * Moves the underlying iterator backwards @a __n steps.
246 * The underlying iterator must be a Random Access Iterator.
247 */
248 _GLIBCXX17_CONSTEXPR reverse_iterator&
249 operator+=(difference_type __n)
250 {
251 current -= __n;
252 return *this;
253 }
254
255 /**
256 * @return A reverse_iterator that refers to @c current - @a __n
257 *
258 * The underlying iterator must be a Random Access Iterator.
259 */
260 _GLIBCXX17_CONSTEXPR reverse_iterator
261 operator-(difference_type __n) const
262 { return reverse_iterator(current + __n); }
263
264 /**
265 * @return *this
266 *
267 * Moves the underlying iterator forwards @a __n steps.
268 * The underlying iterator must be a Random Access Iterator.
269 */
270 _GLIBCXX17_CONSTEXPR reverse_iterator&
271 operator-=(difference_type __n)
272 {
273 current += __n;
274 return *this;
275 }
276
277 /**
278 * @return The value at @c current - @a __n - 1
279 *
280 * The underlying iterator must be a Random Access Iterator.
281 */
282 _GLIBCXX17_CONSTEXPR reference
283 operator[](difference_type __n) const
284 { return *(*this + __n); }
285 };
286
287 //@{
288 /**
289 * @param __x A %reverse_iterator.
290 * @param __y A %reverse_iterator.
291 * @return A simple bool.
292 *
293 * Reverse iterators forward many operations to their underlying base()
294 * iterators. Others are implemented in terms of one another.
295 *
296 */
297 template<typename _Iterator>
298 inline _GLIBCXX17_CONSTEXPR bool
299 operator==(const reverse_iterator<_Iterator>& __x,
300 const reverse_iterator<_Iterator>& __y)
301 { return __x.base() == __y.base(); }
302
303 template<typename _Iterator>
304 inline _GLIBCXX17_CONSTEXPR bool
305 operator<(const reverse_iterator<_Iterator>& __x,
306 const reverse_iterator<_Iterator>& __y)
307 { return __y.base() < __x.base(); }
308
309 template<typename _Iterator>
310 inline _GLIBCXX17_CONSTEXPR bool
311 operator!=(const reverse_iterator<_Iterator>& __x,
312 const reverse_iterator<_Iterator>& __y)
313 { return !(__x == __y); }
314
315 template<typename _Iterator>
316 inline _GLIBCXX17_CONSTEXPR bool
317 operator>(const reverse_iterator<_Iterator>& __x,
318 const reverse_iterator<_Iterator>& __y)
319 { return __y < __x; }
320
321 template<typename _Iterator>
322 inline _GLIBCXX17_CONSTEXPR bool
323 operator<=(const reverse_iterator<_Iterator>& __x,
324 const reverse_iterator<_Iterator>& __y)
325 { return !(__y < __x); }
326
327 template<typename _Iterator>
328 inline _GLIBCXX17_CONSTEXPR bool
329 operator>=(const reverse_iterator<_Iterator>& __x,
330 const reverse_iterator<_Iterator>& __y)
331 { return !(__x < __y); }
332
333 // _GLIBCXX_RESOLVE_LIB_DEFECTS
334 // DR 280. Comparison of reverse_iterator to const reverse_iterator.
335 template<typename _IteratorL, typename _IteratorR>
336 inline _GLIBCXX17_CONSTEXPR bool
337 operator==(const reverse_iterator<_IteratorL>& __x,
338 const reverse_iterator<_IteratorR>& __y)
339 { return __x.base() == __y.base(); }
340
341 template<typename _IteratorL, typename _IteratorR>
342 inline _GLIBCXX17_CONSTEXPR bool
343 operator<(const reverse_iterator<_IteratorL>& __x,
344 const reverse_iterator<_IteratorR>& __y)
345 { return __y.base() < __x.base(); }
346
347 template<typename _IteratorL, typename _IteratorR>
348 inline _GLIBCXX17_CONSTEXPR bool
349 operator!=(const reverse_iterator<_IteratorL>& __x,
350 const reverse_iterator<_IteratorR>& __y)
351 { return !(__x == __y); }
352
353 template<typename _IteratorL, typename _IteratorR>
354 inline _GLIBCXX17_CONSTEXPR bool
355 operator>(const reverse_iterator<_IteratorL>& __x,
356 const reverse_iterator<_IteratorR>& __y)
357 { return __y < __x; }
358
359 template<typename _IteratorL, typename _IteratorR>
360 inline _GLIBCXX17_CONSTEXPR bool
361 operator<=(const reverse_iterator<_IteratorL>& __x,
362 const reverse_iterator<_IteratorR>& __y)
363 { return !(__y < __x); }
364
365 template<typename _IteratorL, typename _IteratorR>
366 inline _GLIBCXX17_CONSTEXPR bool
367 operator>=(const reverse_iterator<_IteratorL>& __x,
368 const reverse_iterator<_IteratorR>& __y)
369 { return !(__x < __y); }
370 //@}
371
372#if __cplusplus < 201103L
373 template<typename _Iterator>
374 inline typename reverse_iterator<_Iterator>::difference_type
375 operator-(const reverse_iterator<_Iterator>& __x,
376 const reverse_iterator<_Iterator>& __y)
377 { return __y.base() - __x.base(); }
378
379 template<typename _IteratorL, typename _IteratorR>
380 inline typename reverse_iterator<_IteratorL>::difference_type
381 operator-(const reverse_iterator<_IteratorL>& __x,
382 const reverse_iterator<_IteratorR>& __y)
383 { return __y.base() - __x.base(); }
384#else
385 // _GLIBCXX_RESOLVE_LIB_DEFECTS
386 // DR 685. reverse_iterator/move_iterator difference has invalid signatures
387 template<typename _IteratorL, typename _IteratorR>
388 inline _GLIBCXX17_CONSTEXPR auto
389 operator-(const reverse_iterator<_IteratorL>& __x,
390 const reverse_iterator<_IteratorR>& __y)
391 -> decltype(__y.base() - __x.base())
392 { return __y.base() - __x.base(); }
393#endif
394
395 template<typename _Iterator>
396 inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
397 operator+(typename reverse_iterator<_Iterator>::difference_type __n,
398 const reverse_iterator<_Iterator>& __x)
399 { return reverse_iterator<_Iterator>(__x.base() - __n); }
400
401#if __cplusplus >= 201103L
402 // Same as C++14 make_reverse_iterator but used in C++03 mode too.
403 template<typename _Iterator>
404 inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
405 __make_reverse_iterator(_Iterator __i)
406 { return reverse_iterator<_Iterator>(__i); }
407
408# if __cplusplus > 201103L
409# define __cpp_lib_make_reverse_iterator 201402
410
411 // _GLIBCXX_RESOLVE_LIB_DEFECTS
412 // DR 2285. make_reverse_iterator
413 /// Generator function for reverse_iterator.
414 template<typename _Iterator>
415 inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
416 make_reverse_iterator(_Iterator __i)
417 { return reverse_iterator<_Iterator>(__i); }
418# endif
419#endif
420
421#if __cplusplus >= 201103L
422 template<typename _Iterator>
423 auto
424 __niter_base(reverse_iterator<_Iterator> __it)
425 -> decltype(__make_reverse_iterator(__niter_base(__it.base())))
426 { return __make_reverse_iterator(__niter_base(__it.base())); }
427
428 template<typename _Iterator>
429 struct __is_move_iterator<reverse_iterator<_Iterator> >
430 : __is_move_iterator<_Iterator>
431 { };
432
433 template<typename _Iterator>
434 auto
435 __miter_base(reverse_iterator<_Iterator> __it)
436 -> decltype(__make_reverse_iterator(__miter_base(__it.base())))
437 { return __make_reverse_iterator(__miter_base(__it.base())); }
438#endif
439
440 // 24.4.2.2.1 back_insert_iterator
441 /**
442 * @brief Turns assignment into insertion.
443 *
444 * These are output iterators, constructed from a container-of-T.
445 * Assigning a T to the iterator appends it to the container using
446 * push_back.
447 *
448 * Tip: Using the back_inserter function to create these iterators can
449 * save typing.
450 */
451 template<typename _Container>
452 class back_insert_iterator
453 : public iterator<output_iterator_tag, void, void, void, void>
454 {
455 protected:
456 _Container* container;
457
458 public:
459 /// A nested typedef for the type of whatever container you used.
460 typedef _Container container_type;
461
462 /// The only way to create this %iterator is with a container.
463 explicit
464 back_insert_iterator(_Container& __x)
465 : container(std::__addressof(__x)) { }
466
467 /**
468 * @param __value An instance of whatever type
469 * container_type::const_reference is; presumably a
470 * reference-to-const T for container<T>.
471 * @return This %iterator, for chained operations.
472 *
473 * This kind of %iterator doesn't really have a @a position in the
474 * container (you can think of the position as being permanently at
475 * the end, if you like). Assigning a value to the %iterator will
476 * always append the value to the end of the container.
477 */
478#if __cplusplus < 201103L
479 back_insert_iterator&
480 operator=(typename _Container::const_reference __value)
481 {
482 container->push_back(__value);
483 return *this;
484 }
485#else
486 back_insert_iterator&
487 operator=(const typename _Container::value_type& __value)
488 {
489 container->push_back(__value);
490 return *this;
491 }
492
493 back_insert_iterator&
494 operator=(typename _Container::value_type&& __value)
495 {
496 container->push_back(std::move(__value));
497 return *this;
498 }
499#endif
500
501 /// Simply returns *this.
502 back_insert_iterator&
503 operator*()
504 { return *this; }
505
506 /// Simply returns *this. (This %iterator does not @a move.)
507 back_insert_iterator&
508 operator++()
509 { return *this; }
510
511 /// Simply returns *this. (This %iterator does not @a move.)
512 back_insert_iterator
513 operator++(int)
514 { return *this; }
515 };
516
517 /**
518 * @param __x A container of arbitrary type.
519 * @return An instance of back_insert_iterator working on @p __x.
520 *
521 * This wrapper function helps in creating back_insert_iterator instances.
522 * Typing the name of the %iterator requires knowing the precise full
523 * type of the container, which can be tedious and impedes generic
524 * programming. Using this function lets you take advantage of automatic
525 * template parameter deduction, making the compiler match the correct
526 * types for you.
527 */
528 template<typename _Container>
529 inline back_insert_iterator<_Container>
530 back_inserter(_Container& __x)
531 { return back_insert_iterator<_Container>(__x); }
532
533 /**
534 * @brief Turns assignment into insertion.
535 *
536 * These are output iterators, constructed from a container-of-T.
537 * Assigning a T to the iterator prepends it to the container using
538 * push_front.
539 *
540 * Tip: Using the front_inserter function to create these iterators can
541 * save typing.
542 */
543 template<typename _Container>
544 class front_insert_iterator
545 : public iterator<output_iterator_tag, void, void, void, void>
546 {
547 protected:
548 _Container* container;
549
550 public:
551 /// A nested typedef for the type of whatever container you used.
552 typedef _Container container_type;
553
554 /// The only way to create this %iterator is with a container.
555 explicit front_insert_iterator(_Container& __x)
556 : container(std::__addressof(__x)) { }
557
558 /**
559 * @param __value An instance of whatever type
560 * container_type::const_reference is; presumably a
561 * reference-to-const T for container<T>.
562 * @return This %iterator, for chained operations.
563 *
564 * This kind of %iterator doesn't really have a @a position in the
565 * container (you can think of the position as being permanently at
566 * the front, if you like). Assigning a value to the %iterator will
567 * always prepend the value to the front of the container.
568 */
569#if __cplusplus < 201103L
570 front_insert_iterator&
571 operator=(typename _Container::const_reference __value)
572 {
573 container->push_front(__value);
574 return *this;
575 }
576#else
577 front_insert_iterator&
578 operator=(const typename _Container::value_type& __value)
579 {
580 container->push_front(__value);
581 return *this;
582 }
583
584 front_insert_iterator&
585 operator=(typename _Container::value_type&& __value)
586 {
587 container->push_front(std::move(__value));
588 return *this;
589 }
590#endif
591
592 /// Simply returns *this.
593 front_insert_iterator&
594 operator*()
595 { return *this; }
596
597 /// Simply returns *this. (This %iterator does not @a move.)
598 front_insert_iterator&
599 operator++()
600 { return *this; }
601
602 /// Simply returns *this. (This %iterator does not @a move.)
603 front_insert_iterator
604 operator++(int)
605 { return *this; }
606 };
607
608 /**
609 * @param __x A container of arbitrary type.
610 * @return An instance of front_insert_iterator working on @p x.
611 *
612 * This wrapper function helps in creating front_insert_iterator instances.
613 * Typing the name of the %iterator requires knowing the precise full
614 * type of the container, which can be tedious and impedes generic
615 * programming. Using this function lets you take advantage of automatic
616 * template parameter deduction, making the compiler match the correct
617 * types for you.
618 */
619 template<typename _Container>
620 inline front_insert_iterator<_Container>
621 front_inserter(_Container& __x)
622 { return front_insert_iterator<_Container>(__x); }
623
624 /**
625 * @brief Turns assignment into insertion.
626 *
627 * These are output iterators, constructed from a container-of-T.
628 * Assigning a T to the iterator inserts it in the container at the
629 * %iterator's position, rather than overwriting the value at that
630 * position.
631 *
632 * (Sequences will actually insert a @e copy of the value before the
633 * %iterator's position.)
634 *
635 * Tip: Using the inserter function to create these iterators can
636 * save typing.
637 */
638 template<typename _Container>
639 class insert_iterator
640 : public iterator<output_iterator_tag, void, void, void, void>
641 {
642 protected:
643 _Container* container;
644 typename _Container::iterator iter;
645
646 public:
647 /// A nested typedef for the type of whatever container you used.
648 typedef _Container container_type;
649
650 /**
651 * The only way to create this %iterator is with a container and an
652 * initial position (a normal %iterator into the container).
653 */
654 insert_iterator(_Container& __x, typename _Container::iterator __i)
655 : container(std::__addressof(__x)), iter(__i) {}
656
657 /**
658 * @param __value An instance of whatever type
659 * container_type::const_reference is; presumably a
660 * reference-to-const T for container<T>.
661 * @return This %iterator, for chained operations.
662 *
663 * This kind of %iterator maintains its own position in the
664 * container. Assigning a value to the %iterator will insert the
665 * value into the container at the place before the %iterator.
666 *
667 * The position is maintained such that subsequent assignments will
668 * insert values immediately after one another. For example,
669 * @code
670 * // vector v contains A and Z
671 *
672 * insert_iterator i (v, ++v.begin());
673 * i = 1;
674 * i = 2;
675 * i = 3;
676 *
677 * // vector v contains A, 1, 2, 3, and Z
678 * @endcode
679 */
680#if __cplusplus < 201103L
681 insert_iterator&
682 operator=(typename _Container::const_reference __value)
683 {
684 iter = container->insert(iter, __value);
685 ++iter;
686 return *this;
687 }
688#else
689 insert_iterator&
690 operator=(const typename _Container::value_type& __value)
691 {
692 iter = container->insert(iter, __value);
693 ++iter;
694 return *this;
695 }
696
697 insert_iterator&
698 operator=(typename _Container::value_type&& __value)
699 {
700 iter = container->insert(iter, std::move(__value));
701 ++iter;
702 return *this;
703 }
704#endif
705
706 /// Simply returns *this.
707 insert_iterator&
708 operator*()
709 { return *this; }
710
711 /// Simply returns *this. (This %iterator does not @a move.)
712 insert_iterator&
713 operator++()
714 { return *this; }
715
716 /// Simply returns *this. (This %iterator does not @a move.)
717 insert_iterator&
718 operator++(int)
719 { return *this; }
720 };
721
722 /**
723 * @param __x A container of arbitrary type.
724 * @param __i An iterator into the container.
725 * @return An instance of insert_iterator working on @p __x.
726 *
727 * This wrapper function helps in creating 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, typename _Iterator>
735 inline insert_iterator<_Container>
736 inserter(_Container& __x, _Iterator __i)
737 {
738 return insert_iterator<_Container>(__x,
739 typename _Container::iterator(__i));
740 }
741
742 // @} group iterators
743
744_GLIBCXX_END_NAMESPACE_VERSION
745} // namespace
746
747namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
748{
749_GLIBCXX_BEGIN_NAMESPACE_VERSION
750
751 // This iterator adapter is @a normal in the sense that it does not
752 // change the semantics of any of the operators of its iterator
753 // parameter. Its primary purpose is to convert an iterator that is
754 // not a class, e.g. a pointer, into an iterator that is a class.
755 // The _Container parameter exists solely so that different containers
756 // using this template can instantiate different types, even if the
757 // _Iterator parameter is the same.
758 using std::iterator_traits;
759 using std::iterator;
760 template<typename _Iterator, typename _Container>
761 class __normal_iterator
762 {
763 protected:
764 _Iterator _M_current;
765
766 typedef iterator_traits<_Iterator> __traits_type;
767
768 public:
769 typedef _Iterator iterator_type;
770 typedef typename __traits_type::iterator_category iterator_category;
771 typedef typename __traits_type::value_type value_type;
772 typedef typename __traits_type::difference_type difference_type;
773 typedef typename __traits_type::reference reference;
774 typedef typename __traits_type::pointer pointer;
775
776 _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT
777 : _M_current(_Iterator()) { }
778
779 explicit
780 __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT
781 : _M_current(__i) { }
782
783 // Allow iterator to const_iterator conversion
784 template<typename _Iter>
785 __normal_iterator(const __normal_iterator<_Iter,
786 typename __enable_if<
787 (std::__are_same<_Iter, typename _Container::pointer>::__value),
788 _Container>::__type>& __i) _GLIBCXX_NOEXCEPT
789 : _M_current(__i.base()) { }
790
791 // Forward iterator requirements
792 reference
793 operator*() const _GLIBCXX_NOEXCEPT
794 { return *_M_current; }
795
796 pointer
797 operator->() const _GLIBCXX_NOEXCEPT
798 { return _M_current; }
799
800 __normal_iterator&
801 operator++() _GLIBCXX_NOEXCEPT
802 {
803 ++_M_current;
804 return *this;
805 }
806
807 __normal_iterator
808 operator++(int) _GLIBCXX_NOEXCEPT
809 { return __normal_iterator(_M_current++); }
810
811 // Bidirectional iterator requirements
812 __normal_iterator&
813 operator--() _GLIBCXX_NOEXCEPT
814 {
815 --_M_current;
816 return *this;
817 }
818
819 __normal_iterator
820 operator--(int) _GLIBCXX_NOEXCEPT
821 { return __normal_iterator(_M_current--); }
822
823 // Random access iterator requirements
824 reference
825 operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
826 { return _M_current[__n]; }
827
828 __normal_iterator&
829 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
830 { _M_current += __n; return *this; }
831
832 __normal_iterator
833 operator+(difference_type __n) const _GLIBCXX_NOEXCEPT
834 { return __normal_iterator(_M_current + __n); }
835
836 __normal_iterator&
837 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
838 { _M_current -= __n; return *this; }
839
840 __normal_iterator
841 operator-(difference_type __n) const _GLIBCXX_NOEXCEPT
842 { return __normal_iterator(_M_current - __n); }
843
844 const _Iterator&
845 base() const _GLIBCXX_NOEXCEPT
846 { return _M_current; }
847 };
848
849 // Note: In what follows, the left- and right-hand-side iterators are
850 // allowed to vary in types (conceptually in cv-qualification) so that
851 // comparison between cv-qualified and non-cv-qualified iterators be
852 // valid. However, the greedy and unfriendly operators in std::rel_ops
853 // will make overload resolution ambiguous (when in scope) if we don't
854 // provide overloads whose operands are of the same type. Can someone
855 // remind me what generic programming is about? -- Gaby
856
857 // Forward iterator requirements
858 template<typename _IteratorL, typename _IteratorR, typename _Container>
859 inline bool
860 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
861 const __normal_iterator<_IteratorR, _Container>& __rhs)
862 _GLIBCXX_NOEXCEPT
863 { return __lhs.base() == __rhs.base(); }
864
865 template<typename _Iterator, typename _Container>
866 inline bool
867 operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
868 const __normal_iterator<_Iterator, _Container>& __rhs)
869 _GLIBCXX_NOEXCEPT
870 { return __lhs.base() == __rhs.base(); }
871
872 template<typename _IteratorL, typename _IteratorR, typename _Container>
873 inline bool
874 operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
875 const __normal_iterator<_IteratorR, _Container>& __rhs)
876 _GLIBCXX_NOEXCEPT
877 { return __lhs.base() != __rhs.base(); }
878
879 template<typename _Iterator, typename _Container>
880 inline bool
881 operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
882 const __normal_iterator<_Iterator, _Container>& __rhs)
883 _GLIBCXX_NOEXCEPT
884 { return __lhs.base() != __rhs.base(); }
885
886 // Random access iterator requirements
887 template<typename _IteratorL, typename _IteratorR, typename _Container>
888 inline bool
889 operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
890 const __normal_iterator<_IteratorR, _Container>& __rhs)
891 _GLIBCXX_NOEXCEPT
892 { return __lhs.base() < __rhs.base(); }
893
894 template<typename _Iterator, typename _Container>
895 inline bool
896 operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
897 const __normal_iterator<_Iterator, _Container>& __rhs)
898 _GLIBCXX_NOEXCEPT
899 { return __lhs.base() < __rhs.base(); }
900
901 template<typename _IteratorL, typename _IteratorR, typename _Container>
902 inline bool
903 operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
904 const __normal_iterator<_IteratorR, _Container>& __rhs)
905 _GLIBCXX_NOEXCEPT
906 { return __lhs.base() > __rhs.base(); }
907
908 template<typename _Iterator, typename _Container>
909 inline bool
910 operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
911 const __normal_iterator<_Iterator, _Container>& __rhs)
912 _GLIBCXX_NOEXCEPT
913 { return __lhs.base() > __rhs.base(); }
914
915 template<typename _IteratorL, typename _IteratorR, typename _Container>
916 inline bool
917 operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
918 const __normal_iterator<_IteratorR, _Container>& __rhs)
919 _GLIBCXX_NOEXCEPT
920 { return __lhs.base() <= __rhs.base(); }
921
922 template<typename _Iterator, typename _Container>
923 inline bool
924 operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
925 const __normal_iterator<_Iterator, _Container>& __rhs)
926 _GLIBCXX_NOEXCEPT
927 { return __lhs.base() <= __rhs.base(); }
928
929 template<typename _IteratorL, typename _IteratorR, typename _Container>
930 inline bool
931 operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
932 const __normal_iterator<_IteratorR, _Container>& __rhs)
933 _GLIBCXX_NOEXCEPT
934 { return __lhs.base() >= __rhs.base(); }
935
936 template<typename _Iterator, typename _Container>
937 inline bool
938 operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
939 const __normal_iterator<_Iterator, _Container>& __rhs)
940 _GLIBCXX_NOEXCEPT
941 { return __lhs.base() >= __rhs.base(); }
942
943 // _GLIBCXX_RESOLVE_LIB_DEFECTS
944 // According to the resolution of DR179 not only the various comparison
945 // operators but also operator- must accept mixed iterator/const_iterator
946 // parameters.
947 template<typename _IteratorL, typename _IteratorR, typename _Container>
948#if __cplusplus >= 201103L
949 // DR 685.
950 inline auto
951 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
952 const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept
953 -> decltype(__lhs.base() - __rhs.base())
954#else
955 inline typename __normal_iterator<_IteratorL, _Container>::difference_type
956 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
957 const __normal_iterator<_IteratorR, _Container>& __rhs)
958#endif
959 { return __lhs.base() - __rhs.base(); }
960
961 template<typename _Iterator, typename _Container>
962 inline typename __normal_iterator<_Iterator, _Container>::difference_type
963 operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
964 const __normal_iterator<_Iterator, _Container>& __rhs)
965 _GLIBCXX_NOEXCEPT
966 { return __lhs.base() - __rhs.base(); }
967
968 template<typename _Iterator, typename _Container>
969 inline __normal_iterator<_Iterator, _Container>
970 operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
971 __n, const __normal_iterator<_Iterator, _Container>& __i)
972 _GLIBCXX_NOEXCEPT
973 { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
974
975_GLIBCXX_END_NAMESPACE_VERSION
976} // namespace
977
978namespace std _GLIBCXX_VISIBILITY(default)
979{
980_GLIBCXX_BEGIN_NAMESPACE_VERSION
981
982 template<typename _Iterator, typename _Container>
983 _Iterator
984 __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
985 { return __it.base(); }
986
987#if __cplusplus >= 201103L
988
989 /**
990 * @addtogroup iterators
991 * @{
992 */
993
994 // 24.4.3 Move iterators
995 /**
996 * Class template move_iterator is an iterator adapter with the same
997 * behavior as the underlying iterator except that its dereference
998 * operator implicitly converts the value returned by the underlying
999 * iterator's dereference operator to an rvalue reference. Some
1000 * generic algorithms can be called with move iterators to replace
1001 * copying with moving.
1002 */
1003 template<typename _Iterator>
1004 class move_iterator
1005 {
1006 protected:
1007 _Iterator _M_current;
1008
1009 typedef iterator_traits<_Iterator> __traits_type;
1010 typedef typename __traits_type::reference __base_ref;
1011
1012 public:
1013 typedef _Iterator iterator_type;
1014 typedef typename __traits_type::iterator_category iterator_category;
1015 typedef typename __traits_type::value_type value_type;
1016 typedef typename __traits_type::difference_type difference_type;
1017 // NB: DR 680.
1018 typedef _Iterator pointer;
1019 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1020 // 2106. move_iterator wrapping iterators returning prvalues
1021 typedef typename conditional<is_reference<__base_ref>::value,
1022 typename remove_reference<__base_ref>::type&&,
1023 __base_ref>::type reference;
1024
1025 _GLIBCXX17_CONSTEXPR
1026 move_iterator()
1027 : _M_current() { }
1028
1029 explicit _GLIBCXX17_CONSTEXPR
1030 move_iterator(iterator_type __i)
1031 : _M_current(__i) { }
1032
1033 template<typename _Iter>
1034 _GLIBCXX17_CONSTEXPR
1035 move_iterator(const move_iterator<_Iter>& __i)
1036 : _M_current(__i.base()) { }
1037
1038 _GLIBCXX17_CONSTEXPR iterator_type
1039 base() const
1040 { return _M_current; }
1041
1042 _GLIBCXX17_CONSTEXPR reference
1043 operator*() const
1044 { return static_cast<reference>(*_M_current); }
1045
1046 _GLIBCXX17_CONSTEXPR pointer
1047 operator->() const
1048 { return _M_current; }
1049
1050 _GLIBCXX17_CONSTEXPR move_iterator&
1051 operator++()
1052 {
1053 ++_M_current;
1054 return *this;
1055 }
1056
1057 _GLIBCXX17_CONSTEXPR move_iterator
1058 operator++(int)
1059 {
1060 move_iterator __tmp = *this;
1061 ++_M_current;
1062 return __tmp;
1063 }
1064
1065 _GLIBCXX17_CONSTEXPR move_iterator&
1066 operator--()
1067 {
1068 --_M_current;
1069 return *this;
1070 }
1071
1072 _GLIBCXX17_CONSTEXPR move_iterator
1073 operator--(int)
1074 {
1075 move_iterator __tmp = *this;
1076 --_M_current;
1077 return __tmp;
1078 }
1079
1080 _GLIBCXX17_CONSTEXPR move_iterator
1081 operator+(difference_type __n) const
1082 { return move_iterator(_M_current + __n); }
1083
1084 _GLIBCXX17_CONSTEXPR move_iterator&
1085 operator+=(difference_type __n)
1086 {
1087 _M_current += __n;
1088 return *this;
1089 }
1090
1091 _GLIBCXX17_CONSTEXPR move_iterator
1092 operator-(difference_type __n) const
1093 { return move_iterator(_M_current - __n); }
1094
1095 _GLIBCXX17_CONSTEXPR move_iterator&
1096 operator-=(difference_type __n)
1097 {
1098 _M_current -= __n;
1099 return *this;
1100 }
1101
1102 _GLIBCXX17_CONSTEXPR reference
1103 operator[](difference_type __n) const
1104 { return std::move(_M_current[__n]); }
1105 };
1106
1107 // Note: See __normal_iterator operators note from Gaby to understand
1108 // why there are always 2 versions for most of the move_iterator
1109 // operators.
1110 template<typename _IteratorL, typename _IteratorR>
1111 inline _GLIBCXX17_CONSTEXPR bool
1112 operator==(const move_iterator<_IteratorL>& __x,
1113 const move_iterator<_IteratorR>& __y)
1114 { return __x.base() == __y.base(); }
1115
1116 template<typename _Iterator>
1117 inline _GLIBCXX17_CONSTEXPR bool
1118 operator==(const move_iterator<_Iterator>& __x,
1119 const move_iterator<_Iterator>& __y)
1120 { return __x.base() == __y.base(); }
1121
1122 template<typename _IteratorL, typename _IteratorR>
1123 inline _GLIBCXX17_CONSTEXPR bool
1124 operator!=(const move_iterator<_IteratorL>& __x,
1125 const move_iterator<_IteratorR>& __y)
1126 { return !(__x == __y); }
1127
1128 template<typename _Iterator>
1129 inline _GLIBCXX17_CONSTEXPR bool
1130 operator!=(const move_iterator<_Iterator>& __x,
1131 const move_iterator<_Iterator>& __y)
1132 { return !(__x == __y); }
1133
1134 template<typename _IteratorL, typename _IteratorR>
1135 inline _GLIBCXX17_CONSTEXPR bool
1136 operator<(const move_iterator<_IteratorL>& __x,
1137 const move_iterator<_IteratorR>& __y)
1138 { return __x.base() < __y.base(); }
1139
1140 template<typename _Iterator>
1141 inline _GLIBCXX17_CONSTEXPR bool
1142 operator<(const move_iterator<_Iterator>& __x,
1143 const move_iterator<_Iterator>& __y)
1144 { return __x.base() < __y.base(); }
1145
1146 template<typename _IteratorL, typename _IteratorR>
1147 inline _GLIBCXX17_CONSTEXPR bool
1148 operator<=(const move_iterator<_IteratorL>& __x,
1149 const move_iterator<_IteratorR>& __y)
1150 { return !(__y < __x); }
1151
1152 template<typename _Iterator>
1153 inline _GLIBCXX17_CONSTEXPR bool
1154 operator<=(const move_iterator<_Iterator>& __x,
1155 const move_iterator<_Iterator>& __y)
1156 { return !(__y < __x); }
1157
1158 template<typename _IteratorL, typename _IteratorR>
1159 inline _GLIBCXX17_CONSTEXPR bool
1160 operator>(const move_iterator<_IteratorL>& __x,
1161 const move_iterator<_IteratorR>& __y)
1162 { return __y < __x; }
1163
1164 template<typename _Iterator>
1165 inline _GLIBCXX17_CONSTEXPR bool
1166 operator>(const move_iterator<_Iterator>& __x,
1167 const move_iterator<_Iterator>& __y)
1168 { return __y < __x; }
1169
1170 template<typename _IteratorL, typename _IteratorR>
1171 inline _GLIBCXX17_CONSTEXPR bool
1172 operator>=(const move_iterator<_IteratorL>& __x,
1173 const move_iterator<_IteratorR>& __y)
1174 { return !(__x < __y); }
1175
1176 template<typename _Iterator>
1177 inline _GLIBCXX17_CONSTEXPR bool
1178 operator>=(const move_iterator<_Iterator>& __x,
1179 const move_iterator<_Iterator>& __y)
1180 { return !(__x < __y); }
1181
1182 // DR 685.
1183 template<typename _IteratorL, typename _IteratorR>
1184 inline _GLIBCXX17_CONSTEXPR auto
1185 operator-(const move_iterator<_IteratorL>& __x,
1186 const move_iterator<_IteratorR>& __y)
1187 -> decltype(__x.base() - __y.base())
1188 { return __x.base() - __y.base(); }
1189
1190 template<typename _Iterator>
1191 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1192 operator+(typename move_iterator<_Iterator>::difference_type __n,
1193 const move_iterator<_Iterator>& __x)
1194 { return __x + __n; }
1195
1196 template<typename _Iterator>
1197 inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
1198 make_move_iterator(_Iterator __i)
1199 { return move_iterator<_Iterator>(__i); }
1200
1201 template<typename _Iterator, typename _ReturnType
1202 = typename conditional<__move_if_noexcept_cond
1203 <typename iterator_traits<_Iterator>::value_type>::value,
1204 _Iterator, move_iterator<_Iterator>>::type>
1205 inline _GLIBCXX17_CONSTEXPR _ReturnType
1206 __make_move_if_noexcept_iterator(_Iterator __i)
1207 { return _ReturnType(__i); }
1208
1209 // Overload for pointers that matches std::move_if_noexcept more closely,
1210 // returning a constant iterator when we don't want to move.
1211 template<typename _Tp, typename _ReturnType
1212 = typename conditional<__move_if_noexcept_cond<_Tp>::value,
1213 const _Tp*, move_iterator<_Tp*>>::type>
1214 inline _GLIBCXX17_CONSTEXPR _ReturnType
1215 __make_move_if_noexcept_iterator(_Tp* __i)
1216 { return _ReturnType(__i); }
1217
1218 // @} group iterators
1219
1220 template<typename _Iterator>
1221 auto
1222 __niter_base(move_iterator<_Iterator> __it)
1223 -> decltype(make_move_iterator(__niter_base(__it.base())))
1224 { return make_move_iterator(__niter_base(__it.base())); }
1225
1226 template<typename _Iterator>
1227 struct __is_move_iterator<move_iterator<_Iterator> >
1228 {
1229 enum { __value = 1 };
1230 typedef __true_type __type;
1231 };
1232
1233 template<typename _Iterator>
1234 auto
1235 __miter_base(move_iterator<_Iterator> __it)
1236 -> decltype(__miter_base(__it.base()))
1237 { return __miter_base(__it.base()); }
1238
1239#define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
1240#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
1241 std::__make_move_if_noexcept_iterator(_Iter)
1242#else
1243#define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
1244#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
1245#endif // C++11
1246
1247#if __cpp_deduction_guides >= 201606
1248 // These helper traits are used for deduction guides
1249 // of associative containers.
1250 template<typename _InputIterator>
1251 using __iter_key_t = remove_const_t<
1252 typename iterator_traits<_InputIterator>::value_type::first_type>;
1253
1254 template<typename _InputIterator>
1255 using __iter_val_t =
1256 typename iterator_traits<_InputIterator>::value_type::second_type;
1257
1258 template<typename _T1, typename _T2>
1259 struct pair;
1260
1261 template<typename _InputIterator>
1262 using __iter_to_alloc_t =
1263 pair<add_const_t<__iter_key_t<_InputIterator>>,
1264 __iter_val_t<_InputIterator>>;
1265
1266#endif
1267
1268_GLIBCXX_END_NAMESPACE_VERSION
1269} // namespace
1270
1271#ifdef _GLIBCXX_DEBUG
1272# include <debug/stl_iterator.h>
1273#endif
1274
1275#endif
1276