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