libstdc++
bits/stl_iterator.h
Go to the documentation of this file.
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
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>
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
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 // 1012. reverse_iterator default ctor should value initialize
122 reverse_iterator() : current() { }
123
124 /**
125 * This %iterator will move in the opposite direction that @p x does.
126 */
127 explicit
128 reverse_iterator(iterator_type __x) : current(__x) { }
129
130 /**
131 * The copy constructor is normal.
132 */
134 : current(__x.current) { }
135
136 /**
137 * A %reverse_iterator across other types can be copied if the
138 * underlying %iterator can be converted to the type of @c current.
139 */
140 template<typename _Iter>
142 : current(__x.base()) { }
143
144 /**
145 * @return @c current, the %iterator used for underlying work.
146 */
147 iterator_type
148 base() const
149 { return current; }
150
151 /**
152 * @return A reference to the value at @c --current
153 *
154 * This requires that @c --current is dereferenceable.
155 *
156 * @warning This implementation requires that for an iterator of the
157 * underlying iterator type, @c x, a reference obtained by
158 * @c *x remains valid after @c x has been modified or
159 * destroyed. This is a bug: http://gcc.gnu.org/PR51823
160 */
161 reference
162 operator*() const
163 {
164 _Iterator __tmp = current;
165 return *--__tmp;
166 }
167
168 /**
169 * @return A pointer to the value at @c --current
170 *
171 * This requires that @c --current is dereferenceable.
172 */
173 // _GLIBCXX_RESOLVE_LIB_DEFECTS
174 // 2188. Reverse iterator does not fully support targets that overload &
175 pointer
177 { return std::__addressof(operator*()); }
178
179 /**
180 * @return @c *this
181 *
182 * Decrements the underlying iterator.
183 */
186 {
187 --current;
188 return *this;
189 }
190
191 /**
192 * @return The original value of @c *this
193 *
194 * Decrements the underlying iterator.
195 */
198 {
199 reverse_iterator __tmp = *this;
200 --current;
201 return __tmp;
202 }
203
204 /**
205 * @return @c *this
206 *
207 * Increments the underlying iterator.
208 */
211 {
212 ++current;
213 return *this;
214 }
215
216 /**
217 * @return A reverse_iterator with the previous value of @c *this
218 *
219 * Increments the underlying iterator.
220 */
223 {
224 reverse_iterator __tmp = *this;
225 ++current;
226 return __tmp;
227 }
228
229 /**
230 * @return A reverse_iterator that refers to @c current - @a __n
231 *
232 * The underlying iterator must be a Random Access Iterator.
233 */
235 operator+(difference_type __n) const
236 { return reverse_iterator(current - __n); }
237
238 /**
239 * @return *this
240 *
241 * Moves the underlying iterator backwards @a __n steps.
242 * The underlying iterator must be a Random Access Iterator.
243 */
245 operator+=(difference_type __n)
246 {
247 current -= __n;
248 return *this;
249 }
250
251 /**
252 * @return A reverse_iterator that refers to @c current - @a __n
253 *
254 * The underlying iterator must be a Random Access Iterator.
255 */
257 operator-(difference_type __n) const
258 { return reverse_iterator(current + __n); }
259
260 /**
261 * @return *this
262 *
263 * Moves the underlying iterator forwards @a __n steps.
264 * The underlying iterator must be a Random Access Iterator.
265 */
267 operator-=(difference_type __n)
268 {
269 current += __n;
270 return *this;
271 }
272
273 /**
274 * @return The value at @c current - @a __n - 1
275 *
276 * The underlying iterator must be a Random Access Iterator.
277 */
278 reference
279 operator[](difference_type __n) const
280 { return *(*this + __n); }
281 };
282
283 //@{
284 /**
285 * @param __x A %reverse_iterator.
286 * @param __y A %reverse_iterator.
287 * @return A simple bool.
288 *
289 * Reverse iterators forward many operations to their underlying base()
290 * iterators. Others are implemented in terms of one another.
291 *
292 */
293 template<typename _Iterator>
294 inline bool
295 operator==(const reverse_iterator<_Iterator>& __x,
297 { return __x.base() == __y.base(); }
298
299 template<typename _Iterator>
300 inline bool
301 operator<(const reverse_iterator<_Iterator>& __x,
302 const reverse_iterator<_Iterator>& __y)
303 { return __y.base() < __x.base(); }
304
305 template<typename _Iterator>
306 inline bool
307 operator!=(const reverse_iterator<_Iterator>& __x,
308 const reverse_iterator<_Iterator>& __y)
309 { return !(__x == __y); }
310
311 template<typename _Iterator>
312 inline bool
313 operator>(const reverse_iterator<_Iterator>& __x,
314 const reverse_iterator<_Iterator>& __y)
315 { return __y < __x; }
316
317 template<typename _Iterator>
318 inline bool
319 operator<=(const reverse_iterator<_Iterator>& __x,
320 const reverse_iterator<_Iterator>& __y)
321 { return !(__y < __x); }
322
323 template<typename _Iterator>
324 inline bool
325 operator>=(const reverse_iterator<_Iterator>& __x,
326 const reverse_iterator<_Iterator>& __y)
327 { return !(__x < __y); }
328
329 template<typename _Iterator>
330#if __cplusplus < 201103L
331 inline typename reverse_iterator<_Iterator>::difference_type
332 operator-(const reverse_iterator<_Iterator>& __x,
333 const reverse_iterator<_Iterator>& __y)
334#else
335 inline auto
336 operator-(const reverse_iterator<_Iterator>& __x,
337 const reverse_iterator<_Iterator>& __y)
338 -> decltype(__x.base() - __y.base())
339#endif
340 { return __y.base() - __x.base(); }
341
342 template<typename _Iterator>
343 inline reverse_iterator<_Iterator>
344 operator+(typename reverse_iterator<_Iterator>::difference_type __n,
345 const reverse_iterator<_Iterator>& __x)
346 { return reverse_iterator<_Iterator>(__x.base() - __n); }
347
348 // _GLIBCXX_RESOLVE_LIB_DEFECTS
349 // DR 280. Comparison of reverse_iterator to const reverse_iterator.
350 template<typename _IteratorL, typename _IteratorR>
351 inline bool
352 operator==(const reverse_iterator<_IteratorL>& __x,
353 const reverse_iterator<_IteratorR>& __y)
354 { return __x.base() == __y.base(); }
355
356 template<typename _IteratorL, typename _IteratorR>
357 inline bool
358 operator<(const reverse_iterator<_IteratorL>& __x,
359 const reverse_iterator<_IteratorR>& __y)
360 { return __y.base() < __x.base(); }
361
362 template<typename _IteratorL, typename _IteratorR>
363 inline bool
364 operator!=(const reverse_iterator<_IteratorL>& __x,
365 const reverse_iterator<_IteratorR>& __y)
366 { return !(__x == __y); }
367
368 template<typename _IteratorL, typename _IteratorR>
369 inline bool
370 operator>(const reverse_iterator<_IteratorL>& __x,
371 const reverse_iterator<_IteratorR>& __y)
372 { return __y < __x; }
373
374 template<typename _IteratorL, typename _IteratorR>
375 inline bool
376 operator<=(const reverse_iterator<_IteratorL>& __x,
377 const reverse_iterator<_IteratorR>& __y)
378 { return !(__y < __x); }
379
380 template<typename _IteratorL, typename _IteratorR>
381 inline bool
382 operator>=(const reverse_iterator<_IteratorL>& __x,
383 const reverse_iterator<_IteratorR>& __y)
384 { return !(__x < __y); }
385
386 template<typename _IteratorL, typename _IteratorR>
387#if __cplusplus >= 201103L
388 // DR 685.
389 inline auto
390 operator-(const reverse_iterator<_IteratorL>& __x,
391 const reverse_iterator<_IteratorR>& __y)
392 -> decltype(__y.base() - __x.base())
393#else
394 inline typename reverse_iterator<_IteratorL>::difference_type
395 operator-(const reverse_iterator<_IteratorL>& __x,
396 const reverse_iterator<_IteratorR>& __y)
397#endif
398 { return __y.base() - __x.base(); }
399 //@}
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 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 reverse_iterator<_Iterator>
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>
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
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
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&
504 { return *this; }
505
506 /// Simply returns *this. (This %iterator does not @a move.)
509 { return *this; }
510
511 /// Simply returns *this. (This %iterator does not @a move.)
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>
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
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
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&
595 { return *this; }
596
597 /// Simply returns *this. (This %iterator does not @a move.)
600 { return *this; }
601
602 /// Simply returns *this. (This %iterator does not @a move.)
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>
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
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
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&
709 { return *this; }
710
711 /// Simply returns *this. (This %iterator does not @a move.)
714 { return *this; }
715
716 /// Simply returns *this. (This %iterator does not @a move.)
719 { return *this; }
720 };
721
722 /**
723 * @param __x A container of arbitrary type.
724 * @return An instance of insert_iterator working on @p __x.
725 *
726 * This wrapper function helps in creating insert_iterator instances.
727 * Typing the name of the %iterator requires knowing the precise full
728 * type of the container, which can be tedious and impedes generic
729 * programming. Using this function lets you take advantage of automatic
730 * template parameter deduction, making the compiler match the correct
731 * types for you.
732 */
733 template<typename _Container, typename _Iterator>
734 inline insert_iterator<_Container>
735 inserter(_Container& __x, _Iterator __i)
736 {
738 typename _Container::iterator(__i));
739 }
740
741 // @} group iterators
742
743_GLIBCXX_END_NAMESPACE_VERSION
744} // namespace
745
746namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
747{
748_GLIBCXX_BEGIN_NAMESPACE_VERSION
749
750 // This iterator adapter is @a normal in the sense that it does not
751 // change the semantics of any of the operators of its iterator
752 // parameter. Its primary purpose is to convert an iterator that is
753 // not a class, e.g. a pointer, into an iterator that is a class.
754 // The _Container parameter exists solely so that different containers
755 // using this template can instantiate different types, even if the
756 // _Iterator parameter is the same.
757 using std::iterator_traits;
758 using std::iterator;
759 template<typename _Iterator, typename _Container>
760 class __normal_iterator
761 {
762 protected:
763 _Iterator _M_current;
764
765 typedef iterator_traits<_Iterator> __traits_type;
766
767 public:
768 typedef _Iterator iterator_type;
769 typedef typename __traits_type::iterator_category iterator_category;
770 typedef typename __traits_type::value_type value_type;
771 typedef typename __traits_type::difference_type difference_type;
772 typedef typename __traits_type::reference reference;
773 typedef typename __traits_type::pointer pointer;
774
775 _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT
776 : _M_current(_Iterator()) { }
777
778 explicit
779 __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT
780 : _M_current(__i) { }
781
782 // Allow iterator to const_iterator conversion
783 template<typename _Iter>
784 __normal_iterator(const __normal_iterator<_Iter,
785 typename __enable_if<
786 (std::__are_same<_Iter, typename _Container::pointer>::__value),
787 _Container>::__type>& __i) _GLIBCXX_NOEXCEPT
788 : _M_current(__i.base()) { }
789
790 // Forward iterator requirements
791 reference
792 operator*() const _GLIBCXX_NOEXCEPT
793 { return *_M_current; }
794
795 pointer
796 operator->() const _GLIBCXX_NOEXCEPT
797 { return _M_current; }
798
799 __normal_iterator&
800 operator++() _GLIBCXX_NOEXCEPT
801 {
802 ++_M_current;
803 return *this;
804 }
805
806 __normal_iterator
807 operator++(int) _GLIBCXX_NOEXCEPT
808 { return __normal_iterator(_M_current++); }
809
810 // Bidirectional iterator requirements
811 __normal_iterator&
812 operator--() _GLIBCXX_NOEXCEPT
813 {
814 --_M_current;
815 return *this;
816 }
817
818 __normal_iterator
819 operator--(int) _GLIBCXX_NOEXCEPT
820 { return __normal_iterator(_M_current--); }
821
822 // Random access iterator requirements
823 reference
824 operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
825 { return _M_current[__n]; }
826
827 __normal_iterator&
828 operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
829 { _M_current += __n; return *this; }
830
831 __normal_iterator
832 operator+(difference_type __n) const _GLIBCXX_NOEXCEPT
833 { return __normal_iterator(_M_current + __n); }
834
835 __normal_iterator&
836 operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
837 { _M_current -= __n; return *this; }
838
839 __normal_iterator
840 operator-(difference_type __n) const _GLIBCXX_NOEXCEPT
841 { return __normal_iterator(_M_current - __n); }
842
843 const _Iterator&
844 base() const _GLIBCXX_NOEXCEPT
845 { return _M_current; }
846 };
847
848 // Note: In what follows, the left- and right-hand-side iterators are
849 // allowed to vary in types (conceptually in cv-qualification) so that
850 // comparison between cv-qualified and non-cv-qualified iterators be
851 // valid. However, the greedy and unfriendly operators in std::rel_ops
852 // will make overload resolution ambiguous (when in scope) if we don't
853 // provide overloads whose operands are of the same type. Can someone
854 // remind me what generic programming is about? -- Gaby
855
856 // Forward iterator requirements
857 template<typename _IteratorL, typename _IteratorR, typename _Container>
858 inline bool
859 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
860 const __normal_iterator<_IteratorR, _Container>& __rhs)
861 _GLIBCXX_NOEXCEPT
862 { return __lhs.base() == __rhs.base(); }
863
864 template<typename _Iterator, typename _Container>
865 inline bool
866 operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
867 const __normal_iterator<_Iterator, _Container>& __rhs)
868 _GLIBCXX_NOEXCEPT
869 { return __lhs.base() == __rhs.base(); }
870
871 template<typename _IteratorL, typename _IteratorR, typename _Container>
872 inline bool
873 operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
874 const __normal_iterator<_IteratorR, _Container>& __rhs)
875 _GLIBCXX_NOEXCEPT
876 { return __lhs.base() != __rhs.base(); }
877
878 template<typename _Iterator, typename _Container>
879 inline bool
880 operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
881 const __normal_iterator<_Iterator, _Container>& __rhs)
882 _GLIBCXX_NOEXCEPT
883 { return __lhs.base() != __rhs.base(); }
884
885 // Random access iterator requirements
886 template<typename _IteratorL, typename _IteratorR, typename _Container>
887 inline bool
888 operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
889 const __normal_iterator<_IteratorR, _Container>& __rhs)
890 _GLIBCXX_NOEXCEPT
891 { return __lhs.base() < __rhs.base(); }
892
893 template<typename _Iterator, typename _Container>
894 inline bool
895 operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
896 const __normal_iterator<_Iterator, _Container>& __rhs)
897 _GLIBCXX_NOEXCEPT
898 { return __lhs.base() < __rhs.base(); }
899
900 template<typename _IteratorL, typename _IteratorR, typename _Container>
901 inline bool
902 operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
903 const __normal_iterator<_IteratorR, _Container>& __rhs)
904 _GLIBCXX_NOEXCEPT
905 { return __lhs.base() > __rhs.base(); }
906
907 template<typename _Iterator, typename _Container>
908 inline bool
909 operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
910 const __normal_iterator<_Iterator, _Container>& __rhs)
911 _GLIBCXX_NOEXCEPT
912 { return __lhs.base() > __rhs.base(); }
913
914 template<typename _IteratorL, typename _IteratorR, typename _Container>
915 inline bool
916 operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
917 const __normal_iterator<_IteratorR, _Container>& __rhs)
918 _GLIBCXX_NOEXCEPT
919 { return __lhs.base() <= __rhs.base(); }
920
921 template<typename _Iterator, typename _Container>
922 inline bool
923 operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
924 const __normal_iterator<_Iterator, _Container>& __rhs)
925 _GLIBCXX_NOEXCEPT
926 { return __lhs.base() <= __rhs.base(); }
927
928 template<typename _IteratorL, typename _IteratorR, typename _Container>
929 inline bool
930 operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
931 const __normal_iterator<_IteratorR, _Container>& __rhs)
932 _GLIBCXX_NOEXCEPT
933 { return __lhs.base() >= __rhs.base(); }
934
935 template<typename _Iterator, typename _Container>
936 inline bool
937 operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
938 const __normal_iterator<_Iterator, _Container>& __rhs)
939 _GLIBCXX_NOEXCEPT
940 { return __lhs.base() >= __rhs.base(); }
941
942 // _GLIBCXX_RESOLVE_LIB_DEFECTS
943 // According to the resolution of DR179 not only the various comparison
944 // operators but also operator- must accept mixed iterator/const_iterator
945 // parameters.
946 template<typename _IteratorL, typename _IteratorR, typename _Container>
947#if __cplusplus >= 201103L
948 // DR 685.
949 inline auto
950 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
951 const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept
952 -> decltype(__lhs.base() - __rhs.base())
953#else
954 inline typename __normal_iterator<_IteratorL, _Container>::difference_type
955 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
956 const __normal_iterator<_IteratorR, _Container>& __rhs)
957#endif
958 { return __lhs.base() - __rhs.base(); }
959
960 template<typename _Iterator, typename _Container>
961 inline typename __normal_iterator<_Iterator, _Container>::difference_type
962 operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
963 const __normal_iterator<_Iterator, _Container>& __rhs)
964 _GLIBCXX_NOEXCEPT
965 { return __lhs.base() - __rhs.base(); }
966
967 template<typename _Iterator, typename _Container>
968 inline __normal_iterator<_Iterator, _Container>
969 operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
970 __n, const __normal_iterator<_Iterator, _Container>& __i)
971 _GLIBCXX_NOEXCEPT
972 { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
973
974_GLIBCXX_END_NAMESPACE_VERSION
975} // namespace
976
977namespace std _GLIBCXX_VISIBILITY(default)
978{
979_GLIBCXX_BEGIN_NAMESPACE_VERSION
980
981 template<typename _Iterator, typename _Container>
982 _Iterator
983 __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
984 { return __it.base(); }
985
986_GLIBCXX_END_NAMESPACE_VERSION
987} // namespace
988
989#if __cplusplus >= 201103L
990
991namespace std _GLIBCXX_VISIBILITY(default)
992{
993_GLIBCXX_BEGIN_NAMESPACE_VERSION
994
995 /**
996 * @addtogroup iterators
997 * @{
998 */
999
1000 // 24.4.3 Move iterators
1001 /**
1002 * Class template move_iterator is an iterator adapter with the same
1003 * behavior as the underlying iterator except that its dereference
1004 * operator implicitly converts the value returned by the underlying
1005 * iterator's dereference operator to an rvalue reference. Some
1006 * generic algorithms can be called with move iterators to replace
1007 * copying with moving.
1008 */
1009 template<typename _Iterator>
1011 {
1012 protected:
1013 _Iterator _M_current;
1014
1016 typedef typename __traits_type::reference __base_ref;
1017
1018 public:
1019 typedef _Iterator iterator_type;
1020 typedef typename __traits_type::iterator_category iterator_category;
1021 typedef typename __traits_type::value_type value_type;
1022 typedef typename __traits_type::difference_type difference_type;
1023 // NB: DR 680.
1024 typedef _Iterator pointer;
1025 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1026 // 2106. move_iterator wrapping iterators returning prvalues
1028 typename remove_reference<__base_ref>::type&&,
1029 __base_ref>::type reference;
1030
1032 : _M_current() { }
1033
1034 explicit
1035 move_iterator(iterator_type __i)
1036 : _M_current(__i) { }
1037
1038 template<typename _Iter>
1040 : _M_current(__i.base()) { }
1041
1042 iterator_type
1043 base() const
1044 { return _M_current; }
1045
1046 reference
1047 operator*() const
1048 { return static_cast<reference>(*_M_current); }
1049
1050 pointer
1051 operator->() const
1052 { return _M_current; }
1053
1055 operator++()
1056 {
1057 ++_M_current;
1058 return *this;
1059 }
1060
1062 operator++(int)
1063 {
1064 move_iterator __tmp = *this;
1065 ++_M_current;
1066 return __tmp;
1067 }
1068
1070 operator--()
1071 {
1072 --_M_current;
1073 return *this;
1074 }
1075
1077 operator--(int)
1078 {
1079 move_iterator __tmp = *this;
1080 --_M_current;
1081 return __tmp;
1082 }
1083
1085 operator+(difference_type __n) const
1086 { return move_iterator(_M_current + __n); }
1087
1089 operator+=(difference_type __n)
1090 {
1091 _M_current += __n;
1092 return *this;
1093 }
1094
1096 operator-(difference_type __n) const
1097 { return move_iterator(_M_current - __n); }
1098
1100 operator-=(difference_type __n)
1101 {
1102 _M_current -= __n;
1103 return *this;
1104 }
1105
1106 reference
1107 operator[](difference_type __n) const
1108 { return std::move(_M_current[__n]); }
1109 };
1110
1111 // Note: See __normal_iterator operators note from Gaby to understand
1112 // why there are always 2 versions for most of the move_iterator
1113 // operators.
1114 template<typename _IteratorL, typename _IteratorR>
1115 inline bool
1116 operator==(const move_iterator<_IteratorL>& __x,
1118 { return __x.base() == __y.base(); }
1119
1120 template<typename _Iterator>
1121 inline bool
1122 operator==(const move_iterator<_Iterator>& __x,
1123 const move_iterator<_Iterator>& __y)
1124 { return __x.base() == __y.base(); }
1125
1126 template<typename _IteratorL, typename _IteratorR>
1127 inline bool
1128 operator!=(const move_iterator<_IteratorL>& __x,
1129 const move_iterator<_IteratorR>& __y)
1130 { return !(__x == __y); }
1131
1132 template<typename _Iterator>
1133 inline bool
1134 operator!=(const move_iterator<_Iterator>& __x,
1135 const move_iterator<_Iterator>& __y)
1136 { return !(__x == __y); }
1137
1138 template<typename _IteratorL, typename _IteratorR>
1139 inline bool
1140 operator<(const move_iterator<_IteratorL>& __x,
1141 const move_iterator<_IteratorR>& __y)
1142 { return __x.base() < __y.base(); }
1143
1144 template<typename _Iterator>
1145 inline bool
1146 operator<(const move_iterator<_Iterator>& __x,
1147 const move_iterator<_Iterator>& __y)
1148 { return __x.base() < __y.base(); }
1149
1150 template<typename _IteratorL, typename _IteratorR>
1151 inline bool
1152 operator<=(const move_iterator<_IteratorL>& __x,
1153 const move_iterator<_IteratorR>& __y)
1154 { return !(__y < __x); }
1155
1156 template<typename _Iterator>
1157 inline bool
1158 operator<=(const move_iterator<_Iterator>& __x,
1159 const move_iterator<_Iterator>& __y)
1160 { return !(__y < __x); }
1161
1162 template<typename _IteratorL, typename _IteratorR>
1163 inline bool
1164 operator>(const move_iterator<_IteratorL>& __x,
1165 const move_iterator<_IteratorR>& __y)
1166 { return __y < __x; }
1167
1168 template<typename _Iterator>
1169 inline bool
1170 operator>(const move_iterator<_Iterator>& __x,
1171 const move_iterator<_Iterator>& __y)
1172 { return __y < __x; }
1173
1174 template<typename _IteratorL, typename _IteratorR>
1175 inline bool
1176 operator>=(const move_iterator<_IteratorL>& __x,
1177 const move_iterator<_IteratorR>& __y)
1178 { return !(__x < __y); }
1179
1180 template<typename _Iterator>
1181 inline bool
1182 operator>=(const move_iterator<_Iterator>& __x,
1183 const move_iterator<_Iterator>& __y)
1184 { return !(__x < __y); }
1185
1186 // DR 685.
1187 template<typename _IteratorL, typename _IteratorR>
1188 inline auto
1189 operator-(const move_iterator<_IteratorL>& __x,
1190 const move_iterator<_IteratorR>& __y)
1191 -> decltype(__x.base() - __y.base())
1192 { return __x.base() - __y.base(); }
1193
1194 template<typename _Iterator>
1195 inline auto
1196 operator-(const move_iterator<_Iterator>& __x,
1197 const move_iterator<_Iterator>& __y)
1198 -> decltype(__x.base() - __y.base())
1199 { return __x.base() - __y.base(); }
1200
1201 template<typename _Iterator>
1202 inline move_iterator<_Iterator>
1203 operator+(typename move_iterator<_Iterator>::difference_type __n,
1204 const move_iterator<_Iterator>& __x)
1205 { return __x + __n; }
1206
1207 template<typename _Iterator>
1208 inline move_iterator<_Iterator>
1209 make_move_iterator(_Iterator __i)
1210 { return move_iterator<_Iterator>(__i); }
1211
1212 template<typename _Iterator, typename _ReturnType
1213 = typename conditional<__move_if_noexcept_cond
1214 <typename iterator_traits<_Iterator>::value_type>::value,
1215 _Iterator, move_iterator<_Iterator>>::type>
1216 inline _ReturnType
1217 __make_move_if_noexcept_iterator(_Iterator __i)
1218 { return _ReturnType(__i); }
1219
1220 // Overload for pointers that matches std::move_if_noexcept more closely,
1221 // returning a constant iterator when we don't want to move.
1222 template<typename _Tp, typename _ReturnType
1223 = typename conditional<__move_if_noexcept_cond<_Tp>::value,
1224 const _Tp*, move_iterator<_Tp*>>::type>
1225 inline _ReturnType
1226 __make_move_if_noexcept_iterator(_Tp* __i)
1227 { return _ReturnType(__i); }
1228
1229 // @} group iterators
1230
1231 template<typename _Iterator>
1232 auto
1233 __niter_base(move_iterator<_Iterator> __it)
1234 -> decltype(make_move_iterator(__niter_base(__it.base())))
1235 { return make_move_iterator(__niter_base(__it.base())); }
1236
1237 template<typename _Iterator>
1238 struct __is_move_iterator<move_iterator<_Iterator> >
1239 {
1240 enum { __value = 1 };
1241 typedef __true_type __type;
1242 };
1243
1244 template<typename _Iterator>
1245 auto
1246 __miter_base(move_iterator<_Iterator> __it)
1247 -> decltype(__miter_base(__it.base()))
1248 { return __miter_base(__it.base()); }
1249
1250_GLIBCXX_END_NAMESPACE_VERSION
1251} // namespace
1252
1253#define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
1254#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
1255 std::__make_move_if_noexcept_iterator(_Iter)
1256#else
1257#define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
1258#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
1259#endif // C++11
1260
1261#ifdef _GLIBCXX_DEBUG
1262# include <debug/stl_iterator.h>
1263#endif
1264
1265#endif
complex< _Tp > operator+(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x plus y.
Definition complex:326
complex< _Tp > operator-(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x minus y.
Definition complex:356
_Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition move.h:47
back_insert_iterator< _Container > back_inserter(_Container &__x)
_Container container_type
A nested typedef for the type of whatever container you used.
front_insert_iterator operator++(int)
Simply returns *this. (This iterator does not move.)
back_insert_iterator(_Container &__x)
The only way to create this iterator is with a container.
back_insert_iterator & operator++()
Simply returns *this. (This iterator does not move.)
reverse_iterator & operator+=(difference_type __n)
reverse_iterator(const reverse_iterator< _Iter > &__x)
insert_iterator & operator=(const typename _Container::value_type &__value)
_Container container_type
A nested typedef for the type of whatever container you used.
reverse_iterator & operator++()
reverse_iterator(const reverse_iterator &__x)
back_insert_iterator & operator*()
Simply returns *this.
back_insert_iterator & operator=(const typename _Container::value_type &__value)
insert_iterator & operator++(int)
Simply returns *this. (This iterator does not move.)
insert_iterator(_Container &__x, typename _Container::iterator __i)
reference operator*() const
reverse_iterator operator+(difference_type __n) const
reverse_iterator & operator--()
reverse_iterator operator++(int)
reference operator[](difference_type __n) const
_Container container_type
A nested typedef for the type of whatever container you used.
insert_iterator< _Container > inserter(_Container &__x, _Iterator __i)
front_insert_iterator & operator*()
Simply returns *this.
reverse_iterator operator--(int)
reverse_iterator operator-(difference_type __n) const
insert_iterator & operator*()
Simply returns *this.
reverse_iterator< _Iterator > make_reverse_iterator(_Iterator __i)
Generator function for reverse_iterator.
front_insert_iterator< _Container > front_inserter(_Container &__x)
reverse_iterator & operator-=(difference_type __n)
iterator_type base() const
reverse_iterator(iterator_type __x)
back_insert_iterator operator++(int)
Simply returns *this. (This iterator does not move.)
front_insert_iterator & operator=(const typename _Container::value_type &__value)
insert_iterator & operator++()
Simply returns *this. (This iterator does not move.)
front_insert_iterator(_Container &__x)
The only way to create this iterator is with a container.
front_insert_iterator & operator++()
Simply returns *this. (This iterator does not move.)
ISO C++ entities toplevel namespace is std.
GNU extensions for public use.
Turns assignment into insertion.
Turns assignment into insertion.
Turns assignment into insertion.
Common iterator class.