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