libstdc++
stl_iterator.h
Go to the documentation of this file.
00001 // Iterators -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2018 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    *  @param __i  An iterator into the container.
00725    *  @return  An instance of insert_iterator working on @p __x.
00726    *
00727    *  This wrapper function helps in creating insert_iterator instances.
00728    *  Typing the name of the %iterator requires knowing the precise full
00729    *  type of the container, which can be tedious and impedes generic
00730    *  programming.  Using this function lets you take advantage of automatic
00731    *  template parameter deduction, making the compiler match the correct
00732    *  types for you.
00733   */
00734   template<typename _Container, typename _Iterator>
00735     inline insert_iterator<_Container>
00736     inserter(_Container& __x, _Iterator __i)
00737     {
00738       return insert_iterator<_Container>(__x,
00739                                          typename _Container::iterator(__i));
00740     }
00741 
00742   // @} group iterators
00743 
00744 _GLIBCXX_END_NAMESPACE_VERSION
00745 } // namespace
00746 
00747 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
00748 {
00749 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00750 
00751   // This iterator adapter is @a normal in the sense that it does not
00752   // change the semantics of any of the operators of its iterator
00753   // parameter.  Its primary purpose is to convert an iterator that is
00754   // not a class, e.g. a pointer, into an iterator that is a class.
00755   // The _Container parameter exists solely so that different containers
00756   // using this template can instantiate different types, even if the
00757   // _Iterator parameter is the same.
00758   using std::iterator_traits;
00759   using std::iterator;
00760   template<typename _Iterator, typename _Container>
00761     class __normal_iterator
00762     {
00763     protected:
00764       _Iterator _M_current;
00765 
00766       typedef iterator_traits<_Iterator>                __traits_type;
00767 
00768     public:
00769       typedef _Iterator                                 iterator_type;
00770       typedef typename __traits_type::iterator_category iterator_category;
00771       typedef typename __traits_type::value_type        value_type;
00772       typedef typename __traits_type::difference_type   difference_type;
00773       typedef typename __traits_type::reference         reference;
00774       typedef typename __traits_type::pointer           pointer;
00775 
00776       _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT
00777       : _M_current(_Iterator()) { }
00778 
00779       explicit
00780       __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT
00781       : _M_current(__i) { }
00782 
00783       // Allow iterator to const_iterator conversion
00784       template<typename _Iter>
00785         __normal_iterator(const __normal_iterator<_Iter,
00786                           typename __enable_if<
00787                (std::__are_same<_Iter, typename _Container::pointer>::__value),
00788                       _Container>::__type>& __i) _GLIBCXX_NOEXCEPT
00789         : _M_current(__i.base()) { }
00790 
00791       // Forward iterator requirements
00792       reference
00793       operator*() const _GLIBCXX_NOEXCEPT
00794       { return *_M_current; }
00795 
00796       pointer
00797       operator->() const _GLIBCXX_NOEXCEPT
00798       { return _M_current; }
00799 
00800       __normal_iterator&
00801       operator++() _GLIBCXX_NOEXCEPT
00802       {
00803         ++_M_current;
00804         return *this;
00805       }
00806 
00807       __normal_iterator
00808       operator++(int) _GLIBCXX_NOEXCEPT
00809       { return __normal_iterator(_M_current++); }
00810 
00811       // Bidirectional iterator requirements
00812       __normal_iterator&
00813       operator--() _GLIBCXX_NOEXCEPT
00814       {
00815         --_M_current;
00816         return *this;
00817       }
00818 
00819       __normal_iterator
00820       operator--(int) _GLIBCXX_NOEXCEPT
00821       { return __normal_iterator(_M_current--); }
00822 
00823       // Random access iterator requirements
00824       reference
00825       operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
00826       { return _M_current[__n]; }
00827 
00828       __normal_iterator&
00829       operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
00830       { _M_current += __n; return *this; }
00831 
00832       __normal_iterator
00833       operator+(difference_type __n) const _GLIBCXX_NOEXCEPT
00834       { return __normal_iterator(_M_current + __n); }
00835 
00836       __normal_iterator&
00837       operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
00838       { _M_current -= __n; return *this; }
00839 
00840       __normal_iterator
00841       operator-(difference_type __n) const _GLIBCXX_NOEXCEPT
00842       { return __normal_iterator(_M_current - __n); }
00843 
00844       const _Iterator&
00845       base() const _GLIBCXX_NOEXCEPT
00846       { return _M_current; }
00847     };
00848 
00849   // Note: In what follows, the left- and right-hand-side iterators are
00850   // allowed to vary in types (conceptually in cv-qualification) so that
00851   // comparison between cv-qualified and non-cv-qualified iterators be
00852   // valid.  However, the greedy and unfriendly operators in std::rel_ops
00853   // will make overload resolution ambiguous (when in scope) if we don't
00854   // provide overloads whose operands are of the same type.  Can someone
00855   // remind me what generic programming is about? -- Gaby
00856 
00857   // Forward iterator requirements
00858   template<typename _IteratorL, typename _IteratorR, typename _Container>
00859     inline bool
00860     operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
00861                const __normal_iterator<_IteratorR, _Container>& __rhs)
00862     _GLIBCXX_NOEXCEPT
00863     { return __lhs.base() == __rhs.base(); }
00864 
00865   template<typename _Iterator, typename _Container>
00866     inline bool
00867     operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
00868                const __normal_iterator<_Iterator, _Container>& __rhs)
00869     _GLIBCXX_NOEXCEPT
00870     { return __lhs.base() == __rhs.base(); }
00871 
00872   template<typename _IteratorL, typename _IteratorR, typename _Container>
00873     inline bool
00874     operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00875                const __normal_iterator<_IteratorR, _Container>& __rhs)
00876     _GLIBCXX_NOEXCEPT
00877     { return __lhs.base() != __rhs.base(); }
00878 
00879   template<typename _Iterator, typename _Container>
00880     inline bool
00881     operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
00882                const __normal_iterator<_Iterator, _Container>& __rhs)
00883     _GLIBCXX_NOEXCEPT
00884     { return __lhs.base() != __rhs.base(); }
00885 
00886   // Random access iterator requirements
00887   template<typename _IteratorL, typename _IteratorR, typename _Container>
00888     inline bool
00889     operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
00890               const __normal_iterator<_IteratorR, _Container>& __rhs)
00891     _GLIBCXX_NOEXCEPT
00892     { return __lhs.base() < __rhs.base(); }
00893 
00894   template<typename _Iterator, typename _Container>
00895     inline bool
00896     operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
00897               const __normal_iterator<_Iterator, _Container>& __rhs)
00898     _GLIBCXX_NOEXCEPT
00899     { return __lhs.base() < __rhs.base(); }
00900 
00901   template<typename _IteratorL, typename _IteratorR, typename _Container>
00902     inline bool
00903     operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
00904               const __normal_iterator<_IteratorR, _Container>& __rhs)
00905     _GLIBCXX_NOEXCEPT
00906     { return __lhs.base() > __rhs.base(); }
00907 
00908   template<typename _Iterator, typename _Container>
00909     inline bool
00910     operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
00911               const __normal_iterator<_Iterator, _Container>& __rhs)
00912     _GLIBCXX_NOEXCEPT
00913     { return __lhs.base() > __rhs.base(); }
00914 
00915   template<typename _IteratorL, typename _IteratorR, typename _Container>
00916     inline bool
00917     operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00918                const __normal_iterator<_IteratorR, _Container>& __rhs)
00919     _GLIBCXX_NOEXCEPT
00920     { return __lhs.base() <= __rhs.base(); }
00921 
00922   template<typename _Iterator, typename _Container>
00923     inline bool
00924     operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
00925                const __normal_iterator<_Iterator, _Container>& __rhs)
00926     _GLIBCXX_NOEXCEPT
00927     { return __lhs.base() <= __rhs.base(); }
00928 
00929   template<typename _IteratorL, typename _IteratorR, typename _Container>
00930     inline bool
00931     operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00932                const __normal_iterator<_IteratorR, _Container>& __rhs)
00933     _GLIBCXX_NOEXCEPT
00934     { return __lhs.base() >= __rhs.base(); }
00935 
00936   template<typename _Iterator, typename _Container>
00937     inline bool
00938     operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
00939                const __normal_iterator<_Iterator, _Container>& __rhs)
00940     _GLIBCXX_NOEXCEPT
00941     { return __lhs.base() >= __rhs.base(); }
00942 
00943   // _GLIBCXX_RESOLVE_LIB_DEFECTS
00944   // According to the resolution of DR179 not only the various comparison
00945   // operators but also operator- must accept mixed iterator/const_iterator
00946   // parameters.
00947   template<typename _IteratorL, typename _IteratorR, typename _Container>
00948 #if __cplusplus >= 201103L
00949     // DR 685.
00950     inline auto
00951     operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
00952               const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept
00953     -> decltype(__lhs.base() - __rhs.base())
00954 #else
00955     inline typename __normal_iterator<_IteratorL, _Container>::difference_type
00956     operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
00957               const __normal_iterator<_IteratorR, _Container>& __rhs)
00958 #endif
00959     { return __lhs.base() - __rhs.base(); }
00960 
00961   template<typename _Iterator, typename _Container>
00962     inline typename __normal_iterator<_Iterator, _Container>::difference_type
00963     operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
00964               const __normal_iterator<_Iterator, _Container>& __rhs)
00965     _GLIBCXX_NOEXCEPT
00966     { return __lhs.base() - __rhs.base(); }
00967 
00968   template<typename _Iterator, typename _Container>
00969     inline __normal_iterator<_Iterator, _Container>
00970     operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
00971               __n, const __normal_iterator<_Iterator, _Container>& __i)
00972     _GLIBCXX_NOEXCEPT
00973     { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
00974 
00975 _GLIBCXX_END_NAMESPACE_VERSION
00976 } // namespace
00977 
00978 namespace std _GLIBCXX_VISIBILITY(default)
00979 {
00980 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00981 
00982   template<typename _Iterator, typename _Container>
00983     _Iterator
00984     __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
00985     { return __it.base(); }
00986 
00987 #if __cplusplus >= 201103L
00988 
00989   /**
00990    * @addtogroup iterators
00991    * @{
00992    */
00993 
00994   // 24.4.3  Move iterators
00995   /**
00996    *  Class template move_iterator is an iterator adapter with the same
00997    *  behavior as the underlying iterator except that its dereference
00998    *  operator implicitly converts the value returned by the underlying
00999    *  iterator's dereference operator to an rvalue reference.  Some
01000    *  generic algorithms can be called with move iterators to replace
01001    *  copying with moving.
01002    */
01003   template<typename _Iterator>
01004     class move_iterator
01005     {
01006     protected:
01007       _Iterator _M_current;
01008 
01009       typedef iterator_traits<_Iterator>                __traits_type;
01010       typedef typename __traits_type::reference         __base_ref;
01011 
01012     public:
01013       typedef _Iterator                                 iterator_type;
01014       typedef typename __traits_type::iterator_category iterator_category;
01015       typedef typename __traits_type::value_type        value_type;
01016       typedef typename __traits_type::difference_type   difference_type;
01017       // NB: DR 680.
01018       typedef _Iterator                                 pointer;
01019       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01020       // 2106. move_iterator wrapping iterators returning prvalues
01021       typedef typename conditional<is_reference<__base_ref>::value,
01022                          typename remove_reference<__base_ref>::type&&,
01023                          __base_ref>::type              reference;
01024 
01025       _GLIBCXX17_CONSTEXPR
01026       move_iterator()
01027       : _M_current() { }
01028 
01029       explicit _GLIBCXX17_CONSTEXPR
01030       move_iterator(iterator_type __i)
01031       : _M_current(__i) { }
01032 
01033       template<typename _Iter>
01034         _GLIBCXX17_CONSTEXPR
01035         move_iterator(const move_iterator<_Iter>& __i)
01036         : _M_current(__i.base()) { }
01037 
01038       _GLIBCXX17_CONSTEXPR iterator_type
01039       base() const
01040       { return _M_current; }
01041 
01042       _GLIBCXX17_CONSTEXPR reference
01043       operator*() const
01044       { return static_cast<reference>(*_M_current); }
01045 
01046       _GLIBCXX17_CONSTEXPR pointer
01047       operator->() const
01048       { return _M_current; }
01049 
01050       _GLIBCXX17_CONSTEXPR move_iterator&
01051       operator++()
01052       {
01053         ++_M_current;
01054         return *this;
01055       }
01056 
01057       _GLIBCXX17_CONSTEXPR move_iterator
01058       operator++(int)
01059       {
01060         move_iterator __tmp = *this;
01061         ++_M_current;
01062         return __tmp;
01063       }
01064 
01065       _GLIBCXX17_CONSTEXPR move_iterator&
01066       operator--()
01067       {
01068         --_M_current;
01069         return *this;
01070       }
01071 
01072       _GLIBCXX17_CONSTEXPR move_iterator
01073       operator--(int)
01074       {
01075         move_iterator __tmp = *this;
01076         --_M_current;
01077         return __tmp;
01078       }
01079 
01080       _GLIBCXX17_CONSTEXPR move_iterator
01081       operator+(difference_type __n) const
01082       { return move_iterator(_M_current + __n); }
01083 
01084       _GLIBCXX17_CONSTEXPR move_iterator&
01085       operator+=(difference_type __n)
01086       {
01087         _M_current += __n;
01088         return *this;
01089       }
01090 
01091       _GLIBCXX17_CONSTEXPR move_iterator
01092       operator-(difference_type __n) const
01093       { return move_iterator(_M_current - __n); }
01094     
01095       _GLIBCXX17_CONSTEXPR move_iterator&
01096       operator-=(difference_type __n)
01097       { 
01098         _M_current -= __n;
01099         return *this;
01100       }
01101 
01102       _GLIBCXX17_CONSTEXPR reference
01103       operator[](difference_type __n) const
01104       { return std::move(_M_current[__n]); }
01105     };
01106 
01107   // Note: See __normal_iterator operators note from Gaby to understand
01108   // why there are always 2 versions for most of the move_iterator
01109   // operators.
01110   template<typename _IteratorL, typename _IteratorR>
01111     inline _GLIBCXX17_CONSTEXPR bool
01112     operator==(const move_iterator<_IteratorL>& __x,
01113                const move_iterator<_IteratorR>& __y)
01114     { return __x.base() == __y.base(); }
01115 
01116   template<typename _Iterator>
01117     inline _GLIBCXX17_CONSTEXPR bool
01118     operator==(const move_iterator<_Iterator>& __x,
01119                const move_iterator<_Iterator>& __y)
01120     { return __x.base() == __y.base(); }
01121 
01122   template<typename _IteratorL, typename _IteratorR>
01123     inline _GLIBCXX17_CONSTEXPR bool
01124     operator!=(const move_iterator<_IteratorL>& __x,
01125                const move_iterator<_IteratorR>& __y)
01126     { return !(__x == __y); }
01127 
01128   template<typename _Iterator>
01129     inline _GLIBCXX17_CONSTEXPR bool
01130     operator!=(const move_iterator<_Iterator>& __x,
01131                const move_iterator<_Iterator>& __y)
01132     { return !(__x == __y); }
01133 
01134   template<typename _IteratorL, typename _IteratorR>
01135     inline _GLIBCXX17_CONSTEXPR bool
01136     operator<(const move_iterator<_IteratorL>& __x,
01137               const move_iterator<_IteratorR>& __y)
01138     { return __x.base() < __y.base(); }
01139 
01140   template<typename _Iterator>
01141     inline _GLIBCXX17_CONSTEXPR bool
01142     operator<(const move_iterator<_Iterator>& __x,
01143               const move_iterator<_Iterator>& __y)
01144     { return __x.base() < __y.base(); }
01145 
01146   template<typename _IteratorL, typename _IteratorR>
01147     inline _GLIBCXX17_CONSTEXPR bool
01148     operator<=(const move_iterator<_IteratorL>& __x,
01149                const move_iterator<_IteratorR>& __y)
01150     { return !(__y < __x); }
01151 
01152   template<typename _Iterator>
01153     inline _GLIBCXX17_CONSTEXPR bool
01154     operator<=(const move_iterator<_Iterator>& __x,
01155                const move_iterator<_Iterator>& __y)
01156     { return !(__y < __x); }
01157 
01158   template<typename _IteratorL, typename _IteratorR>
01159     inline _GLIBCXX17_CONSTEXPR bool
01160     operator>(const move_iterator<_IteratorL>& __x,
01161               const move_iterator<_IteratorR>& __y)
01162     { return __y < __x; }
01163 
01164   template<typename _Iterator>
01165     inline _GLIBCXX17_CONSTEXPR bool
01166     operator>(const move_iterator<_Iterator>& __x,
01167               const move_iterator<_Iterator>& __y)
01168     { return __y < __x; }
01169 
01170   template<typename _IteratorL, typename _IteratorR>
01171     inline _GLIBCXX17_CONSTEXPR bool
01172     operator>=(const move_iterator<_IteratorL>& __x,
01173                const move_iterator<_IteratorR>& __y)
01174     { return !(__x < __y); }
01175 
01176   template<typename _Iterator>
01177     inline _GLIBCXX17_CONSTEXPR bool
01178     operator>=(const move_iterator<_Iterator>& __x,
01179                const move_iterator<_Iterator>& __y)
01180     { return !(__x < __y); }
01181 
01182   // DR 685.
01183   template<typename _IteratorL, typename _IteratorR>
01184     inline _GLIBCXX17_CONSTEXPR auto
01185     operator-(const move_iterator<_IteratorL>& __x,
01186               const move_iterator<_IteratorR>& __y)
01187     -> decltype(__x.base() - __y.base())
01188     { return __x.base() - __y.base(); }
01189 
01190   template<typename _Iterator>
01191     inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
01192     operator+(typename move_iterator<_Iterator>::difference_type __n,
01193               const move_iterator<_Iterator>& __x)
01194     { return __x + __n; }
01195 
01196   template<typename _Iterator>
01197     inline _GLIBCXX17_CONSTEXPR move_iterator<_Iterator>
01198     make_move_iterator(_Iterator __i)
01199     { return move_iterator<_Iterator>(__i); }
01200 
01201   template<typename _Iterator, typename _ReturnType
01202     = typename conditional<__move_if_noexcept_cond
01203       <typename iterator_traits<_Iterator>::value_type>::value,
01204                 _Iterator, move_iterator<_Iterator>>::type>
01205     inline _GLIBCXX17_CONSTEXPR _ReturnType
01206     __make_move_if_noexcept_iterator(_Iterator __i)
01207     { return _ReturnType(__i); }
01208 
01209   // Overload for pointers that matches std::move_if_noexcept more closely,
01210   // returning a constant iterator when we don't want to move.
01211   template<typename _Tp, typename _ReturnType
01212     = typename conditional<__move_if_noexcept_cond<_Tp>::value,
01213                            const _Tp*, move_iterator<_Tp*>>::type>
01214     inline _GLIBCXX17_CONSTEXPR _ReturnType
01215     __make_move_if_noexcept_iterator(_Tp* __i)
01216     { return _ReturnType(__i); }
01217 
01218   // @} group iterators
01219 
01220   template<typename _Iterator>
01221     auto
01222     __niter_base(move_iterator<_Iterator> __it)
01223     -> decltype(make_move_iterator(__niter_base(__it.base())))
01224     { return make_move_iterator(__niter_base(__it.base())); }
01225 
01226   template<typename _Iterator>
01227     struct __is_move_iterator<move_iterator<_Iterator> >
01228     {
01229       enum { __value = 1 };
01230       typedef __true_type __type;
01231     };
01232 
01233   template<typename _Iterator>
01234     auto
01235     __miter_base(move_iterator<_Iterator> __it)
01236     -> decltype(__miter_base(__it.base()))
01237     { return __miter_base(__it.base()); }
01238 
01239 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
01240 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
01241   std::__make_move_if_noexcept_iterator(_Iter)
01242 #else
01243 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
01244 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
01245 #endif // C++11
01246 
01247 #if __cpp_deduction_guides >= 201606
01248   // These helper traits are used for deduction guides
01249   // of associative containers.
01250   template<typename _InputIterator>
01251     using __iter_key_t = remove_const_t<
01252     typename iterator_traits<_InputIterator>::value_type::first_type>;
01253 
01254   template<typename _InputIterator>
01255     using __iter_val_t =
01256     typename iterator_traits<_InputIterator>::value_type::second_type;
01257 
01258   template<typename _T1, typename _T2>
01259     struct pair;
01260 
01261   template<typename _InputIterator>
01262     using __iter_to_alloc_t =
01263     pair<add_const_t<__iter_key_t<_InputIterator>>,
01264          __iter_val_t<_InputIterator>>;
01265 
01266 #endif
01267 
01268 _GLIBCXX_END_NAMESPACE_VERSION
01269 } // namespace
01270 
01271 #ifdef _GLIBCXX_DEBUG
01272 # include <debug/stl_iterator.h>
01273 #endif
01274 
01275 #endif