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