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