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