libstdc++
stl_iterator.h
Go to the documentation of this file.
00001 // Iterators -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2017 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /*
00026  *
00027  * Copyright (c) 1994
00028  * Hewlett-Packard Company
00029  *
00030  * Permission to use, copy, modify, distribute and sell this software
00031  * and its documentation for any purpose is hereby granted without fee,
00032  * provided that the above copyright notice appear in all copies and
00033  * that both that copyright notice and this permission notice appear
00034  * in supporting documentation.  Hewlett-Packard Company makes no
00035  * representations about the suitability of this software for any
00036  * purpose.  It is provided "as is" without express or implied warranty.
00037  *
00038  *
00039  * Copyright (c) 1996-1998
00040  * Silicon Graphics Computer Systems, Inc.
00041  *
00042  * Permission to use, copy, modify, distribute and sell this software
00043  * and its documentation for any purpose is hereby granted without fee,
00044  * provided that the above copyright notice appear in all copies and
00045  * that both that copyright notice and this permission notice appear
00046  * in supporting documentation.  Silicon Graphics makes no
00047  * representations about the suitability of this software for any
00048  * purpose.  It is provided "as is" without express or implied warranty.
00049  */
00050 
00051 /** @file bits/stl_iterator.h
00052  *  This is an internal header file, included by other library headers.
00053  *  Do not attempt to use it directly. @headername{iterator}
00054  *
00055  *  This file implements reverse_iterator, back_insert_iterator,
00056  *  front_insert_iterator, insert_iterator, __normal_iterator, and their
00057  *  supporting functions and overloaded operators.
00058  */
00059 
00060 #ifndef _STL_ITERATOR_H
00061 #define _STL_ITERATOR_H 1
00062 
00063 #include <bits/cpp_type_traits.h>
00064 #include <ext/type_traits.h>
00065 #include <bits/move.h>
00066 #include <bits/ptr_traits.h>
00067 
00068 #if __cplusplus > 201402L
00069 # define __cpp_lib_array_constexpr 201603
00070 #endif
00071 
00072 namespace std _GLIBCXX_VISIBILITY(default)
00073 {
00074 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00075 
00076   /**
00077    * @addtogroup iterators
00078    * @{
00079    */
00080 
00081   // 24.4.1 Reverse iterators
00082   /**
00083    *  Bidirectional and random access iterators have corresponding reverse
00084    *  %iterator adaptors that iterate through the data structure in the
00085    *  opposite direction.  They have the same signatures as the corresponding
00086    *  iterators.  The fundamental relation between a reverse %iterator and its
00087    *  corresponding %iterator @c i is established by the identity:
00088    *  @code
00089    *      &*(reverse_iterator(i)) == &*(i - 1)
00090    *  @endcode
00091    *
00092    *  <em>This mapping is dictated by the fact that while there is always a
00093    *  pointer past the end of an array, there might not be a valid pointer
00094    *  before the beginning of an array.</em> [24.4.1]/1,2
00095    *
00096    *  Reverse iterators can be tricky and surprising at first.  Their
00097    *  semantics make sense, however, and the trickiness is a side effect of
00098    *  the requirement that the iterators must be safe.
00099   */
00100   template<typename _Iterator>
00101     class reverse_iterator
00102     : public iterator<typename iterator_traits<_Iterator>::iterator_category,
00103                       typename iterator_traits<_Iterator>::value_type,
00104                       typename iterator_traits<_Iterator>::difference_type,
00105                       typename iterator_traits<_Iterator>::pointer,
00106                       typename iterator_traits<_Iterator>::reference>
00107     {
00108     protected:
00109       _Iterator current;
00110 
00111       typedef iterator_traits<_Iterator>                __traits_type;
00112 
00113     public:
00114       typedef _Iterator                                 iterator_type;
00115       typedef typename __traits_type::difference_type   difference_type;
00116       typedef typename __traits_type::pointer           pointer;
00117       typedef typename __traits_type::reference         reference;
00118 
00119       /**
00120        *  The default constructor value-initializes member @p current.
00121        *  If it is a pointer, that means it is zero-initialized.
00122       */
00123       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00124       // 235 No specification of default ctor for reverse_iterator
00125       _GLIBCXX17_CONSTEXPR
00126       reverse_iterator() : current() { }
00127 
00128       /**
00129        *  This %iterator will move in the opposite direction that @p x does.
00130       */
00131       explicit _GLIBCXX17_CONSTEXPR
00132       reverse_iterator(iterator_type __x) : current(__x) { }
00133 
00134       /**
00135        *  The copy constructor is normal.
00136       */
00137       _GLIBCXX17_CONSTEXPR
00138       reverse_iterator(const reverse_iterator& __x)
00139       : current(__x.current) { }
00140 
00141       /**
00142        *  A %reverse_iterator across other types can be copied if the
00143        *  underlying %iterator can be converted to the type of @c current.
00144       */
00145       template<typename _Iter>
00146         _GLIBCXX17_CONSTEXPR
00147         reverse_iterator(const reverse_iterator<_Iter>& __x)
00148         : current(__x.base()) { }
00149 
00150       /**
00151        *  @return  @c current, the %iterator used for underlying work.
00152       */
00153       _GLIBCXX17_CONSTEXPR iterator_type
00154       base() const
00155       { return current; }
00156 
00157       /**
00158        *  @return  A reference to the value at @c --current
00159        *
00160        *  This requires that @c --current is dereferenceable.
00161        *
00162        *  @warning This implementation requires that for an iterator of the
00163        *           underlying iterator type, @c x, a reference obtained by
00164        *           @c *x remains valid after @c x has been modified or
00165        *           destroyed. This is a bug: http://gcc.gnu.org/PR51823
00166       */
00167       _GLIBCXX17_CONSTEXPR reference
00168       operator*() const
00169       {
00170         _Iterator __tmp = current;
00171         return *--__tmp;
00172       }
00173 
00174       /**
00175        *  @return  A pointer to the value at @c --current
00176        *
00177        *  This requires that @c --current is dereferenceable.
00178       */
00179       _GLIBCXX17_CONSTEXPR pointer
00180       operator->() const
00181       { return &(operator*()); }
00182 
00183       /**
00184        *  @return  @c *this
00185        *
00186        *  Decrements the underlying iterator.
00187       */
00188       _GLIBCXX17_CONSTEXPR reverse_iterator&
00189       operator++()
00190       {
00191         --current;
00192         return *this;
00193       }
00194 
00195       /**
00196        *  @return  The original value of @c *this
00197        *
00198        *  Decrements the underlying iterator.
00199       */
00200       _GLIBCXX17_CONSTEXPR reverse_iterator
00201       operator++(int)
00202       {
00203         reverse_iterator __tmp = *this;
00204         --current;
00205         return __tmp;
00206       }
00207 
00208       /**
00209        *  @return  @c *this
00210        *
00211        *  Increments the underlying iterator.
00212       */
00213       _GLIBCXX17_CONSTEXPR reverse_iterator&
00214       operator--()
00215       {
00216         ++current;
00217         return *this;
00218       }
00219 
00220       /**
00221        *  @return  A reverse_iterator with the previous value of @c *this
00222        *
00223        *  Increments the underlying iterator.
00224       */
00225       _GLIBCXX17_CONSTEXPR reverse_iterator
00226       operator--(int)
00227       {
00228         reverse_iterator __tmp = *this;
00229         ++current;
00230         return __tmp;
00231       }
00232 
00233       /**
00234        *  @return  A reverse_iterator that refers to @c current - @a __n
00235        *
00236        *  The underlying iterator must be a Random Access Iterator.
00237       */
00238       _GLIBCXX17_CONSTEXPR reverse_iterator
00239       operator+(difference_type __n) const
00240       { return reverse_iterator(current - __n); }
00241 
00242       /**
00243        *  @return  *this
00244        *
00245        *  Moves the underlying iterator backwards @a __n steps.
00246        *  The underlying iterator must be a Random Access Iterator.
00247       */
00248       _GLIBCXX17_CONSTEXPR reverse_iterator&
00249       operator+=(difference_type __n)
00250       {
00251         current -= __n;
00252         return *this;
00253       }
00254 
00255       /**
00256        *  @return  A reverse_iterator that refers to @c current - @a __n
00257        *
00258        *  The underlying iterator must be a Random Access Iterator.
00259       */
00260       _GLIBCXX17_CONSTEXPR reverse_iterator
00261       operator-(difference_type __n) const
00262       { return reverse_iterator(current + __n); }
00263 
00264       /**
00265        *  @return  *this
00266        *
00267        *  Moves the underlying iterator forwards @a __n steps.
00268        *  The underlying iterator must be a Random Access Iterator.
00269       */
00270       _GLIBCXX17_CONSTEXPR reverse_iterator&
00271       operator-=(difference_type __n)
00272       {
00273         current += __n;
00274         return *this;
00275       }
00276 
00277       /**
00278        *  @return  The value at @c current - @a __n - 1
00279        *
00280        *  The underlying iterator must be a Random Access Iterator.
00281       */
00282       _GLIBCXX17_CONSTEXPR reference
00283       operator[](difference_type __n) const
00284       { return *(*this + __n); }
00285     };
00286 
00287   //@{
00288   /**
00289    *  @param  __x  A %reverse_iterator.
00290    *  @param  __y  A %reverse_iterator.
00291    *  @return  A simple bool.
00292    *
00293    *  Reverse iterators forward many operations to their underlying base()
00294    *  iterators.  Others are implemented in terms of one another.
00295    *
00296   */
00297   template<typename _Iterator>
00298     inline _GLIBCXX17_CONSTEXPR bool
00299     operator==(const reverse_iterator<_Iterator>& __x,
00300                const reverse_iterator<_Iterator>& __y)
00301     { return __x.base() == __y.base(); }
00302 
00303   template<typename _Iterator>
00304     inline _GLIBCXX17_CONSTEXPR bool
00305     operator<(const reverse_iterator<_Iterator>& __x,
00306               const reverse_iterator<_Iterator>& __y)
00307     { return __y.base() < __x.base(); }
00308 
00309   template<typename _Iterator>
00310     inline _GLIBCXX17_CONSTEXPR bool
00311     operator!=(const reverse_iterator<_Iterator>& __x,
00312                const reverse_iterator<_Iterator>& __y)
00313     { return !(__x == __y); }
00314 
00315   template<typename _Iterator>
00316     inline _GLIBCXX17_CONSTEXPR bool
00317     operator>(const reverse_iterator<_Iterator>& __x,
00318               const reverse_iterator<_Iterator>& __y)
00319     { return __y < __x; }
00320 
00321   template<typename _Iterator>
00322     inline _GLIBCXX17_CONSTEXPR bool
00323     operator<=(const reverse_iterator<_Iterator>& __x,
00324                const reverse_iterator<_Iterator>& __y)
00325     { return !(__y < __x); }
00326 
00327   template<typename _Iterator>
00328     inline _GLIBCXX17_CONSTEXPR bool
00329     operator>=(const reverse_iterator<_Iterator>& __x,
00330                const reverse_iterator<_Iterator>& __y)
00331     { return !(__x < __y); }
00332 
00333   // _GLIBCXX_RESOLVE_LIB_DEFECTS
00334   // DR 280. Comparison of reverse_iterator to const reverse_iterator.
00335   template<typename _IteratorL, typename _IteratorR>
00336     inline _GLIBCXX17_CONSTEXPR bool
00337     operator==(const reverse_iterator<_IteratorL>& __x,
00338                const reverse_iterator<_IteratorR>& __y)
00339     { return __x.base() == __y.base(); }
00340 
00341   template<typename _IteratorL, typename _IteratorR>
00342     inline _GLIBCXX17_CONSTEXPR bool
00343     operator<(const reverse_iterator<_IteratorL>& __x,
00344               const reverse_iterator<_IteratorR>& __y)
00345     { return __y.base() < __x.base(); }
00346 
00347   template<typename _IteratorL, typename _IteratorR>
00348     inline _GLIBCXX17_CONSTEXPR bool
00349     operator!=(const reverse_iterator<_IteratorL>& __x,
00350                const reverse_iterator<_IteratorR>& __y)
00351     { return !(__x == __y); }
00352 
00353   template<typename _IteratorL, typename _IteratorR>
00354     inline _GLIBCXX17_CONSTEXPR bool
00355     operator>(const reverse_iterator<_IteratorL>& __x,
00356               const reverse_iterator<_IteratorR>& __y)
00357     { return __y < __x; }
00358 
00359   template<typename _IteratorL, typename _IteratorR>
00360     inline _GLIBCXX17_CONSTEXPR bool
00361     operator<=(const reverse_iterator<_IteratorL>& __x,
00362                const reverse_iterator<_IteratorR>& __y)
00363     { return !(__y < __x); }
00364 
00365   template<typename _IteratorL, typename _IteratorR>
00366     inline _GLIBCXX17_CONSTEXPR bool
00367     operator>=(const reverse_iterator<_IteratorL>& __x,
00368                const reverse_iterator<_IteratorR>& __y)
00369     { return !(__x < __y); }
00370   //@}
00371 
00372 #if __cplusplus < 201103L
00373   template<typename _Iterator>
00374     inline typename reverse_iterator<_Iterator>::difference_type
00375     operator-(const reverse_iterator<_Iterator>& __x,
00376               const reverse_iterator<_Iterator>& __y)
00377     { return __y.base() - __x.base(); }
00378 
00379   template<typename _IteratorL, typename _IteratorR>
00380     inline typename reverse_iterator<_IteratorL>::difference_type
00381     operator-(const reverse_iterator<_IteratorL>& __x,
00382               const reverse_iterator<_IteratorR>& __y)
00383     { return __y.base() - __x.base(); }
00384 #else
00385   // _GLIBCXX_RESOLVE_LIB_DEFECTS
00386   // DR 685. reverse_iterator/move_iterator difference has invalid signatures
00387   template<typename _IteratorL, typename _IteratorR>
00388     inline _GLIBCXX17_CONSTEXPR auto
00389     operator-(const reverse_iterator<_IteratorL>& __x,
00390               const reverse_iterator<_IteratorR>& __y)
00391     -> decltype(__y.base() - __x.base())
00392     { return __y.base() - __x.base(); }
00393 #endif
00394 
00395   template<typename _Iterator>
00396     inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
00397     operator+(typename reverse_iterator<_Iterator>::difference_type __n,
00398               const reverse_iterator<_Iterator>& __x)
00399     { return reverse_iterator<_Iterator>(__x.base() - __n); }
00400 
00401 #if __cplusplus >= 201103L
00402   // Same as C++14 make_reverse_iterator but used in C++03 mode too.
00403   template<typename _Iterator>
00404     inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
00405     __make_reverse_iterator(_Iterator __i)
00406     { return reverse_iterator<_Iterator>(__i); }
00407 
00408 # if __cplusplus > 201103L
00409 #  define __cpp_lib_make_reverse_iterator 201402
00410 
00411   // _GLIBCXX_RESOLVE_LIB_DEFECTS
00412   // DR 2285. make_reverse_iterator
00413   /// Generator function for reverse_iterator.
00414   template<typename _Iterator>
00415     inline _GLIBCXX17_CONSTEXPR reverse_iterator<_Iterator>
00416     make_reverse_iterator(_Iterator __i)
00417     { return reverse_iterator<_Iterator>(__i); }
00418 # endif
00419 #endif
00420 
00421 #if __cplusplus >= 201103L
00422   template<typename _Iterator>
00423     auto
00424     __niter_base(reverse_iterator<_Iterator> __it)
00425     -> decltype(__make_reverse_iterator(__niter_base(__it.base())))
00426     { return __make_reverse_iterator(__niter_base(__it.base())); }
00427 
00428   template<typename _Iterator>
00429     struct __is_move_iterator<reverse_iterator<_Iterator> >
00430       : __is_move_iterator<_Iterator>
00431     { };
00432 
00433   template<typename _Iterator>
00434     auto
00435     __miter_base(reverse_iterator<_Iterator> __it)
00436     -> decltype(__make_reverse_iterator(__miter_base(__it.base())))
00437     { return __make_reverse_iterator(__miter_base(__it.base())); }
00438 #endif
00439 
00440   // 24.4.2.2.1 back_insert_iterator
00441   /**
00442    *  @brief  Turns assignment into insertion.
00443    *
00444    *  These are output iterators, constructed from a container-of-T.
00445    *  Assigning a T to the iterator appends it to the container using
00446    *  push_back.
00447    *
00448    *  Tip:  Using the back_inserter function to create these iterators can
00449    *  save typing.
00450   */
00451   template<typename _Container>
00452     class back_insert_iterator
00453     : public iterator<output_iterator_tag, void, void, void, void>
00454     {
00455     protected:
00456       _Container* container;
00457 
00458     public:
00459       /// A nested typedef for the type of whatever container you used.
00460       typedef _Container          container_type;
00461 
00462       /// The only way to create this %iterator is with a container.
00463       explicit
00464       back_insert_iterator(_Container& __x)
00465       : container(std::__addressof(__x)) { }
00466 
00467       /**
00468        *  @param  __value  An instance of whatever type
00469        *                 container_type::const_reference is; presumably a
00470        *                 reference-to-const T for container<T>.
00471        *  @return  This %iterator, for chained operations.
00472        *
00473        *  This kind of %iterator doesn't really have a @a position in the
00474        *  container (you can think of the position as being permanently at
00475        *  the end, if you like).  Assigning a value to the %iterator will
00476        *  always append the value to the end of the container.
00477       */
00478 #if __cplusplus < 201103L
00479       back_insert_iterator&
00480       operator=(typename _Container::const_reference __value)
00481       {
00482         container->push_back(__value);
00483         return *this;
00484       }
00485 #else
00486       back_insert_iterator&
00487       operator=(const typename _Container::value_type& __value)
00488       {
00489         container->push_back(__value);
00490         return *this;
00491       }
00492 
00493       back_insert_iterator&
00494       operator=(typename _Container::value_type&& __value)
00495       {
00496         container->push_back(std::move(__value));
00497         return *this;
00498       }
00499 #endif
00500 
00501       /// Simply returns *this.
00502       back_insert_iterator&
00503       operator*()
00504       { return *this; }
00505 
00506       /// Simply returns *this.  (This %iterator does not @a move.)
00507       back_insert_iterator&
00508       operator++()
00509       { return *this; }
00510 
00511       /// Simply returns *this.  (This %iterator does not @a move.)
00512       back_insert_iterator
00513       operator++(int)
00514       { return *this; }
00515     };
00516 
00517   /**
00518    *  @param  __x  A container of arbitrary type.
00519    *  @return  An instance of back_insert_iterator working on @p __x.
00520    *
00521    *  This wrapper function helps in creating back_insert_iterator instances.
00522    *  Typing the name of the %iterator requires knowing the precise full
00523    *  type of the container, which can be tedious and impedes generic
00524    *  programming.  Using this function lets you take advantage of automatic
00525    *  template parameter deduction, making the compiler match the correct
00526    *  types for you.
00527   */
00528   template<typename _Container>
00529     inline back_insert_iterator<_Container>
00530     back_inserter(_Container& __x)
00531     { return back_insert_iterator<_Container>(__x); }
00532 
00533   /**
00534    *  @brief  Turns assignment into insertion.
00535    *
00536    *  These are output iterators, constructed from a container-of-T.
00537    *  Assigning a T to the iterator prepends it to the container using
00538    *  push_front.
00539    *
00540    *  Tip:  Using the front_inserter function to create these iterators can
00541    *  save typing.
00542   */
00543   template<typename _Container>
00544     class front_insert_iterator
00545     : public iterator<output_iterator_tag, void, void, void, void>
00546     {
00547     protected:
00548       _Container* container;
00549 
00550     public:
00551       /// A nested typedef for the type of whatever container you used.
00552       typedef _Container          container_type;
00553 
00554       /// The only way to create this %iterator is with a container.
00555       explicit front_insert_iterator(_Container& __x)
00556       : container(std::__addressof(__x)) { }
00557 
00558       /**
00559        *  @param  __value  An instance of whatever type
00560        *                 container_type::const_reference is; presumably a
00561        *                 reference-to-const T for container<T>.
00562        *  @return  This %iterator, for chained operations.
00563        *
00564        *  This kind of %iterator doesn't really have a @a position in the
00565        *  container (you can think of the position as being permanently at
00566        *  the front, if you like).  Assigning a value to the %iterator will
00567        *  always prepend the value to the front of the container.
00568       */
00569 #if __cplusplus < 201103L
00570       front_insert_iterator&
00571       operator=(typename _Container::const_reference __value)
00572       {
00573         container->push_front(__value);
00574         return *this;
00575       }
00576 #else
00577       front_insert_iterator&
00578       operator=(const typename _Container::value_type& __value)
00579       {
00580         container->push_front(__value);
00581         return *this;
00582       }
00583 
00584       front_insert_iterator&
00585       operator=(typename _Container::value_type&& __value)
00586       {
00587         container->push_front(std::move(__value));
00588         return *this;
00589       }
00590 #endif
00591 
00592       /// Simply returns *this.
00593       front_insert_iterator&
00594       operator*()
00595       { return *this; }
00596 
00597       /// Simply returns *this.  (This %iterator does not @a move.)
00598       front_insert_iterator&
00599       operator++()
00600       { return *this; }
00601 
00602       /// Simply returns *this.  (This %iterator does not @a move.)
00603       front_insert_iterator
00604       operator++(int)
00605       { return *this; }
00606     };
00607 
00608   /**
00609    *  @param  __x  A container of arbitrary type.
00610    *  @return  An instance of front_insert_iterator working on @p x.
00611    *
00612    *  This wrapper function helps in creating front_insert_iterator instances.
00613    *  Typing the name of the %iterator requires knowing the precise full
00614    *  type of the container, which can be tedious and impedes generic
00615    *  programming.  Using this function lets you take advantage of automatic
00616    *  template parameter deduction, making the compiler match the correct
00617    *  types for you.
00618   */
00619   template<typename _Container>
00620     inline front_insert_iterator<_Container>
00621     front_inserter(_Container& __x)
00622     { return front_insert_iterator<_Container>(__x); }
00623 
00624   /**
00625    *  @brief  Turns assignment into insertion.
00626    *
00627    *  These are output iterators, constructed from a container-of-T.
00628    *  Assigning a T to the iterator inserts it in the container at the
00629    *  %iterator's position, rather than overwriting the value at that
00630    *  position.
00631    *
00632    *  (Sequences will actually insert a @e copy of the value before the
00633    *  %iterator's position.)
00634    *
00635    *  Tip:  Using the inserter function to create these iterators can
00636    *  save typing.
00637   */
00638   template<typename _Container>
00639     class insert_iterator
00640     : public iterator<output_iterator_tag, void, void, void, void>
00641     {
00642     protected:
00643       _Container* container;
00644       typename _Container::iterator iter;
00645 
00646     public:
00647       /// A nested typedef for the type of whatever container you used.
00648       typedef _Container          container_type;
00649 
00650       /**
00651        *  The only way to create this %iterator is with a container and an
00652        *  initial position (a normal %iterator into the container).
00653       */
00654       insert_iterator(_Container& __x, typename _Container::iterator __i)
00655       : container(std::__addressof(__x)), iter(__i) {}
00656 
00657       /**
00658        *  @param  __value  An instance of whatever type
00659        *                 container_type::const_reference is; presumably a
00660        *                 reference-to-const T for container<T>.
00661        *  @return  This %iterator, for chained operations.
00662        *
00663        *  This kind of %iterator maintains its own position in the
00664        *  container.  Assigning a value to the %iterator will insert the
00665        *  value into the container at the place before the %iterator.
00666        *
00667        *  The position is maintained such that subsequent assignments will
00668        *  insert values immediately after one another.  For example,
00669        *  @code
00670        *     // vector v contains A and Z
00671        *
00672        *     insert_iterator i (v, ++v.begin());
00673        *     i = 1;
00674        *     i = 2;
00675        *     i = 3;
00676        *
00677        *     // vector v contains A, 1, 2, 3, and Z
00678        *  @endcode
00679       */
00680 #if __cplusplus < 201103L
00681       insert_iterator&
00682       operator=(typename _Container::const_reference __value)
00683       {
00684         iter = container->insert(iter, __value);
00685         ++iter;
00686         return *this;
00687       }
00688 #else
00689       insert_iterator&
00690       operator=(const typename _Container::value_type& __value)
00691       {
00692         iter = container->insert(iter, __value);
00693         ++iter;
00694         return *this;
00695       }
00696 
00697       insert_iterator&
00698       operator=(typename _Container::value_type&& __value)
00699       {
00700         iter = container->insert(iter, std::move(__value));
00701         ++iter;
00702         return *this;
00703       }
00704 #endif
00705 
00706       /// Simply returns *this.
00707       insert_iterator&
00708       operator*()
00709       { return *this; }
00710 
00711       /// Simply returns *this.  (This %iterator does not @a move.)
00712       insert_iterator&
00713       operator++()
00714       { return *this; }
00715 
00716       /// Simply returns *this.  (This %iterator does not @a move.)
00717       insert_iterator&
00718       operator++(int)
00719       { return *this; }
00720     };
00721 
00722   /**
00723    *  @param __x  A container of arbitrary type.
00724    *  @return  An instance of insert_iterator working on @p __x.
00725    *
00726    *  This wrapper function helps in creating insert_iterator instances.
00727    *  Typing the name of the %iterator requires knowing the precise full
00728    *  type of the container, which can be tedious and impedes generic
00729    *  programming.  Using this function lets you take advantage of automatic
00730    *  template parameter deduction, making the compiler match the correct
00731    *  types for you.
00732   */
00733   template<typename _Container, typename _Iterator>
00734     inline insert_iterator<_Container>
00735     inserter(_Container& __x, _Iterator __i)
00736     {
00737       return insert_iterator<_Container>(__x,
00738                                          typename _Container::iterator(__i));
00739     }
00740 
00741   // @} group iterators
00742 
00743 _GLIBCXX_END_NAMESPACE_VERSION
00744 } // namespace
00745 
00746 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
00747 {
00748 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00749 
00750   // This iterator adapter is @a normal in the sense that it does not
00751   // change the semantics of any of the operators of its iterator
00752   // parameter.  Its primary purpose is to convert an iterator that is
00753   // not a class, e.g. a pointer, into an iterator that is a class.
00754   // The _Container parameter exists solely so that different containers
00755   // using this template can instantiate different types, even if the
00756   // _Iterator parameter is the same.
00757   using std::iterator_traits;
00758   using std::iterator;
00759   template<typename _Iterator, typename _Container>
00760     class __normal_iterator
00761     {
00762     protected:
00763       _Iterator _M_current;
00764 
00765       typedef iterator_traits<_Iterator>                __traits_type;
00766 
00767     public:
00768       typedef _Iterator                                 iterator_type;
00769       typedef typename __traits_type::iterator_category iterator_category;
00770       typedef typename __traits_type::value_type        value_type;
00771       typedef typename __traits_type::difference_type   difference_type;
00772       typedef typename __traits_type::reference         reference;
00773       typedef typename __traits_type::pointer           pointer;
00774 
00775       _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT
00776       : _M_current(_Iterator()) { }
00777 
00778       explicit
00779       __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT
00780       : _M_current(__i) { }
00781 
00782       // Allow iterator to const_iterator conversion
00783       template<typename _Iter>
00784         __normal_iterator(const __normal_iterator<_Iter,
00785                           typename __enable_if<
00786                (std::__are_same<_Iter, typename _Container::pointer>::__value),
00787                       _Container>::__type>& __i) _GLIBCXX_NOEXCEPT
00788         : _M_current(__i.base()) { }
00789 
00790       // Forward iterator requirements
00791       reference
00792       operator*() const _GLIBCXX_NOEXCEPT
00793       { return *_M_current; }
00794 
00795       pointer
00796       operator->() const _GLIBCXX_NOEXCEPT
00797       { return _M_current; }
00798 
00799       __normal_iterator&
00800       operator++() _GLIBCXX_NOEXCEPT
00801       {
00802         ++_M_current;
00803         return *this;
00804       }
00805 
00806       __normal_iterator
00807       operator++(int) _GLIBCXX_NOEXCEPT
00808       { return __normal_iterator(_M_current++); }
00809 
00810       // Bidirectional iterator requirements
00811       __normal_iterator&
00812       operator--() _GLIBCXX_NOEXCEPT
00813       {
00814         --_M_current;
00815         return *this;
00816       }
00817 
00818       __normal_iterator
00819       operator--(int) _GLIBCXX_NOEXCEPT
00820       { return __normal_iterator(_M_current--); }
00821 
00822       // Random access iterator requirements
00823       reference
00824       operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
00825       { return _M_current[__n]; }
00826 
00827       __normal_iterator&
00828       operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
00829       { _M_current += __n; return *this; }
00830 
00831       __normal_iterator
00832       operator+(difference_type __n) const _GLIBCXX_NOEXCEPT
00833       { return __normal_iterator(_M_current + __n); }
00834 
00835       __normal_iterator&
00836       operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
00837       { _M_current -= __n; return *this; }
00838 
00839       __normal_iterator
00840       operator-(difference_type __n) const _GLIBCXX_NOEXCEPT
00841       { return __normal_iterator(_M_current - __n); }
00842 
00843       const _Iterator&
00844       base() const _GLIBCXX_NOEXCEPT
00845       { return _M_current; }
00846     };
00847 
00848   // Note: In what follows, the left- and right-hand-side iterators are
00849   // allowed to vary in types (conceptually in cv-qualification) so that
00850   // comparison between cv-qualified and non-cv-qualified iterators be
00851   // valid.  However, the greedy and unfriendly operators in std::rel_ops
00852   // will make overload resolution ambiguous (when in scope) if we don't
00853   // provide overloads whose operands are of the same type.  Can someone
00854   // remind me what generic programming is about? -- Gaby
00855 
00856   // Forward iterator requirements
00857   template<typename _IteratorL, typename _IteratorR, typename _Container>
00858     inline bool
00859     operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
00860                const __normal_iterator<_IteratorR, _Container>& __rhs)
00861     _GLIBCXX_NOEXCEPT
00862     { return __lhs.base() == __rhs.base(); }
00863 
00864   template<typename _Iterator, typename _Container>
00865     inline bool
00866     operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
00867                const __normal_iterator<_Iterator, _Container>& __rhs)
00868     _GLIBCXX_NOEXCEPT
00869     { return __lhs.base() == __rhs.base(); }
00870 
00871   template<typename _IteratorL, typename _IteratorR, typename _Container>
00872     inline bool
00873     operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00874                const __normal_iterator<_IteratorR, _Container>& __rhs)
00875     _GLIBCXX_NOEXCEPT
00876     { return __lhs.base() != __rhs.base(); }
00877 
00878   template<typename _Iterator, typename _Container>
00879     inline bool
00880     operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
00881                const __normal_iterator<_Iterator, _Container>& __rhs)
00882     _GLIBCXX_NOEXCEPT
00883     { return __lhs.base() != __rhs.base(); }
00884 
00885   // Random access iterator requirements
00886   template<typename _IteratorL, typename _IteratorR, typename _Container>
00887     inline bool
00888     operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
00889               const __normal_iterator<_IteratorR, _Container>& __rhs)
00890     _GLIBCXX_NOEXCEPT
00891     { return __lhs.base() < __rhs.base(); }
00892 
00893   template<typename _Iterator, typename _Container>
00894     inline bool
00895     operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
00896               const __normal_iterator<_Iterator, _Container>& __rhs)
00897     _GLIBCXX_NOEXCEPT
00898     { return __lhs.base() < __rhs.base(); }
00899 
00900   template<typename _IteratorL, typename _IteratorR, typename _Container>
00901     inline bool
00902     operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
00903               const __normal_iterator<_IteratorR, _Container>& __rhs)
00904     _GLIBCXX_NOEXCEPT
00905     { return __lhs.base() > __rhs.base(); }
00906 
00907   template<typename _Iterator, typename _Container>
00908     inline bool
00909     operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
00910               const __normal_iterator<_Iterator, _Container>& __rhs)
00911     _GLIBCXX_NOEXCEPT
00912     { return __lhs.base() > __rhs.base(); }
00913 
00914   template<typename _IteratorL, typename _IteratorR, typename _Container>
00915     inline bool
00916     operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00917                const __normal_iterator<_IteratorR, _Container>& __rhs)
00918     _GLIBCXX_NOEXCEPT
00919     { return __lhs.base() <= __rhs.base(); }
00920 
00921   template<typename _Iterator, typename _Container>
00922     inline bool
00923     operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
00924                const __normal_iterator<_Iterator, _Container>& __rhs)
00925     _GLIBCXX_NOEXCEPT
00926     { return __lhs.base() <= __rhs.base(); }
00927 
00928   template<typename _IteratorL, typename _IteratorR, typename _Container>
00929     inline bool
00930     operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00931                const __normal_iterator<_IteratorR, _Container>& __rhs)
00932     _GLIBCXX_NOEXCEPT
00933     { return __lhs.base() >= __rhs.base(); }
00934 
00935   template<typename _Iterator, typename _Container>
00936     inline bool
00937     operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
00938                const __normal_iterator<_Iterator, _Container>& __rhs)
00939     _GLIBCXX_NOEXCEPT
00940     { return __lhs.base() >= __rhs.base(); }
00941 
00942   // _GLIBCXX_RESOLVE_LIB_DEFECTS
00943   // According to the resolution of DR179 not only the various comparison
00944   // operators but also operator- must accept mixed iterator/const_iterator
00945   // parameters.
00946   template<typename _IteratorL, typename _IteratorR, typename _Container>
00947 #if __cplusplus >= 201103L
00948     // DR 685.
00949     inline auto
00950     operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
00951               const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept
00952     -> decltype(__lhs.base() - __rhs.base())
00953 #else
00954     inline typename __normal_iterator<_IteratorL, _Container>::difference_type
00955     operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
00956               const __normal_iterator<_IteratorR, _Container>& __rhs)
00957 #endif
00958     { return __lhs.base() - __rhs.base(); }
00959 
00960   template<typename _Iterator, typename _Container>
00961     inline typename __normal_iterator<_Iterator, _Container>::difference_type
00962     operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
00963               const __normal_iterator<_Iterator, _Container>& __rhs)
00964     _GLIBCXX_NOEXCEPT
00965     { return __lhs.base() - __rhs.base(); }
00966 
00967   template<typename _Iterator, typename _Container>
00968     inline __normal_iterator<_Iterator, _Container>
00969     operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
00970               __n, const __normal_iterator<_Iterator, _Container>& __i)
00971     _GLIBCXX_NOEXCEPT
00972     { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
00973 
00974 _GLIBCXX_END_NAMESPACE_VERSION
00975 } // namespace
00976 
00977 namespace std _GLIBCXX_VISIBILITY(default)
00978 {
00979 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00980 
00981   template<typename _Iterator, typename _Container>
00982     _Iterator
00983     __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
00984     { return __it.base(); }
00985 
00986 _GLIBCXX_END_NAMESPACE_VERSION
00987 } // namespace
00988 
00989 #if __cplusplus >= 201103L
00990 
00991 namespace std _GLIBCXX_VISIBILITY(default)
00992 {
00993 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00994 
00995   /**
00996    * @addtogroup iterators
00997    * @{
00998    */
00999 
01000   // 24.4.3  Move iterators
01001   /**
01002    *  Class template move_iterator is an iterator adapter with the same
01003    *  behavior as the underlying iterator except that its dereference
01004    *  operator implicitly converts the value returned by the underlying
01005    *  iterator's dereference operator to an rvalue reference.  Some
01006    *  generic algorithms can be called with move iterators to replace
01007    *  copying with moving.
01008    */
01009   template<typename _Iterator>
01010     class move_iterator
01011     {
01012     protected:
01013       _Iterator _M_current;
01014 
01015       typedef iterator_traits<_Iterator>                __traits_type;
01016       typedef typename __traits_type::reference         __base_ref;
01017 
01018     public:
01019       typedef _Iterator                                 iterator_type;
01020       typedef typename __traits_type::iterator_category iterator_category;
01021       typedef typename __traits_type::value_type        value_type;
01022       typedef typename __traits_type::difference_type   difference_type;
01023       // NB: DR 680.
01024       typedef _Iterator                                 pointer;
01025       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01026       // 2106. move_iterator wrapping iterators returning prvalues
01027       typedef typename conditional<is_reference<__base_ref>::value,
01028                          typename remove_reference<__base_ref>::type&&,
01029                          __base_ref>::type              reference;
01030 
01031       _GLIBCXX17_CONSTEXPR
01032       move_iterator()
01033       : _M_current() { }
01034 
01035       explicit _GLIBCXX17_CONSTEXPR
01036       move_iterator(iterator_type __i)
01037       : _M_current(__i) { }
01038 
01039       template<typename _Iter>
01040         _GLIBCXX17_CONSTEXPR
01041         move_iterator(const move_iterator<_Iter>& __i)
01042         : _M_current(__i.base()) { }
01043 
01044       _GLIBCXX17_CONSTEXPR iterator_type
01045       base() const
01046       { return _M_current; }
01047 
01048       _GLIBCXX17_CONSTEXPR reference
01049       operator*() const
01050       { return static_cast<reference>(*_M_current); }
01051 
01052       _GLIBCXX17_CONSTEXPR pointer
01053       operator->() const
01054       { return _M_current; }
01055 
01056       _GLIBCXX17_CONSTEXPR move_iterator&
01057       operator++()
01058       {
01059         ++_M_current;
01060         return *this;
01061       }
01062 
01063       _GLIBCXX17_CONSTEXPR move_iterator
01064       operator++(int)
01065       {
01066         move_iterator __tmp = *this;
01067         ++_M_current;
01068         return __tmp;
01069       }
01070 
01071       _GLIBCXX17_CONSTEXPR move_iterator&
01072       operator--()
01073       {
01074         --_M_current;
01075         return *this;
01076       }
01077 
01078       _GLIBCXX17_CONSTEXPR move_iterator
01079       operator--(int)
01080       {
01081         move_iterator __tmp = *this;
01082         --_M_current;
01083         return __tmp;
01084       }
01085 
01086       _GLIBCXX17_CONSTEXPR move_iterator
01087       operator+(difference_type __n) const
01088       { return move_iterator(_M_current + __n); }
01089 
01090       _GLIBCXX17_CONSTEXPR move_iterator&
01091       operator+=(difference_type __n)
01092       {
01093         _M_current += __n;
01094         return *this;
01095       }
01096 
01097       _GLIBCXX17_CONSTEXPR move_iterator
01098       operator-(difference_type __n) const
01099       { return move_iterator(_M_current - __n); }
01100     
01101       _GLIBCXX17_CONSTEXPR move_iterator&
01102       operator-=(difference_type __n)
01103       { 
01104         _M_current -= __n;
01105         return *this;
01106       }
01107 
01108       _GLIBCXX17_CONSTEXPR reference
01109       operator[](difference_type __n) const
01110       { return std::move(_M_current[__n]); }
01111     };
01112 
01113   // Note: See __normal_iterator operators note from Gaby to understand
01114   // why there are always 2 versions for most of the move_iterator
01115   // operators.
01116   template<typename _IteratorL, typename _IteratorR>
01117     inline _GLIBCXX17_CONSTEXPR bool
01118     operator==(const move_iterator<_IteratorL>& __x,
01119                const move_iterator<_IteratorR>& __y)
01120     { return __x.base() == __y.base(); }
01121 
01122   template<typename _Iterator>
01123     inline _GLIBCXX17_CONSTEXPR bool
01124     operator==(const move_iterator<_Iterator>& __x,
01125                const move_iterator<_Iterator>& __y)
01126     { return __x.base() == __y.base(); }
01127 
01128   template<typename _IteratorL, typename _IteratorR>
01129     inline _GLIBCXX17_CONSTEXPR bool
01130     operator!=(const move_iterator<_IteratorL>& __x,
01131                const move_iterator<_IteratorR>& __y)
01132     { return !(__x == __y); }
01133 
01134   template<typename _Iterator>
01135     inline _GLIBCXX17_CONSTEXPR bool
01136     operator!=(const move_iterator<_Iterator>& __x,
01137                const move_iterator<_Iterator>& __y)
01138     { return !(__x == __y); }
01139 
01140   template<typename _IteratorL, typename _IteratorR>
01141     inline _GLIBCXX17_CONSTEXPR bool
01142     operator<(const move_iterator<_IteratorL>& __x,
01143               const move_iterator<_IteratorR>& __y)
01144     { return __x.base() < __y.base(); }
01145 
01146   template<typename _Iterator>
01147     inline _GLIBCXX17_CONSTEXPR bool
01148     operator<(const move_iterator<_Iterator>& __x,
01149               const move_iterator<_Iterator>& __y)
01150     { return __x.base() < __y.base(); }
01151 
01152   template<typename _IteratorL, typename _IteratorR>
01153     inline _GLIBCXX17_CONSTEXPR bool
01154     operator<=(const move_iterator<_IteratorL>& __x,
01155                const move_iterator<_IteratorR>& __y)
01156     { return !(__y < __x); }
01157 
01158   template<typename _Iterator>
01159     inline _GLIBCXX17_CONSTEXPR bool
01160     operator<=(const move_iterator<_Iterator>& __x,
01161                const move_iterator<_Iterator>& __y)
01162     { return !(__y < __x); }
01163 
01164   template<typename _IteratorL, typename _IteratorR>
01165     inline _GLIBCXX17_CONSTEXPR bool
01166     operator>(const move_iterator<_IteratorL>& __x,
01167               const move_iterator<_IteratorR>& __y)
01168     { return __y < __x; }
01169 
01170   template<typename _Iterator>
01171     inline _GLIBCXX17_CONSTEXPR bool
01172     operator>(const move_iterator<_Iterator>& __x,
01173               const move_iterator<_Iterator>& __y)
01174     { return __y < __x; }
01175 
01176   template<typename _IteratorL, typename _IteratorR>
01177     inline _GLIBCXX17_CONSTEXPR bool
01178     operator>=(const move_iterator<_IteratorL>& __x,
01179                const move_iterator<_IteratorR>& __y)
01180     { return !(__x < __y); }
01181 
01182   template<typename _Iterator>
01183     inline _GLIBCXX17_CONSTEXPR bool
01184     operator>=(const move_iterator<_Iterator>& __x,
01185                const move_iterator<_Iterator>& __y)
01186     { return !(__x < __y); }
01187 
01188   // DR 685.
01189   template<typename _IteratorL, typename _IteratorR>
01190     inline _GLIBCXX17_CONSTEXPR auto
01191     operator-(const move_iterator<_IteratorL>& __x,
01192               const move_iterator<_IteratorR>& __y)
01193     -> decltype(__x.base() - __y.base())
01194     { return __x.base() - __y.base(); }
01195 
01196   template<typename _Iterator>
01197     inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
01198     operator+(typename move_iterator<_Iterator>::difference_type __n,
01199               const move_iterator<_Iterator>& __x)
01200     { return __x + __n; }
01201 
01202   template<typename _Iterator>
01203     inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
01204     make_move_iterator(_Iterator __i)
01205     { return move_iterator<_Iterator>(__i); }
01206 
01207   template<typename _Iterator, typename _ReturnType
01208     = typename conditional<__move_if_noexcept_cond
01209       <typename iterator_traits<_Iterator>::value_type>::value,
01210                 _Iterator, move_iterator<_Iterator>>::type>
01211     inline _GLIBCXX17_CONSTEXPR _ReturnType
01212     __make_move_if_noexcept_iterator(_Iterator __i)
01213     { return _ReturnType(__i); }
01214 
01215   // Overload for pointers that matches std::move_if_noexcept more closely,
01216   // returning a constant iterator when we don't want to move.
01217   template<typename _Tp, typename _ReturnType
01218     = typename conditional<__move_if_noexcept_cond<_Tp>::value,
01219                            const _Tp*, move_iterator<_Tp*>>::type>
01220     inline _GLIBCXX17_CONSTEXPR _ReturnType
01221     __make_move_if_noexcept_iterator(_Tp* __i)
01222     { return _ReturnType(__i); }
01223 
01224   // @} group iterators
01225 
01226   template<typename _Iterator>
01227     auto
01228     __niter_base(move_iterator<_Iterator> __it)
01229     -> decltype(make_move_iterator(__niter_base(__it.base())))
01230     { return make_move_iterator(__niter_base(__it.base())); }
01231 
01232   template<typename _Iterator>
01233     struct __is_move_iterator<move_iterator<_Iterator> >
01234     {
01235       enum { __value = 1 };
01236       typedef __true_type __type;
01237     };
01238 
01239   template<typename _Iterator>
01240     auto
01241     __miter_base(move_iterator<_Iterator> __it)
01242     -> decltype(__miter_base(__it.base()))
01243     { return __miter_base(__it.base()); }
01244 
01245 _GLIBCXX_END_NAMESPACE_VERSION
01246 } // namespace
01247 
01248 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
01249 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
01250   std::__make_move_if_noexcept_iterator(_Iter)
01251 #else
01252 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
01253 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
01254 #endif // C++11
01255 
01256 #ifdef _GLIBCXX_DEBUG
01257 # include <debug/stl_iterator.h>
01258 #endif
01259 
01260 #endif