LCOV - code coverage report
Current view: top level - usr/include/c++/4.9/bits - stl_iterator.h (source / functions) Hit Total Coverage
Test: coverage.info Lines: 30 68 44.1 %
Date: 2016-11-29 15:07:43 Functions: 92 377 24.4 %

          Line data    Source code
       1             : // Iterators -*- C++ -*-
       2             : 
       3             : // Copyright (C) 2001-2014 Free Software Foundation, Inc.
       4             : //
       5             : // This file is part of the GNU ISO C++ Library.  This library is free
       6             : // software; you can redistribute it and/or modify it under the
       7             : // terms of the GNU General Public License as published by the
       8             : // Free Software Foundation; either version 3, or (at your option)
       9             : // any later version.
      10             : 
      11             : // This library is distributed in the hope that it will be useful,
      12             : // but WITHOUT ANY WARRANTY; without even the implied warranty of
      13             : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      14             : // GNU General Public License for more details.
      15             : 
      16             : // Under Section 7 of GPL version 3, you are granted additional
      17             : // permissions described in the GCC Runtime Library Exception, version
      18             : // 3.1, as published by the Free Software Foundation.
      19             : 
      20             : // You should have received a copy of the GNU General Public License and
      21             : // a copy of the GCC Runtime Library Exception along with this program;
      22             : // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
      23             : // <http://www.gnu.org/licenses/>.
      24             : 
      25             : /*
      26             :  *
      27             :  * Copyright (c) 1994
      28             :  * Hewlett-Packard Company
      29             :  *
      30             :  * Permission to use, copy, modify, distribute and sell this software
      31             :  * and its documentation for any purpose is hereby granted without fee,
      32             :  * provided that the above copyright notice appear in all copies and
      33             :  * that both that copyright notice and this permission notice appear
      34             :  * in supporting documentation.  Hewlett-Packard Company makes no
      35             :  * representations about the suitability of this software for any
      36             :  * purpose.  It is provided "as is" without express or implied warranty.
      37             :  *
      38             :  *
      39             :  * Copyright (c) 1996-1998
      40             :  * Silicon Graphics Computer Systems, Inc.
      41             :  *
      42             :  * Permission to use, copy, modify, distribute and sell this software
      43             :  * and its documentation for any purpose is hereby granted without fee,
      44             :  * provided that the above copyright notice appear in all copies and
      45             :  * that both that copyright notice and this permission notice appear
      46             :  * in supporting documentation.  Silicon Graphics makes no
      47             :  * representations about the suitability of this software for any
      48             :  * purpose.  It is provided "as is" without express or implied warranty.
      49             :  */
      50             : 
      51             : /** @file bits/stl_iterator.h
      52             :  *  This is an internal header file, included by other library headers.
      53             :  *  Do not attempt to use it directly. @headername{iterator}
      54             :  *
      55             :  *  This file implements reverse_iterator, back_insert_iterator,
      56             :  *  front_insert_iterator, insert_iterator, __normal_iterator, and their
      57             :  *  supporting functions and overloaded operators.
      58             :  */
      59             : 
      60             : #ifndef _STL_ITERATOR_H
      61             : #define _STL_ITERATOR_H 1
      62             : 
      63             : #include <bits/cpp_type_traits.h>
      64             : #include <ext/type_traits.h>
      65             : #include <bits/move.h>
      66             : #include <bits/ptr_traits.h>
      67             : 
      68             : namespace std _GLIBCXX_VISIBILITY(default)
      69             : {
      70             : _GLIBCXX_BEGIN_NAMESPACE_VERSION
      71             : 
      72             :   /**
      73             :    * @addtogroup iterators
      74             :    * @{
      75             :    */
      76             : 
      77             :   // 24.4.1 Reverse iterators
      78             :   /**
      79             :    *  Bidirectional and random access iterators have corresponding reverse
      80             :    *  %iterator adaptors that iterate through the data structure in the
      81             :    *  opposite direction.  They have the same signatures as the corresponding
      82             :    *  iterators.  The fundamental relation between a reverse %iterator and its
      83             :    *  corresponding %iterator @c i is established by the identity:
      84             :    *  @code
      85             :    *      &*(reverse_iterator(i)) == &*(i - 1)
      86             :    *  @endcode
      87             :    *
      88             :    *  <em>This mapping is dictated by the fact that while there is always a
      89             :    *  pointer past the end of an array, there might not be a valid pointer
      90             :    *  before the beginning of an array.</em> [24.4.1]/1,2
      91             :    *
      92             :    *  Reverse iterators can be tricky and surprising at first.  Their
      93             :    *  semantics make sense, however, and the trickiness is a side effect of
      94             :    *  the requirement that the iterators must be safe.
      95             :   */
      96             :   template<typename _Iterator>
      97             :     class reverse_iterator
      98             :     : public iterator<typename iterator_traits<_Iterator>::iterator_category,
      99             :                       typename iterator_traits<_Iterator>::value_type,
     100             :                       typename iterator_traits<_Iterator>::difference_type,
     101             :                       typename iterator_traits<_Iterator>::pointer,
     102             :                       typename iterator_traits<_Iterator>::reference>
     103             :     {
     104             :     protected:
     105             :       _Iterator current;
     106             : 
     107             :       typedef iterator_traits<_Iterator>          __traits_type;
     108             : 
     109             :     public:
     110             :       typedef _Iterator                                 iterator_type;
     111             :       typedef typename __traits_type::difference_type   difference_type;
     112             :       typedef typename __traits_type::pointer           pointer;
     113             :       typedef typename __traits_type::reference         reference;
     114             : 
     115             :       /**
     116             :        *  The default constructor value-initializes member @p current.
     117             :        *  If it is a pointer, that means it is zero-initialized.
     118             :       */
     119             :       // _GLIBCXX_RESOLVE_LIB_DEFECTS
     120             :       // 235 No specification of default ctor for reverse_iterator
     121             :       reverse_iterator() : current() { }
     122             : 
     123             :       /**
     124             :        *  This %iterator will move in the opposite direction that @p x does.
     125             :       */
     126             :       explicit
     127             :       reverse_iterator(iterator_type __x) : current(__x) { }
     128             : 
     129             :       /**
     130             :        *  The copy constructor is normal.
     131             :       */
     132             :       reverse_iterator(const reverse_iterator& __x)
     133             :       : current(__x.current) { }
     134             : 
     135             :       /**
     136             :        *  A %reverse_iterator across other types can be copied if the
     137             :        *  underlying %iterator can be converted to the type of @c current.
     138             :       */
     139             :       template<typename _Iter>
     140             :         reverse_iterator(const reverse_iterator<_Iter>& __x)
     141             :         : current(__x.base()) { }
     142             : 
     143             :       /**
     144             :        *  @return  @c current, the %iterator used for underlying work.
     145             :       */
     146             :       iterator_type
     147             :       base() const
     148             :       { return current; }
     149             : 
     150             :       /**
     151             :        *  @return  A reference to the value at @c --current
     152             :        *
     153             :        *  This requires that @c --current is dereferenceable.
     154             :        *
     155             :        *  @warning This implementation requires that for an iterator of the
     156             :        *           underlying iterator type, @c x, a reference obtained by
     157             :        *           @c *x remains valid after @c x has been modified or
     158             :        *           destroyed. This is a bug: http://gcc.gnu.org/PR51823
     159             :       */
     160             :       reference
     161             :       operator*() const
     162             :       {
     163             :         _Iterator __tmp = current;
     164             :         return *--__tmp;
     165             :       }
     166             : 
     167             :       /**
     168             :        *  @return  A pointer to the value at @c --current
     169             :        *
     170             :        *  This requires that @c --current is dereferenceable.
     171             :       */
     172             :       pointer
     173             :       operator->() const
     174             :       { return &(operator*()); }
     175             : 
     176             :       /**
     177             :        *  @return  @c *this
     178             :        *
     179             :        *  Decrements the underlying iterator.
     180             :       */
     181             :       reverse_iterator&
     182             :       operator++()
     183             :       {
     184             :         --current;
     185             :         return *this;
     186             :       }
     187             : 
     188             :       /**
     189             :        *  @return  The original value of @c *this
     190             :        *
     191             :        *  Decrements the underlying iterator.
     192             :       */
     193             :       reverse_iterator
     194             :       operator++(int)
     195             :       {
     196             :         reverse_iterator __tmp = *this;
     197             :         --current;
     198             :         return __tmp;
     199             :       }
     200             : 
     201             :       /**
     202             :        *  @return  @c *this
     203             :        *
     204             :        *  Increments the underlying iterator.
     205             :       */
     206             :       reverse_iterator&
     207             :       operator--()
     208             :       {
     209             :         ++current;
     210             :         return *this;
     211             :       }
     212             : 
     213             :       /**
     214             :        *  @return  A reverse_iterator with the previous value of @c *this
     215             :        *
     216             :        *  Increments the underlying iterator.
     217             :       */
     218             :       reverse_iterator
     219             :       operator--(int)
     220             :       {
     221             :         reverse_iterator __tmp = *this;
     222             :         ++current;
     223             :         return __tmp;
     224             :       }
     225             : 
     226             :       /**
     227             :        *  @return  A reverse_iterator that refers to @c current - @a __n
     228             :        *
     229             :        *  The underlying iterator must be a Random Access Iterator.
     230             :       */
     231             :       reverse_iterator
     232             :       operator+(difference_type __n) const
     233             :       { return reverse_iterator(current - __n); }
     234             : 
     235             :       /**
     236             :        *  @return  *this
     237             :        *
     238             :        *  Moves the underlying iterator backwards @a __n steps.
     239             :        *  The underlying iterator must be a Random Access Iterator.
     240             :       */
     241             :       reverse_iterator&
     242             :       operator+=(difference_type __n)
     243             :       {
     244             :         current -= __n;
     245             :         return *this;
     246             :       }
     247             : 
     248             :       /**
     249             :        *  @return  A reverse_iterator that refers to @c current - @a __n
     250             :        *
     251             :        *  The underlying iterator must be a Random Access Iterator.
     252             :       */
     253             :       reverse_iterator
     254             :       operator-(difference_type __n) const
     255             :       { return reverse_iterator(current + __n); }
     256             : 
     257             :       /**
     258             :        *  @return  *this
     259             :        *
     260             :        *  Moves the underlying iterator forwards @a __n steps.
     261             :        *  The underlying iterator must be a Random Access Iterator.
     262             :       */
     263             :       reverse_iterator&
     264             :       operator-=(difference_type __n)
     265             :       {
     266             :         current += __n;
     267             :         return *this;
     268             :       }
     269             : 
     270             :       /**
     271             :        *  @return  The value at @c current - @a __n - 1
     272             :        *
     273             :        *  The underlying iterator must be a Random Access Iterator.
     274             :       */
     275             :       reference
     276             :       operator[](difference_type __n) const
     277             :       { return *(*this + __n); }
     278             :     };
     279             : 
     280             :   //@{
     281             :   /**
     282             :    *  @param  __x  A %reverse_iterator.
     283             :    *  @param  __y  A %reverse_iterator.
     284             :    *  @return  A simple bool.
     285             :    *
     286             :    *  Reverse iterators forward many operations to their underlying base()
     287             :    *  iterators.  Others are implemented in terms of one another.
     288             :    *
     289             :   */
     290             :   template<typename _Iterator>
     291             :     inline bool
     292             :     operator==(const reverse_iterator<_Iterator>& __x,
     293             :                const reverse_iterator<_Iterator>& __y)
     294             :     { return __x.base() == __y.base(); }
     295             : 
     296             :   template<typename _Iterator>
     297             :     inline bool
     298             :     operator<(const reverse_iterator<_Iterator>& __x,
     299             :               const reverse_iterator<_Iterator>& __y)
     300             :     { return __y.base() < __x.base(); }
     301             : 
     302             :   template<typename _Iterator>
     303             :     inline bool
     304             :     operator!=(const reverse_iterator<_Iterator>& __x,
     305             :                const reverse_iterator<_Iterator>& __y)
     306             :     { return !(__x == __y); }
     307             : 
     308             :   template<typename _Iterator>
     309             :     inline bool
     310             :     operator>(const reverse_iterator<_Iterator>& __x,
     311             :               const reverse_iterator<_Iterator>& __y)
     312             :     { return __y < __x; }
     313             : 
     314             :   template<typename _Iterator>
     315             :     inline bool
     316             :     operator<=(const reverse_iterator<_Iterator>& __x,
     317             :                const reverse_iterator<_Iterator>& __y)
     318             :     { return !(__y < __x); }
     319             : 
     320             :   template<typename _Iterator>
     321             :     inline bool
     322             :     operator>=(const reverse_iterator<_Iterator>& __x,
     323             :                const reverse_iterator<_Iterator>& __y)
     324             :     { return !(__x < __y); }
     325             : 
     326             :   template<typename _Iterator>
     327             :     inline typename reverse_iterator<_Iterator>::difference_type
     328             :     operator-(const reverse_iterator<_Iterator>& __x,
     329             :               const reverse_iterator<_Iterator>& __y)
     330             :     { return __y.base() - __x.base(); }
     331             : 
     332             :   template<typename _Iterator>
     333             :     inline reverse_iterator<_Iterator>
     334             :     operator+(typename reverse_iterator<_Iterator>::difference_type __n,
     335             :               const reverse_iterator<_Iterator>& __x)
     336             :     { return reverse_iterator<_Iterator>(__x.base() - __n); }
     337             : 
     338             :   // _GLIBCXX_RESOLVE_LIB_DEFECTS
     339             :   // DR 280. Comparison of reverse_iterator to const reverse_iterator.
     340             :   template<typename _IteratorL, typename _IteratorR>
     341             :     inline bool
     342             :     operator==(const reverse_iterator<_IteratorL>& __x,
     343             :                const reverse_iterator<_IteratorR>& __y)
     344             :     { return __x.base() == __y.base(); }
     345             : 
     346             :   template<typename _IteratorL, typename _IteratorR>
     347             :     inline bool
     348             :     operator<(const reverse_iterator<_IteratorL>& __x,
     349             :               const reverse_iterator<_IteratorR>& __y)
     350             :     { return __y.base() < __x.base(); }
     351             : 
     352             :   template<typename _IteratorL, typename _IteratorR>
     353             :     inline bool
     354             :     operator!=(const reverse_iterator<_IteratorL>& __x,
     355             :                const reverse_iterator<_IteratorR>& __y)
     356             :     { return !(__x == __y); }
     357             : 
     358             :   template<typename _IteratorL, typename _IteratorR>
     359             :     inline bool
     360             :     operator>(const reverse_iterator<_IteratorL>& __x,
     361             :               const reverse_iterator<_IteratorR>& __y)
     362             :     { return __y < __x; }
     363             : 
     364             :   template<typename _IteratorL, typename _IteratorR>
     365             :     inline bool
     366             :     operator<=(const reverse_iterator<_IteratorL>& __x,
     367             :                const reverse_iterator<_IteratorR>& __y)
     368             :     { return !(__y < __x); }
     369             : 
     370             :   template<typename _IteratorL, typename _IteratorR>
     371             :     inline bool
     372             :     operator>=(const reverse_iterator<_IteratorL>& __x,
     373             :                const reverse_iterator<_IteratorR>& __y)
     374             :     { return !(__x < __y); }
     375             : 
     376             :   template<typename _IteratorL, typename _IteratorR>
     377             : #if __cplusplus >= 201103L
     378             :     // DR 685.
     379             :     inline auto
     380             :     operator-(const reverse_iterator<_IteratorL>& __x,
     381             :               const reverse_iterator<_IteratorR>& __y)
     382             :     -> decltype(__y.base() - __x.base())
     383             : #else
     384             :     inline typename reverse_iterator<_IteratorL>::difference_type
     385             :     operator-(const reverse_iterator<_IteratorL>& __x,
     386             :               const reverse_iterator<_IteratorR>& __y)
     387             : #endif
     388             :     { return __y.base() - __x.base(); }
     389             :   //@}
     390             : 
     391             :   // 24.4.2.2.1 back_insert_iterator
     392             :   /**
     393             :    *  @brief  Turns assignment into insertion.
     394             :    *
     395             :    *  These are output iterators, constructed from a container-of-T.
     396             :    *  Assigning a T to the iterator appends it to the container using
     397             :    *  push_back.
     398             :    *
     399             :    *  Tip:  Using the back_inserter function to create these iterators can
     400             :    *  save typing.
     401             :   */
     402             :   template<typename _Container>
     403             :     class back_insert_iterator
     404             :     : public iterator<output_iterator_tag, void, void, void, void>
     405             :     {
     406             :     protected:
     407             :       _Container* container;
     408             : 
     409             :     public:
     410             :       /// A nested typedef for the type of whatever container you used.
     411             :       typedef _Container          container_type;
     412             : 
     413             :       /// The only way to create this %iterator is with a container.
     414             :       explicit
     415           0 :       back_insert_iterator(_Container& __x) : container(&__x) { }
     416             : 
     417             :       /**
     418             :        *  @param  __value  An instance of whatever type
     419             :        *                 container_type::const_reference is; presumably a
     420             :        *                 reference-to-const T for container<T>.
     421             :        *  @return  This %iterator, for chained operations.
     422             :        *
     423             :        *  This kind of %iterator doesn't really have a @a position in the
     424             :        *  container (you can think of the position as being permanently at
     425             :        *  the end, if you like).  Assigning a value to the %iterator will
     426             :        *  always append the value to the end of the container.
     427             :       */
     428             : #if __cplusplus < 201103L
     429             :       back_insert_iterator&
     430             :       operator=(typename _Container::const_reference __value)
     431             :       {
     432             :         container->push_back(__value);
     433             :         return *this;
     434             :       }
     435             : #else
     436             :       back_insert_iterator&
     437           0 :       operator=(const typename _Container::value_type& __value)
     438             :       {
     439           0 :         container->push_back(__value);
     440           0 :         return *this;
     441             :       }
     442             : 
     443             :       back_insert_iterator&
     444           0 :       operator=(typename _Container::value_type&& __value)
     445             :       {
     446           0 :         container->push_back(std::move(__value));
     447           0 :         return *this;
     448             :       }
     449             : #endif
     450             : 
     451             :       /// Simply returns *this.
     452             :       back_insert_iterator&
     453           0 :       operator*()
     454           0 :       { return *this; }
     455             : 
     456             :       /// Simply returns *this.  (This %iterator does not @a move.)
     457             :       back_insert_iterator&
     458           0 :       operator++()
     459           0 :       { return *this; }
     460             : 
     461             :       /// Simply returns *this.  (This %iterator does not @a move.)
     462             :       back_insert_iterator
     463             :       operator++(int)
     464             :       { return *this; }
     465             :     };
     466             : 
     467             :   /**
     468             :    *  @param  __x  A container of arbitrary type.
     469             :    *  @return  An instance of back_insert_iterator working on @p __x.
     470             :    *
     471             :    *  This wrapper function helps in creating back_insert_iterator instances.
     472             :    *  Typing the name of the %iterator requires knowing the precise full
     473             :    *  type of the container, which can be tedious and impedes generic
     474             :    *  programming.  Using this function lets you take advantage of automatic
     475             :    *  template parameter deduction, making the compiler match the correct
     476             :    *  types for you.
     477             :   */
     478             :   template<typename _Container>
     479             :     inline back_insert_iterator<_Container>
     480           0 :     back_inserter(_Container& __x)
     481           0 :     { return back_insert_iterator<_Container>(__x); }
     482             : 
     483             :   /**
     484             :    *  @brief  Turns assignment into insertion.
     485             :    *
     486             :    *  These are output iterators, constructed from a container-of-T.
     487             :    *  Assigning a T to the iterator prepends it to the container using
     488             :    *  push_front.
     489             :    *
     490             :    *  Tip:  Using the front_inserter function to create these iterators can
     491             :    *  save typing.
     492             :   */
     493             :   template<typename _Container>
     494             :     class front_insert_iterator
     495             :     : public iterator<output_iterator_tag, void, void, void, void>
     496             :     {
     497             :     protected:
     498             :       _Container* container;
     499             : 
     500             :     public:
     501             :       /// A nested typedef for the type of whatever container you used.
     502             :       typedef _Container          container_type;
     503             : 
     504             :       /// The only way to create this %iterator is with a container.
     505             :       explicit front_insert_iterator(_Container& __x) : container(&__x) { }
     506             : 
     507             :       /**
     508             :        *  @param  __value  An instance of whatever type
     509             :        *                 container_type::const_reference is; presumably a
     510             :        *                 reference-to-const T for container<T>.
     511             :        *  @return  This %iterator, for chained operations.
     512             :        *
     513             :        *  This kind of %iterator doesn't really have a @a position in the
     514             :        *  container (you can think of the position as being permanently at
     515             :        *  the front, if you like).  Assigning a value to the %iterator will
     516             :        *  always prepend the value to the front of the container.
     517             :       */
     518             : #if __cplusplus < 201103L
     519             :       front_insert_iterator&
     520             :       operator=(typename _Container::const_reference __value)
     521             :       {
     522             :         container->push_front(__value);
     523             :         return *this;
     524             :       }
     525             : #else
     526             :       front_insert_iterator&
     527             :       operator=(const typename _Container::value_type& __value)
     528             :       {
     529             :         container->push_front(__value);
     530             :         return *this;
     531             :       }
     532             : 
     533             :       front_insert_iterator&
     534             :       operator=(typename _Container::value_type&& __value)
     535             :       {
     536             :         container->push_front(std::move(__value));
     537             :         return *this;
     538             :       }
     539             : #endif
     540             : 
     541             :       /// Simply returns *this.
     542             :       front_insert_iterator&
     543             :       operator*()
     544             :       { return *this; }
     545             : 
     546             :       /// Simply returns *this.  (This %iterator does not @a move.)
     547             :       front_insert_iterator&
     548             :       operator++()
     549             :       { return *this; }
     550             : 
     551             :       /// Simply returns *this.  (This %iterator does not @a move.)
     552             :       front_insert_iterator
     553             :       operator++(int)
     554             :       { return *this; }
     555             :     };
     556             : 
     557             :   /**
     558             :    *  @param  __x  A container of arbitrary type.
     559             :    *  @return  An instance of front_insert_iterator working on @p x.
     560             :    *
     561             :    *  This wrapper function helps in creating front_insert_iterator instances.
     562             :    *  Typing the name of the %iterator requires knowing the precise full
     563             :    *  type of the container, which can be tedious and impedes generic
     564             :    *  programming.  Using this function lets you take advantage of automatic
     565             :    *  template parameter deduction, making the compiler match the correct
     566             :    *  types for you.
     567             :   */
     568             :   template<typename _Container>
     569             :     inline front_insert_iterator<_Container>
     570             :     front_inserter(_Container& __x)
     571             :     { return front_insert_iterator<_Container>(__x); }
     572             : 
     573             :   /**
     574             :    *  @brief  Turns assignment into insertion.
     575             :    *
     576             :    *  These are output iterators, constructed from a container-of-T.
     577             :    *  Assigning a T to the iterator inserts it in the container at the
     578             :    *  %iterator's position, rather than overwriting the value at that
     579             :    *  position.
     580             :    *
     581             :    *  (Sequences will actually insert a @e copy of the value before the
     582             :    *  %iterator's position.)
     583             :    *
     584             :    *  Tip:  Using the inserter function to create these iterators can
     585             :    *  save typing.
     586             :   */
     587             :   template<typename _Container>
     588             :     class insert_iterator
     589             :     : public iterator<output_iterator_tag, void, void, void, void>
     590             :     {
     591             :     protected:
     592             :       _Container* container;
     593             :       typename _Container::iterator iter;
     594             : 
     595             :     public:
     596             :       /// A nested typedef for the type of whatever container you used.
     597             :       typedef _Container          container_type;
     598             : 
     599             :       /**
     600             :        *  The only way to create this %iterator is with a container and an
     601             :        *  initial position (a normal %iterator into the container).
     602             :       */
     603             :       insert_iterator(_Container& __x, typename _Container::iterator __i)
     604             :       : container(&__x), iter(__i) {}
     605             : 
     606             :       /**
     607             :        *  @param  __value  An instance of whatever type
     608             :        *                 container_type::const_reference is; presumably a
     609             :        *                 reference-to-const T for container<T>.
     610             :        *  @return  This %iterator, for chained operations.
     611             :        *
     612             :        *  This kind of %iterator maintains its own position in the
     613             :        *  container.  Assigning a value to the %iterator will insert the
     614             :        *  value into the container at the place before the %iterator.
     615             :        *
     616             :        *  The position is maintained such that subsequent assignments will
     617             :        *  insert values immediately after one another.  For example,
     618             :        *  @code
     619             :        *     // vector v contains A and Z
     620             :        *
     621             :        *     insert_iterator i (v, ++v.begin());
     622             :        *     i = 1;
     623             :        *     i = 2;
     624             :        *     i = 3;
     625             :        *
     626             :        *     // vector v contains A, 1, 2, 3, and Z
     627             :        *  @endcode
     628             :       */
     629             : #if __cplusplus < 201103L
     630             :       insert_iterator&
     631             :       operator=(typename _Container::const_reference __value)
     632             :       {
     633             :         iter = container->insert(iter, __value);
     634             :         ++iter;
     635             :         return *this;
     636             :       }
     637             : #else
     638             :       insert_iterator&
     639             :       operator=(const typename _Container::value_type& __value)
     640             :       {
     641             :         iter = container->insert(iter, __value);
     642             :         ++iter;
     643             :         return *this;
     644             :       }
     645             : 
     646             :       insert_iterator&
     647             :       operator=(typename _Container::value_type&& __value)
     648             :       {
     649             :         iter = container->insert(iter, std::move(__value));
     650             :         ++iter;
     651             :         return *this;
     652             :       }
     653             : #endif
     654             : 
     655             :       /// Simply returns *this.
     656             :       insert_iterator&
     657             :       operator*()
     658             :       { return *this; }
     659             : 
     660             :       /// Simply returns *this.  (This %iterator does not @a move.)
     661             :       insert_iterator&
     662             :       operator++()
     663             :       { return *this; }
     664             : 
     665             :       /// Simply returns *this.  (This %iterator does not @a move.)
     666             :       insert_iterator&
     667             :       operator++(int)
     668             :       { return *this; }
     669             :     };
     670             : 
     671             :   /**
     672             :    *  @param __x  A container of arbitrary type.
     673             :    *  @return  An instance of insert_iterator working on @p __x.
     674             :    *
     675             :    *  This wrapper function helps in creating insert_iterator instances.
     676             :    *  Typing the name of the %iterator requires knowing the precise full
     677             :    *  type of the container, which can be tedious and impedes generic
     678             :    *  programming.  Using this function lets you take advantage of automatic
     679             :    *  template parameter deduction, making the compiler match the correct
     680             :    *  types for you.
     681             :   */
     682             :   template<typename _Container, typename _Iterator>
     683             :     inline insert_iterator<_Container>
     684             :     inserter(_Container& __x, _Iterator __i)
     685             :     {
     686             :       return insert_iterator<_Container>(__x,
     687             :                                          typename _Container::iterator(__i));
     688             :     }
     689             : 
     690             :   // @} group iterators
     691             : 
     692             : _GLIBCXX_END_NAMESPACE_VERSION
     693             : } // namespace
     694             : 
     695             : namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
     696             : {
     697             : _GLIBCXX_BEGIN_NAMESPACE_VERSION
     698             : 
     699             :   // This iterator adapter is @a normal in the sense that it does not
     700             :   // change the semantics of any of the operators of its iterator
     701             :   // parameter.  Its primary purpose is to convert an iterator that is
     702             :   // not a class, e.g. a pointer, into an iterator that is a class.
     703             :   // The _Container parameter exists solely so that different containers
     704             :   // using this template can instantiate different types, even if the
     705             :   // _Iterator parameter is the same.
     706             :   using std::iterator_traits;
     707             :   using std::iterator;
     708             :   template<typename _Iterator, typename _Container>
     709             :     class __normal_iterator
     710             :     {
     711             :     protected:
     712             :       _Iterator _M_current;
     713             : 
     714             :       typedef iterator_traits<_Iterator>          __traits_type;
     715             : 
     716             :     public:
     717             :       typedef _Iterator                                 iterator_type;
     718             :       typedef typename __traits_type::iterator_category iterator_category;
     719             :       typedef typename __traits_type::value_type        value_type;
     720             :       typedef typename __traits_type::difference_type   difference_type;
     721             :       typedef typename __traits_type::reference         reference;
     722             :       typedef typename __traits_type::pointer           pointer;
     723             : 
     724           0 :       _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT
     725           0 :       : _M_current(_Iterator()) { }
     726             : 
     727             :       explicit
     728         356 :       __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT
     729         356 :       : _M_current(__i) { }
     730             : 
     731             :       // Allow iterator to const_iterator conversion
     732             :       template<typename _Iter>
     733           0 :         __normal_iterator(const __normal_iterator<_Iter,
     734             :                           typename __enable_if<
     735             :                (std::__are_same<_Iter, typename _Container::pointer>::__value),
     736             :                       _Container>::__type>& __i) _GLIBCXX_NOEXCEPT
     737           0 :         : _M_current(__i.base()) { }
     738             : 
     739             :       // Forward iterator requirements
     740             :       reference
     741         161 :       operator*() const _GLIBCXX_NOEXCEPT
     742         161 :       { return *_M_current; }
     743             : 
     744             :       pointer
     745          24 :       operator->() const _GLIBCXX_NOEXCEPT
     746          24 :       { return _M_current; }
     747             : 
     748             :       __normal_iterator&
     749         126 :       operator++() _GLIBCXX_NOEXCEPT
     750             :       {
     751         126 :         ++_M_current;
     752         126 :         return *this;
     753             :       }
     754             : 
     755             :       __normal_iterator
     756           0 :       operator++(int) _GLIBCXX_NOEXCEPT
     757           0 :       { return __normal_iterator(_M_current++); }
     758             : 
     759             :       // Bidirectional iterator requirements
     760             :       __normal_iterator&
     761           0 :       operator--() _GLIBCXX_NOEXCEPT
     762             :       {
     763           0 :         --_M_current;
     764           0 :         return *this;
     765             :       }
     766             : 
     767             :       __normal_iterator
     768             :       operator--(int) _GLIBCXX_NOEXCEPT
     769             :       { return __normal_iterator(_M_current--); }
     770             : 
     771             :       // Random access iterator requirements
     772             :       reference
     773             :       operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
     774             :       { return _M_current[__n]; }
     775             : 
     776             :       __normal_iterator&
     777           0 :       operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
     778           0 :       { _M_current += __n; return *this; }
     779             : 
     780             :       __normal_iterator
     781           0 :       operator+(difference_type __n) const _GLIBCXX_NOEXCEPT
     782           0 :       { return __normal_iterator(_M_current + __n); }
     783             : 
     784             :       __normal_iterator&
     785             :       operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
     786             :       { _M_current -= __n; return *this; }
     787             : 
     788             :       __normal_iterator
     789           0 :       operator-(difference_type __n) const _GLIBCXX_NOEXCEPT
     790           0 :       { return __normal_iterator(_M_current - __n); }
     791             : 
     792             :       const _Iterator&
     793         575 :       base() const _GLIBCXX_NOEXCEPT
     794         575 :       { return _M_current; }
     795             :     };
     796             : 
     797             :   // Note: In what follows, the left- and right-hand-side iterators are
     798             :   // allowed to vary in types (conceptually in cv-qualification) so that
     799             :   // comparison between cv-qualified and non-cv-qualified iterators be
     800             :   // valid.  However, the greedy and unfriendly operators in std::rel_ops
     801             :   // will make overload resolution ambiguous (when in scope) if we don't
     802             :   // provide overloads whose operands are of the same type.  Can someone
     803             :   // remind me what generic programming is about? -- Gaby
     804             : 
     805             :   // Forward iterator requirements
     806             :   template<typename _IteratorL, typename _IteratorR, typename _Container>
     807             :     inline bool
     808           0 :     operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
     809             :                const __normal_iterator<_IteratorR, _Container>& __rhs)
     810             :     _GLIBCXX_NOEXCEPT
     811           0 :     { return __lhs.base() == __rhs.base(); }
     812             : 
     813             :   template<typename _Iterator, typename _Container>
     814             :     inline bool
     815           9 :     operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
     816             :                const __normal_iterator<_Iterator, _Container>& __rhs)
     817             :     _GLIBCXX_NOEXCEPT
     818           9 :     { return __lhs.base() == __rhs.base(); }
     819             : 
     820             :   template<typename _IteratorL, typename _IteratorR, typename _Container>
     821             :     inline bool
     822           0 :     operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
     823             :                const __normal_iterator<_IteratorR, _Container>& __rhs)
     824             :     _GLIBCXX_NOEXCEPT
     825           0 :     { return __lhs.base() != __rhs.base(); }
     826             : 
     827             :   template<typename _Iterator, typename _Container>
     828             :     inline bool
     829         271 :     operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
     830             :                const __normal_iterator<_Iterator, _Container>& __rhs)
     831             :     _GLIBCXX_NOEXCEPT
     832         271 :     { return __lhs.base() != __rhs.base(); }
     833             : 
     834             :   // Random access iterator requirements
     835             :   template<typename _IteratorL, typename _IteratorR, typename _Container>
     836             :     inline bool
     837             :     operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
     838             :               const __normal_iterator<_IteratorR, _Container>& __rhs)
     839             :     _GLIBCXX_NOEXCEPT
     840             :     { return __lhs.base() < __rhs.base(); }
     841             : 
     842             :   template<typename _Iterator, typename _Container>
     843             :     inline bool
     844           0 :     operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
     845             :               const __normal_iterator<_Iterator, _Container>& __rhs)
     846             :     _GLIBCXX_NOEXCEPT
     847           0 :     { return __lhs.base() < __rhs.base(); }
     848             : 
     849             :   template<typename _IteratorL, typename _IteratorR, typename _Container>
     850             :     inline bool
     851             :     operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
     852             :               const __normal_iterator<_IteratorR, _Container>& __rhs)
     853             :     _GLIBCXX_NOEXCEPT
     854             :     { return __lhs.base() > __rhs.base(); }
     855             : 
     856             :   template<typename _Iterator, typename _Container>
     857             :     inline bool
     858             :     operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
     859             :               const __normal_iterator<_Iterator, _Container>& __rhs)
     860             :     _GLIBCXX_NOEXCEPT
     861             :     { return __lhs.base() > __rhs.base(); }
     862             : 
     863             :   template<typename _IteratorL, typename _IteratorR, typename _Container>
     864             :     inline bool
     865             :     operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
     866             :                const __normal_iterator<_IteratorR, _Container>& __rhs)
     867             :     _GLIBCXX_NOEXCEPT
     868             :     { return __lhs.base() <= __rhs.base(); }
     869             : 
     870             :   template<typename _Iterator, typename _Container>
     871             :     inline bool
     872             :     operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
     873             :                const __normal_iterator<_Iterator, _Container>& __rhs)
     874             :     _GLIBCXX_NOEXCEPT
     875             :     { return __lhs.base() <= __rhs.base(); }
     876             : 
     877             :   template<typename _IteratorL, typename _IteratorR, typename _Container>
     878             :     inline bool
     879             :     operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
     880             :                const __normal_iterator<_IteratorR, _Container>& __rhs)
     881             :     _GLIBCXX_NOEXCEPT
     882             :     { return __lhs.base() >= __rhs.base(); }
     883             : 
     884             :   template<typename _Iterator, typename _Container>
     885             :     inline bool
     886             :     operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
     887             :                const __normal_iterator<_Iterator, _Container>& __rhs)
     888             :     _GLIBCXX_NOEXCEPT
     889             :     { return __lhs.base() >= __rhs.base(); }
     890             : 
     891             :   // _GLIBCXX_RESOLVE_LIB_DEFECTS
     892             :   // According to the resolution of DR179 not only the various comparison
     893             :   // operators but also operator- must accept mixed iterator/const_iterator
     894             :   // parameters.
     895             :   template<typename _IteratorL, typename _IteratorR, typename _Container>
     896             : #if __cplusplus >= 201103L
     897             :     // DR 685.
     898             :     inline auto
     899           0 :     operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
     900             :               const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept
     901             :     -> decltype(__lhs.base() - __rhs.base())
     902             : #else
     903             :     inline typename __normal_iterator<_IteratorL, _Container>::difference_type
     904             :     operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
     905             :               const __normal_iterator<_IteratorR, _Container>& __rhs)
     906             : #endif
     907           0 :     { return __lhs.base() - __rhs.base(); }
     908             : 
     909             :   template<typename _Iterator, typename _Container>
     910             :     inline typename __normal_iterator<_Iterator, _Container>::difference_type
     911           0 :     operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
     912             :               const __normal_iterator<_Iterator, _Container>& __rhs)
     913             :     _GLIBCXX_NOEXCEPT
     914           0 :     { return __lhs.base() - __rhs.base(); }
     915             : 
     916             :   template<typename _Iterator, typename _Container>
     917             :     inline __normal_iterator<_Iterator, _Container>
     918             :     operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
     919             :               __n, const __normal_iterator<_Iterator, _Container>& __i)
     920             :     _GLIBCXX_NOEXCEPT
     921             :     { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
     922             : 
     923             : _GLIBCXX_END_NAMESPACE_VERSION
     924             : } // namespace
     925             : 
     926             : #if __cplusplus >= 201103L
     927             : 
     928             : namespace std _GLIBCXX_VISIBILITY(default)
     929             : {
     930             : _GLIBCXX_BEGIN_NAMESPACE_VERSION
     931             : 
     932             :   /**
     933             :    * @addtogroup iterators
     934             :    * @{
     935             :    */
     936             : 
     937             :   // 24.4.3  Move iterators
     938             :   /**
     939             :    *  Class template move_iterator is an iterator adapter with the same
     940             :    *  behavior as the underlying iterator except that its dereference
     941             :    *  operator implicitly converts the value returned by the underlying
     942             :    *  iterator's dereference operator to an rvalue reference.  Some
     943             :    *  generic algorithms can be called with move iterators to replace
     944             :    *  copying with moving.
     945             :    */
     946             :   template<typename _Iterator>
     947             :     class move_iterator
     948             :     {
     949             :     protected:
     950             :       _Iterator _M_current;
     951             : 
     952             :       typedef iterator_traits<_Iterator>          __traits_type;
     953             : 
     954             :     public:
     955             :       typedef _Iterator                                 iterator_type;
     956             :       typedef typename __traits_type::iterator_category iterator_category;
     957             :       typedef typename __traits_type::value_type        value_type;
     958             :       typedef typename __traits_type::difference_type   difference_type;
     959             :       // NB: DR 680.
     960             :       typedef _Iterator                                 pointer;
     961             :       typedef value_type&&                              reference;
     962             : 
     963             :       move_iterator()
     964             :       : _M_current() { }
     965             : 
     966             :       explicit
     967         204 :       move_iterator(iterator_type __i)
     968         204 :       : _M_current(__i) { }
     969             : 
     970             :       template<typename _Iter>
     971             :         move_iterator(const move_iterator<_Iter>& __i)
     972             :         : _M_current(__i.base()) { }
     973             : 
     974             :       iterator_type
     975         232 :       base() const
     976         232 :       { return _M_current; }
     977             : 
     978             :       reference
     979          14 :       operator*() const
     980          14 :       { return std::move(*_M_current); }
     981             : 
     982             :       pointer
     983             :       operator->() const
     984             :       { return _M_current; }
     985             : 
     986             :       move_iterator&
     987          14 :       operator++()
     988             :       {
     989          14 :         ++_M_current;
     990          14 :         return *this;
     991             :       }
     992             : 
     993             :       move_iterator
     994             :       operator++(int)
     995             :       {
     996             :         move_iterator __tmp = *this;
     997             :         ++_M_current;
     998             :         return __tmp;
     999             :       }
    1000             : 
    1001             :       move_iterator&
    1002             :       operator--()
    1003             :       {
    1004             :         --_M_current;
    1005             :         return *this;
    1006             :       }
    1007             : 
    1008             :       move_iterator
    1009             :       operator--(int)
    1010             :       {
    1011             :         move_iterator __tmp = *this;
    1012             :         --_M_current;
    1013             :         return __tmp;
    1014             :       }
    1015             : 
    1016             :       move_iterator
    1017             :       operator+(difference_type __n) const
    1018             :       { return move_iterator(_M_current + __n); }
    1019             : 
    1020             :       move_iterator&
    1021             :       operator+=(difference_type __n)
    1022             :       {
    1023             :         _M_current += __n;
    1024             :         return *this;
    1025             :       }
    1026             : 
    1027             :       move_iterator
    1028             :       operator-(difference_type __n) const
    1029             :       { return move_iterator(_M_current - __n); }
    1030             :     
    1031             :       move_iterator&
    1032             :       operator-=(difference_type __n)
    1033             :       { 
    1034             :         _M_current -= __n;
    1035             :         return *this;
    1036             :       }
    1037             : 
    1038             :       reference
    1039             :       operator[](difference_type __n) const
    1040             :       { return std::move(_M_current[__n]); }
    1041             :     };
    1042             : 
    1043             :   // Note: See __normal_iterator operators note from Gaby to understand
    1044             :   // why there are always 2 versions for most of the move_iterator
    1045             :   // operators.
    1046             :   template<typename _IteratorL, typename _IteratorR>
    1047             :     inline bool
    1048             :     operator==(const move_iterator<_IteratorL>& __x,
    1049             :                const move_iterator<_IteratorR>& __y)
    1050             :     { return __x.base() == __y.base(); }
    1051             : 
    1052             :   template<typename _Iterator>
    1053             :     inline bool
    1054         115 :     operator==(const move_iterator<_Iterator>& __x,
    1055             :                const move_iterator<_Iterator>& __y)
    1056         115 :     { return __x.base() == __y.base(); }
    1057             : 
    1058             :   template<typename _IteratorL, typename _IteratorR>
    1059             :     inline bool
    1060             :     operator!=(const move_iterator<_IteratorL>& __x,
    1061             :                const move_iterator<_IteratorR>& __y)
    1062             :     { return !(__x == __y); }
    1063             : 
    1064             :   template<typename _Iterator>
    1065             :     inline bool
    1066         115 :     operator!=(const move_iterator<_Iterator>& __x,
    1067             :                const move_iterator<_Iterator>& __y)
    1068         115 :     { return !(__x == __y); }
    1069             : 
    1070             :   template<typename _IteratorL, typename _IteratorR>
    1071             :     inline bool
    1072             :     operator<(const move_iterator<_IteratorL>& __x,
    1073             :               const move_iterator<_IteratorR>& __y)
    1074             :     { return __x.base() < __y.base(); }
    1075             : 
    1076             :   template<typename _Iterator>
    1077             :     inline bool
    1078             :     operator<(const move_iterator<_Iterator>& __x,
    1079             :               const move_iterator<_Iterator>& __y)
    1080             :     { return __x.base() < __y.base(); }
    1081             : 
    1082             :   template<typename _IteratorL, typename _IteratorR>
    1083             :     inline bool
    1084             :     operator<=(const move_iterator<_IteratorL>& __x,
    1085             :                const move_iterator<_IteratorR>& __y)
    1086             :     { return !(__y < __x); }
    1087             : 
    1088             :   template<typename _Iterator>
    1089             :     inline bool
    1090             :     operator<=(const move_iterator<_Iterator>& __x,
    1091             :                const move_iterator<_Iterator>& __y)
    1092             :     { return !(__y < __x); }
    1093             : 
    1094             :   template<typename _IteratorL, typename _IteratorR>
    1095             :     inline bool
    1096             :     operator>(const move_iterator<_IteratorL>& __x,
    1097             :               const move_iterator<_IteratorR>& __y)
    1098             :     { return __y < __x; }
    1099             : 
    1100             :   template<typename _Iterator>
    1101             :     inline bool
    1102             :     operator>(const move_iterator<_Iterator>& __x,
    1103             :               const move_iterator<_Iterator>& __y)
    1104             :     { return __y < __x; }
    1105             : 
    1106             :   template<typename _IteratorL, typename _IteratorR>
    1107             :     inline bool
    1108             :     operator>=(const move_iterator<_IteratorL>& __x,
    1109             :                const move_iterator<_IteratorR>& __y)
    1110             :     { return !(__x < __y); }
    1111             : 
    1112             :   template<typename _Iterator>
    1113             :     inline bool
    1114             :     operator>=(const move_iterator<_Iterator>& __x,
    1115             :                const move_iterator<_Iterator>& __y)
    1116             :     { return !(__x < __y); }
    1117             : 
    1118             :   // DR 685.
    1119             :   template<typename _IteratorL, typename _IteratorR>
    1120             :     inline auto
    1121             :     operator-(const move_iterator<_IteratorL>& __x,
    1122             :               const move_iterator<_IteratorR>& __y)
    1123             :     -> decltype(__x.base() - __y.base())
    1124             :     { return __x.base() - __y.base(); }
    1125             : 
    1126             :   template<typename _Iterator>
    1127             :     inline auto
    1128             :     operator-(const move_iterator<_Iterator>& __x,
    1129             :               const move_iterator<_Iterator>& __y)
    1130             :     -> decltype(__x.base() - __y.base())
    1131             :     { return __x.base() - __y.base(); }
    1132             : 
    1133             :   template<typename _Iterator>
    1134             :     inline move_iterator<_Iterator>
    1135             :     operator+(typename move_iterator<_Iterator>::difference_type __n,
    1136             :               const move_iterator<_Iterator>& __x)
    1137             :     { return __x + __n; }
    1138             : 
    1139             :   template<typename _Iterator>
    1140             :     inline move_iterator<_Iterator>
    1141             :     make_move_iterator(_Iterator __i)
    1142             :     { return move_iterator<_Iterator>(__i); }
    1143             : 
    1144             :   template<typename _Iterator, typename _ReturnType
    1145             :     = typename conditional<__move_if_noexcept_cond
    1146             :       <typename iterator_traits<_Iterator>::value_type>::value,
    1147             :                 _Iterator, move_iterator<_Iterator>>::type>
    1148             :     inline _ReturnType
    1149         204 :     __make_move_if_noexcept_iterator(_Iterator __i)
    1150         204 :     { return _ReturnType(__i); }
    1151             : 
    1152             :   // @} group iterators
    1153             : 
    1154             : _GLIBCXX_END_NAMESPACE_VERSION
    1155             : } // namespace
    1156             : 
    1157             : #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
    1158             : #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
    1159             :   std::__make_move_if_noexcept_iterator(_Iter)
    1160             : #else
    1161             : #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
    1162             : #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
    1163             : #endif // C++11
    1164             : 
    1165             : #endif

Generated by: LCOV version 1.11