wpkg test coverage results

Coverage test results of the Windows Packager by Made to Order Software Corporation.

LCOV - code coverage report
Current view: top level - usr/include/c++/4.6/bits - stl_deque.h (source / functions) Hit Total Coverage
Test: coverage.info Lines: 34 36 94.4 %
Date: 2013-06-17 Functions: 14 15 93.3 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : // Deque implementation -*- C++ -*-
       2             : 
       3             : // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
       4             : // 2011 Free Software Foundation, Inc.
       5             : //
       6             : // This file is part of the GNU ISO C++ Library.  This library is free
       7             : // software; you can redistribute it and/or modify it under the
       8             : // terms of the GNU General Public License as published by the
       9             : // Free Software Foundation; either version 3, or (at your option)
      10             : // any later version.
      11             : 
      12             : // This library is distributed in the hope that it will be useful,
      13             : // but WITHOUT ANY WARRANTY; without even the implied warranty of
      14             : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      15             : // GNU General Public License for more details.
      16             : 
      17             : // Under Section 7 of GPL version 3, you are granted additional
      18             : // permissions described in the GCC Runtime Library Exception, version
      19             : // 3.1, as published by the Free Software Foundation.
      20             : 
      21             : // You should have received a copy of the GNU General Public License and
      22             : // a copy of the GCC Runtime Library Exception along with this program;
      23             : // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
      24             : // <http://www.gnu.org/licenses/>.
      25             : 
      26             : /*
      27             :  *
      28             :  * Copyright (c) 1994
      29             :  * Hewlett-Packard Company
      30             :  *
      31             :  * Permission to use, copy, modify, distribute and sell this software
      32             :  * and its documentation for any purpose is hereby granted without fee,
      33             :  * provided that the above copyright notice appear in all copies and
      34             :  * that both that copyright notice and this permission notice appear
      35             :  * in supporting documentation.  Hewlett-Packard Company makes no
      36             :  * representations about the suitability of this software for any
      37             :  * purpose.  It is provided "as is" without express or implied warranty.
      38             :  *
      39             :  *
      40             :  * Copyright (c) 1997
      41             :  * Silicon Graphics Computer Systems, Inc.
      42             :  *
      43             :  * Permission to use, copy, modify, distribute and sell this software
      44             :  * and its documentation for any purpose is hereby granted without fee,
      45             :  * provided that the above copyright notice appear in all copies and
      46             :  * that both that copyright notice and this permission notice appear
      47             :  * in supporting documentation.  Silicon Graphics makes no
      48             :  * representations about the suitability of this software for any
      49             :  * purpose.  It is provided "as is" without express or implied warranty.
      50             :  */
      51             : 
      52             : /** @file bits/stl_deque.h
      53             :  *  This is an internal header file, included by other library headers.
      54             :  *  Do not attempt to use it directly. @headername{deque}
      55             :  */
      56             : 
      57             : #ifndef _STL_DEQUE_H
      58             : #define _STL_DEQUE_H 1
      59             : 
      60             : #include <bits/concept_check.h>
      61             : #include <bits/stl_iterator_base_types.h>
      62             : #include <bits/stl_iterator_base_funcs.h>
      63             : #include <initializer_list>
      64             : 
      65             : namespace std _GLIBCXX_VISIBILITY(default)
      66             : {
      67             : _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
      68             : 
      69             :   /**
      70             :    *  @brief This function controls the size of memory nodes.
      71             :    *  @param  size  The size of an element.
      72             :    *  @return   The number (not byte size) of elements per node.
      73             :    *
      74             :    *  This function started off as a compiler kludge from SGI, but
      75             :    *  seems to be a useful wrapper around a repeated constant
      76             :    *  expression.  The @b 512 is tunable (and no other code needs to
      77             :    *  change), but no investigation has been done since inheriting the
      78             :    *  SGI code.  Touch _GLIBCXX_DEQUE_BUF_SIZE only if you know what
      79             :    *  you are doing, however: changing it breaks the binary
      80             :    *  compatibility!!
      81             :   */
      82             : 
      83             : #ifndef _GLIBCXX_DEQUE_BUF_SIZE
      84             : #define _GLIBCXX_DEQUE_BUF_SIZE 512
      85             : #endif
      86             : 
      87             :   inline size_t
      88      288577 :   __deque_buf_size(size_t __size)
      89             :   { return (__size < _GLIBCXX_DEQUE_BUF_SIZE
      90      288577 :             ? size_t(_GLIBCXX_DEQUE_BUF_SIZE / __size) : size_t(1)); }
      91             : 
      92             : 
      93             :   /**
      94             :    *  @brief A deque::iterator.
      95             :    *
      96             :    *  Quite a bit of intelligence here.  Much of the functionality of
      97             :    *  deque is actually passed off to this class.  A deque holds two
      98             :    *  of these internally, marking its valid range.  Access to
      99             :    *  elements is done as offsets of either of those two, relying on
     100             :    *  operator overloading in this class.
     101             :    *
     102             :    *  All the functions are op overloads except for _M_set_node.
     103             :   */
     104             :   template<typename _Tp, typename _Ref, typename _Ptr>
     105             :     struct _Deque_iterator
     106             :     {
     107             :       typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;
     108             :       typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
     109             : 
     110             :       static size_t _S_buffer_size()
     111             :       { return __deque_buf_size(sizeof(_Tp)); }
     112             : 
     113             :       typedef std::random_access_iterator_tag iterator_category;
     114             :       typedef _Tp                             value_type;
     115             :       typedef _Ptr                            pointer;
     116             :       typedef _Ref                            reference;
     117             :       typedef size_t                          size_type;
     118             :       typedef ptrdiff_t                       difference_type;
     119             :       typedef _Tp**                           _Map_pointer;
     120             :       typedef _Deque_iterator                 _Self;
     121             : 
     122             :       _Tp* _M_cur;
     123             :       _Tp* _M_first;
     124             :       _Tp* _M_last;
     125             :       _Map_pointer _M_node;
     126             : 
     127             :       _Deque_iterator(_Tp* __x, _Map_pointer __y)
     128             :       : _M_cur(__x), _M_first(*__y),
     129             :         _M_last(*__y + _S_buffer_size()), _M_node(__y) { }
     130             : 
     131             :       _Deque_iterator()
     132             :       : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) { }
     133             : 
     134     1154308 :       _Deque_iterator(const iterator& __x)
     135             :       : _M_cur(__x._M_cur), _M_first(__x._M_first),
     136     1154308 :         _M_last(__x._M_last), _M_node(__x._M_node) { }
     137             : 
     138             :       reference
     139             :       operator*() const
     140             :       { return *_M_cur; }
     141             : 
     142             :       pointer
     143             :       operator->() const
     144             :       { return _M_cur; }
     145             : 
     146             :       _Self&
     147             :       operator++()
     148             :       {
     149             :         ++_M_cur;
     150             :         if (_M_cur == _M_last)
     151             :           {
     152             :             _M_set_node(_M_node + 1);
     153             :             _M_cur = _M_first;
     154             :           }
     155             :         return *this;
     156             :       }
     157             : 
     158             :       _Self
     159             :       operator++(int)
     160             :       {
     161             :         _Self __tmp = *this;
     162             :         ++*this;
     163             :         return __tmp;
     164             :       }
     165             : 
     166             :       _Self&
     167             :       operator--()
     168             :       {
     169             :         if (_M_cur == _M_first)
     170             :           {
     171             :             _M_set_node(_M_node - 1);
     172             :             _M_cur = _M_last;
     173             :           }
     174             :         --_M_cur;
     175             :         return *this;
     176             :       }
     177             : 
     178             :       _Self
     179             :       operator--(int)
     180             :       {
     181             :         _Self __tmp = *this;
     182             :         --*this;
     183             :         return __tmp;
     184             :       }
     185             : 
     186             :       _Self&
     187             :       operator+=(difference_type __n)
     188             :       {
     189             :         const difference_type __offset = __n + (_M_cur - _M_first);
     190             :         if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
     191             :           _M_cur += __n;
     192             :         else
     193             :           {
     194             :             const difference_type __node_offset =
     195             :               __offset > 0 ? __offset / difference_type(_S_buffer_size())
     196             :                            : -difference_type((-__offset - 1)
     197             :                                               / _S_buffer_size()) - 1;
     198             :             _M_set_node(_M_node + __node_offset);
     199             :             _M_cur = _M_first + (__offset - __node_offset
     200             :                                  * difference_type(_S_buffer_size()));
     201             :           }
     202             :         return *this;
     203             :       }
     204             : 
     205             :       _Self
     206             :       operator+(difference_type __n) const
     207             :       {
     208             :         _Self __tmp = *this;
     209             :         return __tmp += __n;
     210             :       }
     211             : 
     212             :       _Self&
     213             :       operator-=(difference_type __n)
     214             :       { return *this += -__n; }
     215             : 
     216             :       _Self
     217             :       operator-(difference_type __n) const
     218             :       {
     219             :         _Self __tmp = *this;
     220             :         return __tmp -= __n;
     221             :       }
     222             : 
     223             :       reference
     224             :       operator[](difference_type __n) const
     225             :       { return *(*this + __n); }
     226             : 
     227             :       /** 
     228             :        *  Prepares to traverse new_node.  Sets everything except
     229             :        *  _M_cur, which should therefore be set by the caller
     230             :        *  immediately afterwards, based on _M_first and _M_last.
     231             :        */
     232             :       void
     233             :       _M_set_node(_Map_pointer __new_node)
     234             :       {
     235             :         _M_node = __new_node;
     236             :         _M_first = *__new_node;
     237             :         _M_last = _M_first + difference_type(_S_buffer_size());
     238             :       }
     239             :     };
     240             : 
     241             :   // Note: we also provide overloads whose operands are of the same type in
     242             :   // order to avoid ambiguous overload resolution when std::rel_ops operators
     243             :   // are in scope (for additional details, see libstdc++/3628)
     244             :   template<typename _Tp, typename _Ref, typename _Ptr>
     245             :     inline bool
     246             :     operator==(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
     247             :                const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
     248             :     { return __x._M_cur == __y._M_cur; }
     249             : 
     250             :   template<typename _Tp, typename _RefL, typename _PtrL,
     251             :            typename _RefR, typename _PtrR>
     252             :     inline bool
     253             :     operator==(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
     254             :                const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
     255             :     { return __x._M_cur == __y._M_cur; }
     256             : 
     257             :   template<typename _Tp, typename _Ref, typename _Ptr>
     258             :     inline bool
     259             :     operator!=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
     260             :                const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
     261             :     { return !(__x == __y); }
     262             : 
     263             :   template<typename _Tp, typename _RefL, typename _PtrL,
     264             :            typename _RefR, typename _PtrR>
     265             :     inline bool
     266             :     operator!=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
     267             :                const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
     268             :     { return !(__x == __y); }
     269             : 
     270             :   template<typename _Tp, typename _Ref, typename _Ptr>
     271             :     inline bool
     272             :     operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
     273             :               const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
     274             :     { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)
     275             :                                           : (__x._M_node < __y._M_node); }
     276             : 
     277             :   template<typename _Tp, typename _RefL, typename _PtrL,
     278             :            typename _RefR, typename _PtrR>
     279             :     inline bool
     280             :     operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
     281             :               const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
     282             :     { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)
     283             :                                           : (__x._M_node < __y._M_node); }
     284             : 
     285             :   template<typename _Tp, typename _Ref, typename _Ptr>
     286             :     inline bool
     287             :     operator>(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
     288             :               const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
     289             :     { return __y < __x; }
     290             : 
     291             :   template<typename _Tp, typename _RefL, typename _PtrL,
     292             :            typename _RefR, typename _PtrR>
     293             :     inline bool
     294             :     operator>(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
     295             :               const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
     296             :     { return __y < __x; }
     297             : 
     298             :   template<typename _Tp, typename _Ref, typename _Ptr>
     299             :     inline bool
     300             :     operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
     301             :                const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
     302             :     { return !(__y < __x); }
     303             : 
     304             :   template<typename _Tp, typename _RefL, typename _PtrL,
     305             :            typename _RefR, typename _PtrR>
     306             :     inline bool
     307             :     operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
     308             :                const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
     309             :     { return !(__y < __x); }
     310             : 
     311             :   template<typename _Tp, typename _Ref, typename _Ptr>
     312             :     inline bool
     313             :     operator>=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
     314             :                const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
     315             :     { return !(__x < __y); }
     316             : 
     317             :   template<typename _Tp, typename _RefL, typename _PtrL,
     318             :            typename _RefR, typename _PtrR>
     319             :     inline bool
     320             :     operator>=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
     321             :                const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
     322             :     { return !(__x < __y); }
     323             : 
     324             :   // _GLIBCXX_RESOLVE_LIB_DEFECTS
     325             :   // According to the resolution of DR179 not only the various comparison
     326             :   // operators but also operator- must accept mixed iterator/const_iterator
     327             :   // parameters.
     328             :   template<typename _Tp, typename _Ref, typename _Ptr>
     329             :     inline typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type
     330             :     operator-(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
     331             :               const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
     332             :     {
     333             :       return typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type
     334             :         (_Deque_iterator<_Tp, _Ref, _Ptr>::_S_buffer_size())
     335             :         * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
     336             :         + (__y._M_last - __y._M_cur);
     337             :     }
     338             : 
     339             :   template<typename _Tp, typename _RefL, typename _PtrL,
     340             :            typename _RefR, typename _PtrR>
     341             :     inline typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
     342             :     operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
     343             :               const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
     344             :     {
     345             :       return typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
     346             :         (_Deque_iterator<_Tp, _RefL, _PtrL>::_S_buffer_size())
     347             :         * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
     348             :         + (__y._M_last - __y._M_cur);
     349             :     }
     350             : 
     351             :   template<typename _Tp, typename _Ref, typename _Ptr>
     352             :     inline _Deque_iterator<_Tp, _Ref, _Ptr>
     353             :     operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x)
     354             :     { return __x + __n; }
     355             : 
     356             :   template<typename _Tp>
     357             :     void
     358             :     fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>&,
     359             :          const _Deque_iterator<_Tp, _Tp&, _Tp*>&, const _Tp&);
     360             : 
     361             :   template<typename _Tp>
     362             :     _Deque_iterator<_Tp, _Tp&, _Tp*>
     363             :     copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
     364             :          _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
     365             :          _Deque_iterator<_Tp, _Tp&, _Tp*>);
     366             : 
     367             :   template<typename _Tp>
     368             :     inline _Deque_iterator<_Tp, _Tp&, _Tp*>
     369             :     copy(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
     370             :          _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
     371             :          _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
     372             :     { return std::copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),
     373             :                        _Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last),
     374             :                        __result); }
     375             : 
     376             :   template<typename _Tp>
     377             :     _Deque_iterator<_Tp, _Tp&, _Tp*>
     378             :     copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
     379             :                   _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
     380             :                   _Deque_iterator<_Tp, _Tp&, _Tp*>);
     381             : 
     382             :   template<typename _Tp>
     383             :     inline _Deque_iterator<_Tp, _Tp&, _Tp*>
     384             :     copy_backward(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
     385             :                   _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
     386             :                   _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
     387             :     { return std::copy_backward(_Deque_iterator<_Tp,
     388             :                                 const _Tp&, const _Tp*>(__first),
     389             :                                 _Deque_iterator<_Tp,
     390             :                                 const _Tp&, const _Tp*>(__last),
     391             :                                 __result); }
     392             : 
     393             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
     394             :   template<typename _Tp>
     395             :     _Deque_iterator<_Tp, _Tp&, _Tp*>
     396             :     move(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
     397             :          _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
     398             :          _Deque_iterator<_Tp, _Tp&, _Tp*>);
     399             : 
     400             :   template<typename _Tp>
     401             :     inline _Deque_iterator<_Tp, _Tp&, _Tp*>
     402             :     move(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
     403             :          _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
     404             :          _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
     405             :     { return std::move(_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),
     406             :                        _Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last),
     407             :                        __result); }
     408             : 
     409             :   template<typename _Tp>
     410             :     _Deque_iterator<_Tp, _Tp&, _Tp*>
     411             :     move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
     412             :                   _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
     413             :                   _Deque_iterator<_Tp, _Tp&, _Tp*>);
     414             : 
     415             :   template<typename _Tp>
     416             :     inline _Deque_iterator<_Tp, _Tp&, _Tp*>
     417             :     move_backward(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
     418             :                   _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
     419             :                   _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
     420             :     { return std::move_backward(_Deque_iterator<_Tp,
     421             :                                 const _Tp&, const _Tp*>(__first),
     422             :                                 _Deque_iterator<_Tp,
     423             :                                 const _Tp&, const _Tp*>(__last),
     424             :                                 __result); }
     425             : #endif
     426             : 
     427             :   /**
     428             :    *  Deque base class.  This class provides the unified face for %deque's
     429             :    *  allocation.  This class's constructor and destructor allocate and
     430             :    *  deallocate (but do not initialize) storage.  This makes %exception
     431             :    *  safety easier.
     432             :    *
     433             :    *  Nothing in this class ever constructs or destroys an actual Tp element.
     434             :    *  (Deque handles that itself.)  Only/All memory management is performed
     435             :    *  here.
     436             :   */
     437             :   template<typename _Tp, typename _Alloc>
     438             :     class _Deque_base
     439             :     {
     440             :     public:
     441             :       typedef _Alloc                  allocator_type;
     442             : 
     443             :       allocator_type
     444             :       get_allocator() const
     445             :       { return allocator_type(_M_get_Tp_allocator()); }
     446             : 
     447             :       typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;
     448             :       typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
     449             : 
     450             :       _Deque_base()
     451             :       : _M_impl()
     452             :       { _M_initialize_map(0); }
     453             : 
     454             :       _Deque_base(size_t __num_elements)
     455             :       : _M_impl()
     456             :       { _M_initialize_map(__num_elements); }
     457             : 
     458             :       _Deque_base(const allocator_type& __a, size_t __num_elements)
     459             :       : _M_impl(__a)
     460             :       { _M_initialize_map(__num_elements); }
     461             : 
     462             :       _Deque_base(const allocator_type& __a)
     463             :       : _M_impl(__a)
     464             :       { }
     465             : 
     466             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
     467             :       _Deque_base(_Deque_base&& __x)
     468             :       : _M_impl(__x._M_get_Tp_allocator())
     469             :       {
     470             :         _M_initialize_map(0);
     471             :         if (__x._M_impl._M_map)
     472             :           {
     473             :             std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
     474             :             std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
     475             :             std::swap(this->_M_impl._M_map, __x._M_impl._M_map);
     476             :             std::swap(this->_M_impl._M_map_size, __x._M_impl._M_map_size);
     477             :           }
     478             :       }
     479             : #endif
     480             : 
     481             :       ~_Deque_base();
     482             : 
     483             :     protected:
     484             :       //This struct encapsulates the implementation of the std::deque
     485             :       //standard container and at the same time makes use of the EBO
     486             :       //for empty allocators.
     487             :       typedef typename _Alloc::template rebind<_Tp*>::other _Map_alloc_type;
     488             : 
     489             :       typedef typename _Alloc::template rebind<_Tp>::other  _Tp_alloc_type;
     490             : 
     491      288577 :       struct _Deque_impl
     492             :       : public _Tp_alloc_type
     493             :       {
     494             :         _Tp** _M_map;
     495             :         size_t _M_map_size;
     496             :         iterator _M_start;
     497             :         iterator _M_finish;
     498             : 
     499             :         _Deque_impl()
     500             :         : _Tp_alloc_type(), _M_map(0), _M_map_size(0),
     501             :           _M_start(), _M_finish()
     502             :         { }
     503             : 
     504             :         _Deque_impl(const _Tp_alloc_type& __a)
     505             :         : _Tp_alloc_type(__a), _M_map(0), _M_map_size(0),
     506             :           _M_start(), _M_finish()
     507             :         { }
     508             :       };
     509             : 
     510             :       _Tp_alloc_type&
     511      577154 :       _M_get_Tp_allocator()
     512      577154 :       { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }
     513             : 
     514             :       const _Tp_alloc_type&
     515      288577 :       _M_get_Tp_allocator() const
     516      288577 :       { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }
     517             : 
     518             :       _Map_alloc_type
     519      288577 :       _M_get_map_allocator() const
     520      288577 :       { return _Map_alloc_type(_M_get_Tp_allocator()); }
     521             : 
     522             :       _Tp*
     523             :       _M_allocate_node()
     524             :       { 
     525             :         return _M_impl._Tp_alloc_type::allocate(__deque_buf_size(sizeof(_Tp)));
     526             :       }
     527             : 
     528             :       void
     529      288577 :       _M_deallocate_node(_Tp* __p)
     530             :       {
     531      288577 :         _M_impl._Tp_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp)));
     532      288577 :       }
     533             : 
     534             :       _Tp**
     535             :       _M_allocate_map(size_t __n)
     536             :       { return _M_get_map_allocator().allocate(__n); }
     537             : 
     538             :       void
     539      288577 :       _M_deallocate_map(_Tp** __p, size_t __n)
     540      288577 :       { _M_get_map_allocator().deallocate(__p, __n); }
     541             : 
     542             :     protected:
     543             :       void _M_initialize_map(size_t);
     544             :       void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
     545             :       void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
     546             :       enum { _S_initial_map_size = 8 };
     547             : 
     548             :       _Deque_impl _M_impl;
     549             :     };
     550             : 
     551             :   template<typename _Tp, typename _Alloc>
     552      288577 :     _Deque_base<_Tp, _Alloc>::
     553             :     ~_Deque_base()
     554             :     {
     555      288577 :       if (this->_M_impl._M_map)
     556             :         {
     557      288577 :           _M_destroy_nodes(this->_M_impl._M_start._M_node,
     558             :                            this->_M_impl._M_finish._M_node + 1);
     559      288577 :           _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
     560             :         }
     561      288577 :     }
     562             : 
     563             :   /**
     564             :    *  @brief Layout storage.
     565             :    *  @param  num_elements  The count of T's for which to allocate space
     566             :    *                        at first.
     567             :    *  @return   Nothing.
     568             :    *
     569             :    *  The initial underlying memory layout is a bit complicated...
     570             :   */
     571             :   template<typename _Tp, typename _Alloc>
     572             :     void
     573             :     _Deque_base<_Tp, _Alloc>::
     574             :     _M_initialize_map(size_t __num_elements)
     575             :     {
     576             :       const size_t __num_nodes = (__num_elements/ __deque_buf_size(sizeof(_Tp))
     577             :                                   + 1);
     578             : 
     579             :       this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size,
     580             :                                            size_t(__num_nodes + 2));
     581             :       this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
     582             : 
     583             :       // For "small" maps (needing less than _M_map_size nodes), allocation
     584             :       // starts in the middle elements and grows outwards.  So nstart may be
     585             :       // the beginning of _M_map, but for small maps it may be as far in as
     586             :       // _M_map+3.
     587             : 
     588             :       _Tp** __nstart = (this->_M_impl._M_map
     589             :                         + (this->_M_impl._M_map_size - __num_nodes) / 2);
     590             :       _Tp** __nfinish = __nstart + __num_nodes;
     591             : 
     592             :       __try
     593             :         { _M_create_nodes(__nstart, __nfinish); }
     594             :       __catch(...)
     595             :         {
     596             :           _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
     597             :           this->_M_impl._M_map = 0;
     598             :           this->_M_impl._M_map_size = 0;
     599             :           __throw_exception_again;
     600             :         }
     601             : 
     602             :       this->_M_impl._M_start._M_set_node(__nstart);
     603             :       this->_M_impl._M_finish._M_set_node(__nfinish - 1);
     604             :       this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
     605             :       this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
     606             :                                         + __num_elements
     607             :                                         % __deque_buf_size(sizeof(_Tp)));
     608             :     }
     609             : 
     610             :   template<typename _Tp, typename _Alloc>
     611             :     void
     612             :     _Deque_base<_Tp, _Alloc>::
     613             :     _M_create_nodes(_Tp** __nstart, _Tp** __nfinish)
     614             :     {
     615             :       _Tp** __cur;
     616             :       __try
     617             :         {
     618             :           for (__cur = __nstart; __cur < __nfinish; ++__cur)
     619             :             *__cur = this->_M_allocate_node();
     620             :         }
     621             :       __catch(...)
     622             :         {
     623             :           _M_destroy_nodes(__nstart, __cur);
     624             :           __throw_exception_again;
     625             :         }
     626             :     }
     627             : 
     628             :   template<typename _Tp, typename _Alloc>
     629             :     void
     630      288577 :     _Deque_base<_Tp, _Alloc>::
     631             :     _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish)
     632             :     {
     633      577154 :       for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
     634      288577 :         _M_deallocate_node(*__n);
     635      288577 :     }
     636             : 
     637             :   /**
     638             :    *  @brief  A standard container using fixed-size memory allocation and
     639             :    *  constant-time manipulation of elements at either end.
     640             :    *
     641             :    *  @ingroup sequences
     642             :    *
     643             :    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
     644             :    *  <a href="tables.html#66">reversible container</a>, and a
     645             :    *  <a href="tables.html#67">sequence</a>, including the
     646             :    *  <a href="tables.html#68">optional sequence requirements</a>.
     647             :    *
     648             :    *  In previous HP/SGI versions of deque, there was an extra template
     649             :    *  parameter so users could control the node size.  This extension turned
     650             :    *  out to violate the C++ standard (it can be detected using template
     651             :    *  template parameters), and it was removed.
     652             :    *
     653             :    *  Here's how a deque<Tp> manages memory.  Each deque has 4 members:
     654             :    *
     655             :    *  - Tp**        _M_map
     656             :    *  - size_t      _M_map_size
     657             :    *  - iterator    _M_start, _M_finish
     658             :    *
     659             :    *  map_size is at least 8.  %map is an array of map_size
     660             :    *  pointers-to-@anodes.  (The name %map has nothing to do with the
     661             :    *  std::map class, and @b nodes should not be confused with
     662             :    *  std::list's usage of @a node.)
     663             :    *
     664             :    *  A @a node has no specific type name as such, but it is referred
     665             :    *  to as @a node in this file.  It is a simple array-of-Tp.  If Tp
     666             :    *  is very large, there will be one Tp element per node (i.e., an
     667             :    *  @a array of one).  For non-huge Tp's, node size is inversely
     668             :    *  related to Tp size: the larger the Tp, the fewer Tp's will fit
     669             :    *  in a node.  The goal here is to keep the total size of a node
     670             :    *  relatively small and constant over different Tp's, to improve
     671             :    *  allocator efficiency.
     672             :    *
     673             :    *  Not every pointer in the %map array will point to a node.  If
     674             :    *  the initial number of elements in the deque is small, the
     675             :    *  /middle/ %map pointers will be valid, and the ones at the edges
     676             :    *  will be unused.  This same situation will arise as the %map
     677             :    *  grows: available %map pointers, if any, will be on the ends.  As
     678             :    *  new nodes are created, only a subset of the %map's pointers need
     679             :    *  to be copied @a outward.
     680             :    *
     681             :    *  Class invariants:
     682             :    * - For any nonsingular iterator i:
     683             :    *    - i.node points to a member of the %map array.  (Yes, you read that
     684             :    *      correctly:  i.node does not actually point to a node.)  The member of
     685             :    *      the %map array is what actually points to the node.
     686             :    *    - i.first == *(i.node)    (This points to the node (first Tp element).)
     687             :    *    - i.last  == i.first + node_size
     688             :    *    - i.cur is a pointer in the range [i.first, i.last).  NOTE:
     689             :    *      the implication of this is that i.cur is always a dereferenceable
     690             :    *      pointer, even if i is a past-the-end iterator.
     691             :    * - Start and Finish are always nonsingular iterators.  NOTE: this
     692             :    * means that an empty deque must have one node, a deque with <N
     693             :    * elements (where N is the node buffer size) must have one node, a
     694             :    * deque with N through (2N-1) elements must have two nodes, etc.
     695             :    * - For every node other than start.node and finish.node, every
     696             :    * element in the node is an initialized object.  If start.node ==
     697             :    * finish.node, then [start.cur, finish.cur) are initialized
     698             :    * objects, and the elements outside that range are uninitialized
     699             :    * storage.  Otherwise, [start.cur, start.last) and [finish.first,
     700             :    * finish.cur) are initialized objects, and [start.first, start.cur)
     701             :    * and [finish.cur, finish.last) are uninitialized storage.
     702             :    * - [%map, %map + map_size) is a valid, non-empty range.
     703             :    * - [start.node, finish.node] is a valid range contained within
     704             :    *   [%map, %map + map_size).
     705             :    * - A pointer in the range [%map, %map + map_size) points to an allocated
     706             :    *   node if and only if the pointer is in the range
     707             :    *   [start.node, finish.node].
     708             :    *
     709             :    *  Here's the magic:  nothing in deque is @b aware of the discontiguous
     710             :    *  storage!
     711             :    *
     712             :    *  The memory setup and layout occurs in the parent, _Base, and the iterator
     713             :    *  class is entirely responsible for @a leaping from one node to the next.
     714             :    *  All the implementation routines for deque itself work only through the
     715             :    *  start and finish iterators.  This keeps the routines simple and sane,
     716             :    *  and we can use other standard algorithms as well.
     717             :   */
     718             :   template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
     719             :     class deque : protected _Deque_base<_Tp, _Alloc>
     720             :     {
     721             :       // concept requirements
     722             :       typedef typename _Alloc::value_type        _Alloc_value_type;
     723             :       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
     724             :       __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
     725             : 
     726             :       typedef _Deque_base<_Tp, _Alloc>           _Base;
     727             :       typedef typename _Base::_Tp_alloc_type     _Tp_alloc_type;
     728             : 
     729             :     public:
     730             :       typedef _Tp                                        value_type;
     731             :       typedef typename _Tp_alloc_type::pointer           pointer;
     732             :       typedef typename _Tp_alloc_type::const_pointer     const_pointer;
     733             :       typedef typename _Tp_alloc_type::reference         reference;
     734             :       typedef typename _Tp_alloc_type::const_reference   const_reference;
     735             :       typedef typename _Base::iterator                   iterator;
     736             :       typedef typename _Base::const_iterator             const_iterator;
     737             :       typedef std::reverse_iterator<const_iterator>      const_reverse_iterator;
     738             :       typedef std::reverse_iterator<iterator>            reverse_iterator;
     739             :       typedef size_t                             size_type;
     740             :       typedef ptrdiff_t                          difference_type;
     741             :       typedef _Alloc                             allocator_type;
     742             : 
     743             :     protected:
     744             :       typedef pointer*                           _Map_pointer;
     745             : 
     746           0 :       static size_t _S_buffer_size()
     747           0 :       { return __deque_buf_size(sizeof(_Tp)); }
     748             : 
     749             :       // Functions controlling memory layout, and nothing else.
     750             :       using _Base::_M_initialize_map;
     751             :       using _Base::_M_create_nodes;
     752             :       using _Base::_M_destroy_nodes;
     753             :       using _Base::_M_allocate_node;
     754             :       using _Base::_M_deallocate_node;
     755             :       using _Base::_M_allocate_map;
     756             :       using _Base::_M_deallocate_map;
     757             :       using _Base::_M_get_Tp_allocator;
     758             : 
     759             :       /** 
     760             :        *  A total of four data members accumulated down the hierarchy.
     761             :        *  May be accessed via _M_impl.*
     762             :        */
     763             :       using _Base::_M_impl;
     764             : 
     765             :     public:
     766             :       // [23.2.1.1] construct/copy/destroy
     767             :       // (assign() and get_allocator() are also listed in this section)
     768             :       /**
     769             :        *  @brief  Default constructor creates no elements.
     770             :        */
     771             :       deque()
     772             :       : _Base() { }
     773             : 
     774             :       /**
     775             :        *  @brief  Creates a %deque with no elements.
     776             :        *  @param  a  An allocator object.
     777             :        */
     778             :       explicit
     779             :       deque(const allocator_type& __a)
     780             :       : _Base(__a, 0) { }
     781             : 
     782             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
     783             :       /**
     784             :        *  @brief  Creates a %deque with default constructed elements.
     785             :        *  @param  n  The number of elements to initially create.
     786             :        *
     787             :        *  This constructor fills the %deque with @a n default
     788             :        *  constructed elements.
     789             :        */
     790             :       explicit
     791             :       deque(size_type __n)
     792             :       : _Base(__n)
     793             :       { _M_default_initialize(); }
     794             : 
     795             :       /**
     796             :        *  @brief  Creates a %deque with copies of an exemplar element.
     797             :        *  @param  n  The number of elements to initially create.
     798             :        *  @param  value  An element to copy.
     799             :        *  @param  a  An allocator.
     800             :        *
     801             :        *  This constructor fills the %deque with @a n copies of @a value.
     802             :        */
     803             :       deque(size_type __n, const value_type& __value,
     804             :             const allocator_type& __a = allocator_type())
     805             :       : _Base(__a, __n)
     806             :       { _M_fill_initialize(__value); }
     807             : #else
     808             :       /**
     809             :        *  @brief  Creates a %deque with copies of an exemplar element.
     810             :        *  @param  n  The number of elements to initially create.
     811             :        *  @param  value  An element to copy.
     812             :        *  @param  a  An allocator.
     813             :        *
     814             :        *  This constructor fills the %deque with @a n copies of @a value.
     815             :        */
     816             :       explicit
     817             :       deque(size_type __n, const value_type& __value = value_type(),
     818             :             const allocator_type& __a = allocator_type())
     819             :       : _Base(__a, __n)
     820             :       { _M_fill_initialize(__value); }
     821             : #endif
     822             : 
     823             :       /**
     824             :        *  @brief  %Deque copy constructor.
     825             :        *  @param  x  A %deque of identical element and allocator types.
     826             :        *
     827             :        *  The newly-created %deque uses a copy of the allocation object used
     828             :        *  by @a x.
     829             :        */
     830             :       deque(const deque& __x)
     831             :       : _Base(__x._M_get_Tp_allocator(), __x.size())
     832             :       { std::__uninitialized_copy_a(__x.begin(), __x.end(), 
     833             :                                     this->_M_impl._M_start,
     834             :                                     _M_get_Tp_allocator()); }
     835             : 
     836             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
     837             :       /**
     838             :        *  @brief  %Deque move constructor.
     839             :        *  @param  x  A %deque of identical element and allocator types.
     840             :        *
     841             :        *  The newly-created %deque contains the exact contents of @a x.
     842             :        *  The contents of @a x are a valid, but unspecified %deque.
     843             :        */
     844             :       deque(deque&& __x)
     845             :       : _Base(std::move(__x)) { }
     846             : 
     847             :       /**
     848             :        *  @brief  Builds a %deque from an initializer list.
     849             :        *  @param  l  An initializer_list.
     850             :        *  @param  a  An allocator object.
     851             :        *
     852             :        *  Create a %deque consisting of copies of the elements in the
     853             :        *  initializer_list @a l.
     854             :        *
     855             :        *  This will call the element type's copy constructor N times
     856             :        *  (where N is l.size()) and do no memory reallocation.
     857             :        */
     858             :       deque(initializer_list<value_type> __l,
     859             :             const allocator_type& __a = allocator_type())
     860             :       : _Base(__a)
     861             :       {
     862             :         _M_range_initialize(__l.begin(), __l.end(),
     863             :                             random_access_iterator_tag());
     864             :       }
     865             : #endif
     866             : 
     867             :       /**
     868             :        *  @brief  Builds a %deque from a range.
     869             :        *  @param  first  An input iterator.
     870             :        *  @param  last  An input iterator.
     871             :        *  @param  a  An allocator object.
     872             :        *
     873             :        *  Create a %deque consisting of copies of the elements from [first,
     874             :        *  last).
     875             :        *
     876             :        *  If the iterators are forward, bidirectional, or random-access, then
     877             :        *  this will call the elements' copy constructor N times (where N is
     878             :        *  distance(first,last)) and do no memory reallocation.  But if only
     879             :        *  input iterators are used, then this will do at most 2N calls to the
     880             :        *  copy constructor, and logN memory reallocations.
     881             :        */
     882             :       template<typename _InputIterator>
     883             :         deque(_InputIterator __first, _InputIterator __last,
     884             :               const allocator_type& __a = allocator_type())
     885             :         : _Base(__a)
     886             :         {
     887             :           // Check whether it's an integral type.  If so, it's not an iterator.
     888             :           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
     889             :           _M_initialize_dispatch(__first, __last, _Integral());
     890             :         }
     891             : 
     892             :       /**
     893             :        *  The dtor only erases the elements, and note that if the elements
     894             :        *  themselves are pointers, the pointed-to memory is not touched in any
     895             :        *  way.  Managing the pointer is the user's responsibility.
     896             :        */
     897      288577 :       ~deque()
     898      288577 :       { _M_destroy_data(begin(), end(), _M_get_Tp_allocator()); }
     899             : 
     900             :       /**
     901             :        *  @brief  %Deque assignment operator.
     902             :        *  @param  x  A %deque of identical element and allocator types.
     903             :        *
     904             :        *  All the elements of @a x are copied, but unlike the copy constructor,
     905             :        *  the allocator object is not copied.
     906             :        */
     907             :       deque&
     908             :       operator=(const deque& __x);
     909             : 
     910             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
     911             :       /**
     912             :        *  @brief  %Deque move assignment operator.
     913             :        *  @param  x  A %deque of identical element and allocator types.
     914             :        *
     915             :        *  The contents of @a x are moved into this deque (without copying).
     916             :        *  @a x is a valid, but unspecified %deque.
     917             :        */
     918             :       deque&
     919             :       operator=(deque&& __x)
     920             :       {
     921             :         // NB: DR 1204.
     922             :         // NB: DR 675.
     923             :         this->clear();
     924             :         this->swap(__x);
     925             :         return *this;
     926             :       }
     927             : 
     928             :       /**
     929             :        *  @brief  Assigns an initializer list to a %deque.
     930             :        *  @param  l  An initializer_list.
     931             :        *
     932             :        *  This function fills a %deque with copies of the elements in the
     933             :        *  initializer_list @a l.
     934             :        *
     935             :        *  Note that the assignment completely changes the %deque and that the
     936             :        *  resulting %deque's size is the same as the number of elements
     937             :        *  assigned.  Old data may be lost.
     938             :        */
     939             :       deque&
     940             :       operator=(initializer_list<value_type> __l)
     941             :       {
     942             :         this->assign(__l.begin(), __l.end());
     943             :         return *this;
     944             :       }
     945             : #endif
     946             : 
     947             :       /**
     948             :        *  @brief  Assigns a given value to a %deque.
     949             :        *  @param  n  Number of elements to be assigned.
     950             :        *  @param  val  Value to be assigned.
     951             :        *
     952             :        *  This function fills a %deque with @a n copies of the given
     953             :        *  value.  Note that the assignment completely changes the
     954             :        *  %deque and that the resulting %deque's size is the same as
     955             :        *  the number of elements assigned.  Old data may be lost.
     956             :        */
     957             :       void
     958             :       assign(size_type __n, const value_type& __val)
     959             :       { _M_fill_assign(__n, __val); }
     960             : 
     961             :       /**
     962             :        *  @brief  Assigns a range to a %deque.
     963             :        *  @param  first  An input iterator.
     964             :        *  @param  last   An input iterator.
     965             :        *
     966             :        *  This function fills a %deque with copies of the elements in the
     967             :        *  range [first,last).
     968             :        *
     969             :        *  Note that the assignment completely changes the %deque and that the
     970             :        *  resulting %deque's size is the same as the number of elements
     971             :        *  assigned.  Old data may be lost.
     972             :        */
     973             :       template<typename _InputIterator>
     974             :         void
     975             :         assign(_InputIterator __first, _InputIterator __last)
     976             :         {
     977             :           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
     978             :           _M_assign_dispatch(__first, __last, _Integral());
     979             :         }
     980             : 
     981             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
     982             :       /**
     983             :        *  @brief  Assigns an initializer list to a %deque.
     984             :        *  @param  l  An initializer_list.
     985             :        *
     986             :        *  This function fills a %deque with copies of the elements in the
     987             :        *  initializer_list @a l.
     988             :        *
     989             :        *  Note that the assignment completely changes the %deque and that the
     990             :        *  resulting %deque's size is the same as the number of elements
     991             :        *  assigned.  Old data may be lost.
     992             :        */
     993             :       void
     994             :       assign(initializer_list<value_type> __l)
     995             :       { this->assign(__l.begin(), __l.end()); }
     996             : #endif
     997             : 
     998             :       /// Get a copy of the memory allocation object.
     999             :       allocator_type
    1000             :       get_allocator() const
    1001             :       { return _Base::get_allocator(); }
    1002             : 
    1003             :       // iterators
    1004             :       /**
    1005             :        *  Returns a read/write iterator that points to the first element in the
    1006             :        *  %deque.  Iteration is done in ordinary element order.
    1007             :        */
    1008             :       iterator
    1009      288577 :       begin()
    1010      288577 :       { return this->_M_impl._M_start; }
    1011             : 
    1012             :       /**
    1013             :        *  Returns a read-only (constant) iterator that points to the first
    1014             :        *  element in the %deque.  Iteration is done in ordinary element order.
    1015             :        */
    1016             :       const_iterator
    1017             :       begin() const
    1018             :       { return this->_M_impl._M_start; }
    1019             : 
    1020             :       /**
    1021             :        *  Returns a read/write iterator that points one past the last
    1022             :        *  element in the %deque.  Iteration is done in ordinary
    1023             :        *  element order.
    1024             :        */
    1025             :       iterator
    1026      288577 :       end()
    1027      288577 :       { return this->_M_impl._M_finish; }
    1028             : 
    1029             :       /**
    1030             :        *  Returns a read-only (constant) iterator that points one past
    1031             :        *  the last element in the %deque.  Iteration is done in
    1032             :        *  ordinary element order.
    1033             :        */
    1034             :       const_iterator
    1035             :       end() const
    1036             :       { return this->_M_impl._M_finish; }
    1037             : 
    1038             :       /**
    1039             :        *  Returns a read/write reverse iterator that points to the
    1040             :        *  last element in the %deque.  Iteration is done in reverse
    1041             :        *  element order.
    1042             :        */
    1043             :       reverse_iterator
    1044             :       rbegin()
    1045             :       { return reverse_iterator(this->_M_impl._M_finish); }
    1046             : 
    1047             :       /**
    1048             :        *  Returns a read-only (constant) reverse iterator that points
    1049             :        *  to the last element in the %deque.  Iteration is done in
    1050             :        *  reverse element order.
    1051             :        */
    1052             :       const_reverse_iterator
    1053             :       rbegin() const
    1054             :       { return const_reverse_iterator(this->_M_impl._M_finish); }
    1055             : 
    1056             :       /**
    1057             :        *  Returns a read/write reverse iterator that points to one
    1058             :        *  before the first element in the %deque.  Iteration is done
    1059             :        *  in reverse element order.
    1060             :        */
    1061             :       reverse_iterator
    1062             :       rend()
    1063             :       { return reverse_iterator(this->_M_impl._M_start); }
    1064             : 
    1065             :       /**
    1066             :        *  Returns a read-only (constant) reverse iterator that points
    1067             :        *  to one before the first element in the %deque.  Iteration is
    1068             :        *  done in reverse element order.
    1069             :        */
    1070             :       const_reverse_iterator
    1071             :       rend() const
    1072             :       { return const_reverse_iterator(this->_M_impl._M_start); }
    1073             : 
    1074             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
    1075             :       /**
    1076             :        *  Returns a read-only (constant) iterator that points to the first
    1077             :        *  element in the %deque.  Iteration is done in ordinary element order.
    1078             :        */
    1079             :       const_iterator
    1080             :       cbegin() const
    1081             :       { return this->_M_impl._M_start; }
    1082             : 
    1083             :       /**
    1084             :        *  Returns a read-only (constant) iterator that points one past
    1085             :        *  the last element in the %deque.  Iteration is done in
    1086             :        *  ordinary element order.
    1087             :        */
    1088             :       const_iterator
    1089             :       cend() const
    1090             :       { return this->_M_impl._M_finish; }
    1091             : 
    1092             :       /**
    1093             :        *  Returns a read-only (constant) reverse iterator that points
    1094             :        *  to the last element in the %deque.  Iteration is done in
    1095             :        *  reverse element order.
    1096             :        */
    1097             :       const_reverse_iterator
    1098             :       crbegin() const
    1099             :       { return const_reverse_iterator(this->_M_impl._M_finish); }
    1100             : 
    1101             :       /**
    1102             :        *  Returns a read-only (constant) reverse iterator that points
    1103             :        *  to one before the first element in the %deque.  Iteration is
    1104             :        *  done in reverse element order.
    1105             :        */
    1106             :       const_reverse_iterator
    1107             :       crend() const
    1108             :       { return const_reverse_iterator(this->_M_impl._M_start); }
    1109             : #endif
    1110             : 
    1111             :       // [23.2.1.2] capacity
    1112             :       /**  Returns the number of elements in the %deque.  */
    1113             :       size_type
    1114             :       size() const
    1115             :       { return this->_M_impl._M_finish - this->_M_impl._M_start; }
    1116             : 
    1117             :       /**  Returns the size() of the largest possible %deque.  */
    1118             :       size_type
    1119             :       max_size() const
    1120             :       { return _M_get_Tp_allocator().max_size(); }
    1121             : 
    1122             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
    1123             :       /**
    1124             :        *  @brief  Resizes the %deque to the specified number of elements.
    1125             :        *  @param  new_size  Number of elements the %deque should contain.
    1126             :        *
    1127             :        *  This function will %resize the %deque to the specified
    1128             :        *  number of elements.  If the number is smaller than the
    1129             :        *  %deque's current size the %deque is truncated, otherwise
    1130             :        *  default constructed elements are appended.
    1131             :        */
    1132             :       void
    1133             :       resize(size_type __new_size)
    1134             :       {
    1135             :         const size_type __len = size();
    1136             :         if (__new_size > __len)
    1137             :           _M_default_append(__new_size - __len);
    1138             :         else if (__new_size < __len)
    1139             :           _M_erase_at_end(this->_M_impl._M_start
    1140             :                           + difference_type(__new_size));
    1141             :       }
    1142             : 
    1143             :       /**
    1144             :        *  @brief  Resizes the %deque to the specified number of elements.
    1145             :        *  @param  new_size  Number of elements the %deque should contain.
    1146             :        *  @param  x  Data with which new elements should be populated.
    1147             :        *
    1148             :        *  This function will %resize the %deque to the specified
    1149             :        *  number of elements.  If the number is smaller than the
    1150             :        *  %deque's current size the %deque is truncated, otherwise the
    1151             :        *  %deque is extended and new elements are populated with given
    1152             :        *  data.
    1153             :        */
    1154             :       void
    1155             :       resize(size_type __new_size, const value_type& __x)
    1156             :       {
    1157             :         const size_type __len = size();
    1158             :         if (__new_size > __len)
    1159             :           insert(this->_M_impl._M_finish, __new_size - __len, __x);
    1160             :         else if (__new_size < __len)
    1161             :           _M_erase_at_end(this->_M_impl._M_start
    1162             :                           + difference_type(__new_size));
    1163             :       }
    1164             : #else
    1165             :       /**
    1166             :        *  @brief  Resizes the %deque to the specified number of elements.
    1167             :        *  @param  new_size  Number of elements the %deque should contain.
    1168             :        *  @param  x  Data with which new elements should be populated.
    1169             :        *
    1170             :        *  This function will %resize the %deque to the specified
    1171             :        *  number of elements.  If the number is smaller than the
    1172             :        *  %deque's current size the %deque is truncated, otherwise the
    1173             :        *  %deque is extended and new elements are populated with given
    1174             :        *  data.
    1175             :        */
    1176             :       void
    1177             :       resize(size_type __new_size, value_type __x = value_type())
    1178             :       {
    1179             :         const size_type __len = size();
    1180             :         if (__new_size > __len)
    1181             :           insert(this->_M_impl._M_finish, __new_size - __len, __x);
    1182             :         else if (__new_size < __len)
    1183             :           _M_erase_at_end(this->_M_impl._M_start
    1184             :                           + difference_type(__new_size));
    1185             :       }
    1186             : #endif
    1187             : 
    1188             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
    1189             :       /**  A non-binding request to reduce memory use.  */
    1190             :       void
    1191             :       shrink_to_fit()
    1192             :       { std::__shrink_to_fit<deque>::_S_do_it(*this); }
    1193             : #endif
    1194             : 
    1195             :       /**
    1196             :        *  Returns true if the %deque is empty.  (Thus begin() would
    1197             :        *  equal end().)
    1198             :        */
    1199             :       bool
    1200             :       empty() const
    1201             :       { return this->_M_impl._M_finish == this->_M_impl._M_start; }
    1202             : 
    1203             :       // element access
    1204             :       /**
    1205             :        *  @brief Subscript access to the data contained in the %deque.
    1206             :        *  @param n The index of the element for which data should be
    1207             :        *  accessed.
    1208             :        *  @return  Read/write reference to data.
    1209             :        *
    1210             :        *  This operator allows for easy, array-style, data access.
    1211             :        *  Note that data access with this operator is unchecked and
    1212             :        *  out_of_range lookups are not defined. (For checked lookups
    1213             :        *  see at().)
    1214             :        */
    1215             :       reference
    1216             :       operator[](size_type __n)
    1217             :       { return this->_M_impl._M_start[difference_type(__n)]; }
    1218             : 
    1219             :       /**
    1220             :        *  @brief Subscript access to the data contained in the %deque.
    1221             :        *  @param n The index of the element for which data should be
    1222             :        *  accessed.
    1223             :        *  @return  Read-only (constant) reference to data.
    1224             :        *
    1225             :        *  This operator allows for easy, array-style, data access.
    1226             :        *  Note that data access with this operator is unchecked and
    1227             :        *  out_of_range lookups are not defined. (For checked lookups
    1228             :        *  see at().)
    1229             :        */
    1230             :       const_reference
    1231             :       operator[](size_type __n) const
    1232             :       { return this->_M_impl._M_start[difference_type(__n)]; }
    1233             : 
    1234             :     protected:
    1235             :       /// Safety check used only from at().
    1236             :       void
    1237             :       _M_range_check(size_type __n) const
    1238             :       {
    1239             :         if (__n >= this->size())
    1240             :           __throw_out_of_range(__N("deque::_M_range_check"));
    1241             :       }
    1242             : 
    1243             :     public:
    1244             :       /**
    1245             :        *  @brief  Provides access to the data contained in the %deque.
    1246             :        *  @param n The index of the element for which data should be
    1247             :        *  accessed.
    1248             :        *  @return  Read/write reference to data.
    1249             :        *  @throw  std::out_of_range  If @a n is an invalid index.
    1250             :        *
    1251             :        *  This function provides for safer data access.  The parameter
    1252             :        *  is first checked that it is in the range of the deque.  The
    1253             :        *  function throws out_of_range if the check fails.
    1254             :        */
    1255             :       reference
    1256             :       at(size_type __n)
    1257             :       {
    1258             :         _M_range_check(__n);
    1259             :         return (*this)[__n];
    1260             :       }
    1261             : 
    1262             :       /**
    1263             :        *  @brief  Provides access to the data contained in the %deque.
    1264             :        *  @param n The index of the element for which data should be
    1265             :        *  accessed.
    1266             :        *  @return  Read-only (constant) reference to data.
    1267             :        *  @throw  std::out_of_range  If @a n is an invalid index.
    1268             :        *
    1269             :        *  This function provides for safer data access.  The parameter is first
    1270             :        *  checked that it is in the range of the deque.  The function throws
    1271             :        *  out_of_range if the check fails.
    1272             :        */
    1273             :       const_reference
    1274             :       at(size_type __n) const
    1275             :       {
    1276             :         _M_range_check(__n);
    1277             :         return (*this)[__n];
    1278             :       }
    1279             : 
    1280             :       /**
    1281             :        *  Returns a read/write reference to the data at the first
    1282             :        *  element of the %deque.
    1283             :        */
    1284             :       reference
    1285             :       front()
    1286             :       { return *begin(); }
    1287             : 
    1288             :       /**
    1289             :        *  Returns a read-only (constant) reference to the data at the first
    1290             :        *  element of the %deque.
    1291             :        */
    1292             :       const_reference
    1293             :       front() const
    1294             :       { return *begin(); }
    1295             : 
    1296             :       /**
    1297             :        *  Returns a read/write reference to the data at the last element of the
    1298             :        *  %deque.
    1299             :        */
    1300             :       reference
    1301             :       back()
    1302             :       {
    1303             :         iterator __tmp = end();
    1304             :         --__tmp;
    1305             :         return *__tmp;
    1306             :       }
    1307             : 
    1308             :       /**
    1309             :        *  Returns a read-only (constant) reference to the data at the last
    1310             :        *  element of the %deque.
    1311             :        */
    1312             :       const_reference
    1313             :       back() const
    1314             :       {
    1315             :         const_iterator __tmp = end();
    1316             :         --__tmp;
    1317             :         return *__tmp;
    1318             :       }
    1319             : 
    1320             :       // [23.2.1.2] modifiers
    1321             :       /**
    1322             :        *  @brief  Add data to the front of the %deque.
    1323             :        *  @param  x  Data to be added.
    1324             :        *
    1325             :        *  This is a typical stack operation.  The function creates an
    1326             :        *  element at the front of the %deque and assigns the given
    1327             :        *  data to it.  Due to the nature of a %deque this operation
    1328             :        *  can be done in constant time.
    1329             :        */
    1330             :       void
    1331             :       push_front(const value_type& __x)
    1332             :       {
    1333             :         if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
    1334             :           {
    1335             :             this->_M_impl.construct(this->_M_impl._M_start._M_cur - 1, __x);
    1336             :             --this->_M_impl._M_start._M_cur;
    1337             :           }
    1338             :         else
    1339             :           _M_push_front_aux(__x);
    1340             :       }
    1341             : 
    1342             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
    1343             :       void
    1344             :       push_front(value_type&& __x)
    1345             :       { emplace_front(std::move(__x)); }
    1346             : 
    1347             :       template<typename... _Args>
    1348             :         void
    1349             :         emplace_front(_Args&&... __args);
    1350             : #endif
    1351             : 
    1352             :       /**
    1353             :        *  @brief  Add data to the end of the %deque.
    1354             :        *  @param  x  Data to be added.
    1355             :        *
    1356             :        *  This is a typical stack operation.  The function creates an
    1357             :        *  element at the end of the %deque and assigns the given data
    1358             :        *  to it.  Due to the nature of a %deque this operation can be
    1359             :        *  done in constant time.
    1360             :        */
    1361             :       void
    1362             :       push_back(const value_type& __x)
    1363             :       {
    1364             :         if (this->_M_impl._M_finish._M_cur
    1365             :             != this->_M_impl._M_finish._M_last - 1)
    1366             :           {
    1367             :             this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __x);
    1368             :             ++this->_M_impl._M_finish._M_cur;
    1369             :           }
    1370             :         else
    1371             :           _M_push_back_aux(__x);
    1372             :       }
    1373             : 
    1374             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
    1375             :       void
    1376             :       push_back(value_type&& __x)
    1377             :       { emplace_back(std::move(__x)); }
    1378             : 
    1379             :       template<typename... _Args>
    1380             :         void
    1381             :         emplace_back(_Args&&... __args);
    1382             : #endif
    1383             : 
    1384             :       /**
    1385             :        *  @brief  Removes first element.
    1386             :        *
    1387             :        *  This is a typical stack operation.  It shrinks the %deque by one.
    1388             :        *
    1389             :        *  Note that no data is returned, and if the first element's data is
    1390             :        *  needed, it should be retrieved before pop_front() is called.
    1391             :        */
    1392             :       void
    1393             :       pop_front()
    1394             :       {
    1395             :         if (this->_M_impl._M_start._M_cur
    1396             :             != this->_M_impl._M_start._M_last - 1)
    1397             :           {
    1398             :             this->_M_impl.destroy(this->_M_impl._M_start._M_cur);
    1399             :             ++this->_M_impl._M_start._M_cur;
    1400             :           }
    1401             :         else
    1402             :           _M_pop_front_aux();
    1403             :       }
    1404             : 
    1405             :       /**
    1406             :        *  @brief  Removes last element.
    1407             :        *
    1408             :        *  This is a typical stack operation.  It shrinks the %deque by one.
    1409             :        *
    1410             :        *  Note that no data is returned, and if the last element's data is
    1411             :        *  needed, it should be retrieved before pop_back() is called.
    1412             :        */
    1413             :       void
    1414             :       pop_back()
    1415             :       {
    1416             :         if (this->_M_impl._M_finish._M_cur
    1417             :             != this->_M_impl._M_finish._M_first)
    1418             :           {
    1419             :             --this->_M_impl._M_finish._M_cur;
    1420             :             this->_M_impl.destroy(this->_M_impl._M_finish._M_cur);
    1421             :           }
    1422             :         else
    1423             :           _M_pop_back_aux();
    1424             :       }
    1425             : 
    1426             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
    1427             :       /**
    1428             :        *  @brief  Inserts an object in %deque before specified iterator.
    1429             :        *  @param  position  An iterator into the %deque.
    1430             :        *  @param  args  Arguments.
    1431             :        *  @return  An iterator that points to the inserted data.
    1432             :        *
    1433             :        *  This function will insert an object of type T constructed
    1434             :        *  with T(std::forward<Args>(args)...) before the specified location.
    1435             :        */
    1436             :       template<typename... _Args>
    1437             :         iterator
    1438             :         emplace(iterator __position, _Args&&... __args);
    1439             : #endif
    1440             : 
    1441             :       /**
    1442             :        *  @brief  Inserts given value into %deque before specified iterator.
    1443             :        *  @param  position  An iterator into the %deque.
    1444             :        *  @param  x  Data to be inserted.
    1445             :        *  @return  An iterator that points to the inserted data.
    1446             :        *
    1447             :        *  This function will insert a copy of the given value before the
    1448             :        *  specified location.
    1449             :        */
    1450             :       iterator
    1451             :       insert(iterator __position, const value_type& __x);
    1452             : 
    1453             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
    1454             :       /**
    1455             :        *  @brief  Inserts given rvalue into %deque before specified iterator.
    1456             :        *  @param  position  An iterator into the %deque.
    1457             :        *  @param  x  Data to be inserted.
    1458             :        *  @return  An iterator that points to the inserted data.
    1459             :        *
    1460             :        *  This function will insert a copy of the given rvalue before the
    1461             :        *  specified location.
    1462             :        */
    1463             :       iterator
    1464             :       insert(iterator __position, value_type&& __x)
    1465             :       { return emplace(__position, std::move(__x)); }
    1466             : 
    1467             :       /**
    1468             :        *  @brief  Inserts an initializer list into the %deque.
    1469             :        *  @param  p  An iterator into the %deque.
    1470             :        *  @param  l  An initializer_list.
    1471             :        *
    1472             :        *  This function will insert copies of the data in the
    1473             :        *  initializer_list @a l into the %deque before the location
    1474             :        *  specified by @a p.  This is known as <em>list insert</em>.
    1475             :        */
    1476             :       void
    1477             :       insert(iterator __p, initializer_list<value_type> __l)
    1478             :       { this->insert(__p, __l.begin(), __l.end()); }
    1479             : #endif
    1480             : 
    1481             :       /**
    1482             :        *  @brief  Inserts a number of copies of given data into the %deque.
    1483             :        *  @param  position  An iterator into the %deque.
    1484             :        *  @param  n  Number of elements to be inserted.
    1485             :        *  @param  x  Data to be inserted.
    1486             :        *
    1487             :        *  This function will insert a specified number of copies of the given
    1488             :        *  data before the location specified by @a position.
    1489             :        */
    1490             :       void
    1491             :       insert(iterator __position, size_type __n, const value_type& __x)
    1492             :       { _M_fill_insert(__position, __n, __x); }
    1493             : 
    1494             :       /**
    1495             :        *  @brief  Inserts a range into the %deque.
    1496             :        *  @param  position  An iterator into the %deque.
    1497             :        *  @param  first  An input iterator.
    1498             :        *  @param  last   An input iterator.
    1499             :        *
    1500             :        *  This function will insert copies of the data in the range
    1501             :        *  [first,last) into the %deque before the location specified
    1502             :        *  by @a pos.  This is known as <em>range insert</em>.
    1503             :        */
    1504             :       template<typename _InputIterator>
    1505             :         void
    1506             :         insert(iterator __position, _InputIterator __first,
    1507             :                _InputIterator __last)
    1508             :         {
    1509             :           // Check whether it's an integral type.  If so, it's not an iterator.
    1510             :           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
    1511             :           _M_insert_dispatch(__position, __first, __last, _Integral());
    1512             :         }
    1513             : 
    1514             :       /**
    1515             :        *  @brief  Remove element at given position.
    1516             :        *  @param  position  Iterator pointing to element to be erased.
    1517             :        *  @return  An iterator pointing to the next element (or end()).
    1518             :        *
    1519             :        *  This function will erase the element at the given position and thus
    1520             :        *  shorten the %deque by one.
    1521             :        *
    1522             :        *  The user is cautioned that
    1523             :        *  this function only erases the element, and that if the element is
    1524             :        *  itself a pointer, the pointed-to memory is not touched in any way.
    1525             :        *  Managing the pointer is the user's responsibility.
    1526             :        */
    1527             :       iterator
    1528             :       erase(iterator __position);
    1529             : 
    1530             :       /**
    1531             :        *  @brief  Remove a range of elements.
    1532             :        *  @param  first  Iterator pointing to the first element to be erased.
    1533             :        *  @param  last  Iterator pointing to one past the last element to be
    1534             :        *                erased.
    1535             :        *  @return  An iterator pointing to the element pointed to by @a last
    1536             :        *           prior to erasing (or end()).
    1537             :        *
    1538             :        *  This function will erase the elements in the range [first,last) and
    1539             :        *  shorten the %deque accordingly.
    1540             :        *
    1541             :        *  The user is cautioned that
    1542             :        *  this function only erases the elements, and that if the elements
    1543             :        *  themselves are pointers, the pointed-to memory is not touched in any
    1544             :        *  way.  Managing the pointer is the user's responsibility.
    1545             :        */
    1546             :       iterator
    1547             :       erase(iterator __first, iterator __last);
    1548             : 
    1549             :       /**
    1550             :        *  @brief  Swaps data with another %deque.
    1551             :        *  @param  x  A %deque of the same element and allocator types.
    1552             :        *
    1553             :        *  This exchanges the elements between two deques in constant time.
    1554             :        *  (Four pointers, so it should be quite fast.)
    1555             :        *  Note that the global std::swap() function is specialized such that
    1556             :        *  std::swap(d1,d2) will feed to this function.
    1557             :        */
    1558             :       void
    1559             :       swap(deque& __x)
    1560             :       {
    1561             :         std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
    1562             :         std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
    1563             :         std::swap(this->_M_impl._M_map, __x._M_impl._M_map);
    1564             :         std::swap(this->_M_impl._M_map_size, __x._M_impl._M_map_size);
    1565             : 
    1566             :         // _GLIBCXX_RESOLVE_LIB_DEFECTS
    1567             :         // 431. Swapping containers with unequal allocators.
    1568             :         std::__alloc_swap<_Tp_alloc_type>::_S_do_it(_M_get_Tp_allocator(),
    1569             :                                                     __x._M_get_Tp_allocator());
    1570             :       }
    1571             : 
    1572             :       /**
    1573             :        *  Erases all the elements.  Note that this function only erases the
    1574             :        *  elements, and that if the elements themselves are pointers, the
    1575             :        *  pointed-to memory is not touched in any way.  Managing the pointer is
    1576             :        *  the user's responsibility.
    1577             :        */
    1578             :       void
    1579             :       clear()
    1580             :       { _M_erase_at_end(begin()); }
    1581             : 
    1582             :     protected:
    1583             :       // Internal constructor functions follow.
    1584             : 
    1585             :       // called by the range constructor to implement [23.1.1]/9
    1586             : 
    1587             :       // _GLIBCXX_RESOLVE_LIB_DEFECTS
    1588             :       // 438. Ambiguity in the "do the right thing" clause
    1589             :       template<typename _Integer>
    1590             :         void
    1591             :         _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
    1592             :         {
    1593             :           _M_initialize_map(static_cast<size_type>(__n));
    1594             :           _M_fill_initialize(__x);
    1595             :         }
    1596             : 
    1597             :       // called by the range constructor to implement [23.1.1]/9
    1598             :       template<typename _InputIterator>
    1599             :         void
    1600             :         _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
    1601             :                                __false_type)
    1602             :         {
    1603             :           typedef typename std::iterator_traits<_InputIterator>::
    1604             :             iterator_category _IterCategory;
    1605             :           _M_range_initialize(__first, __last, _IterCategory());
    1606             :         }
    1607             : 
    1608             :       // called by the second initialize_dispatch above
    1609             :       //@{
    1610             :       /**
    1611             :        *  @brief Fills the deque with whatever is in [first,last).
    1612             :        *  @param  first  An input iterator.
    1613             :        *  @param  last  An input iterator.
    1614             :        *  @return   Nothing.
    1615             :        *
    1616             :        *  If the iterators are actually forward iterators (or better), then the
    1617             :        *  memory layout can be done all at once.  Else we move forward using
    1618             :        *  push_back on each value from the iterator.
    1619             :        */
    1620             :       template<typename _InputIterator>
    1621             :         void
    1622             :         _M_range_initialize(_InputIterator __first, _InputIterator __last,
    1623             :                             std::input_iterator_tag);
    1624             : 
    1625             :       // called by the second initialize_dispatch above
    1626             :       template<typename _ForwardIterator>
    1627             :         void
    1628             :         _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
    1629             :                             std::forward_iterator_tag);
    1630             :       //@}
    1631             : 
    1632             :       /**
    1633             :        *  @brief Fills the %deque with copies of value.
    1634             :        *  @param  value  Initial value.
    1635             :        *  @return   Nothing.
    1636             :        *  @pre _M_start and _M_finish have already been initialized,
    1637             :        *  but none of the %deque's elements have yet been constructed.
    1638             :        *
    1639             :        *  This function is called only when the user provides an explicit size
    1640             :        *  (with or without an explicit exemplar value).
    1641             :        */
    1642             :       void
    1643             :       _M_fill_initialize(const value_type& __value);
    1644             : 
    1645             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
    1646             :       // called by deque(n).
    1647             :       void
    1648             :       _M_default_initialize();
    1649             : #endif
    1650             : 
    1651             :       // Internal assign functions follow.  The *_aux functions do the actual
    1652             :       // assignment work for the range versions.
    1653             : 
    1654             :       // called by the range assign to implement [23.1.1]/9
    1655             : 
    1656             :       // _GLIBCXX_RESOLVE_LIB_DEFECTS
    1657             :       // 438. Ambiguity in the "do the right thing" clause
    1658             :       template<typename _Integer>
    1659             :         void
    1660             :         _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
    1661             :         { _M_fill_assign(__n, __val); }
    1662             : 
    1663             :       // called by the range assign to implement [23.1.1]/9
    1664             :       template<typename _InputIterator>
    1665             :         void
    1666             :         _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
    1667             :                            __false_type)
    1668             :         {
    1669             :           typedef typename std::iterator_traits<_InputIterator>::
    1670             :             iterator_category _IterCategory;
    1671             :           _M_assign_aux(__first, __last, _IterCategory());
    1672             :         }
    1673             : 
    1674             :       // called by the second assign_dispatch above
    1675             :       template<typename _InputIterator>
    1676             :         void
    1677             :         _M_assign_aux(_InputIterator __first, _InputIterator __last,
    1678             :                       std::input_iterator_tag);
    1679             : 
    1680             :       // called by the second assign_dispatch above
    1681             :       template<typename _ForwardIterator>
    1682             :         void
    1683             :         _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
    1684             :                       std::forward_iterator_tag)
    1685             :         {
    1686             :           const size_type __len = std::distance(__first, __last);
    1687             :           if (__len > size())
    1688             :             {
    1689             :               _ForwardIterator __mid = __first;
    1690             :               std::advance(__mid, size());
    1691             :               std::copy(__first, __mid, begin());
    1692             :               insert(end(), __mid, __last);
    1693             :             }
    1694             :           else
    1695             :             _M_erase_at_end(std::copy(__first, __last, begin()));
    1696             :         }
    1697             : 
    1698             :       // Called by assign(n,t), and the range assign when it turns out
    1699             :       // to be the same thing.
    1700             :       void
    1701             :       _M_fill_assign(size_type __n, const value_type& __val)
    1702             :       {
    1703             :         if (__n > size())
    1704             :           {
    1705             :             std::fill(begin(), end(), __val);
    1706             :             insert(end(), __n - size(), __val);
    1707             :           }
    1708             :         else
    1709             :           {
    1710             :             _M_erase_at_end(begin() + difference_type(__n));
    1711             :             std::fill(begin(), end(), __val);
    1712             :           }
    1713             :       }
    1714             : 
    1715             :       //@{
    1716             :       /// Helper functions for push_* and pop_*.
    1717             : #ifndef __GXX_EXPERIMENTAL_CXX0X__
    1718             :       void _M_push_back_aux(const value_type&);
    1719             : 
    1720             :       void _M_push_front_aux(const value_type&);
    1721             : #else
    1722             :       template<typename... _Args>
    1723             :         void _M_push_back_aux(_Args&&... __args);
    1724             : 
    1725             :       template<typename... _Args>
    1726             :         void _M_push_front_aux(_Args&&... __args);
    1727             : #endif
    1728             : 
    1729             :       void _M_pop_back_aux();
    1730             : 
    1731             :       void _M_pop_front_aux();
    1732             :       //@}
    1733             : 
    1734             :       // Internal insert functions follow.  The *_aux functions do the actual
    1735             :       // insertion work when all shortcuts fail.
    1736             : 
    1737             :       // called by the range insert to implement [23.1.1]/9
    1738             : 
    1739             :       // _GLIBCXX_RESOLVE_LIB_DEFECTS
    1740             :       // 438. Ambiguity in the "do the right thing" clause
    1741             :       template<typename _Integer>
    1742             :         void
    1743             :         _M_insert_dispatch(iterator __pos,
    1744             :                            _Integer __n, _Integer __x, __true_type)
    1745             :         { _M_fill_insert(__pos, __n, __x); }
    1746             : 
    1747             :       // called by the range insert to implement [23.1.1]/9
    1748             :       template<typename _InputIterator>
    1749             :         void
    1750             :         _M_insert_dispatch(iterator __pos,
    1751             :                            _InputIterator __first, _InputIterator __last,
    1752             :                            __false_type)
    1753             :         {
    1754             :           typedef typename std::iterator_traits<_InputIterator>::
    1755             :             iterator_category _IterCategory;
    1756             :           _M_range_insert_aux(__pos, __first, __last, _IterCategory());
    1757             :         }
    1758             : 
    1759             :       // called by the second insert_dispatch above
    1760             :       template<typename _InputIterator>
    1761             :         void
    1762             :         _M_range_insert_aux(iterator __pos, _InputIterator __first,
    1763             :                             _InputIterator __last, std::input_iterator_tag);
    1764             : 
    1765             :       // called by the second insert_dispatch above
    1766             :       template<typename _ForwardIterator>
    1767             :         void
    1768             :         _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
    1769             :                             _ForwardIterator __last, std::forward_iterator_tag);
    1770             : 
    1771             :       // Called by insert(p,n,x), and the range insert when it turns out to be
    1772             :       // the same thing.  Can use fill functions in optimal situations,
    1773             :       // otherwise passes off to insert_aux(p,n,x).
    1774             :       void
    1775             :       _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
    1776             : 
    1777             :       // called by insert(p,x)
    1778             : #ifndef __GXX_EXPERIMENTAL_CXX0X__
    1779             :       iterator
    1780             :       _M_insert_aux(iterator __pos, const value_type& __x);
    1781             : #else
    1782             :       template<typename... _Args>
    1783             :         iterator
    1784             :         _M_insert_aux(iterator __pos, _Args&&... __args);
    1785             : #endif
    1786             : 
    1787             :       // called by insert(p,n,x) via fill_insert
    1788             :       void
    1789             :       _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
    1790             : 
    1791             :       // called by range_insert_aux for forward iterators
    1792             :       template<typename _ForwardIterator>
    1793             :         void
    1794             :         _M_insert_aux(iterator __pos,
    1795             :                       _ForwardIterator __first, _ForwardIterator __last,
    1796             :                       size_type __n);
    1797             : 
    1798             : 
    1799             :       // Internal erase functions follow.
    1800             : 
    1801             :       void
    1802             :       _M_destroy_data_aux(iterator __first, iterator __last);
    1803             : 
    1804             :       // Called by ~deque().
    1805             :       // NB: Doesn't deallocate the nodes.
    1806             :       template<typename _Alloc1>
    1807             :         void
    1808             :         _M_destroy_data(iterator __first, iterator __last, const _Alloc1&)
    1809             :         { _M_destroy_data_aux(__first, __last); }
    1810             : 
    1811             :       void
    1812      288577 :       _M_destroy_data(iterator __first, iterator __last,
    1813             :                       const std::allocator<_Tp>&)
    1814             :       {
    1815             :         if (!__has_trivial_destructor(value_type))
    1816      288577 :           _M_destroy_data_aux(__first, __last);
    1817      288577 :       }
    1818             : 
    1819             :       // Called by erase(q1, q2).
    1820             :       void
    1821             :       _M_erase_at_begin(iterator __pos)
    1822             :       {
    1823             :         _M_destroy_data(begin(), __pos, _M_get_Tp_allocator());
    1824             :         _M_destroy_nodes(this->_M_impl._M_start._M_node, __pos._M_node);
    1825             :         this->_M_impl._M_start = __pos;
    1826             :       }
    1827             : 
    1828             :       // Called by erase(q1, q2), resize(), clear(), _M_assign_aux,
    1829             :       // _M_fill_assign, operator=.
    1830             :       void
    1831             :       _M_erase_at_end(iterator __pos)
    1832             :       {
    1833             :         _M_destroy_data(__pos, end(), _M_get_Tp_allocator());
    1834             :         _M_destroy_nodes(__pos._M_node + 1,
    1835             :                          this->_M_impl._M_finish._M_node + 1);
    1836             :         this->_M_impl._M_finish = __pos;
    1837             :       }
    1838             : 
    1839             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
    1840             :       // Called by resize(sz).
    1841             :       void
    1842             :       _M_default_append(size_type __n);
    1843             : #endif
    1844             : 
    1845             :       //@{
    1846             :       /// Memory-handling helpers for the previous internal insert functions.
    1847             :       iterator
    1848             :       _M_reserve_elements_at_front(size_type __n)
    1849             :       {
    1850             :         const size_type __vacancies = this->_M_impl._M_start._M_cur
    1851             :                                       - this->_M_impl._M_start._M_first;
    1852             :         if (__n > __vacancies)
    1853             :           _M_new_elements_at_front(__n - __vacancies);
    1854             :         return this->_M_impl._M_start - difference_type(__n);
    1855             :       }
    1856             : 
    1857             :       iterator
    1858             :       _M_reserve_elements_at_back(size_type __n)
    1859             :       {
    1860             :         const size_type __vacancies = (this->_M_impl._M_finish._M_last
    1861             :                                        - this->_M_impl._M_finish._M_cur) - 1;
    1862             :         if (__n > __vacancies)
    1863             :           _M_new_elements_at_back(__n - __vacancies);
    1864             :         return this->_M_impl._M_finish + difference_type(__n);
    1865             :       }
    1866             : 
    1867             :       void
    1868             :       _M_new_elements_at_front(size_type __new_elements);
    1869             : 
    1870             :       void
    1871             :       _M_new_elements_at_back(size_type __new_elements);
    1872             :       //@}
    1873             : 
    1874             : 
    1875             :       //@{
    1876             :       /**
    1877             :        *  @brief Memory-handling helpers for the major %map.
    1878             :        *
    1879             :        *  Makes sure the _M_map has space for new nodes.  Does not
    1880             :        *  actually add the nodes.  Can invalidate _M_map pointers.
    1881             :        *  (And consequently, %deque iterators.)
    1882             :        */
    1883             :       void
    1884             :       _M_reserve_map_at_back(size_type __nodes_to_add = 1)
    1885             :       {
    1886             :         if (__nodes_to_add + 1 > this->_M_impl._M_map_size
    1887             :             - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
    1888             :           _M_reallocate_map(__nodes_to_add, false);
    1889             :       }
    1890             : 
    1891             :       void
    1892             :       _M_reserve_map_at_front(size_type __nodes_to_add = 1)
    1893             :       {
    1894             :         if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node
    1895             :                                        - this->_M_impl._M_map))
    1896             :           _M_reallocate_map(__nodes_to_add, true);
    1897             :       }
    1898             : 
    1899             :       void
    1900             :       _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
    1901             :       //@}
    1902             :     };
    1903             : 
    1904             : 
    1905             :   /**
    1906             :    *  @brief  Deque equality comparison.
    1907             :    *  @param  x  A %deque.
    1908             :    *  @param  y  A %deque of the same type as @a x.
    1909             :    *  @return  True iff the size and elements of the deques are equal.
    1910             :    *
    1911             :    *  This is an equivalence relation.  It is linear in the size of the
    1912             :    *  deques.  Deques are considered equivalent if their sizes are equal,
    1913             :    *  and if corresponding elements compare equal.
    1914             :   */
    1915             :   template<typename _Tp, typename _Alloc>
    1916             :     inline bool
    1917             :     operator==(const deque<_Tp, _Alloc>& __x,
    1918             :                          const deque<_Tp, _Alloc>& __y)
    1919             :     { return __x.size() == __y.size()
    1920             :              && std::equal(__x.begin(), __x.end(), __y.begin()); }
    1921             : 
    1922             :   /**
    1923             :    *  @brief  Deque ordering relation.
    1924             :    *  @param  x  A %deque.
    1925             :    *  @param  y  A %deque of the same type as @a x.
    1926             :    *  @return  True iff @a x is lexicographically less than @a y.
    1927             :    *
    1928             :    *  This is a total ordering relation.  It is linear in the size of the
    1929             :    *  deques.  The elements must be comparable with @c <.
    1930             :    *
    1931             :    *  See std::lexicographical_compare() for how the determination is made.
    1932             :   */
    1933             :   template<typename _Tp, typename _Alloc>
    1934             :     inline bool
    1935             :     operator<(const deque<_Tp, _Alloc>& __x,
    1936             :               const deque<_Tp, _Alloc>& __y)
    1937             :     { return std::lexicographical_compare(__x.begin(), __x.end(),
    1938             :                                           __y.begin(), __y.end()); }
    1939             : 
    1940             :   /// Based on operator==
    1941             :   template<typename _Tp, typename _Alloc>
    1942             :     inline bool
    1943             :     operator!=(const deque<_Tp, _Alloc>& __x,
    1944             :                const deque<_Tp, _Alloc>& __y)
    1945             :     { return !(__x == __y); }
    1946             : 
    1947             :   /// Based on operator<
    1948             :   template<typename _Tp, typename _Alloc>
    1949             :     inline bool
    1950             :     operator>(const deque<_Tp, _Alloc>& __x,
    1951             :               const deque<_Tp, _Alloc>& __y)
    1952             :     { return __y < __x; }
    1953             : 
    1954             :   /// Based on operator<
    1955             :   template<typename _Tp, typename _Alloc>
    1956             :     inline bool
    1957             :     operator<=(const deque<_Tp, _Alloc>& __x,
    1958             :                const deque<_Tp, _Alloc>& __y)
    1959             :     { return !(__y < __x); }
    1960             : 
    1961             :   /// Based on operator<
    1962             :   template<typename _Tp, typename _Alloc>
    1963             :     inline bool
    1964             :     operator>=(const deque<_Tp, _Alloc>& __x,
    1965             :                const deque<_Tp, _Alloc>& __y)
    1966             :     { return !(__x < __y); }
    1967             : 
    1968             :   /// See std::deque::swap().
    1969             :   template<typename _Tp, typename _Alloc>
    1970             :     inline void
    1971             :     swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y)
    1972             :     { __x.swap(__y); }
    1973             : 
    1974             : #undef _GLIBCXX_DEQUE_BUF_SIZE
    1975             : 
    1976             : _GLIBCXX_END_NAMESPACE_CONTAINER
    1977             : } // namespace std
    1978             : 
    1979             : #endif /* _STL_DEQUE_H */

Generated by: LCOV version 1.9

The wpkg tool is an open source tool created by Made to Order Software Corporation.