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 #if __cplusplus < 201103L
00328     inline typename reverse_iterator<_Iterator>::difference_type
00329     operator-(const reverse_iterator<_Iterator>& __x,
00330               const reverse_iterator<_Iterator>& __y)
00331 #else
00332     inline auto
00333     operator-(const reverse_iterator<_Iterator>& __x,
00334               const reverse_iterator<_Iterator>& __y)
00335     -> decltype(__x.base() - __y.base())
00336 #endif
00337     { return __y.base() - __x.base(); }
00338 
00339   template<typename _Iterator>
00340     inline reverse_iterator<_Iterator>
00341     operator+(typename reverse_iterator<_Iterator>::difference_type __n,
00342               const reverse_iterator<_Iterator>& __x)
00343     { return reverse_iterator<_Iterator>(__x.base() - __n); }
00344 
00345   // _GLIBCXX_RESOLVE_LIB_DEFECTS
00346   // DR 280. Comparison of reverse_iterator to const reverse_iterator.
00347   template<typename _IteratorL, typename _IteratorR>
00348     inline bool
00349     operator==(const reverse_iterator<_IteratorL>& __x,
00350                const reverse_iterator<_IteratorR>& __y)
00351     { return __x.base() == __y.base(); }
00352 
00353   template<typename _IteratorL, typename _IteratorR>
00354     inline bool
00355     operator<(const reverse_iterator<_IteratorL>& __x,
00356               const reverse_iterator<_IteratorR>& __y)
00357     { return __y.base() < __x.base(); }
00358 
00359   template<typename _IteratorL, typename _IteratorR>
00360     inline bool
00361     operator!=(const reverse_iterator<_IteratorL>& __x,
00362                const reverse_iterator<_IteratorR>& __y)
00363     { return !(__x == __y); }
00364 
00365   template<typename _IteratorL, typename _IteratorR>
00366     inline bool
00367     operator>(const reverse_iterator<_IteratorL>& __x,
00368               const reverse_iterator<_IteratorR>& __y)
00369     { return __y < __x; }
00370 
00371   template<typename _IteratorL, typename _IteratorR>
00372     inline bool
00373     operator<=(const reverse_iterator<_IteratorL>& __x,
00374                const reverse_iterator<_IteratorR>& __y)
00375     { return !(__y < __x); }
00376 
00377   template<typename _IteratorL, typename _IteratorR>
00378     inline bool
00379     operator>=(const reverse_iterator<_IteratorL>& __x,
00380                const reverse_iterator<_IteratorR>& __y)
00381     { return !(__x < __y); }
00382 
00383   template<typename _IteratorL, typename _IteratorR>
00384 #if __cplusplus >= 201103L
00385     // DR 685.
00386     inline auto
00387     operator-(const reverse_iterator<_IteratorL>& __x,
00388               const reverse_iterator<_IteratorR>& __y)
00389     -> decltype(__y.base() - __x.base())
00390 #else
00391     inline typename reverse_iterator<_IteratorL>::difference_type
00392     operator-(const reverse_iterator<_IteratorL>& __x,
00393               const reverse_iterator<_IteratorR>& __y)
00394 #endif
00395     { return __y.base() - __x.base(); }
00396   //@}
00397 
00398 #if __cplusplus >= 201103L
00399   // Same as C++14 make_reverse_iterator but used in C++03 mode too.
00400   template<typename _Iterator>
00401     inline reverse_iterator<_Iterator>
00402     __make_reverse_iterator(_Iterator __i)
00403     { return reverse_iterator<_Iterator>(__i); }
00404 
00405 # if __cplusplus > 201103L
00406 #  define __cpp_lib_make_reverse_iterator 201402
00407 
00408   // _GLIBCXX_RESOLVE_LIB_DEFECTS
00409   // DR 2285. make_reverse_iterator
00410   /// Generator function for reverse_iterator.
00411   template<typename _Iterator>
00412     inline reverse_iterator<_Iterator>
00413     make_reverse_iterator(_Iterator __i)
00414     { return reverse_iterator<_Iterator>(__i); }
00415 # endif
00416 #endif
00417 
00418 #if __cplusplus >= 201103L
00419   template<typename _Iterator>
00420     auto
00421     __niter_base(reverse_iterator<_Iterator> __it)
00422     -> decltype(__make_reverse_iterator(__niter_base(__it.base())))
00423     { return __make_reverse_iterator(__niter_base(__it.base())); }
00424 
00425   template<typename _Iterator>
00426     struct __is_move_iterator<reverse_iterator<_Iterator> >
00427       : __is_move_iterator<_Iterator>
00428     { };
00429 
00430   template<typename _Iterator>
00431     auto
00432     __miter_base(reverse_iterator<_Iterator> __it)
00433     -> decltype(__make_reverse_iterator(__miter_base(__it.base())))
00434     { return __make_reverse_iterator(__miter_base(__it.base())); }
00435 #endif
00436 
00437   // 24.4.2.2.1 back_insert_iterator
00438   /**
00439    *  @brief  Turns assignment into insertion.
00440    *
00441    *  These are output iterators, constructed from a container-of-T.
00442    *  Assigning a T to the iterator appends it to the container using
00443    *  push_back.
00444    *
00445    *  Tip:  Using the back_inserter function to create these iterators can
00446    *  save typing.
00447   */
00448   template<typename _Container>
00449     class back_insert_iterator
00450     : public iterator<output_iterator_tag, void, void, void, void>
00451     {
00452     protected:
00453       _Container* container;
00454 
00455     public:
00456       /// A nested typedef for the type of whatever container you used.
00457       typedef _Container          container_type;
00458 
00459       /// The only way to create this %iterator is with a container.
00460       explicit
00461       back_insert_iterator(_Container& __x)
00462       : container(std::__addressof(__x)) { }
00463 
00464       /**
00465        *  @param  __value  An instance of whatever type
00466        *                 container_type::const_reference is; presumably a
00467        *                 reference-to-const T for container<T>.
00468        *  @return  This %iterator, for chained operations.
00469        *
00470        *  This kind of %iterator doesn't really have a @a position in the
00471        *  container (you can think of the position as being permanently at
00472        *  the end, if you like).  Assigning a value to the %iterator will
00473        *  always append the value to the end of the container.
00474       */
00475 #if __cplusplus < 201103L
00476       back_insert_iterator&
00477       operator=(typename _Container::const_reference __value)
00478       {
00479         container->push_back(__value);
00480         return *this;
00481       }
00482 #else
00483       back_insert_iterator&
00484       operator=(const typename _Container::value_type& __value)
00485       {
00486         container->push_back(__value);
00487         return *this;
00488       }
00489 
00490       back_insert_iterator&
00491       operator=(typename _Container::value_type&& __value)
00492       {
00493         container->push_back(std::move(__value));
00494         return *this;
00495       }
00496 #endif
00497 
00498       /// Simply returns *this.
00499       back_insert_iterator&
00500       operator*()
00501       { return *this; }
00502 
00503       /// Simply returns *this.  (This %iterator does not @a move.)
00504       back_insert_iterator&
00505       operator++()
00506       { return *this; }
00507 
00508       /// Simply returns *this.  (This %iterator does not @a move.)
00509       back_insert_iterator
00510       operator++(int)
00511       { return *this; }
00512     };
00513 
00514   /**
00515    *  @param  __x  A container of arbitrary type.
00516    *  @return  An instance of back_insert_iterator working on @p __x.
00517    *
00518    *  This wrapper function helps in creating back_insert_iterator instances.
00519    *  Typing the name of the %iterator requires knowing the precise full
00520    *  type of the container, which can be tedious and impedes generic
00521    *  programming.  Using this function lets you take advantage of automatic
00522    *  template parameter deduction, making the compiler match the correct
00523    *  types for you.
00524   */
00525   template<typename _Container>
00526     inline back_insert_iterator<_Container>
00527     back_inserter(_Container& __x)
00528     { return back_insert_iterator<_Container>(__x); }
00529 
00530   /**
00531    *  @brief  Turns assignment into insertion.
00532    *
00533    *  These are output iterators, constructed from a container-of-T.
00534    *  Assigning a T to the iterator prepends it to the container using
00535    *  push_front.
00536    *
00537    *  Tip:  Using the front_inserter function to create these iterators can
00538    *  save typing.
00539   */
00540   template<typename _Container>
00541     class front_insert_iterator
00542     : public iterator<output_iterator_tag, void, void, void, void>
00543     {
00544     protected:
00545       _Container* container;
00546 
00547     public:
00548       /// A nested typedef for the type of whatever container you used.
00549       typedef _Container          container_type;
00550 
00551       /// The only way to create this %iterator is with a container.
00552       explicit front_insert_iterator(_Container& __x)
00553       : container(std::__addressof(__x)) { }
00554 
00555       /**
00556        *  @param  __value  An instance of whatever type
00557        *                 container_type::const_reference is; presumably a
00558        *                 reference-to-const T for container<T>.
00559        *  @return  This %iterator, for chained operations.
00560        *
00561        *  This kind of %iterator doesn't really have a @a position in the
00562        *  container (you can think of the position as being permanently at
00563        *  the front, if you like).  Assigning a value to the %iterator will
00564        *  always prepend the value to the front of the container.
00565       */
00566 #if __cplusplus < 201103L
00567       front_insert_iterator&
00568       operator=(typename _Container::const_reference __value)
00569       {
00570         container->push_front(__value);
00571         return *this;
00572       }
00573 #else
00574       front_insert_iterator&
00575       operator=(const typename _Container::value_type& __value)
00576       {
00577         container->push_front(__value);
00578         return *this;
00579       }
00580 
00581       front_insert_iterator&
00582       operator=(typename _Container::value_type&& __value)
00583       {
00584         container->push_front(std::move(__value));
00585         return *this;
00586       }
00587 #endif
00588 
00589       /// Simply returns *this.
00590       front_insert_iterator&
00591       operator*()
00592       { return *this; }
00593 
00594       /// Simply returns *this.  (This %iterator does not @a move.)
00595       front_insert_iterator&
00596       operator++()
00597       { return *this; }
00598 
00599       /// Simply returns *this.  (This %iterator does not @a move.)
00600       front_insert_iterator
00601       operator++(int)
00602       { return *this; }
00603     };
00604 
00605   /**
00606    *  @param  __x  A container of arbitrary type.
00607    *  @return  An instance of front_insert_iterator working on @p x.
00608    *
00609    *  This wrapper function helps in creating front_insert_iterator instances.
00610    *  Typing the name of the %iterator requires knowing the precise full
00611    *  type of the container, which can be tedious and impedes generic
00612    *  programming.  Using this function lets you take advantage of automatic
00613    *  template parameter deduction, making the compiler match the correct
00614    *  types for you.
00615   */
00616   template<typename _Container>
00617     inline front_insert_iterator<_Container>
00618     front_inserter(_Container& __x)
00619     { return front_insert_iterator<_Container>(__x); }
00620 
00621   /**
00622    *  @brief  Turns assignment into insertion.
00623    *
00624    *  These are output iterators, constructed from a container-of-T.
00625    *  Assigning a T to the iterator inserts it in the container at the
00626    *  %iterator's position, rather than overwriting the value at that
00627    *  position.
00628    *
00629    *  (Sequences will actually insert a @e copy of the value before the
00630    *  %iterator's position.)
00631    *
00632    *  Tip:  Using the inserter function to create these iterators can
00633    *  save typing.
00634   */
00635   template<typename _Container>
00636     class insert_iterator
00637     : public iterator<output_iterator_tag, void, void, void, void>
00638     {
00639     protected:
00640       _Container* container;
00641       typename _Container::iterator iter;
00642 
00643     public:
00644       /// A nested typedef for the type of whatever container you used.
00645       typedef _Container          container_type;
00646 
00647       /**
00648        *  The only way to create this %iterator is with a container and an
00649        *  initial position (a normal %iterator into the container).
00650       */
00651       insert_iterator(_Container& __x, typename _Container::iterator __i)
00652       : container(std::__addressof(__x)), iter(__i) {}
00653 
00654       /**
00655        *  @param  __value  An instance of whatever type
00656        *                 container_type::const_reference is; presumably a
00657        *                 reference-to-const T for container<T>.
00658        *  @return  This %iterator, for chained operations.
00659        *
00660        *  This kind of %iterator maintains its own position in the
00661        *  container.  Assigning a value to the %iterator will insert the
00662        *  value into the container at the place before the %iterator.
00663        *
00664        *  The position is maintained such that subsequent assignments will
00665        *  insert values immediately after one another.  For example,
00666        *  @code
00667        *     // vector v contains A and Z
00668        *
00669        *     insert_iterator i (v, ++v.begin());
00670        *     i = 1;
00671        *     i = 2;
00672        *     i = 3;
00673        *
00674        *     // vector v contains A, 1, 2, 3, and Z
00675        *  @endcode
00676       */
00677 #if __cplusplus < 201103L
00678       insert_iterator&
00679       operator=(typename _Container::const_reference __value)
00680       {
00681         iter = container->insert(iter, __value);
00682         ++iter;
00683         return *this;
00684       }
00685 #else
00686       insert_iterator&
00687       operator=(const typename _Container::value_type& __value)
00688       {
00689         iter = container->insert(iter, __value);
00690         ++iter;
00691         return *this;
00692       }
00693 
00694       insert_iterator&
00695       operator=(typename _Container::value_type&& __value)
00696       {
00697         iter = container->insert(iter, std::move(__value));
00698         ++iter;
00699         return *this;
00700       }
00701 #endif
00702 
00703       /// Simply returns *this.
00704       insert_iterator&
00705       operator*()
00706       { return *this; }
00707 
00708       /// Simply returns *this.  (This %iterator does not @a move.)
00709       insert_iterator&
00710       operator++()
00711       { return *this; }
00712 
00713       /// Simply returns *this.  (This %iterator does not @a move.)
00714       insert_iterator&
00715       operator++(int)
00716       { return *this; }
00717     };
00718 
00719   /**
00720    *  @param __x  A container of arbitrary type.
00721    *  @return  An instance of insert_iterator working on @p __x.
00722    *
00723    *  This wrapper function helps in creating insert_iterator instances.
00724    *  Typing the name of the %iterator requires knowing the precise full
00725    *  type of the container, which can be tedious and impedes generic
00726    *  programming.  Using this function lets you take advantage of automatic
00727    *  template parameter deduction, making the compiler match the correct
00728    *  types for you.
00729   */
00730   template<typename _Container, typename _Iterator>
00731     inline insert_iterator<_Container>
00732     inserter(_Container& __x, _Iterator __i)
00733     {
00734       return insert_iterator<_Container>(__x,
00735                                          typename _Container::iterator(__i));
00736     }
00737 
00738   // @} group iterators
00739 
00740 _GLIBCXX_END_NAMESPACE_VERSION
00741 } // namespace
00742 
00743 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
00744 {
00745 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00746 
00747   // This iterator adapter is @a normal in the sense that it does not
00748   // change the semantics of any of the operators of its iterator
00749   // parameter.  Its primary purpose is to convert an iterator that is
00750   // not a class, e.g. a pointer, into an iterator that is a class.
00751   // The _Container parameter exists solely so that different containers
00752   // using this template can instantiate different types, even if the
00753   // _Iterator parameter is the same.
00754   using std::iterator_traits;
00755   using std::iterator;
00756   template<typename _Iterator, typename _Container>
00757     class __normal_iterator
00758     {
00759     protected:
00760       _Iterator _M_current;
00761 
00762       typedef iterator_traits<_Iterator>                __traits_type;
00763 
00764     public:
00765       typedef _Iterator                                 iterator_type;
00766       typedef typename __traits_type::iterator_category iterator_category;
00767       typedef typename __traits_type::value_type        value_type;
00768       typedef typename __traits_type::difference_type   difference_type;
00769       typedef typename __traits_type::reference         reference;
00770       typedef typename __traits_type::pointer           pointer;
00771 
00772       _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT
00773       : _M_current(_Iterator()) { }
00774 
00775       explicit
00776       __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT
00777       : _M_current(__i) { }
00778 
00779       // Allow iterator to const_iterator conversion
00780       template<typename _Iter>
00781         __normal_iterator(const __normal_iterator<_Iter,
00782                           typename __enable_if<
00783                (std::__are_same<_Iter, typename _Container::pointer>::__value),
00784                       _Container>::__type>& __i) _GLIBCXX_NOEXCEPT
00785         : _M_current(__i.base()) { }
00786 
00787       // Forward iterator requirements
00788       reference
00789       operator*() const _GLIBCXX_NOEXCEPT
00790       { return *_M_current; }
00791 
00792       pointer
00793       operator->() const _GLIBCXX_NOEXCEPT
00794       { return _M_current; }
00795 
00796       __normal_iterator&
00797       operator++() _GLIBCXX_NOEXCEPT
00798       {
00799         ++_M_current;
00800         return *this;
00801       }
00802 
00803       __normal_iterator
00804       operator++(int) _GLIBCXX_NOEXCEPT
00805       { return __normal_iterator(_M_current++); }
00806 
00807       // Bidirectional iterator requirements
00808       __normal_iterator&
00809       operator--() _GLIBCXX_NOEXCEPT
00810       {
00811         --_M_current;
00812         return *this;
00813       }
00814 
00815       __normal_iterator
00816       operator--(int) _GLIBCXX_NOEXCEPT
00817       { return __normal_iterator(_M_current--); }
00818 
00819       // Random access iterator requirements
00820       reference
00821       operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
00822       { return _M_current[__n]; }
00823 
00824       __normal_iterator&
00825       operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
00826       { _M_current += __n; return *this; }
00827 
00828       __normal_iterator
00829       operator+(difference_type __n) const _GLIBCXX_NOEXCEPT
00830       { return __normal_iterator(_M_current + __n); }
00831 
00832       __normal_iterator&
00833       operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
00834       { _M_current -= __n; return *this; }
00835 
00836       __normal_iterator
00837       operator-(difference_type __n) const _GLIBCXX_NOEXCEPT
00838       { return __normal_iterator(_M_current - __n); }
00839 
00840       const _Iterator&
00841       base() const _GLIBCXX_NOEXCEPT
00842       { return _M_current; }
00843     };
00844 
00845   // Note: In what follows, the left- and right-hand-side iterators are
00846   // allowed to vary in types (conceptually in cv-qualification) so that
00847   // comparison between cv-qualified and non-cv-qualified iterators be
00848   // valid.  However, the greedy and unfriendly operators in std::rel_ops
00849   // will make overload resolution ambiguous (when in scope) if we don't
00850   // provide overloads whose operands are of the same type.  Can someone
00851   // remind me what generic programming is about? -- Gaby
00852 
00853   // Forward iterator requirements
00854   template<typename _IteratorL, typename _IteratorR, typename _Container>
00855     inline bool
00856     operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
00857                const __normal_iterator<_IteratorR, _Container>& __rhs)
00858     _GLIBCXX_NOEXCEPT
00859     { return __lhs.base() == __rhs.base(); }
00860 
00861   template<typename _Iterator, typename _Container>
00862     inline bool
00863     operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
00864                const __normal_iterator<_Iterator, _Container>& __rhs)
00865     _GLIBCXX_NOEXCEPT
00866     { return __lhs.base() == __rhs.base(); }
00867 
00868   template<typename _IteratorL, typename _IteratorR, typename _Container>
00869     inline bool
00870     operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00871                const __normal_iterator<_IteratorR, _Container>& __rhs)
00872     _GLIBCXX_NOEXCEPT
00873     { return __lhs.base() != __rhs.base(); }
00874 
00875   template<typename _Iterator, typename _Container>
00876     inline bool
00877     operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
00878                const __normal_iterator<_Iterator, _Container>& __rhs)
00879     _GLIBCXX_NOEXCEPT
00880     { return __lhs.base() != __rhs.base(); }
00881 
00882   // Random access iterator requirements
00883   template<typename _IteratorL, typename _IteratorR, typename _Container>
00884     inline bool
00885     operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
00886               const __normal_iterator<_IteratorR, _Container>& __rhs)
00887     _GLIBCXX_NOEXCEPT
00888     { return __lhs.base() < __rhs.base(); }
00889 
00890   template<typename _Iterator, typename _Container>
00891     inline bool
00892     operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
00893               const __normal_iterator<_Iterator, _Container>& __rhs)
00894     _GLIBCXX_NOEXCEPT
00895     { return __lhs.base() < __rhs.base(); }
00896 
00897   template<typename _IteratorL, typename _IteratorR, typename _Container>
00898     inline bool
00899     operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
00900               const __normal_iterator<_IteratorR, _Container>& __rhs)
00901     _GLIBCXX_NOEXCEPT
00902     { return __lhs.base() > __rhs.base(); }
00903 
00904   template<typename _Iterator, typename _Container>
00905     inline bool
00906     operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
00907               const __normal_iterator<_Iterator, _Container>& __rhs)
00908     _GLIBCXX_NOEXCEPT
00909     { return __lhs.base() > __rhs.base(); }
00910 
00911   template<typename _IteratorL, typename _IteratorR, typename _Container>
00912     inline bool
00913     operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00914                const __normal_iterator<_IteratorR, _Container>& __rhs)
00915     _GLIBCXX_NOEXCEPT
00916     { return __lhs.base() <= __rhs.base(); }
00917 
00918   template<typename _Iterator, typename _Container>
00919     inline bool
00920     operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
00921                const __normal_iterator<_Iterator, _Container>& __rhs)
00922     _GLIBCXX_NOEXCEPT
00923     { return __lhs.base() <= __rhs.base(); }
00924 
00925   template<typename _IteratorL, typename _IteratorR, typename _Container>
00926     inline bool
00927     operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00928                const __normal_iterator<_IteratorR, _Container>& __rhs)
00929     _GLIBCXX_NOEXCEPT
00930     { return __lhs.base() >= __rhs.base(); }
00931 
00932   template<typename _Iterator, typename _Container>
00933     inline bool
00934     operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
00935                const __normal_iterator<_Iterator, _Container>& __rhs)
00936     _GLIBCXX_NOEXCEPT
00937     { return __lhs.base() >= __rhs.base(); }
00938 
00939   // _GLIBCXX_RESOLVE_LIB_DEFECTS
00940   // According to the resolution of DR179 not only the various comparison
00941   // operators but also operator- must accept mixed iterator/const_iterator
00942   // parameters.
00943   template<typename _IteratorL, typename _IteratorR, typename _Container>
00944 #if __cplusplus >= 201103L
00945     // DR 685.
00946     inline auto
00947     operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
00948               const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept
00949     -> decltype(__lhs.base() - __rhs.base())
00950 #else
00951     inline typename __normal_iterator<_IteratorL, _Container>::difference_type
00952     operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
00953               const __normal_iterator<_IteratorR, _Container>& __rhs)
00954 #endif
00955     { return __lhs.base() - __rhs.base(); }
00956 
00957   template<typename _Iterator, typename _Container>
00958     inline typename __normal_iterator<_Iterator, _Container>::difference_type
00959     operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
00960               const __normal_iterator<_Iterator, _Container>& __rhs)
00961     _GLIBCXX_NOEXCEPT
00962     { return __lhs.base() - __rhs.base(); }
00963 
00964   template<typename _Iterator, typename _Container>
00965     inline __normal_iterator<_Iterator, _Container>
00966     operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
00967               __n, const __normal_iterator<_Iterator, _Container>& __i)
00968     _GLIBCXX_NOEXCEPT
00969     { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
00970 
00971 _GLIBCXX_END_NAMESPACE_VERSION
00972 } // namespace
00973 
00974 namespace std _GLIBCXX_VISIBILITY(default)
00975 {
00976 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00977 
00978   template<typename _Iterator, typename _Container>
00979     _Iterator
00980     __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
00981     { return __it.base(); }
00982 
00983 _GLIBCXX_END_NAMESPACE_VERSION
00984 } // namespace
00985 
00986 #if __cplusplus >= 201103L
00987 
00988 namespace std _GLIBCXX_VISIBILITY(default)
00989 {
00990 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00991 
00992   /**
00993    * @addtogroup iterators
00994    * @{
00995    */
00996 
00997   // 24.4.3  Move iterators
00998   /**
00999    *  Class template move_iterator is an iterator adapter with the same
01000    *  behavior as the underlying iterator except that its dereference
01001    *  operator implicitly converts the value returned by the underlying
01002    *  iterator's dereference operator to an rvalue reference.  Some
01003    *  generic algorithms can be called with move iterators to replace
01004    *  copying with moving.
01005    */
01006   template<typename _Iterator>
01007     class move_iterator
01008     {
01009     protected:
01010       _Iterator _M_current;
01011 
01012       typedef iterator_traits<_Iterator>                __traits_type;
01013       typedef typename __traits_type::reference         __base_ref;
01014 
01015     public:
01016       typedef _Iterator                                 iterator_type;
01017       typedef typename __traits_type::iterator_category iterator_category;
01018       typedef typename __traits_type::value_type        value_type;
01019       typedef typename __traits_type::difference_type   difference_type;
01020       // NB: DR 680.
01021       typedef _Iterator                                 pointer;
01022       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01023       // 2106. move_iterator wrapping iterators returning prvalues
01024       typedef typename conditional<is_reference<__base_ref>::value,
01025                          typename remove_reference<__base_ref>::type&&,
01026                          __base_ref>::type              reference;
01027 
01028       move_iterator()
01029       : _M_current() { }
01030 
01031       explicit
01032       move_iterator(iterator_type __i)
01033       : _M_current(__i) { }
01034 
01035       template<typename _Iter>
01036         move_iterator(const move_iterator<_Iter>& __i)
01037         : _M_current(__i.base()) { }
01038 
01039       iterator_type
01040       base() const
01041       { return _M_current; }
01042 
01043       reference
01044       operator*() const
01045       { return static_cast<reference>(*_M_current); }
01046 
01047       pointer
01048       operator->() const
01049       { return _M_current; }
01050 
01051       move_iterator&
01052       operator++()
01053       {
01054         ++_M_current;
01055         return *this;
01056       }
01057 
01058       move_iterator
01059       operator++(int)
01060       {
01061         move_iterator __tmp = *this;
01062         ++_M_current;
01063         return __tmp;
01064       }
01065 
01066       move_iterator&
01067       operator--()
01068       {
01069         --_M_current;
01070         return *this;
01071       }
01072 
01073       move_iterator
01074       operator--(int)
01075       {
01076         move_iterator __tmp = *this;
01077         --_M_current;
01078         return __tmp;
01079       }
01080 
01081       move_iterator
01082       operator+(difference_type __n) const
01083       { return move_iterator(_M_current + __n); }
01084 
01085       move_iterator&
01086       operator+=(difference_type __n)
01087       {
01088         _M_current += __n;
01089         return *this;
01090       }
01091 
01092       move_iterator
01093       operator-(difference_type __n) const
01094       { return move_iterator(_M_current - __n); }
01095     
01096       move_iterator&
01097       operator-=(difference_type __n)
01098       { 
01099         _M_current -= __n;
01100         return *this;
01101       }
01102 
01103       reference
01104       operator[](difference_type __n) const
01105       { return std::move(_M_current[__n]); }
01106     };
01107 
01108   // Note: See __normal_iterator operators note from Gaby to understand
01109   // why there are always 2 versions for most of the move_iterator
01110   // operators.
01111   template<typename _IteratorL, typename _IteratorR>
01112     inline bool
01113     operator==(const move_iterator<_IteratorL>& __x,
01114                const move_iterator<_IteratorR>& __y)
01115     { return __x.base() == __y.base(); }
01116 
01117   template<typename _Iterator>
01118     inline bool
01119     operator==(const move_iterator<_Iterator>& __x,
01120                const move_iterator<_Iterator>& __y)
01121     { return __x.base() == __y.base(); }
01122 
01123   template<typename _IteratorL, typename _IteratorR>
01124     inline bool
01125     operator!=(const move_iterator<_IteratorL>& __x,
01126                const move_iterator<_IteratorR>& __y)
01127     { return !(__x == __y); }
01128 
01129   template<typename _Iterator>
01130     inline bool
01131     operator!=(const move_iterator<_Iterator>& __x,
01132                const move_iterator<_Iterator>& __y)
01133     { return !(__x == __y); }
01134 
01135   template<typename _IteratorL, typename _IteratorR>
01136     inline bool
01137     operator<(const move_iterator<_IteratorL>& __x,
01138               const move_iterator<_IteratorR>& __y)
01139     { return __x.base() < __y.base(); }
01140 
01141   template<typename _Iterator>
01142     inline bool
01143     operator<(const move_iterator<_Iterator>& __x,
01144               const move_iterator<_Iterator>& __y)
01145     { return __x.base() < __y.base(); }
01146 
01147   template<typename _IteratorL, typename _IteratorR>
01148     inline bool
01149     operator<=(const move_iterator<_IteratorL>& __x,
01150                const move_iterator<_IteratorR>& __y)
01151     { return !(__y < __x); }
01152 
01153   template<typename _Iterator>
01154     inline bool
01155     operator<=(const move_iterator<_Iterator>& __x,
01156                const move_iterator<_Iterator>& __y)
01157     { return !(__y < __x); }
01158 
01159   template<typename _IteratorL, typename _IteratorR>
01160     inline bool
01161     operator>(const move_iterator<_IteratorL>& __x,
01162               const move_iterator<_IteratorR>& __y)
01163     { return __y < __x; }
01164 
01165   template<typename _Iterator>
01166     inline bool
01167     operator>(const move_iterator<_Iterator>& __x,
01168               const move_iterator<_Iterator>& __y)
01169     { return __y < __x; }
01170 
01171   template<typename _IteratorL, typename _IteratorR>
01172     inline bool
01173     operator>=(const move_iterator<_IteratorL>& __x,
01174                const move_iterator<_IteratorR>& __y)
01175     { return !(__x < __y); }
01176 
01177   template<typename _Iterator>
01178     inline bool
01179     operator>=(const move_iterator<_Iterator>& __x,
01180                const move_iterator<_Iterator>& __y)
01181     { return !(__x < __y); }
01182 
01183   // DR 685.
01184   template<typename _IteratorL, typename _IteratorR>
01185     inline auto
01186     operator-(const move_iterator<_IteratorL>& __x,
01187               const move_iterator<_IteratorR>& __y)
01188     -> decltype(__x.base() - __y.base())
01189     { return __x.base() - __y.base(); }
01190 
01191   template<typename _Iterator>
01192     inline auto
01193     operator-(const move_iterator<_Iterator>& __x,
01194               const move_iterator<_Iterator>& __y)
01195     -> decltype(__x.base() - __y.base())
01196     { return __x.base() - __y.base(); }
01197 
01198   template<typename _Iterator>
01199     inline move_iterator<_Iterator>
01200     operator+(typename move_iterator<_Iterator>::difference_type __n,
01201               const move_iterator<_Iterator>& __x)
01202     { return __x + __n; }
01203 
01204   template<typename _Iterator>
01205     inline move_iterator<_Iterator>
01206     make_move_iterator(_Iterator __i)
01207     { return move_iterator<_Iterator>(__i); }
01208 
01209   template<typename _Iterator, typename _ReturnType
01210     = typename conditional<__move_if_noexcept_cond
01211       <typename iterator_traits<_Iterator>::value_type>::value,
01212                 _Iterator, move_iterator<_Iterator>>::type>
01213     inline _ReturnType
01214     __make_move_if_noexcept_iterator(_Iterator __i)
01215     { return _ReturnType(__i); }
01216 
01217   // Overload for pointers that matches std::move_if_noexcept more closely,
01218   // returning a constant iterator when we don't want to move.
01219   template<typename _Tp, typename _ReturnType
01220     = typename conditional<__move_if_noexcept_cond<_Tp>::value,
01221                            const _Tp*, move_iterator<_Tp*>>::type>
01222     inline _ReturnType
01223     __make_move_if_noexcept_iterator(_Tp* __i)
01224     { return _ReturnType(__i); }
01225 
01226   // @} group iterators
01227 
01228   template<typename _Iterator>
01229     auto
01230     __niter_base(move_iterator<_Iterator> __it)
01231     -> decltype(make_move_iterator(__niter_base(__it.base())))
01232     { return make_move_iterator(__niter_base(__it.base())); }
01233 
01234   template<typename _Iterator>
01235     struct __is_move_iterator<move_iterator<_Iterator> >
01236     {
01237       enum { __value = 1 };
01238       typedef __true_type __type;
01239     };
01240 
01241   template<typename _Iterator>
01242     auto
01243     __miter_base(move_iterator<_Iterator> __it)
01244     -> decltype(__miter_base(__it.base()))
01245     { return __miter_base(__it.base()); }
01246 
01247 _GLIBCXX_END_NAMESPACE_VERSION
01248 } // namespace
01249 
01250 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
01251 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
01252   std::__make_move_if_noexcept_iterator(_Iter)
01253 #else
01254 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
01255 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
01256 #endif // C++11
01257 
01258 #ifdef _GLIBCXX_DEBUG
01259 # include <debug/stl_iterator.h>
01260 #endif
01261 
01262 #endif