1// Iterators -*- C++ -*-
2
3// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
4// 2010, 2011, 2012
5// Free Software Foundation, Inc.
6//
7// This file is part of the GNU ISO C++ Library. This library is free
8// software; you can redistribute it and/or modify it under the
9// terms of the GNU General Public License as published by the
10// Free Software Foundation; either version 3, or (at your option)
11// any later version.
12
13// This library is distributed in the hope that it will be useful,
14// but WITHOUT ANY WARRANTY; without even the implied warranty of
15// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16// GNU General Public License for more details.
17
18// Under Section 7 of GPL version 3, you are granted additional
19// permissions described in the GCC Runtime Library Exception, version
20// 3.1, as published by the Free Software Foundation.
21
22// You should have received a copy of the GNU General Public License and
23// a copy of the GCC Runtime Library Exception along with this program;
24// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
25// <http://www.gnu.org/licenses/>.
26
27/*
28 *
29 * Copyright (c) 1994
30 * Hewlett-Packard Company
31 *
32 * Permission to use, copy, modify, distribute and sell this software
33 * and its documentation for any purpose is hereby granted without fee,
34 * provided that the above copyright notice appear in all copies and
35 * that both that copyright notice and this permission notice appear
36 * in supporting documentation. Hewlett-Packard Company makes no
37 * representations about the suitability of this software for any
38 * purpose. It is provided "as is" without express or implied warranty.
39 *
40 *
41 * Copyright (c) 1996-1998
42 * Silicon Graphics Computer Systems, Inc.
43 *
44 * Permission to use, copy, modify, distribute and sell this software
45 * and its documentation for any purpose is hereby granted without fee,
46 * provided that the above copyright notice appear in all copies and
47 * that both that copyright notice and this permission notice appear
48 * in supporting documentation. Silicon Graphics makes no
49 * representations about the suitability of this software for any
50 * purpose. It is provided "as is" without express or implied warranty.
51 */
52
53/** @file bits/stl_iterator.h
54 * This is an internal header file, included by other library headers.
55 * Do not attempt to use it directly. @headername{iterator}
56 *
57 * This file implements reverse_iterator, back_insert_iterator,
58 * front_insert_iterator, insert_iterator, __normal_iterator, and their
59 * supporting functions and overloaded operators.
60 */
61
62#ifndef _STL_ITERATOR_H
63#define _STL_ITERATOR_H 1
64
65#include <bits/cpp_type_traits.h>
66#include <ext/type_traits.h>
67#include <bits/move.h>
68
69namespace std _GLIBCXX_VISIBILITY(default)
70{
71_GLIBCXX_BEGIN_NAMESPACE_VERSION
72
73 /**
74 * @addtogroup iterators
75 * @{
76 */
77
78 // 24.4.1 Reverse iterators
79 /**
80 * Bidirectional and random access iterators have corresponding reverse
81 * %iterator adaptors that iterate through the data structure in the
82 * opposite direction. They have the same signatures as the corresponding
83 * iterators. The fundamental relation between a reverse %iterator and its
84 * corresponding %iterator @c i is established by the identity:
85 * @code
86 * &*(reverse_iterator(i)) == &*(i - 1)
87 * @endcode
88 *
89 * <em>This mapping is dictated by the fact that while there is always a
90 * pointer past the end of an array, there might not be a valid pointer
91 * before the beginning of an array.</em> [24.4.1]/1,2
92 *
93 * Reverse iterators can be tricky and surprising at first. Their
94 * semantics make sense, however, and the trickiness is a side effect of
95 * the requirement that the iterators must be safe.
96 */
97 template<typename _Iterator>
98 class reverse_iterator
99 : public iterator<typename iterator_traits<_Iterator>::iterator_category,
100 typename iterator_traits<_Iterator>::value_type,
101 typename iterator_traits<_Iterator>::difference_type,
102 typename iterator_traits<_Iterator>::pointer,
103 typename iterator_traits<_Iterator>::reference>
104 {
105 protected:
106 _Iterator current;
107
108 typedef iterator_traits<_Iterator> __traits_type;
109
110 public:
111 typedef _Iterator iterator_type;
112 typedef typename __traits_type::difference_type difference_type;
113 typedef typename __traits_type::pointer pointer;
114 typedef typename __traits_type::reference reference;
115
116 /**
117 * The default constructor value-initializes member @p current.
118 * If it is a pointer, that means it is zero-initialized.
119 */
120 // _GLIBCXX_RESOLVE_LIB_DEFECTS
121 // 235 No specification of default ctor for reverse_iterator
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 */
133 reverse_iterator(const reverse_iterator& __x)
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>
141 reverse_iterator(const reverse_iterator<_Iter>& __x)
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 pointer
174 operator->() const
175 { return &(operator*()); }
176
177 /**
178 * @return @c *this
179 *
180 * Decrements the underlying iterator.
181 */
182 reverse_iterator&
183 operator++()
184 {
185 --current;
186 return *this;
187 }
188
189 /**
190 * @return The original value of @c *this
191 *
192 * Decrements the underlying iterator.
193 */
194 reverse_iterator
195 operator++(int)
196 {
197 reverse_iterator __tmp = *this;
198 --current;
199 return __tmp;
200 }
201
202 /**
203 * @return @c *this
204 *
205 * Increments the underlying iterator.
206 */
207 reverse_iterator&
208 operator--()
209 {
210 ++current;
211 return *this;
212 }
213
214 /**
215 * @return A reverse_iterator with the previous value of @c *this
216 *
217 * Increments the underlying iterator.
218 */
219 reverse_iterator
220 operator--(int)
221 {
222 reverse_iterator __tmp = *this;
223 ++current;
224 return __tmp;
225 }
226
227 /**
228 * @return A reverse_iterator that refers to @c current - @a __n
229 *
230 * The underlying iterator must be a Random Access Iterator.
231 */
232 reverse_iterator
233 operator+(difference_type __n) const
234 { return reverse_iterator(current - __n); }
235
236 /**
237 * @return *this
238 *
239 * Moves the underlying iterator backwards @a __n steps.
240 * The underlying iterator must be a Random Access Iterator.
241 */
242 reverse_iterator&
243 operator+=(difference_type __n)
244 {
245 current -= __n;
246 return *this;
247 }
248
249 /**
250 * @return A reverse_iterator that refers to @c current - @a __n
251 *
252 * The underlying iterator must be a Random Access Iterator.
253 */
254 reverse_iterator
255 operator-(difference_type __n) const
256 { return reverse_iterator(current + __n); }
257
258 /**
259 * @return *this
260 *
261 * Moves the underlying iterator forwards @a __n steps.
262 * The underlying iterator must be a Random Access Iterator.
263 */
264 reverse_iterator&
265 operator-=(difference_type __n)
266 {
267 current += __n;
268 return *this;
269 }
270
271 /**
272 * @return The value at @c current - @a __n - 1
273 *
274 * The underlying iterator must be a Random Access Iterator.
275 */
276 reference
277 operator[](difference_type __n) const
278 { return *(*this + __n); }
279 };
280
281 //@{
282 /**
283 * @param __x A %reverse_iterator.
284 * @param __y A %reverse_iterator.
285 * @return A simple bool.
286 *
287 * Reverse iterators forward many operations to their underlying base()
288 * iterators. Others are implemented in terms of one another.
289 *
290 */
291 template<typename _Iterator>
292 inline bool
293 operator==(const reverse_iterator<_Iterator>& __x,
294 const reverse_iterator<_Iterator>& __y)
295 { return __x.base() == __y.base(); }
296
297 template<typename _Iterator>
298 inline bool
299 operator<(const reverse_iterator<_Iterator>& __x,
300 const reverse_iterator<_Iterator>& __y)
301 { return __y.base() < __x.base(); }
302
303 template<typename _Iterator>
304 inline bool
305 operator!=(const reverse_iterator<_Iterator>& __x,
306 const reverse_iterator<_Iterator>& __y)
307 { return !(__x == __y); }
308
309 template<typename _Iterator>
310 inline bool
311 operator>(const reverse_iterator<_Iterator>& __x,
312 const reverse_iterator<_Iterator>& __y)
313 { return __y < __x; }
314
315 template<typename _Iterator>
316 inline bool
317 operator<=(const reverse_iterator<_Iterator>& __x,
318 const reverse_iterator<_Iterator>& __y)
319 { return !(__y < __x); }
320
321 template<typename _Iterator>
322 inline bool
323 operator>=(const reverse_iterator<_Iterator>& __x,
324 const reverse_iterator<_Iterator>& __y)
325 { return !(__x < __y); }
326
327 template<typename _Iterator>
328 inline typename reverse_iterator<_Iterator>::difference_type
329 operator-(const reverse_iterator<_Iterator>& __x,
330 const reverse_iterator<_Iterator>& __y)
331 { return __y.base() - __x.base(); }
332
333 template<typename _Iterator>
334 inline reverse_iterator<_Iterator>
335 operator+(typename reverse_iterator<_Iterator>::difference_type __n,
336 const reverse_iterator<_Iterator>& __x)
337 { return reverse_iterator<_Iterator>(__x.base() - __n); }
338
339 // _GLIBCXX_RESOLVE_LIB_DEFECTS
340 // DR 280. Comparison of reverse_iterator to const reverse_iterator.
341 template<typename _IteratorL, typename _IteratorR>
342 inline bool
343 operator==(const reverse_iterator<_IteratorL>& __x,
344 const reverse_iterator<_IteratorR>& __y)
345 { return __x.base() == __y.base(); }
346
347 template<typename _IteratorL, typename _IteratorR>
348 inline bool
349 operator<(const reverse_iterator<_IteratorL>& __x,
350 const reverse_iterator<_IteratorR>& __y)
351 { return __y.base() < __x.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 !(__x == __y); }
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 __y < __x; }
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 !(__x < __y); }
376
377 template<typename _IteratorL, typename _IteratorR>
378#ifdef __GXX_EXPERIMENTAL_CXX0X__
379 // DR 685.
380 inline auto
381 operator-(const reverse_iterator<_IteratorL>& __x,
382 const reverse_iterator<_IteratorR>& __y)
383 -> decltype(__y.base() - __x.base())
384#else
385 inline typename reverse_iterator<_IteratorL>::difference_type
386 operator-(const reverse_iterator<_IteratorL>& __x,
387 const reverse_iterator<_IteratorR>& __y)
388#endif
389 { return __y.base() - __x.base(); }
390 //@}
391
392 // 24.4.2.2.1 back_insert_iterator
393 /**
394 * @brief Turns assignment into insertion.
395 *
396 * These are output iterators, constructed from a container-of-T.
397 * Assigning a T to the iterator appends it to the container using
398 * push_back.
399 *
400 * Tip: Using the back_inserter function to create these iterators can
401 * save typing.
402 */
403 template<typename _Container>
404 class back_insert_iterator
405 : public iterator<output_iterator_tag, void, void, void, void>
406 {
407 protected:
408 _Container* container;
409
410 public:
411 /// A nested typedef for the type of whatever container you used.
412 typedef _Container container_type;
413
414 /// The only way to create this %iterator is with a container.
415 explicit
416 back_insert_iterator(_Container& __x) : container(&__x) { }
417
418 /**
419 * @param __value An instance of whatever type
420 * container_type::const_reference is; presumably a
421 * reference-to-const T for container<T>.
422 * @return This %iterator, for chained operations.
423 *
424 * This kind of %iterator doesn't really have a @a position in the
425 * container (you can think of the position as being permanently at
426 * the end, if you like). Assigning a value to the %iterator will
427 * always append the value to the end of the container.
428 */
429#ifndef __GXX_EXPERIMENTAL_CXX0X__
430 back_insert_iterator&
431 operator=(typename _Container::const_reference __value)
432 {
433 container->push_back(__value);
434 return *this;
435 }
436#else
437 back_insert_iterator&
438 operator=(const typename _Container::value_type& __value)
439 {
440 container->push_back(__value);
441 return *this;
442 }
443
444 back_insert_iterator&
445 operator=(typename _Container::value_type&& __value)
446 {
447 container->push_back(std::move(__value));
448 return *this;
449 }
450#endif
451
452 /// Simply returns *this.
453 back_insert_iterator&
454 operator*()
455 { return *this; }
456
457 /// Simply returns *this. (This %iterator does not @a move.)
458 back_insert_iterator&
459 operator++()
460 { return *this; }
461
462 /// Simply returns *this. (This %iterator does not @a move.)
463 back_insert_iterator
464 operator++(int)
465 { return *this; }
466 };
467
468 /**
469 * @param __x A container of arbitrary type.
470 * @return An instance of back_insert_iterator working on @p __x.
471 *
472 * This wrapper function helps in creating back_insert_iterator instances.
473 * Typing the name of the %iterator requires knowing the precise full
474 * type of the container, which can be tedious and impedes generic
475 * programming. Using this function lets you take advantage of automatic
476 * template parameter deduction, making the compiler match the correct
477 * types for you.
478 */
479 template<typename _Container>
480 inline back_insert_iterator<_Container>
481 back_inserter(_Container& __x)
482 { return back_insert_iterator<_Container>(__x); }
483
484 /**
485 * @brief Turns assignment into insertion.
486 *
487 * These are output iterators, constructed from a container-of-T.
488 * Assigning a T to the iterator prepends it to the container using
489 * push_front.
490 *
491 * Tip: Using the front_inserter function to create these iterators can
492 * save typing.
493 */
494 template<typename _Container>
495 class front_insert_iterator
496 : public iterator<output_iterator_tag, void, void, void, void>
497 {
498 protected:
499 _Container* container;
500
501 public:
502 /// A nested typedef for the type of whatever container you used.
503 typedef _Container container_type;
504
505 /// The only way to create this %iterator is with a container.
506 explicit front_insert_iterator(_Container& __x) : container(&__x) { }
507
508 /**
509 * @param __value An instance of whatever type
510 * container_type::const_reference is; presumably a
511 * reference-to-const T for container<T>.
512 * @return This %iterator, for chained operations.
513 *
514 * This kind of %iterator doesn't really have a @a position in the
515 * container (you can think of the position as being permanently at
516 * the front, if you like). Assigning a value to the %iterator will
517 * always prepend the value to the front of the container.
518 */
519#ifndef __GXX_EXPERIMENTAL_CXX0X__
520 front_insert_iterator&
521 operator=(typename _Container::const_reference __value)
522 {
523 container->push_front(__value);
524 return *this;
525 }
526#else
527 front_insert_iterator&
528 operator=(const typename _Container::value_type& __value)
529 {
530 container->push_front(__value);
531 return *this;
532 }
533
534 front_insert_iterator&
535 operator=(typename _Container::value_type&& __value)
536 {
537 container->push_front(std::move(__value));
538 return *this;
539 }
540#endif
541
542 /// Simply returns *this.
543 front_insert_iterator&
544 operator*()
545 { return *this; }
546
547 /// Simply returns *this. (This %iterator does not @a move.)
548 front_insert_iterator&
549 operator++()
550 { return *this; }
551
552 /// Simply returns *this. (This %iterator does not @a move.)
553 front_insert_iterator
554 operator++(int)
555 { return *this; }
556 };
557
558 /**
559 * @param __x A container of arbitrary type.
560 * @return An instance of front_insert_iterator working on @p x.
561 *
562 * This wrapper function helps in creating front_insert_iterator instances.
563 * Typing the name of the %iterator requires knowing the precise full
564 * type of the container, which can be tedious and impedes generic
565 * programming. Using this function lets you take advantage of automatic
566 * template parameter deduction, making the compiler match the correct
567 * types for you.
568 */
569 template<typename _Container>
570 inline front_insert_iterator<_Container>
571 front_inserter(_Container& __x)
572 { return front_insert_iterator<_Container>(__x); }
573
574 /**
575 * @brief Turns assignment into insertion.
576 *
577 * These are output iterators, constructed from a container-of-T.
578 * Assigning a T to the iterator inserts it in the container at the
579 * %iterator's position, rather than overwriting the value at that
580 * position.
581 *
582 * (Sequences will actually insert a @e copy of the value before the
583 * %iterator's position.)
584 *
585 * Tip: Using the inserter function to create these iterators can
586 * save typing.
587 */
588 template<typename _Container>
589 class insert_iterator
590 : public iterator<output_iterator_tag, void, void, void, void>
591 {
592 protected:
593 _Container* container;
594 typename _Container::iterator iter;
595
596 public:
597 /// A nested typedef for the type of whatever container you used.
598 typedef _Container container_type;
599
600 /**
601 * The only way to create this %iterator is with a container and an
602 * initial position (a normal %iterator into the container).
603 */
604 insert_iterator(_Container& __x, typename _Container::iterator __i)
605 : container(&__x), iter(__i) {}
606
607 /**
608 * @param __value An instance of whatever type
609 * container_type::const_reference is; presumably a
610 * reference-to-const T for container<T>.
611 * @return This %iterator, for chained operations.
612 *
613 * This kind of %iterator maintains its own position in the
614 * container. Assigning a value to the %iterator will insert the
615 * value into the container at the place before the %iterator.
616 *
617 * The position is maintained such that subsequent assignments will
618 * insert values immediately after one another. For example,
619 * @code
620 * // vector v contains A and Z
621 *
622 * insert_iterator i (v, ++v.begin());
623 * i = 1;
624 * i = 2;
625 * i = 3;
626 *
627 * // vector v contains A, 1, 2, 3, and Z
628 * @endcode
629 */
630#ifndef __GXX_EXPERIMENTAL_CXX0X__
631 insert_iterator&
632 operator=(typename _Container::const_reference __value)
633 {
634 iter = container->insert(iter, __value);
635 ++iter;
636 return *this;
637 }
638#else
639 insert_iterator&
640 operator=(const typename _Container::value_type& __value)
641 {
642 iter = container->insert(iter, __value);
643 ++iter;
644 return *this;
645 }
646
647 insert_iterator&
648 operator=(typename _Container::value_type&& __value)
649 {
650 iter = container->insert(iter, std::move(__value));
651 ++iter;
652 return *this;
653 }
654#endif
655
656 /// Simply returns *this.
657 insert_iterator&
658 operator*()
659 { return *this; }
660
661 /// Simply returns *this. (This %iterator does not @a move.)
662 insert_iterator&
663 operator++()
664 { return *this; }
665
666 /// Simply returns *this. (This %iterator does not @a move.)
667 insert_iterator&
668 operator++(int)
669 { return *this; }
670 };
671
672 /**
673 * @param __x A container of arbitrary type.
674 * @return An instance of insert_iterator working on @p __x.
675 *
676 * This wrapper function helps in creating insert_iterator instances.
677 * Typing the name of the %iterator requires knowing the precise full
678 * type of the container, which can be tedious and impedes generic
679 * programming. Using this function lets you take advantage of automatic
680 * template parameter deduction, making the compiler match the correct
681 * types for you.
682 */
683 template<typename _Container, typename _Iterator>
684 inline insert_iterator<_Container>
685 inserter(_Container& __x, _Iterator __i)
686 {
687 return insert_iterator<_Container>(__x,
688 typename _Container::iterator(__i));
689 }
690
691 // @} group iterators
692
693_GLIBCXX_END_NAMESPACE_VERSION
694} // namespace
695
696namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
697{
698_GLIBCXX_BEGIN_NAMESPACE_VERSION
699
700 // This iterator adapter is @a normal in the sense that it does not
701 // change the semantics of any of the operators of its iterator
702 // parameter. Its primary purpose is to convert an iterator that is
703 // not a class, e.g. a pointer, into an iterator that is a class.
704 // The _Container parameter exists solely so that different containers
705 // using this template can instantiate different types, even if the
706 // _Iterator parameter is the same.
707 using std::iterator_traits;
708 using std::iterator;
709 template<typename _Iterator, typename _Container>
710 class __normal_iterator
711 {
712 protected:
713 _Iterator _M_current;
714
715 typedef iterator_traits<_Iterator> __traits_type;
716
717 public:
718 typedef _Iterator iterator_type;
719 typedef typename __traits_type::iterator_category iterator_category;
720 typedef typename __traits_type::value_type value_type;
721 typedef typename __traits_type::difference_type difference_type;
722 typedef typename __traits_type::reference reference;
723 typedef typename __traits_type::pointer pointer;
724
725 _GLIBCXX_CONSTEXPR __normal_iterator() : _M_current(_Iterator()) { }
726
727 explicit
728 __normal_iterator(const _Iterator& __i) : _M_current(__i) { }
729
730 // Allow iterator to const_iterator conversion
731 template<typename _Iter>
732 __normal_iterator(const __normal_iterator<_Iter,
733 typename __enable_if<
734 (std::__are_same<_Iter, typename _Container::pointer>::__value),
735 _Container>::__type>& __i)
736 : _M_current(__i.base()) { }
737
738 // Forward iterator requirements
739 reference
740 operator*() const
741 { return *_M_current; }
742
743 pointer
744 operator->() const
745 { return _M_current; }
746
747 __normal_iterator&
748 operator++()
749 {
750 ++_M_current;
751 return *this;
752 }
753
754 __normal_iterator
755 operator++(int)
756 { return __normal_iterator(_M_current++); }
757
758 // Bidirectional iterator requirements
759 __normal_iterator&
760 operator--()
761 {
762 --_M_current;
763 return *this;
764 }
765
766 __normal_iterator
767 operator--(int)
768 { return __normal_iterator(_M_current--); }
769
770 // Random access iterator requirements
771 reference
772 operator[](const difference_type& __n) const
773 { return _M_current[__n]; }
774
775 __normal_iterator&
776 operator+=(const difference_type& __n)
777 { _M_current += __n; return *this; }
778
779 __normal_iterator
780 operator+(const difference_type& __n) const
781 { return __normal_iterator(_M_current + __n); }
782
783 __normal_iterator&
784 operator-=(const difference_type& __n)
785 { _M_current -= __n; return *this; }
786
787 __normal_iterator
788 operator-(const difference_type& __n) const
789 { return __normal_iterator(_M_current - __n); }
790
791 const _Iterator&
792 base() const
793 { return _M_current; }
794 };
795
796 // Note: In what follows, the left- and right-hand-side iterators are
797 // allowed to vary in types (conceptually in cv-qualification) so that
798 // comparison between cv-qualified and non-cv-qualified iterators be
799 // valid. However, the greedy and unfriendly operators in std::rel_ops
800 // will make overload resolution ambiguous (when in scope) if we don't
801 // provide overloads whose operands are of the same type. Can someone
802 // remind me what generic programming is about? -- Gaby
803
804 // Forward iterator requirements
805 template<typename _IteratorL, typename _IteratorR, typename _Container>
806 inline bool
807 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
808 const __normal_iterator<_IteratorR, _Container>& __rhs)
809 { return __lhs.base() == __rhs.base(); }
810
811 template<typename _Iterator, typename _Container>
812 inline bool
813 operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
814 const __normal_iterator<_Iterator, _Container>& __rhs)
815 { return __lhs.base() == __rhs.base(); }
816
817 template<typename _IteratorL, typename _IteratorR, typename _Container>
818 inline bool
819 operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
820 const __normal_iterator<_IteratorR, _Container>& __rhs)
821 { return __lhs.base() != __rhs.base(); }
822
823 template<typename _Iterator, typename _Container>
824 inline bool
825 operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
826 const __normal_iterator<_Iterator, _Container>& __rhs)
827 { return __lhs.base() != __rhs.base(); }
828
829 // Random access iterator requirements
830 template<typename _IteratorL, typename _IteratorR, typename _Container>
831 inline bool
832 operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
833 const __normal_iterator<_IteratorR, _Container>& __rhs)
834 { return __lhs.base() < __rhs.base(); }
835
836 template<typename _Iterator, typename _Container>
837 inline bool
838 operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
839 const __normal_iterator<_Iterator, _Container>& __rhs)
840 { return __lhs.base() < __rhs.base(); }
841
842 template<typename _IteratorL, typename _IteratorR, typename _Container>
843 inline bool
844 operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
845 const __normal_iterator<_IteratorR, _Container>& __rhs)
846 { return __lhs.base() > __rhs.base(); }
847
848 template<typename _Iterator, typename _Container>
849 inline bool
850 operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
851 const __normal_iterator<_Iterator, _Container>& __rhs)
852 { return __lhs.base() > __rhs.base(); }
853
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 { return __lhs.base() <= __rhs.base(); }
859
860 template<typename _Iterator, typename _Container>
861 inline bool
862 operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
863 const __normal_iterator<_Iterator, _Container>& __rhs)
864 { return __lhs.base() <= __rhs.base(); }
865
866 template<typename _IteratorL, typename _IteratorR, typename _Container>
867 inline bool
868 operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
869 const __normal_iterator<_IteratorR, _Container>& __rhs)
870 { return __lhs.base() >= __rhs.base(); }
871
872 template<typename _Iterator, typename _Container>
873 inline bool
874 operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
875 const __normal_iterator<_Iterator, _Container>& __rhs)
876 { return __lhs.base() >= __rhs.base(); }
877
878 // _GLIBCXX_RESOLVE_LIB_DEFECTS
879 // According to the resolution of DR179 not only the various comparison
880 // operators but also operator- must accept mixed iterator/const_iterator
881 // parameters.
882 template<typename _IteratorL, typename _IteratorR, typename _Container>
883#ifdef __GXX_EXPERIMENTAL_CXX0X__
884 // DR 685.
885 inline auto
886 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
887 const __normal_iterator<_IteratorR, _Container>& __rhs)
888 -> decltype(__lhs.base() - __rhs.base())
889#else
890 inline typename __normal_iterator<_IteratorL, _Container>::difference_type
891 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
892 const __normal_iterator<_IteratorR, _Container>& __rhs)
893#endif
894 { return __lhs.base() - __rhs.base(); }
895
896 template<typename _Iterator, typename _Container>
897 inline typename __normal_iterator<_Iterator, _Container>::difference_type
898 operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
899 const __normal_iterator<_Iterator, _Container>& __rhs)
900 { return __lhs.base() - __rhs.base(); }
901
902 template<typename _Iterator, typename _Container>
903 inline __normal_iterator<_Iterator, _Container>
904 operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
905 __n, const __normal_iterator<_Iterator, _Container>& __i)
906 { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
907
908_GLIBCXX_END_NAMESPACE_VERSION
909} // namespace
910
911#ifdef __GXX_EXPERIMENTAL_CXX0X__
912
913namespace std _GLIBCXX_VISIBILITY(default)
914{
915_GLIBCXX_BEGIN_NAMESPACE_VERSION
916
917 /**
918 * @addtogroup iterators
919 * @{
920 */
921
922 // 24.4.3 Move iterators
923 /**
924 * Class template move_iterator is an iterator adapter with the same
925 * behavior as the underlying iterator except that its dereference
926 * operator implicitly converts the value returned by the underlying
927 * iterator's dereference operator to an rvalue reference. Some
928 * generic algorithms can be called with move iterators to replace
929 * copying with moving.
930 */
931 template<typename _Iterator>
932 class move_iterator
933 {
934 protected:
935 _Iterator _M_current;
936
937 typedef iterator_traits<_Iterator> __traits_type;
938
939 public:
940 typedef _Iterator iterator_type;
941 typedef typename __traits_type::iterator_category iterator_category;
942 typedef typename __traits_type::value_type value_type;
943 typedef typename __traits_type::difference_type difference_type;
944 // NB: DR 680.
945 typedef _Iterator pointer;
946 typedef value_type&& reference;
947
948 move_iterator()
949 : _M_current() { }
950
951 explicit
952 move_iterator(iterator_type __i)
953 : _M_current(__i) { }
954
955 template<typename _Iter>
956 move_iterator(const move_iterator<_Iter>& __i)
957 : _M_current(__i.base()) { }
958
959 iterator_type
960 base() const
961 { return _M_current; }
962
963 reference
964 operator*() const
965 { return std::move(*_M_current); }
966
967 pointer
968 operator->() const
969 { return _M_current; }
970
971 move_iterator&
972 operator++()
973 {
974 ++_M_current;
975 return *this;
976 }
977
978 move_iterator
979 operator++(int)
980 {
981 move_iterator __tmp = *this;
982 ++_M_current;
983 return __tmp;
984 }
985
986 move_iterator&
987 operator--()
988 {
989 --_M_current;
990 return *this;
991 }
992
993 move_iterator
994 operator--(int)
995 {
996 move_iterator __tmp = *this;
997 --_M_current;
998 return __tmp;
999 }
1000
1001 move_iterator
1002 operator+(difference_type __n) const
1003 { return move_iterator(_M_current + __n); }
1004
1005 move_iterator&
1006 operator+=(difference_type __n)
1007 {
1008 _M_current += __n;
1009 return *this;
1010 }
1011
1012 move_iterator
1013 operator-(difference_type __n) const
1014 { return move_iterator(_M_current - __n); }
1015
1016 move_iterator&
1017 operator-=(difference_type __n)
1018 {
1019 _M_current -= __n;
1020 return *this;
1021 }
1022
1023 reference
1024 operator[](difference_type __n) const
1025 { return std::move(_M_current[__n]); }
1026 };
1027
1028 // Note: See __normal_iterator operators note from Gaby to understand
1029 // why there are always 2 versions for most of the move_iterator
1030 // operators.
1031 template<typename _IteratorL, typename _IteratorR>
1032 inline bool
1033 operator==(const move_iterator<_IteratorL>& __x,
1034 const move_iterator<_IteratorR>& __y)
1035 { return __x.base() == __y.base(); }
1036
1037 template<typename _Iterator>
1038 inline bool
1039 operator==(const move_iterator<_Iterator>& __x,
1040 const move_iterator<_Iterator>& __y)
1041 { return __x.base() == __y.base(); }
1042
1043 template<typename _IteratorL, typename _IteratorR>
1044 inline bool
1045 operator!=(const move_iterator<_IteratorL>& __x,
1046 const move_iterator<_IteratorR>& __y)
1047 { return !(__x == __y); }
1048
1049 template<typename _Iterator>
1050 inline bool
1051 operator!=(const move_iterator<_Iterator>& __x,
1052 const move_iterator<_Iterator>& __y)
1053 { return !(__x == __y); }
1054
1055 template<typename _IteratorL, typename _IteratorR>
1056 inline bool
1057 operator<(const move_iterator<_IteratorL>& __x,
1058 const move_iterator<_IteratorR>& __y)
1059 { return __x.base() < __y.base(); }
1060
1061 template<typename _Iterator>
1062 inline bool
1063 operator<(const move_iterator<_Iterator>& __x,
1064 const move_iterator<_Iterator>& __y)
1065 { return __x.base() < __y.base(); }
1066
1067 template<typename _IteratorL, typename _IteratorR>
1068 inline bool
1069 operator<=(const move_iterator<_IteratorL>& __x,
1070 const move_iterator<_IteratorR>& __y)
1071 { return !(__y < __x); }
1072
1073 template<typename _Iterator>
1074 inline bool
1075 operator<=(const move_iterator<_Iterator>& __x,
1076 const move_iterator<_Iterator>& __y)
1077 { return !(__y < __x); }
1078
1079 template<typename _IteratorL, typename _IteratorR>
1080 inline bool
1081 operator>(const move_iterator<_IteratorL>& __x,
1082 const move_iterator<_IteratorR>& __y)
1083 { return __y < __x; }
1084
1085 template<typename _Iterator>
1086 inline bool
1087 operator>(const move_iterator<_Iterator>& __x,
1088 const move_iterator<_Iterator>& __y)
1089 { return __y < __x; }
1090
1091 template<typename _IteratorL, typename _IteratorR>
1092 inline bool
1093 operator>=(const move_iterator<_IteratorL>& __x,
1094 const move_iterator<_IteratorR>& __y)
1095 { return !(__x < __y); }
1096
1097 template<typename _Iterator>
1098 inline bool
1099 operator>=(const move_iterator<_Iterator>& __x,
1100 const move_iterator<_Iterator>& __y)
1101 { return !(__x < __y); }
1102
1103 // DR 685.
1104 template<typename _IteratorL, typename _IteratorR>
1105 inline auto
1106 operator-(const move_iterator<_IteratorL>& __x,
1107 const move_iterator<_IteratorR>& __y)
1108 -> decltype(__x.base() - __y.base())
1109 { return __x.base() - __y.base(); }
1110
1111 template<typename _Iterator>
1112 inline auto
1113 operator-(const move_iterator<_Iterator>& __x,
1114 const move_iterator<_Iterator>& __y)
1115 -> decltype(__x.base() - __y.base())
1116 { return __x.base() - __y.base(); }
1117
1118 template<typename _Iterator>
1119 inline move_iterator<_Iterator>
1120 operator+(typename move_iterator<_Iterator>::difference_type __n,
1121 const move_iterator<_Iterator>& __x)
1122 { return __x + __n; }
1123
1124 template<typename _Iterator>
1125 inline move_iterator<_Iterator>
1126 make_move_iterator(_Iterator __i)
1127 { return move_iterator<_Iterator>(__i); }
1128
1129 template<typename _Iterator, typename _ReturnType
1130 = typename conditional<__move_if_noexcept_cond
1131 <typename iterator_traits<_Iterator>::value_type>::value,
1132 _Iterator, move_iterator<_Iterator>>::type>
1133 inline _ReturnType
1134 __make_move_if_noexcept_iterator(_Iterator __i)
1135 { return _ReturnType(__i); }
1136
1137 // @} group iterators
1138
1139_GLIBCXX_END_NAMESPACE_VERSION
1140} // namespace
1141
1142#define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
1143#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
1144 std::__make_move_if_noexcept_iterator(_Iter)
1145#else
1146#define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
1147#define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
1148#endif // __GXX_EXPERIMENTAL_CXX0X__
1149
1150#endif
1151