1 // Iterators -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
4 // Free Software Foundation, Inc.
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 2, or (at your option)
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
17 // You should have received a copy of the GNU General Public License along
18 // with this library; see the file COPYING. If not, write to the Free
19 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
22 // As a special exception, you may use this file as part of a free software
23 // library without restriction. Specifically, if other files instantiate
24 // templates or use macros or inline functions from this file, or you compile
25 // this file and link it with other files to produce an executable, this
26 // file does not by itself cause the resulting executable to be covered by
27 // the GNU General Public License. This exception does not however
28 // invalidate any other reasons why the executable file might be covered by
29 // the GNU General Public License.
34 * Hewlett-Packard Company
36 * Permission to use, copy, modify, distribute and sell this software
37 * and its documentation for any purpose is hereby granted without fee,
38 * provided that the above copyright notice appear in all copies and
39 * that both that copyright notice and this permission notice appear
40 * in supporting documentation. Hewlett-Packard Company makes no
41 * representations about the suitability of this software for any
42 * purpose. It is provided "as is" without express or implied warranty.
45 * Copyright (c) 1996-1998
46 * Silicon Graphics Computer Systems, Inc.
48 * Permission to use, copy, modify, distribute and sell this software
49 * and its documentation for any purpose is hereby granted without fee,
50 * provided that the above copyright notice appear in all copies and
51 * that both that copyright notice and this permission notice appear
52 * in supporting documentation. Silicon Graphics makes no
53 * representations about the suitability of this software for any
54 * purpose. It is provided "as is" without express or implied warranty.
57 /** @file stl_iterator.h
58 * This is an internal header file, included by other library headers.
59 * You should not attempt to use it directly.
61 * This file implements reverse_iterator, back_insert_iterator,
62 * front_insert_iterator, insert_iterator, __normal_iterator, and their
63 * supporting functions and overloaded operators.
69 #include <bits/cpp_type_traits.h>
70 #include <ext/type_traits.h>
72 _GLIBCXX_BEGIN_NAMESPACE(std
)
74 // 24.4.1 Reverse iterators
76 * "Bidirectional and random access iterators have corresponding reverse
77 * %iterator adaptors that iterate through the data structure in the
78 * opposite direction. They have the same signatures as the corresponding
79 * iterators. The fundamental relation between a reverse %iterator and its
80 * corresponding %iterator @c i is established by the identity:
82 * &*(reverse_iterator(i)) == &*(i - 1)
85 * This mapping is dictated by the fact that while there is always a
86 * pointer past the end of an array, there might not be a valid pointer
87 * before the beginning of an array." [24.4.1]/1,2
89 * Reverse iterators can be tricky and surprising at first. Their
90 * semantics make sense, however, and the trickiness is a side effect of
91 * the requirement that the iterators must be safe.
93 template<typename _Iterator
>
94 class reverse_iterator
95 : public iterator
<typename iterator_traits
<_Iterator
>::iterator_category
,
96 typename iterator_traits
<_Iterator
>::value_type
,
97 typename iterator_traits
<_Iterator
>::difference_type
,
98 typename iterator_traits
<_Iterator
>::pointer
,
99 typename iterator_traits
<_Iterator
>::reference
>
105 typedef _Iterator iterator_type
;
106 typedef typename iterator_traits
<_Iterator
>::difference_type
108 typedef typename iterator_traits
<_Iterator
>::reference reference
;
109 typedef typename iterator_traits
<_Iterator
>::pointer pointer
;
113 * The default constructor default-initializes member @p current.
114 * If it is a pointer, that means it is zero-initialized.
116 // _GLIBCXX_RESOLVE_LIB_DEFECTS
117 // 235 No specification of default ctor for reverse_iterator
118 reverse_iterator() : current() { }
121 * This %iterator will move in the opposite direction that @p x does.
124 reverse_iterator(iterator_type __x
) : current(__x
) { }
127 * The copy constructor is normal.
129 reverse_iterator(const reverse_iterator
& __x
)
130 : current(__x
.current
) { }
133 * A reverse_iterator across other types can be copied in the normal
136 template<typename _Iter
>
137 reverse_iterator(const reverse_iterator
<_Iter
>& __x
)
138 : current(__x
.base()) { }
141 * @return @c current, the %iterator used for underlying work.
155 _Iterator __tmp
= current
;
166 { return &(operator*()); }
188 reverse_iterator __tmp
= *this;
213 reverse_iterator __tmp
= *this;
224 operator+(difference_type __n
) const
225 { return reverse_iterator(current
- __n
); }
233 operator+=(difference_type __n
)
245 operator-(difference_type __n
) const
246 { return reverse_iterator(current
+ __n
); }
254 operator-=(difference_type __n
)
266 operator[](difference_type __n
) const
267 { return *(*this + __n
); }
272 * @param x A %reverse_iterator.
273 * @param y A %reverse_iterator.
274 * @return A simple bool.
276 * Reverse iterators forward many operations to their underlying base()
277 * iterators. Others are implemented in terms of one another.
280 template<typename _Iterator
>
282 operator==(const reverse_iterator
<_Iterator
>& __x
,
283 const reverse_iterator
<_Iterator
>& __y
)
284 { return __x
.base() == __y
.base(); }
286 template<typename _Iterator
>
288 operator<(const reverse_iterator
<_Iterator
>& __x
,
289 const reverse_iterator
<_Iterator
>& __y
)
290 { return __y
.base() < __x
.base(); }
292 template<typename _Iterator
>
294 operator!=(const reverse_iterator
<_Iterator
>& __x
,
295 const reverse_iterator
<_Iterator
>& __y
)
296 { return !(__x
== __y
); }
298 template<typename _Iterator
>
300 operator>(const reverse_iterator
<_Iterator
>& __x
,
301 const reverse_iterator
<_Iterator
>& __y
)
302 { return __y
< __x
; }
304 template<typename _Iterator
>
306 operator<=(const reverse_iterator
<_Iterator
>& __x
,
307 const reverse_iterator
<_Iterator
>& __y
)
308 { return !(__y
< __x
); }
310 template<typename _Iterator
>
312 operator>=(const reverse_iterator
<_Iterator
>& __x
,
313 const reverse_iterator
<_Iterator
>& __y
)
314 { return !(__x
< __y
); }
316 template<typename _Iterator
>
317 inline typename reverse_iterator
<_Iterator
>::difference_type
318 operator-(const reverse_iterator
<_Iterator
>& __x
,
319 const reverse_iterator
<_Iterator
>& __y
)
320 { return __y
.base() - __x
.base(); }
322 template<typename _Iterator
>
323 inline reverse_iterator
<_Iterator
>
324 operator+(typename reverse_iterator
<_Iterator
>::difference_type __n
,
325 const reverse_iterator
<_Iterator
>& __x
)
326 { return reverse_iterator
<_Iterator
>(__x
.base() - __n
); }
328 // _GLIBCXX_RESOLVE_LIB_DEFECTS
329 // DR 280. Comparison of reverse_iterator to const reverse_iterator.
330 template<typename _IteratorL
, typename _IteratorR
>
332 operator==(const reverse_iterator
<_IteratorL
>& __x
,
333 const reverse_iterator
<_IteratorR
>& __y
)
334 { return __x
.base() == __y
.base(); }
336 template<typename _IteratorL
, typename _IteratorR
>
338 operator<(const reverse_iterator
<_IteratorL
>& __x
,
339 const reverse_iterator
<_IteratorR
>& __y
)
340 { return __y
.base() < __x
.base(); }
342 template<typename _IteratorL
, typename _IteratorR
>
344 operator!=(const reverse_iterator
<_IteratorL
>& __x
,
345 const reverse_iterator
<_IteratorR
>& __y
)
346 { return !(__x
== __y
); }
348 template<typename _IteratorL
, typename _IteratorR
>
350 operator>(const reverse_iterator
<_IteratorL
>& __x
,
351 const reverse_iterator
<_IteratorR
>& __y
)
352 { return __y
< __x
; }
354 template<typename _IteratorL
, typename _IteratorR
>
356 operator<=(const reverse_iterator
<_IteratorL
>& __x
,
357 const reverse_iterator
<_IteratorR
>& __y
)
358 { return !(__y
< __x
); }
360 template<typename _IteratorL
, typename _IteratorR
>
362 operator>=(const reverse_iterator
<_IteratorL
>& __x
,
363 const reverse_iterator
<_IteratorR
>& __y
)
364 { return !(__x
< __y
); }
366 template<typename _IteratorL
, typename _IteratorR
>
367 inline typename reverse_iterator
<_IteratorL
>::difference_type
368 operator-(const reverse_iterator
<_IteratorL
>& __x
,
369 const reverse_iterator
<_IteratorR
>& __y
)
370 { return __y
.base() - __x
.base(); }
373 // 24.4.2.2.1 back_insert_iterator
375 * @brief Turns assignment into insertion.
377 * These are output iterators, constructed from a container-of-T.
378 * Assigning a T to the iterator appends it to the container using
381 * Tip: Using the back_inserter function to create these iterators can
384 template<typename _Container
>
385 class back_insert_iterator
386 : public iterator
<output_iterator_tag
, void, void, void, void>
389 _Container
* container
;
392 /// A nested typedef for the type of whatever container you used.
393 typedef _Container container_type
;
395 /// The only way to create this %iterator is with a container.
397 back_insert_iterator(_Container
& __x
) : container(&__x
) { }
400 * @param value An instance of whatever type
401 * container_type::const_reference is; presumably a
402 * reference-to-const T for container<T>.
403 * @return This %iterator, for chained operations.
405 * This kind of %iterator doesn't really have a "position" in the
406 * container (you can think of the position as being permanently at
407 * the end, if you like). Assigning a value to the %iterator will
408 * always append the value to the end of the container.
410 back_insert_iterator
&
411 operator=(typename
_Container::const_reference __value
)
413 container
->push_back(__value
);
417 /// Simply returns *this.
418 back_insert_iterator
&
422 /// Simply returns *this. (This %iterator does not "move".)
423 back_insert_iterator
&
427 /// Simply returns *this. (This %iterator does not "move".)
434 * @param x A container of arbitrary type.
435 * @return An instance of back_insert_iterator working on @p x.
437 * This wrapper function helps in creating back_insert_iterator instances.
438 * Typing the name of the %iterator requires knowing the precise full
439 * type of the container, which can be tedious and impedes generic
440 * programming. Using this function lets you take advantage of automatic
441 * template parameter deduction, making the compiler match the correct
444 template<typename _Container
>
445 inline back_insert_iterator
<_Container
>
446 back_inserter(_Container
& __x
)
447 { return back_insert_iterator
<_Container
>(__x
); }
450 * @brief Turns assignment into insertion.
452 * These are output iterators, constructed from a container-of-T.
453 * Assigning a T to the iterator prepends it to the container using
456 * Tip: Using the front_inserter function to create these iterators can
459 template<typename _Container
>
460 class front_insert_iterator
461 : public iterator
<output_iterator_tag
, void, void, void, void>
464 _Container
* container
;
467 /// A nested typedef for the type of whatever container you used.
468 typedef _Container container_type
;
470 /// The only way to create this %iterator is with a container.
471 explicit front_insert_iterator(_Container
& __x
) : container(&__x
) { }
474 * @param value An instance of whatever type
475 * container_type::const_reference is; presumably a
476 * reference-to-const T for container<T>.
477 * @return This %iterator, for chained operations.
479 * This kind of %iterator doesn't really have a "position" in the
480 * container (you can think of the position as being permanently at
481 * the front, if you like). Assigning a value to the %iterator will
482 * always prepend the value to the front of the container.
484 front_insert_iterator
&
485 operator=(typename
_Container::const_reference __value
)
487 container
->push_front(__value
);
491 /// Simply returns *this.
492 front_insert_iterator
&
496 /// Simply returns *this. (This %iterator does not "move".)
497 front_insert_iterator
&
501 /// Simply returns *this. (This %iterator does not "move".)
502 front_insert_iterator
508 * @param x A container of arbitrary type.
509 * @return An instance of front_insert_iterator working on @p x.
511 * This wrapper function helps in creating front_insert_iterator instances.
512 * Typing the name of the %iterator requires knowing the precise full
513 * type of the container, which can be tedious and impedes generic
514 * programming. Using this function lets you take advantage of automatic
515 * template parameter deduction, making the compiler match the correct
518 template<typename _Container
>
519 inline front_insert_iterator
<_Container
>
520 front_inserter(_Container
& __x
)
521 { return front_insert_iterator
<_Container
>(__x
); }
524 * @brief Turns assignment into insertion.
526 * These are output iterators, constructed from a container-of-T.
527 * Assigning a T to the iterator inserts it in the container at the
528 * %iterator's position, rather than overwriting the value at that
531 * (Sequences will actually insert a @e copy of the value before the
532 * %iterator's position.)
534 * Tip: Using the inserter function to create these iterators can
537 template<typename _Container
>
538 class insert_iterator
539 : public iterator
<output_iterator_tag
, void, void, void, void>
542 _Container
* container
;
543 typename
_Container::iterator iter
;
546 /// A nested typedef for the type of whatever container you used.
547 typedef _Container container_type
;
550 * The only way to create this %iterator is with a container and an
551 * initial position (a normal %iterator into the container).
553 insert_iterator(_Container
& __x
, typename
_Container::iterator __i
)
554 : container(&__x
), iter(__i
) {}
557 * @param value An instance of whatever type
558 * container_type::const_reference is; presumably a
559 * reference-to-const T for container<T>.
560 * @return This %iterator, for chained operations.
562 * This kind of %iterator maintains its own position in the
563 * container. Assigning a value to the %iterator will insert the
564 * value into the container at the place before the %iterator.
566 * The position is maintained such that subsequent assignments will
567 * insert values immediately after one another. For example,
569 * // vector v contains A and Z
571 * insert_iterator i (v, ++v.begin());
576 * // vector v contains A, 1, 2, 3, and Z
580 operator=(const typename
_Container::const_reference __value
)
582 iter
= container
->insert(iter
, __value
);
587 /// Simply returns *this.
592 /// Simply returns *this. (This %iterator does not "move".)
597 /// Simply returns *this. (This %iterator does not "move".)
604 * @param x A container of arbitrary type.
605 * @return An instance of insert_iterator working on @p x.
607 * This wrapper function helps in creating insert_iterator instances.
608 * Typing the name of the %iterator requires knowing the precise full
609 * type of the container, which can be tedious and impedes generic
610 * programming. Using this function lets you take advantage of automatic
611 * template parameter deduction, making the compiler match the correct
614 template<typename _Container
, typename _Iterator
>
615 inline insert_iterator
<_Container
>
616 inserter(_Container
& __x
, _Iterator __i
)
618 return insert_iterator
<_Container
>(__x
,
619 typename
_Container::iterator(__i
));
622 _GLIBCXX_END_NAMESPACE
624 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx
)
626 // This iterator adapter is 'normal' in the sense that it does not
627 // change the semantics of any of the operators of its iterator
628 // parameter. Its primary purpose is to convert an iterator that is
629 // not a class, e.g. a pointer, into an iterator that is a class.
630 // The _Container parameter exists solely so that different containers
631 // using this template can instantiate different types, even if the
632 // _Iterator parameter is the same.
633 using std::iterator_traits
;
635 template<typename _Iterator
, typename _Container
>
636 class __normal_iterator
639 _Iterator _M_current
;
642 typedef typename iterator_traits
<_Iterator
>::iterator_category
644 typedef typename iterator_traits
<_Iterator
>::value_type value_type
;
645 typedef typename iterator_traits
<_Iterator
>::difference_type
647 typedef typename iterator_traits
<_Iterator
>::reference reference
;
648 typedef typename iterator_traits
<_Iterator
>::pointer pointer
;
650 typedef _Iterator _Iterator_type
;
652 __normal_iterator() : _M_current(_Iterator()) { }
655 __normal_iterator(const _Iterator
& __i
) : _M_current(__i
) { }
657 // Allow iterator to const_iterator conversion
658 template<typename _Iter
>
659 __normal_iterator(const __normal_iterator
<_Iter
,
660 typename __enable_if
<
661 (std::__are_same
<_Iter
, typename
_Container::pointer
>::__value
),
662 _Container
>::__type
>& __i
)
663 : _M_current(__i
.base()) { }
665 // Forward iterator requirements
668 { return *_M_current
; }
672 { return _M_current
; }
683 { return __normal_iterator(_M_current
++); }
685 // Bidirectional iterator requirements
695 { return __normal_iterator(_M_current
--); }
697 // Random access iterator requirements
699 operator[](const difference_type
& __n
) const
700 { return _M_current
[__n
]; }
703 operator+=(const difference_type
& __n
)
704 { _M_current
+= __n
; return *this; }
707 operator+(const difference_type
& __n
) const
708 { return __normal_iterator(_M_current
+ __n
); }
711 operator-=(const difference_type
& __n
)
712 { _M_current
-= __n
; return *this; }
715 operator-(const difference_type
& __n
) const
716 { return __normal_iterator(_M_current
- __n
); }
720 { return _M_current
; }
723 // Note: In what follows, the left- and right-hand-side iterators are
724 // allowed to vary in types (conceptually in cv-qualification) so that
725 // comparaison between cv-qualified and non-cv-qualified iterators be
726 // valid. However, the greedy and unfriendly operators in std::rel_ops
727 // will make overload resolution ambiguous (when in scope) if we don't
728 // provide overloads whose operands are of the same type. Can someone
729 // remind me what generic programming is about? -- Gaby
731 // Forward iterator requirements
732 template<typename _IteratorL
, typename _IteratorR
, typename _Container
>
734 operator==(const __normal_iterator
<_IteratorL
, _Container
>& __lhs
,
735 const __normal_iterator
<_IteratorR
, _Container
>& __rhs
)
736 { return __lhs
.base() == __rhs
.base(); }
738 template<typename _Iterator
, typename _Container
>
740 operator==(const __normal_iterator
<_Iterator
, _Container
>& __lhs
,
741 const __normal_iterator
<_Iterator
, _Container
>& __rhs
)
742 { return __lhs
.base() == __rhs
.base(); }
744 template<typename _IteratorL
, typename _IteratorR
, typename _Container
>
746 operator!=(const __normal_iterator
<_IteratorL
, _Container
>& __lhs
,
747 const __normal_iterator
<_IteratorR
, _Container
>& __rhs
)
748 { return __lhs
.base() != __rhs
.base(); }
750 template<typename _Iterator
, typename _Container
>
752 operator!=(const __normal_iterator
<_Iterator
, _Container
>& __lhs
,
753 const __normal_iterator
<_Iterator
, _Container
>& __rhs
)
754 { return __lhs
.base() != __rhs
.base(); }
756 // Random access iterator requirements
757 template<typename _IteratorL
, typename _IteratorR
, typename _Container
>
759 operator<(const __normal_iterator
<_IteratorL
, _Container
>& __lhs
,
760 const __normal_iterator
<_IteratorR
, _Container
>& __rhs
)
761 { return __lhs
.base() < __rhs
.base(); }
763 template<typename _Iterator
, typename _Container
>
765 operator<(const __normal_iterator
<_Iterator
, _Container
>& __lhs
,
766 const __normal_iterator
<_Iterator
, _Container
>& __rhs
)
767 { return __lhs
.base() < __rhs
.base(); }
769 template<typename _IteratorL
, typename _IteratorR
, typename _Container
>
771 operator>(const __normal_iterator
<_IteratorL
, _Container
>& __lhs
,
772 const __normal_iterator
<_IteratorR
, _Container
>& __rhs
)
773 { return __lhs
.base() > __rhs
.base(); }
775 template<typename _Iterator
, typename _Container
>
777 operator>(const __normal_iterator
<_Iterator
, _Container
>& __lhs
,
778 const __normal_iterator
<_Iterator
, _Container
>& __rhs
)
779 { return __lhs
.base() > __rhs
.base(); }
781 template<typename _IteratorL
, typename _IteratorR
, typename _Container
>
783 operator<=(const __normal_iterator
<_IteratorL
, _Container
>& __lhs
,
784 const __normal_iterator
<_IteratorR
, _Container
>& __rhs
)
785 { return __lhs
.base() <= __rhs
.base(); }
787 template<typename _Iterator
, typename _Container
>
789 operator<=(const __normal_iterator
<_Iterator
, _Container
>& __lhs
,
790 const __normal_iterator
<_Iterator
, _Container
>& __rhs
)
791 { return __lhs
.base() <= __rhs
.base(); }
793 template<typename _IteratorL
, typename _IteratorR
, typename _Container
>
795 operator>=(const __normal_iterator
<_IteratorL
, _Container
>& __lhs
,
796 const __normal_iterator
<_IteratorR
, _Container
>& __rhs
)
797 { return __lhs
.base() >= __rhs
.base(); }
799 template<typename _Iterator
, typename _Container
>
801 operator>=(const __normal_iterator
<_Iterator
, _Container
>& __lhs
,
802 const __normal_iterator
<_Iterator
, _Container
>& __rhs
)
803 { return __lhs
.base() >= __rhs
.base(); }
805 // _GLIBCXX_RESOLVE_LIB_DEFECTS
806 // According to the resolution of DR179 not only the various comparison
807 // operators but also operator- must accept mixed iterator/const_iterator
809 template<typename _IteratorL
, typename _IteratorR
, typename _Container
>
810 inline typename __normal_iterator
<_IteratorL
, _Container
>::difference_type
811 operator-(const __normal_iterator
<_IteratorL
, _Container
>& __lhs
,
812 const __normal_iterator
<_IteratorR
, _Container
>& __rhs
)
813 { return __lhs
.base() - __rhs
.base(); }
815 template<typename _Iterator
, typename _Container
>
816 inline typename __normal_iterator
<_Iterator
, _Container
>::difference_type
817 operator-(const __normal_iterator
<_Iterator
, _Container
>& __lhs
,
818 const __normal_iterator
<_Iterator
, _Container
>& __rhs
)
819 { return __lhs
.base() - __rhs
.base(); }
821 template<typename _Iterator
, typename _Container
>
822 inline __normal_iterator
<_Iterator
, _Container
>
823 operator+(typename __normal_iterator
<_Iterator
, _Container
>::difference_type
824 __n
, const __normal_iterator
<_Iterator
, _Container
>& __i
)
825 { return __normal_iterator
<_Iterator
, _Container
>(__i
.base() + __n
); }
827 _GLIBCXX_END_NAMESPACE