libstdc++
stl_deque.h
Go to the documentation of this file.
00001 // Deque implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2015 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /*
00026  *
00027  * Copyright (c) 1994
00028  * Hewlett-Packard Company
00029  *
00030  * Permission to use, copy, modify, distribute and sell this software
00031  * and its documentation for any purpose is hereby granted without fee,
00032  * provided that the above copyright notice appear in all copies and
00033  * that both that copyright notice and this permission notice appear
00034  * in supporting documentation.  Hewlett-Packard Company makes no
00035  * representations about the suitability of this software for any
00036  * purpose.  It is provided "as is" without express or implied warranty.
00037  *
00038  *
00039  * Copyright (c) 1997
00040  * Silicon Graphics Computer Systems, Inc.
00041  *
00042  * Permission to use, copy, modify, distribute and sell this software
00043  * and its documentation for any purpose is hereby granted without fee,
00044  * provided that the above copyright notice appear in all copies and
00045  * that both that copyright notice and this permission notice appear
00046  * in supporting documentation.  Silicon Graphics makes no
00047  * representations about the suitability of this software for any
00048  * purpose.  It is provided "as is" without express or implied warranty.
00049  */
00050 
00051 /** @file bits/stl_deque.h
00052  *  This is an internal header file, included by other library headers.
00053  *  Do not attempt to use it directly. @headername{deque}
00054  */
00055 
00056 #ifndef _STL_DEQUE_H
00057 #define _STL_DEQUE_H 1
00058 
00059 #include <bits/concept_check.h>
00060 #include <bits/stl_iterator_base_types.h>
00061 #include <bits/stl_iterator_base_funcs.h>
00062 #if __cplusplus >= 201103L
00063 #include <initializer_list>
00064 #endif
00065 
00066 namespace std _GLIBCXX_VISIBILITY(default)
00067 {
00068 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
00069 
00070   /**
00071    *  @brief This function controls the size of memory nodes.
00072    *  @param  __size  The size of an element.
00073    *  @return   The number (not byte size) of elements per node.
00074    *
00075    *  This function started off as a compiler kludge from SGI, but
00076    *  seems to be a useful wrapper around a repeated constant
00077    *  expression.  The @b 512 is tunable (and no other code needs to
00078    *  change), but no investigation has been done since inheriting the
00079    *  SGI code.  Touch _GLIBCXX_DEQUE_BUF_SIZE only if you know what
00080    *  you are doing, however: changing it breaks the binary
00081    *  compatibility!!
00082   */
00083 
00084 #ifndef _GLIBCXX_DEQUE_BUF_SIZE
00085 #define _GLIBCXX_DEQUE_BUF_SIZE 512
00086 #endif
00087 
00088   _GLIBCXX_CONSTEXPR inline size_t
00089   __deque_buf_size(size_t __size)
00090   { return (__size < _GLIBCXX_DEQUE_BUF_SIZE
00091             ? size_t(_GLIBCXX_DEQUE_BUF_SIZE / __size) : size_t(1)); }
00092 
00093 
00094   /**
00095    *  @brief A deque::iterator.
00096    *
00097    *  Quite a bit of intelligence here.  Much of the functionality of
00098    *  deque is actually passed off to this class.  A deque holds two
00099    *  of these internally, marking its valid range.  Access to
00100    *  elements is done as offsets of either of those two, relying on
00101    *  operator overloading in this class.
00102    *
00103    *  All the functions are op overloads except for _M_set_node.
00104   */
00105   template<typename _Tp, typename _Ref, typename _Ptr>
00106     struct _Deque_iterator
00107     {
00108 #if __cplusplus < 201103L
00109       typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;
00110       typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
00111       typedef _Tp*                                         _Elt_pointer;
00112       typedef _Tp**                                        _Map_pointer;
00113 #else
00114     private:
00115       template<typename _Up>
00116         using __ptr_to = typename pointer_traits<_Ptr>::template rebind<_Up>;
00117       template<typename _CvTp>
00118         using __iter = _Deque_iterator<_Tp, _CvTp&, __ptr_to<_CvTp>>;
00119     public:
00120       typedef __iter<_Tp>               iterator;
00121       typedef __iter<const _Tp>         const_iterator;
00122       typedef __ptr_to<_Tp>             _Elt_pointer;
00123       typedef __ptr_to<_Elt_pointer>    _Map_pointer;
00124 #endif
00125 
00126       static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
00127       { return __deque_buf_size(sizeof(_Tp)); }
00128 
00129       typedef std::random_access_iterator_tag iterator_category;
00130       typedef _Tp                             value_type;
00131       typedef _Ptr                            pointer;
00132       typedef _Ref                            reference;
00133       typedef size_t                          size_type;
00134       typedef ptrdiff_t                       difference_type;
00135       typedef _Deque_iterator                 _Self;
00136 
00137       _Elt_pointer _M_cur;
00138       _Elt_pointer _M_first;
00139       _Elt_pointer _M_last;
00140       _Map_pointer _M_node;
00141 
00142       _Deque_iterator(_Elt_pointer __x, _Map_pointer __y) _GLIBCXX_NOEXCEPT
00143       : _M_cur(__x), _M_first(*__y),
00144         _M_last(*__y + _S_buffer_size()), _M_node(__y) { }
00145 
00146       _Deque_iterator() _GLIBCXX_NOEXCEPT
00147       : _M_cur(), _M_first(), _M_last(), _M_node() { }
00148 
00149       _Deque_iterator(const iterator& __x) _GLIBCXX_NOEXCEPT
00150       : _M_cur(__x._M_cur), _M_first(__x._M_first),
00151         _M_last(__x._M_last), _M_node(__x._M_node) { }
00152 
00153       iterator
00154       _M_const_cast() const _GLIBCXX_NOEXCEPT
00155       { return iterator(_M_cur, _M_node); }
00156 
00157       reference
00158       operator*() const _GLIBCXX_NOEXCEPT
00159       { return *_M_cur; }
00160 
00161       pointer
00162       operator->() const _GLIBCXX_NOEXCEPT
00163       { return _M_cur; }
00164 
00165       _Self&
00166       operator++() _GLIBCXX_NOEXCEPT
00167       {
00168         ++_M_cur;
00169         if (_M_cur == _M_last)
00170           {
00171             _M_set_node(_M_node + 1);
00172             _M_cur = _M_first;
00173           }
00174         return *this;
00175       }
00176 
00177       _Self
00178       operator++(int) _GLIBCXX_NOEXCEPT
00179       {
00180         _Self __tmp = *this;
00181         ++*this;
00182         return __tmp;
00183       }
00184 
00185       _Self&
00186       operator--() _GLIBCXX_NOEXCEPT
00187       {
00188         if (_M_cur == _M_first)
00189           {
00190             _M_set_node(_M_node - 1);
00191             _M_cur = _M_last;
00192           }
00193         --_M_cur;
00194         return *this;
00195       }
00196 
00197       _Self
00198       operator--(int) _GLIBCXX_NOEXCEPT
00199       {
00200         _Self __tmp = *this;
00201         --*this;
00202         return __tmp;
00203       }
00204 
00205       _Self&
00206       operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
00207       {
00208         const difference_type __offset = __n + (_M_cur - _M_first);
00209         if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
00210           _M_cur += __n;
00211         else
00212           {
00213             const difference_type __node_offset =
00214               __offset > 0 ? __offset / difference_type(_S_buffer_size())
00215                            : -difference_type((-__offset - 1)
00216                                               / _S_buffer_size()) - 1;
00217             _M_set_node(_M_node + __node_offset);
00218             _M_cur = _M_first + (__offset - __node_offset
00219                                  * difference_type(_S_buffer_size()));
00220           }
00221         return *this;
00222       }
00223 
00224       _Self
00225       operator+(difference_type __n) const _GLIBCXX_NOEXCEPT
00226       {
00227         _Self __tmp = *this;
00228         return __tmp += __n;
00229       }
00230 
00231       _Self&
00232       operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
00233       { return *this += -__n; }
00234 
00235       _Self
00236       operator-(difference_type __n) const _GLIBCXX_NOEXCEPT
00237       {
00238         _Self __tmp = *this;
00239         return __tmp -= __n;
00240       }
00241 
00242       reference
00243       operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
00244       { return *(*this + __n); }
00245 
00246       /** 
00247        *  Prepares to traverse new_node.  Sets everything except
00248        *  _M_cur, which should therefore be set by the caller
00249        *  immediately afterwards, based on _M_first and _M_last.
00250        */
00251       void
00252       _M_set_node(_Map_pointer __new_node) _GLIBCXX_NOEXCEPT
00253       {
00254         _M_node = __new_node;
00255         _M_first = *__new_node;
00256         _M_last = _M_first + difference_type(_S_buffer_size());
00257       }
00258     };
00259 
00260   // Note: we also provide overloads whose operands are of the same type in
00261   // order to avoid ambiguous overload resolution when std::rel_ops operators
00262   // are in scope (for additional details, see libstdc++/3628)
00263   template<typename _Tp, typename _Ref, typename _Ptr>
00264     inline bool
00265     operator==(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00266                const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT
00267     { return __x._M_cur == __y._M_cur; }
00268 
00269   template<typename _Tp, typename _RefL, typename _PtrL,
00270            typename _RefR, typename _PtrR>
00271     inline bool
00272     operator==(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00273                const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
00274     { return __x._M_cur == __y._M_cur; }
00275 
00276   template<typename _Tp, typename _Ref, typename _Ptr>
00277     inline bool
00278     operator!=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00279                const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT
00280     { return !(__x == __y); }
00281 
00282   template<typename _Tp, typename _RefL, typename _PtrL,
00283            typename _RefR, typename _PtrR>
00284     inline bool
00285     operator!=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00286                const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
00287     { return !(__x == __y); }
00288 
00289   template<typename _Tp, typename _Ref, typename _Ptr>
00290     inline bool
00291     operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00292               const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT
00293     { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)
00294                                           : (__x._M_node < __y._M_node); }
00295 
00296   template<typename _Tp, typename _RefL, typename _PtrL,
00297            typename _RefR, typename _PtrR>
00298     inline bool
00299     operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00300               const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
00301     { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)
00302                                           : (__x._M_node < __y._M_node); }
00303 
00304   template<typename _Tp, typename _Ref, typename _Ptr>
00305     inline bool
00306     operator>(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00307               const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT
00308     { return __y < __x; }
00309 
00310   template<typename _Tp, typename _RefL, typename _PtrL,
00311            typename _RefR, typename _PtrR>
00312     inline bool
00313     operator>(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00314               const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
00315     { return __y < __x; }
00316 
00317   template<typename _Tp, typename _Ref, typename _Ptr>
00318     inline bool
00319     operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00320                const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT
00321     { return !(__y < __x); }
00322 
00323   template<typename _Tp, typename _RefL, typename _PtrL,
00324            typename _RefR, typename _PtrR>
00325     inline bool
00326     operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00327                const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
00328     { return !(__y < __x); }
00329 
00330   template<typename _Tp, typename _Ref, typename _Ptr>
00331     inline bool
00332     operator>=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00333                const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT
00334     { return !(__x < __y); }
00335 
00336   template<typename _Tp, typename _RefL, typename _PtrL,
00337            typename _RefR, typename _PtrR>
00338     inline bool
00339     operator>=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00340                const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
00341     { return !(__x < __y); }
00342 
00343   // _GLIBCXX_RESOLVE_LIB_DEFECTS
00344   // According to the resolution of DR179 not only the various comparison
00345   // operators but also operator- must accept mixed iterator/const_iterator
00346   // parameters.
00347   template<typename _Tp, typename _Ref, typename _Ptr>
00348     inline typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type
00349     operator-(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
00350               const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT
00351     {
00352       return typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type
00353         (_Deque_iterator<_Tp, _Ref, _Ptr>::_S_buffer_size())
00354         * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
00355         + (__y._M_last - __y._M_cur);
00356     }
00357 
00358   template<typename _Tp, typename _RefL, typename _PtrL,
00359            typename _RefR, typename _PtrR>
00360     inline typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
00361     operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
00362               const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
00363     {
00364       return typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
00365         (_Deque_iterator<_Tp, _RefL, _PtrL>::_S_buffer_size())
00366         * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
00367         + (__y._M_last - __y._M_cur);
00368     }
00369 
00370   template<typename _Tp, typename _Ref, typename _Ptr>
00371     inline _Deque_iterator<_Tp, _Ref, _Ptr>
00372     operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x)
00373     _GLIBCXX_NOEXCEPT
00374     { return __x + __n; }
00375 
00376   template<typename _Tp>
00377     void
00378     fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>&,
00379          const _Deque_iterator<_Tp, _Tp&, _Tp*>&, const _Tp&);
00380 
00381   template<typename _Tp>
00382     _Deque_iterator<_Tp, _Tp&, _Tp*>
00383     copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
00384          _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
00385          _Deque_iterator<_Tp, _Tp&, _Tp*>);
00386 
00387   template<typename _Tp>
00388     inline _Deque_iterator<_Tp, _Tp&, _Tp*>
00389     copy(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
00390          _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
00391          _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
00392     { return std::copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),
00393                        _Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last),
00394                        __result); }
00395 
00396   template<typename _Tp>
00397     _Deque_iterator<_Tp, _Tp&, _Tp*>
00398     copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
00399                   _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
00400                   _Deque_iterator<_Tp, _Tp&, _Tp*>);
00401 
00402   template<typename _Tp>
00403     inline _Deque_iterator<_Tp, _Tp&, _Tp*>
00404     copy_backward(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
00405                   _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
00406                   _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
00407     { return std::copy_backward(_Deque_iterator<_Tp,
00408                                 const _Tp&, const _Tp*>(__first),
00409                                 _Deque_iterator<_Tp,
00410                                 const _Tp&, const _Tp*>(__last),
00411                                 __result); }
00412 
00413 #if __cplusplus >= 201103L
00414   template<typename _Tp>
00415     _Deque_iterator<_Tp, _Tp&, _Tp*>
00416     move(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
00417          _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
00418          _Deque_iterator<_Tp, _Tp&, _Tp*>);
00419 
00420   template<typename _Tp>
00421     inline _Deque_iterator<_Tp, _Tp&, _Tp*>
00422     move(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
00423          _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
00424          _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
00425     { return std::move(_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),
00426                        _Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last),
00427                        __result); }
00428 
00429   template<typename _Tp>
00430     _Deque_iterator<_Tp, _Tp&, _Tp*>
00431     move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
00432                   _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
00433                   _Deque_iterator<_Tp, _Tp&, _Tp*>);
00434 
00435   template<typename _Tp>
00436     inline _Deque_iterator<_Tp, _Tp&, _Tp*>
00437     move_backward(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
00438                   _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
00439                   _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
00440     { return std::move_backward(_Deque_iterator<_Tp,
00441                                 const _Tp&, const _Tp*>(__first),
00442                                 _Deque_iterator<_Tp,
00443                                 const _Tp&, const _Tp*>(__last),
00444                                 __result); }
00445 #endif
00446 
00447   /**
00448    *  Deque base class.  This class provides the unified face for %deque's
00449    *  allocation.  This class's constructor and destructor allocate and
00450    *  deallocate (but do not initialize) storage.  This makes %exception
00451    *  safety easier.
00452    *
00453    *  Nothing in this class ever constructs or destroys an actual Tp element.
00454    *  (Deque handles that itself.)  Only/All memory management is performed
00455    *  here.
00456   */
00457   template<typename _Tp, typename _Alloc>
00458     class _Deque_base
00459     {
00460     protected:
00461       typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
00462         rebind<_Tp>::other _Tp_alloc_type;
00463       typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type>  _Alloc_traits;
00464 
00465 #if __cplusplus < 201103L
00466       typedef _Tp*                                      _Ptr;
00467       typedef const _Tp*                                _Ptr_const;
00468 #else
00469       typedef typename _Alloc_traits::pointer           _Ptr;
00470       typedef typename _Alloc_traits::const_pointer     _Ptr_const;
00471 #endif
00472 
00473       typedef typename _Alloc_traits::template rebind<_Ptr>::other
00474         _Map_alloc_type;
00475       typedef __gnu_cxx::__alloc_traits<_Map_alloc_type> _Map_alloc_traits;
00476 
00477     public:
00478       typedef _Alloc                  allocator_type;
00479       typedef typename _Alloc_traits::size_type size_type;
00480 
00481       allocator_type
00482       get_allocator() const _GLIBCXX_NOEXCEPT
00483       { return allocator_type(_M_get_Tp_allocator()); }
00484 
00485       typedef _Deque_iterator<_Tp, _Tp&, _Ptr>          iterator;
00486       typedef _Deque_iterator<_Tp, const _Tp&, _Ptr_const>   const_iterator;
00487 
00488       _Deque_base()
00489       : _M_impl()
00490       { _M_initialize_map(0); }
00491 
00492       _Deque_base(size_t __num_elements)
00493       : _M_impl()
00494       { _M_initialize_map(__num_elements); }
00495 
00496       _Deque_base(const allocator_type& __a, size_t __num_elements)
00497       : _M_impl(__a)
00498       { _M_initialize_map(__num_elements); }
00499 
00500       _Deque_base(const allocator_type& __a)
00501       : _M_impl(__a)
00502       { /* Caller must initialize map. */ }
00503 
00504 #if __cplusplus >= 201103L
00505       _Deque_base(_Deque_base&& __x, false_type)
00506       : _M_impl(__x._M_move_impl())
00507       { }
00508 
00509       _Deque_base(_Deque_base&& __x, true_type)
00510       : _M_impl(std::move(__x._M_get_Tp_allocator()))
00511       {
00512         _M_initialize_map(0);
00513         if (__x._M_impl._M_map)
00514           this->_M_impl._M_swap_data(__x._M_impl);
00515       }
00516 
00517       _Deque_base(_Deque_base&& __x)
00518       : _Deque_base(std::move(__x),
00519                     __gnu_cxx::__allocator_always_compares_equal<_Alloc>{})
00520       { }
00521 
00522       _Deque_base(_Deque_base&& __x, const allocator_type& __a, size_type __n)
00523       : _M_impl(__a)
00524       {
00525         if (__x.get_allocator() == __a)
00526           {
00527             if (__x._M_impl._M_map)
00528               {
00529                 _M_initialize_map(0);
00530                 this->_M_impl._M_swap_data(__x._M_impl);
00531               }
00532           }
00533         else
00534           {
00535             _M_initialize_map(__n);
00536           }
00537       }
00538 #endif
00539 
00540       ~_Deque_base() _GLIBCXX_NOEXCEPT;
00541 
00542     protected:
00543       typedef typename iterator::_Map_pointer _Map_pointer;
00544 
00545       //This struct encapsulates the implementation of the std::deque
00546       //standard container and at the same time makes use of the EBO
00547       //for empty allocators.
00548       struct _Deque_impl
00549       : public _Tp_alloc_type
00550       {
00551         _Map_pointer _M_map;
00552         size_t _M_map_size;
00553         iterator _M_start;
00554         iterator _M_finish;
00555 
00556         _Deque_impl()
00557         : _Tp_alloc_type(), _M_map(), _M_map_size(0),
00558           _M_start(), _M_finish()
00559         { }
00560 
00561         _Deque_impl(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
00562         : _Tp_alloc_type(__a), _M_map(), _M_map_size(0),
00563           _M_start(), _M_finish()
00564         { }
00565 
00566 #if __cplusplus >= 201103L
00567         _Deque_impl(_Deque_impl&&) = default;
00568 
00569         _Deque_impl(_Tp_alloc_type&& __a) noexcept
00570         : _Tp_alloc_type(std::move(__a)), _M_map(), _M_map_size(0),
00571           _M_start(), _M_finish()
00572         { }
00573 #endif
00574 
00575         void _M_swap_data(_Deque_impl& __x) _GLIBCXX_NOEXCEPT
00576         {
00577           using std::swap;
00578           swap(this->_M_start, __x._M_start);
00579           swap(this->_M_finish, __x._M_finish);
00580           swap(this->_M_map, __x._M_map);
00581           swap(this->_M_map_size, __x._M_map_size);
00582         }
00583       };
00584 
00585       _Tp_alloc_type&
00586       _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
00587       { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }
00588 
00589       const _Tp_alloc_type&
00590       _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT
00591       { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }
00592 
00593       _Map_alloc_type
00594       _M_get_map_allocator() const _GLIBCXX_NOEXCEPT
00595       { return _Map_alloc_type(_M_get_Tp_allocator()); }
00596 
00597       _Ptr
00598       _M_allocate_node()
00599       { 
00600         typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Traits;
00601         return _Traits::allocate(_M_impl, __deque_buf_size(sizeof(_Tp)));
00602       }
00603 
00604       void
00605       _M_deallocate_node(_Ptr __p) _GLIBCXX_NOEXCEPT
00606       {
00607         typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Traits;
00608         _Traits::deallocate(_M_impl, __p, __deque_buf_size(sizeof(_Tp)));
00609       }
00610 
00611       _Map_pointer
00612       _M_allocate_map(size_t __n)
00613       {
00614         _Map_alloc_type __map_alloc = _M_get_map_allocator();
00615         return _Map_alloc_traits::allocate(__map_alloc, __n);
00616       }
00617 
00618       void
00619       _M_deallocate_map(_Map_pointer __p, size_t __n) _GLIBCXX_NOEXCEPT
00620       {
00621         _Map_alloc_type __map_alloc = _M_get_map_allocator();
00622         _Map_alloc_traits::deallocate(__map_alloc, __p, __n);
00623       }
00624 
00625     protected:
00626       void _M_initialize_map(size_t);
00627       void _M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish);
00628       void _M_destroy_nodes(_Map_pointer __nstart,
00629                             _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT;
00630       enum { _S_initial_map_size = 8 };
00631 
00632       _Deque_impl _M_impl;
00633 
00634 #if __cplusplus >= 201103L
00635     private:
00636       _Deque_impl
00637       _M_move_impl()
00638       {
00639         if (!_M_impl._M_map)
00640           return std::move(_M_impl);
00641 
00642         // Create a copy of the current allocator.
00643         _Tp_alloc_type __alloc{_M_get_Tp_allocator()};
00644         // Put that copy in a moved-from state.
00645         _Tp_alloc_type __sink __attribute((__unused__)) {std::move(__alloc)};
00646         // Create an empty map that allocates using the moved-from allocator.
00647         _Deque_base __empty{__alloc};
00648         // Now safe to modify current allocator and perform non-throwing swaps.
00649         _Deque_impl __ret{std::move(_M_get_Tp_allocator())};
00650         _M_impl._M_swap_data(__ret);
00651         _M_impl._M_swap_data(__empty._M_impl);
00652         return __ret;
00653       }
00654 #endif
00655     };
00656 
00657   template<typename _Tp, typename _Alloc>
00658     _Deque_base<_Tp, _Alloc>::
00659     ~_Deque_base() _GLIBCXX_NOEXCEPT
00660     {
00661       if (this->_M_impl._M_map)
00662         {
00663           _M_destroy_nodes(this->_M_impl._M_start._M_node,
00664                            this->_M_impl._M_finish._M_node + 1);
00665           _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
00666         }
00667     }
00668 
00669   /**
00670    *  @brief Layout storage.
00671    *  @param  __num_elements  The count of T's for which to allocate space
00672    *                          at first.
00673    *  @return   Nothing.
00674    *
00675    *  The initial underlying memory layout is a bit complicated...
00676   */
00677   template<typename _Tp, typename _Alloc>
00678     void
00679     _Deque_base<_Tp, _Alloc>::
00680     _M_initialize_map(size_t __num_elements)
00681     {
00682       const size_t __num_nodes = (__num_elements/ __deque_buf_size(sizeof(_Tp))
00683                                   + 1);
00684 
00685       this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size,
00686                                            size_t(__num_nodes + 2));
00687       this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
00688 
00689       // For "small" maps (needing less than _M_map_size nodes), allocation
00690       // starts in the middle elements and grows outwards.  So nstart may be
00691       // the beginning of _M_map, but for small maps it may be as far in as
00692       // _M_map+3.
00693 
00694       _Map_pointer __nstart = (this->_M_impl._M_map
00695                                + (this->_M_impl._M_map_size - __num_nodes) / 2);
00696       _Map_pointer __nfinish = __nstart + __num_nodes;
00697 
00698       __try
00699         { _M_create_nodes(__nstart, __nfinish); }
00700       __catch(...)
00701         {
00702           _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
00703           this->_M_impl._M_map = _Map_pointer();
00704           this->_M_impl._M_map_size = 0;
00705           __throw_exception_again;
00706         }
00707 
00708       this->_M_impl._M_start._M_set_node(__nstart);
00709       this->_M_impl._M_finish._M_set_node(__nfinish - 1);
00710       this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
00711       this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
00712                                         + __num_elements
00713                                         % __deque_buf_size(sizeof(_Tp)));
00714     }
00715 
00716   template<typename _Tp, typename _Alloc>
00717     void
00718     _Deque_base<_Tp, _Alloc>::
00719     _M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish)
00720     {
00721       _Map_pointer __cur;
00722       __try
00723         {
00724           for (__cur = __nstart; __cur < __nfinish; ++__cur)
00725             *__cur = this->_M_allocate_node();
00726         }
00727       __catch(...)
00728         {
00729           _M_destroy_nodes(__nstart, __cur);
00730           __throw_exception_again;
00731         }
00732     }
00733 
00734   template<typename _Tp, typename _Alloc>
00735     void
00736     _Deque_base<_Tp, _Alloc>::
00737     _M_destroy_nodes(_Map_pointer __nstart,
00738                      _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT
00739     {
00740       for (_Map_pointer __n = __nstart; __n < __nfinish; ++__n)
00741         _M_deallocate_node(*__n);
00742     }
00743 
00744   /**
00745    *  @brief  A standard container using fixed-size memory allocation and
00746    *  constant-time manipulation of elements at either end.
00747    *
00748    *  @ingroup sequences
00749    *
00750    *  @tparam _Tp  Type of element.
00751    *  @tparam _Alloc  Allocator type, defaults to allocator<_Tp>.
00752    *
00753    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
00754    *  <a href="tables.html#66">reversible container</a>, and a
00755    *  <a href="tables.html#67">sequence</a>, including the
00756    *  <a href="tables.html#68">optional sequence requirements</a>.
00757    *
00758    *  In previous HP/SGI versions of deque, there was an extra template
00759    *  parameter so users could control the node size.  This extension turned
00760    *  out to violate the C++ standard (it can be detected using template
00761    *  template parameters), and it was removed.
00762    *
00763    *  Here's how a deque<Tp> manages memory.  Each deque has 4 members:
00764    *
00765    *  - Tp**        _M_map
00766    *  - size_t      _M_map_size
00767    *  - iterator    _M_start, _M_finish
00768    *
00769    *  map_size is at least 8.  %map is an array of map_size
00770    *  pointers-to-@a nodes.  (The name %map has nothing to do with the
00771    *  std::map class, and @b nodes should not be confused with
00772    *  std::list's usage of @a node.)
00773    *
00774    *  A @a node has no specific type name as such, but it is referred
00775    *  to as @a node in this file.  It is a simple array-of-Tp.  If Tp
00776    *  is very large, there will be one Tp element per node (i.e., an
00777    *  @a array of one).  For non-huge Tp's, node size is inversely
00778    *  related to Tp size: the larger the Tp, the fewer Tp's will fit
00779    *  in a node.  The goal here is to keep the total size of a node
00780    *  relatively small and constant over different Tp's, to improve
00781    *  allocator efficiency.
00782    *
00783    *  Not every pointer in the %map array will point to a node.  If
00784    *  the initial number of elements in the deque is small, the
00785    *  /middle/ %map pointers will be valid, and the ones at the edges
00786    *  will be unused.  This same situation will arise as the %map
00787    *  grows: available %map pointers, if any, will be on the ends.  As
00788    *  new nodes are created, only a subset of the %map's pointers need
00789    *  to be copied @a outward.
00790    *
00791    *  Class invariants:
00792    * - For any nonsingular iterator i:
00793    *    - i.node points to a member of the %map array.  (Yes, you read that
00794    *      correctly:  i.node does not actually point to a node.)  The member of
00795    *      the %map array is what actually points to the node.
00796    *    - i.first == *(i.node)    (This points to the node (first Tp element).)
00797    *    - i.last  == i.first + node_size
00798    *    - i.cur is a pointer in the range [i.first, i.last).  NOTE:
00799    *      the implication of this is that i.cur is always a dereferenceable
00800    *      pointer, even if i is a past-the-end iterator.
00801    * - Start and Finish are always nonsingular iterators.  NOTE: this
00802    * means that an empty deque must have one node, a deque with <N
00803    * elements (where N is the node buffer size) must have one node, a
00804    * deque with N through (2N-1) elements must have two nodes, etc.
00805    * - For every node other than start.node and finish.node, every
00806    * element in the node is an initialized object.  If start.node ==
00807    * finish.node, then [start.cur, finish.cur) are initialized
00808    * objects, and the elements outside that range are uninitialized
00809    * storage.  Otherwise, [start.cur, start.last) and [finish.first,
00810    * finish.cur) are initialized objects, and [start.first, start.cur)
00811    * and [finish.cur, finish.last) are uninitialized storage.
00812    * - [%map, %map + map_size) is a valid, non-empty range.
00813    * - [start.node, finish.node] is a valid range contained within
00814    *   [%map, %map + map_size).
00815    * - A pointer in the range [%map, %map + map_size) points to an allocated
00816    *   node if and only if the pointer is in the range
00817    *   [start.node, finish.node].
00818    *
00819    *  Here's the magic:  nothing in deque is @b aware of the discontiguous
00820    *  storage!
00821    *
00822    *  The memory setup and layout occurs in the parent, _Base, and the iterator
00823    *  class is entirely responsible for @a leaping from one node to the next.
00824    *  All the implementation routines for deque itself work only through the
00825    *  start and finish iterators.  This keeps the routines simple and sane,
00826    *  and we can use other standard algorithms as well.
00827   */
00828   template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
00829     class deque : protected _Deque_base<_Tp, _Alloc>
00830     {
00831       // concept requirements
00832       typedef typename _Alloc::value_type        _Alloc_value_type;
00833       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00834       __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
00835 
00836       typedef _Deque_base<_Tp, _Alloc>                  _Base;
00837       typedef typename _Base::_Tp_alloc_type            _Tp_alloc_type;
00838       typedef typename _Base::_Alloc_traits             _Alloc_traits;
00839       typedef typename _Base::_Map_pointer              _Map_pointer;
00840 
00841     public:
00842       typedef _Tp                                        value_type;
00843       typedef typename _Alloc_traits::pointer            pointer;
00844       typedef typename _Alloc_traits::const_pointer      const_pointer;
00845       typedef typename _Alloc_traits::reference          reference;
00846       typedef typename _Alloc_traits::const_reference    const_reference;
00847       typedef typename _Base::iterator                   iterator;
00848       typedef typename _Base::const_iterator             const_iterator;
00849       typedef std::reverse_iterator<const_iterator>      const_reverse_iterator;
00850       typedef std::reverse_iterator<iterator>            reverse_iterator;
00851       typedef size_t                             size_type;
00852       typedef ptrdiff_t                          difference_type;
00853       typedef _Alloc                             allocator_type;
00854 
00855     protected:
00856       static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
00857       { return __deque_buf_size(sizeof(_Tp)); }
00858 
00859       // Functions controlling memory layout, and nothing else.
00860       using _Base::_M_initialize_map;
00861       using _Base::_M_create_nodes;
00862       using _Base::_M_destroy_nodes;
00863       using _Base::_M_allocate_node;
00864       using _Base::_M_deallocate_node;
00865       using _Base::_M_allocate_map;
00866       using _Base::_M_deallocate_map;
00867       using _Base::_M_get_Tp_allocator;
00868 
00869       /** 
00870        *  A total of four data members accumulated down the hierarchy.
00871        *  May be accessed via _M_impl.*
00872        */
00873       using _Base::_M_impl;
00874 
00875     public:
00876       // [23.2.1.1] construct/copy/destroy
00877       // (assign() and get_allocator() are also listed in this section)
00878 
00879       /**
00880        *  @brief  Creates a %deque with no elements.
00881        */
00882       deque() : _Base() { }
00883 
00884       /**
00885        *  @brief  Creates a %deque with no elements.
00886        *  @param  __a  An allocator object.
00887        */
00888       explicit
00889       deque(const allocator_type& __a)
00890       : _Base(__a, 0) { }
00891 
00892 #if __cplusplus >= 201103L
00893       /**
00894        *  @brief  Creates a %deque with default constructed elements.
00895        *  @param  __n  The number of elements to initially create.
00896        *
00897        *  This constructor fills the %deque with @a n default
00898        *  constructed elements.
00899        */
00900       explicit
00901       deque(size_type __n, const allocator_type& __a = allocator_type())
00902       : _Base(__a, __n)
00903       { _M_default_initialize(); }
00904 
00905       /**
00906        *  @brief  Creates a %deque with copies of an exemplar element.
00907        *  @param  __n  The number of elements to initially create.
00908        *  @param  __value  An element to copy.
00909        *  @param  __a  An allocator.
00910        *
00911        *  This constructor fills the %deque with @a __n copies of @a __value.
00912        */
00913       deque(size_type __n, const value_type& __value,
00914             const allocator_type& __a = allocator_type())
00915       : _Base(__a, __n)
00916       { _M_fill_initialize(__value); }
00917 #else
00918       /**
00919        *  @brief  Creates a %deque with copies of an exemplar element.
00920        *  @param  __n  The number of elements to initially create.
00921        *  @param  __value  An element to copy.
00922        *  @param  __a  An allocator.
00923        *
00924        *  This constructor fills the %deque with @a __n copies of @a __value.
00925        */
00926       explicit
00927       deque(size_type __n, const value_type& __value = value_type(),
00928             const allocator_type& __a = allocator_type())
00929       : _Base(__a, __n)
00930       { _M_fill_initialize(__value); }
00931 #endif
00932 
00933       /**
00934        *  @brief  %Deque copy constructor.
00935        *  @param  __x  A %deque of identical element and allocator types.
00936        *
00937        *  The newly-created %deque uses a copy of the allocation object used
00938        *  by @a __x.
00939        */
00940       deque(const deque& __x)
00941       : _Base(_Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator()),
00942               __x.size())
00943       { std::__uninitialized_copy_a(__x.begin(), __x.end(), 
00944                                     this->_M_impl._M_start,
00945                                     _M_get_Tp_allocator()); }
00946 
00947 #if __cplusplus >= 201103L
00948       /**
00949        *  @brief  %Deque move constructor.
00950        *  @param  __x  A %deque of identical element and allocator types.
00951        *
00952        *  The newly-created %deque contains the exact contents of @a __x.
00953        *  The contents of @a __x are a valid, but unspecified %deque.
00954        */
00955       deque(deque&& __x)
00956       : _Base(std::move(__x)) { }
00957 
00958       /// Copy constructor with alternative allocator
00959       deque(const deque& __x, const allocator_type& __a)
00960       : _Base(__a, __x.size())
00961       { std::__uninitialized_copy_a(__x.begin(), __x.end(),
00962                                     this->_M_impl._M_start,
00963                                     _M_get_Tp_allocator()); }
00964 
00965       /// Move constructor with alternative allocator
00966       deque(deque&& __x, const allocator_type& __a)
00967       : _Base(std::move(__x), __a, __x.size())
00968       {
00969         if (__x.get_allocator() != __a)
00970           {
00971             std::__uninitialized_move_a(__x.begin(), __x.end(),
00972                                         this->_M_impl._M_start,
00973                                         _M_get_Tp_allocator());
00974             __x.clear();
00975           }
00976       }
00977 
00978       /**
00979        *  @brief  Builds a %deque from an initializer list.
00980        *  @param  __l  An initializer_list.
00981        *  @param  __a  An allocator object.
00982        *
00983        *  Create a %deque consisting of copies of the elements in the
00984        *  initializer_list @a __l.
00985        *
00986        *  This will call the element type's copy constructor N times
00987        *  (where N is __l.size()) and do no memory reallocation.
00988        */
00989       deque(initializer_list<value_type> __l,
00990             const allocator_type& __a = allocator_type())
00991       : _Base(__a)
00992       {
00993         _M_range_initialize(__l.begin(), __l.end(),
00994                             random_access_iterator_tag());
00995       }
00996 #endif
00997 
00998       /**
00999        *  @brief  Builds a %deque from a range.
01000        *  @param  __first  An input iterator.
01001        *  @param  __last  An input iterator.
01002        *  @param  __a  An allocator object.
01003        *
01004        *  Create a %deque consisting of copies of the elements from [__first,
01005        *  __last).
01006        *
01007        *  If the iterators are forward, bidirectional, or random-access, then
01008        *  this will call the elements' copy constructor N times (where N is
01009        *  distance(__first,__last)) and do no memory reallocation.  But if only
01010        *  input iterators are used, then this will do at most 2N calls to the
01011        *  copy constructor, and logN memory reallocations.
01012        */
01013 #if __cplusplus >= 201103L
01014       template<typename _InputIterator,
01015                typename = std::_RequireInputIter<_InputIterator>>
01016         deque(_InputIterator __first, _InputIterator __last,
01017               const allocator_type& __a = allocator_type())
01018         : _Base(__a)
01019         { _M_initialize_dispatch(__first, __last, __false_type()); }
01020 #else
01021       template<typename _InputIterator>
01022         deque(_InputIterator __first, _InputIterator __last,
01023               const allocator_type& __a = allocator_type())
01024         : _Base(__a)
01025         {
01026           // Check whether it's an integral type.  If so, it's not an iterator.
01027           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
01028           _M_initialize_dispatch(__first, __last, _Integral());
01029         }
01030 #endif
01031 
01032       /**
01033        *  The dtor only erases the elements, and note that if the elements
01034        *  themselves are pointers, the pointed-to memory is not touched in any
01035        *  way.  Managing the pointer is the user's responsibility.
01036        */
01037       ~deque()
01038       { _M_destroy_data(begin(), end(), _M_get_Tp_allocator()); }
01039 
01040       /**
01041        *  @brief  %Deque assignment operator.
01042        *  @param  __x  A %deque of identical element and allocator types.
01043        *
01044        *  All the elements of @a x are copied, but unlike the copy constructor,
01045        *  the allocator object is not copied.
01046        */
01047       deque&
01048       operator=(const deque& __x);
01049 
01050 #if __cplusplus >= 201103L
01051       /**
01052        *  @brief  %Deque move assignment operator.
01053        *  @param  __x  A %deque of identical element and allocator types.
01054        *
01055        *  The contents of @a __x are moved into this deque (without copying,
01056        *  if the allocators permit it).
01057        *  @a __x is a valid, but unspecified %deque.
01058        */
01059       deque&
01060       operator=(deque&& __x) noexcept(_Alloc_traits::_S_always_equal())
01061       {
01062         constexpr bool __always_equal = _Alloc_traits::_S_always_equal();
01063         _M_move_assign1(std::move(__x),
01064                         integral_constant<bool, __always_equal>());
01065         return *this;
01066       }
01067 
01068       /**
01069        *  @brief  Assigns an initializer list to a %deque.
01070        *  @param  __l  An initializer_list.
01071        *
01072        *  This function fills a %deque with copies of the elements in the
01073        *  initializer_list @a __l.
01074        *
01075        *  Note that the assignment completely changes the %deque and that the
01076        *  resulting %deque's size is the same as the number of elements
01077        *  assigned.  Old data may be lost.
01078        */
01079       deque&
01080       operator=(initializer_list<value_type> __l)
01081       {
01082         this->assign(__l.begin(), __l.end());
01083         return *this;
01084       }
01085 #endif
01086 
01087       /**
01088        *  @brief  Assigns a given value to a %deque.
01089        *  @param  __n  Number of elements to be assigned.
01090        *  @param  __val  Value to be assigned.
01091        *
01092        *  This function fills a %deque with @a n copies of the given
01093        *  value.  Note that the assignment completely changes the
01094        *  %deque and that the resulting %deque's size is the same as
01095        *  the number of elements assigned.  Old data may be lost.
01096        */
01097       void
01098       assign(size_type __n, const value_type& __val)
01099       { _M_fill_assign(__n, __val); }
01100 
01101       /**
01102        *  @brief  Assigns a range to a %deque.
01103        *  @param  __first  An input iterator.
01104        *  @param  __last   An input iterator.
01105        *
01106        *  This function fills a %deque with copies of the elements in the
01107        *  range [__first,__last).
01108        *
01109        *  Note that the assignment completely changes the %deque and that the
01110        *  resulting %deque's size is the same as the number of elements
01111        *  assigned.  Old data may be lost.
01112        */
01113 #if __cplusplus >= 201103L
01114       template<typename _InputIterator,
01115                typename = std::_RequireInputIter<_InputIterator>>
01116         void
01117         assign(_InputIterator __first, _InputIterator __last)
01118         { _M_assign_dispatch(__first, __last, __false_type()); }
01119 #else
01120       template<typename _InputIterator>
01121         void
01122         assign(_InputIterator __first, _InputIterator __last)
01123         {
01124           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
01125           _M_assign_dispatch(__first, __last, _Integral());
01126         }
01127 #endif
01128 
01129 #if __cplusplus >= 201103L
01130       /**
01131        *  @brief  Assigns an initializer list to a %deque.
01132        *  @param  __l  An initializer_list.
01133        *
01134        *  This function fills a %deque with copies of the elements in the
01135        *  initializer_list @a __l.
01136        *
01137        *  Note that the assignment completely changes the %deque and that the
01138        *  resulting %deque's size is the same as the number of elements
01139        *  assigned.  Old data may be lost.
01140        */
01141       void
01142       assign(initializer_list<value_type> __l)
01143       { this->assign(__l.begin(), __l.end()); }
01144 #endif
01145 
01146       /// Get a copy of the memory allocation object.
01147       allocator_type
01148       get_allocator() const _GLIBCXX_NOEXCEPT
01149       { return _Base::get_allocator(); }
01150 
01151       // iterators
01152       /**
01153        *  Returns a read/write iterator that points to the first element in the
01154        *  %deque.  Iteration is done in ordinary element order.
01155        */
01156       iterator
01157       begin() _GLIBCXX_NOEXCEPT
01158       { return this->_M_impl._M_start; }
01159 
01160       /**
01161        *  Returns a read-only (constant) iterator that points to the first
01162        *  element in the %deque.  Iteration is done in ordinary element order.
01163        */
01164       const_iterator
01165       begin() const _GLIBCXX_NOEXCEPT
01166       { return this->_M_impl._M_start; }
01167 
01168       /**
01169        *  Returns a read/write iterator that points one past the last
01170        *  element in the %deque.  Iteration is done in ordinary
01171        *  element order.
01172        */
01173       iterator
01174       end() _GLIBCXX_NOEXCEPT
01175       { return this->_M_impl._M_finish; }
01176 
01177       /**
01178        *  Returns a read-only (constant) iterator that points one past
01179        *  the last element in the %deque.  Iteration is done in
01180        *  ordinary element order.
01181        */
01182       const_iterator
01183       end() const _GLIBCXX_NOEXCEPT
01184       { return this->_M_impl._M_finish; }
01185 
01186       /**
01187        *  Returns a read/write reverse iterator that points to the
01188        *  last element in the %deque.  Iteration is done in reverse
01189        *  element order.
01190        */
01191       reverse_iterator
01192       rbegin() _GLIBCXX_NOEXCEPT
01193       { return reverse_iterator(this->_M_impl._M_finish); }
01194 
01195       /**
01196        *  Returns a read-only (constant) reverse iterator that points
01197        *  to the last element in the %deque.  Iteration is done in
01198        *  reverse element order.
01199        */
01200       const_reverse_iterator
01201       rbegin() const _GLIBCXX_NOEXCEPT
01202       { return const_reverse_iterator(this->_M_impl._M_finish); }
01203 
01204       /**
01205        *  Returns a read/write reverse iterator that points to one
01206        *  before the first element in the %deque.  Iteration is done
01207        *  in reverse element order.
01208        */
01209       reverse_iterator
01210       rend() _GLIBCXX_NOEXCEPT
01211       { return reverse_iterator(this->_M_impl._M_start); }
01212 
01213       /**
01214        *  Returns a read-only (constant) reverse iterator that points
01215        *  to one before the first element in the %deque.  Iteration is
01216        *  done in reverse element order.
01217        */
01218       const_reverse_iterator
01219       rend() const _GLIBCXX_NOEXCEPT
01220       { return const_reverse_iterator(this->_M_impl._M_start); }
01221 
01222 #if __cplusplus >= 201103L
01223       /**
01224        *  Returns a read-only (constant) iterator that points to the first
01225        *  element in the %deque.  Iteration is done in ordinary element order.
01226        */
01227       const_iterator
01228       cbegin() const noexcept
01229       { return this->_M_impl._M_start; }
01230 
01231       /**
01232        *  Returns a read-only (constant) iterator that points one past
01233        *  the last element in the %deque.  Iteration is done in
01234        *  ordinary element order.
01235        */
01236       const_iterator
01237       cend() const noexcept
01238       { return this->_M_impl._M_finish; }
01239 
01240       /**
01241        *  Returns a read-only (constant) reverse iterator that points
01242        *  to the last element in the %deque.  Iteration is done in
01243        *  reverse element order.
01244        */
01245       const_reverse_iterator
01246       crbegin() const noexcept
01247       { return const_reverse_iterator(this->_M_impl._M_finish); }
01248 
01249       /**
01250        *  Returns a read-only (constant) reverse iterator that points
01251        *  to one before the first element in the %deque.  Iteration is
01252        *  done in reverse element order.
01253        */
01254       const_reverse_iterator
01255       crend() const noexcept
01256       { return const_reverse_iterator(this->_M_impl._M_start); }
01257 #endif
01258 
01259       // [23.2.1.2] capacity
01260       /**  Returns the number of elements in the %deque.  */
01261       size_type
01262       size() const _GLIBCXX_NOEXCEPT
01263       { return this->_M_impl._M_finish - this->_M_impl._M_start; }
01264 
01265       /**  Returns the size() of the largest possible %deque.  */
01266       size_type
01267       max_size() const _GLIBCXX_NOEXCEPT
01268       { return _Alloc_traits::max_size(_M_get_Tp_allocator()); }
01269 
01270 #if __cplusplus >= 201103L
01271       /**
01272        *  @brief  Resizes the %deque to the specified number of elements.
01273        *  @param  __new_size  Number of elements the %deque should contain.
01274        *
01275        *  This function will %resize the %deque to the specified
01276        *  number of elements.  If the number is smaller than the
01277        *  %deque's current size the %deque is truncated, otherwise
01278        *  default constructed elements are appended.
01279        */
01280       void
01281       resize(size_type __new_size)
01282       {
01283         const size_type __len = size();
01284         if (__new_size > __len)
01285           _M_default_append(__new_size - __len);
01286         else if (__new_size < __len)
01287           _M_erase_at_end(this->_M_impl._M_start
01288                           + difference_type(__new_size));
01289       }
01290 
01291       /**
01292        *  @brief  Resizes the %deque to the specified number of elements.
01293        *  @param  __new_size  Number of elements the %deque should contain.
01294        *  @param  __x  Data with which new elements should be populated.
01295        *
01296        *  This function will %resize the %deque to the specified
01297        *  number of elements.  If the number is smaller than the
01298        *  %deque's current size the %deque is truncated, otherwise the
01299        *  %deque is extended and new elements are populated with given
01300        *  data.
01301        */
01302       void
01303       resize(size_type __new_size, const value_type& __x)
01304       {
01305         const size_type __len = size();
01306         if (__new_size > __len)
01307           insert(this->_M_impl._M_finish, __new_size - __len, __x);
01308         else if (__new_size < __len)
01309           _M_erase_at_end(this->_M_impl._M_start
01310                           + difference_type(__new_size));
01311       }
01312 #else
01313       /**
01314        *  @brief  Resizes the %deque to the specified number of elements.
01315        *  @param  __new_size  Number of elements the %deque should contain.
01316        *  @param  __x  Data with which new elements should be populated.
01317        *
01318        *  This function will %resize the %deque to the specified
01319        *  number of elements.  If the number is smaller than the
01320        *  %deque's current size the %deque is truncated, otherwise the
01321        *  %deque is extended and new elements are populated with given
01322        *  data.
01323        */
01324       void
01325       resize(size_type __new_size, value_type __x = value_type())
01326       {
01327         const size_type __len = size();
01328         if (__new_size > __len)
01329           insert(this->_M_impl._M_finish, __new_size - __len, __x);
01330         else if (__new_size < __len)
01331           _M_erase_at_end(this->_M_impl._M_start
01332                           + difference_type(__new_size));
01333       }
01334 #endif
01335 
01336 #if __cplusplus >= 201103L
01337       /**  A non-binding request to reduce memory use.  */
01338       void
01339       shrink_to_fit() noexcept
01340       { _M_shrink_to_fit(); }
01341 #endif
01342 
01343       /**
01344        *  Returns true if the %deque is empty.  (Thus begin() would
01345        *  equal end().)
01346        */
01347       bool
01348       empty() const _GLIBCXX_NOEXCEPT
01349       { return this->_M_impl._M_finish == this->_M_impl._M_start; }
01350 
01351       // element access
01352       /**
01353        *  @brief Subscript access to the data contained in the %deque.
01354        *  @param __n The index of the element for which data should be
01355        *  accessed.
01356        *  @return  Read/write reference to data.
01357        *
01358        *  This operator allows for easy, array-style, data access.
01359        *  Note that data access with this operator is unchecked and
01360        *  out_of_range lookups are not defined. (For checked lookups
01361        *  see at().)
01362        */
01363       reference
01364       operator[](size_type __n) _GLIBCXX_NOEXCEPT
01365       { return this->_M_impl._M_start[difference_type(__n)]; }
01366 
01367       /**
01368        *  @brief Subscript access to the data contained in the %deque.
01369        *  @param __n The index of the element for which data should be
01370        *  accessed.
01371        *  @return  Read-only (constant) reference to data.
01372        *
01373        *  This operator allows for easy, array-style, data access.
01374        *  Note that data access with this operator is unchecked and
01375        *  out_of_range lookups are not defined. (For checked lookups
01376        *  see at().)
01377        */
01378       const_reference
01379       operator[](size_type __n) const _GLIBCXX_NOEXCEPT
01380       { return this->_M_impl._M_start[difference_type(__n)]; }
01381 
01382     protected:
01383       /// Safety check used only from at().
01384       void
01385       _M_range_check(size_type __n) const
01386       {
01387         if (__n >= this->size())
01388           __throw_out_of_range_fmt(__N("deque::_M_range_check: __n "
01389                                        "(which is %zu)>= this->size() "
01390                                        "(which is %zu)"),
01391                                    __n, this->size());
01392       }
01393 
01394     public:
01395       /**
01396        *  @brief  Provides access to the data contained in the %deque.
01397        *  @param __n The index of the element for which data should be
01398        *  accessed.
01399        *  @return  Read/write reference to data.
01400        *  @throw  std::out_of_range  If @a __n is an invalid index.
01401        *
01402        *  This function provides for safer data access.  The parameter
01403        *  is first checked that it is in the range of the deque.  The
01404        *  function throws out_of_range if the check fails.
01405        */
01406       reference
01407       at(size_type __n)
01408       {
01409         _M_range_check(__n);
01410         return (*this)[__n];
01411       }
01412 
01413       /**
01414        *  @brief  Provides access to the data contained in the %deque.
01415        *  @param __n The index of the element for which data should be
01416        *  accessed.
01417        *  @return  Read-only (constant) reference to data.
01418        *  @throw  std::out_of_range  If @a __n is an invalid index.
01419        *
01420        *  This function provides for safer data access.  The parameter is first
01421        *  checked that it is in the range of the deque.  The function throws
01422        *  out_of_range if the check fails.
01423        */
01424       const_reference
01425       at(size_type __n) const
01426       {
01427         _M_range_check(__n);
01428         return (*this)[__n];
01429       }
01430 
01431       /**
01432        *  Returns a read/write reference to the data at the first
01433        *  element of the %deque.
01434        */
01435       reference
01436       front() _GLIBCXX_NOEXCEPT
01437       { return *begin(); }
01438 
01439       /**
01440        *  Returns a read-only (constant) reference to the data at the first
01441        *  element of the %deque.
01442        */
01443       const_reference
01444       front() const _GLIBCXX_NOEXCEPT
01445       { return *begin(); }
01446 
01447       /**
01448        *  Returns a read/write reference to the data at the last element of the
01449        *  %deque.
01450        */
01451       reference
01452       back() _GLIBCXX_NOEXCEPT
01453       {
01454         iterator __tmp = end();
01455         --__tmp;
01456         return *__tmp;
01457       }
01458 
01459       /**
01460        *  Returns a read-only (constant) reference to the data at the last
01461        *  element of the %deque.
01462        */
01463       const_reference
01464       back() const _GLIBCXX_NOEXCEPT
01465       {
01466         const_iterator __tmp = end();
01467         --__tmp;
01468         return *__tmp;
01469       }
01470 
01471       // [23.2.1.2] modifiers
01472       /**
01473        *  @brief  Add data to the front of the %deque.
01474        *  @param  __x  Data to be added.
01475        *
01476        *  This is a typical stack operation.  The function creates an
01477        *  element at the front of the %deque and assigns the given
01478        *  data to it.  Due to the nature of a %deque this operation
01479        *  can be done in constant time.
01480        */
01481       void
01482       push_front(const value_type& __x)
01483       {
01484         if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
01485           {
01486             _Alloc_traits::construct(this->_M_impl,
01487                                      this->_M_impl._M_start._M_cur - 1,
01488                                      __x);
01489             --this->_M_impl._M_start._M_cur;
01490           }
01491         else
01492           _M_push_front_aux(__x);
01493       }
01494 
01495 #if __cplusplus >= 201103L
01496       void
01497       push_front(value_type&& __x)
01498       { emplace_front(std::move(__x)); }
01499 
01500       template<typename... _Args>
01501         void
01502         emplace_front(_Args&&... __args);
01503 #endif
01504 
01505       /**
01506        *  @brief  Add data to the end of the %deque.
01507        *  @param  __x  Data to be added.
01508        *
01509        *  This is a typical stack operation.  The function creates an
01510        *  element at the end of the %deque and assigns the given data
01511        *  to it.  Due to the nature of a %deque this operation can be
01512        *  done in constant time.
01513        */
01514       void
01515       push_back(const value_type& __x)
01516       {
01517         if (this->_M_impl._M_finish._M_cur
01518             != this->_M_impl._M_finish._M_last - 1)
01519           {
01520             _Alloc_traits::construct(this->_M_impl,
01521                                      this->_M_impl._M_finish._M_cur, __x);
01522             ++this->_M_impl._M_finish._M_cur;
01523           }
01524         else
01525           _M_push_back_aux(__x);
01526       }
01527 
01528 #if __cplusplus >= 201103L
01529       void
01530       push_back(value_type&& __x)
01531       { emplace_back(std::move(__x)); }
01532 
01533       template<typename... _Args>
01534         void
01535         emplace_back(_Args&&... __args);
01536 #endif
01537 
01538       /**
01539        *  @brief  Removes first element.
01540        *
01541        *  This is a typical stack operation.  It shrinks the %deque by one.
01542        *
01543        *  Note that no data is returned, and if the first element's data is
01544        *  needed, it should be retrieved before pop_front() is called.
01545        */
01546       void
01547       pop_front() _GLIBCXX_NOEXCEPT
01548       {
01549         if (this->_M_impl._M_start._M_cur
01550             != this->_M_impl._M_start._M_last - 1)
01551           {
01552             _Alloc_traits::destroy(this->_M_impl,
01553                                    this->_M_impl._M_start._M_cur);
01554             ++this->_M_impl._M_start._M_cur;
01555           }
01556         else
01557           _M_pop_front_aux();
01558       }
01559 
01560       /**
01561        *  @brief  Removes last element.
01562        *
01563        *  This is a typical stack operation.  It shrinks the %deque by one.
01564        *
01565        *  Note that no data is returned, and if the last element's data is
01566        *  needed, it should be retrieved before pop_back() is called.
01567        */
01568       void
01569       pop_back() _GLIBCXX_NOEXCEPT
01570       {
01571         if (this->_M_impl._M_finish._M_cur
01572             != this->_M_impl._M_finish._M_first)
01573           {
01574             --this->_M_impl._M_finish._M_cur;
01575             _Alloc_traits::destroy(this->_M_impl,
01576                                    this->_M_impl._M_finish._M_cur);
01577           }
01578         else
01579           _M_pop_back_aux();
01580       }
01581 
01582 #if __cplusplus >= 201103L
01583       /**
01584        *  @brief  Inserts an object in %deque before specified iterator.
01585        *  @param  __position  A const_iterator into the %deque.
01586        *  @param  __args  Arguments.
01587        *  @return  An iterator that points to the inserted data.
01588        *
01589        *  This function will insert an object of type T constructed
01590        *  with T(std::forward<Args>(args)...) before the specified location.
01591        */
01592       template<typename... _Args>
01593         iterator
01594         emplace(const_iterator __position, _Args&&... __args);
01595 
01596       /**
01597        *  @brief  Inserts given value into %deque before specified iterator.
01598        *  @param  __position  A const_iterator into the %deque.
01599        *  @param  __x  Data to be inserted.
01600        *  @return  An iterator that points to the inserted data.
01601        *
01602        *  This function will insert a copy of the given value before the
01603        *  specified location.
01604        */
01605       iterator
01606       insert(const_iterator __position, const value_type& __x);
01607 #else
01608       /**
01609        *  @brief  Inserts given value into %deque before specified iterator.
01610        *  @param  __position  An iterator into the %deque.
01611        *  @param  __x  Data to be inserted.
01612        *  @return  An iterator that points to the inserted data.
01613        *
01614        *  This function will insert a copy of the given value before the
01615        *  specified location.
01616        */
01617       iterator
01618       insert(iterator __position, const value_type& __x);
01619 #endif
01620 
01621 #if __cplusplus >= 201103L
01622       /**
01623        *  @brief  Inserts given rvalue into %deque before specified iterator.
01624        *  @param  __position  A const_iterator into the %deque.
01625        *  @param  __x  Data to be inserted.
01626        *  @return  An iterator that points to the inserted data.
01627        *
01628        *  This function will insert a copy of the given rvalue before the
01629        *  specified location.
01630        */
01631       iterator
01632       insert(const_iterator __position, value_type&& __x)
01633       { return emplace(__position, std::move(__x)); }
01634 
01635       /**
01636        *  @brief  Inserts an initializer list into the %deque.
01637        *  @param  __p  An iterator into the %deque.
01638        *  @param  __l  An initializer_list.
01639        *
01640        *  This function will insert copies of the data in the
01641        *  initializer_list @a __l into the %deque before the location
01642        *  specified by @a __p.  This is known as <em>list insert</em>.
01643        */
01644       iterator
01645       insert(const_iterator __p, initializer_list<value_type> __l)
01646       { return this->insert(__p, __l.begin(), __l.end()); }
01647 #endif
01648 
01649 #if __cplusplus >= 201103L
01650       /**
01651        *  @brief  Inserts a number of copies of given data into the %deque.
01652        *  @param  __position  A const_iterator into the %deque.
01653        *  @param  __n  Number of elements to be inserted.
01654        *  @param  __x  Data to be inserted.
01655        *  @return  An iterator that points to the inserted data.
01656        *
01657        *  This function will insert a specified number of copies of the given
01658        *  data before the location specified by @a __position.
01659        */
01660       iterator
01661       insert(const_iterator __position, size_type __n, const value_type& __x)
01662       {
01663         difference_type __offset = __position - cbegin();
01664         _M_fill_insert(__position._M_const_cast(), __n, __x);
01665         return begin() + __offset;
01666       }
01667 #else
01668       /**
01669        *  @brief  Inserts a number of copies of given data into the %deque.
01670        *  @param  __position  An iterator into the %deque.
01671        *  @param  __n  Number of elements to be inserted.
01672        *  @param  __x  Data to be inserted.
01673        *
01674        *  This function will insert a specified number of copies of the given
01675        *  data before the location specified by @a __position.
01676        */
01677       void
01678       insert(iterator __position, size_type __n, const value_type& __x)
01679       { _M_fill_insert(__position, __n, __x); }
01680 #endif
01681 
01682 #if __cplusplus >= 201103L
01683       /**
01684        *  @brief  Inserts a range into the %deque.
01685        *  @param  __position  A const_iterator into the %deque.
01686        *  @param  __first  An input iterator.
01687        *  @param  __last   An input iterator.
01688        *  @return  An iterator that points to the inserted data.
01689        *
01690        *  This function will insert copies of the data in the range
01691        *  [__first,__last) into the %deque before the location specified
01692        *  by @a __position.  This is known as <em>range insert</em>.
01693        */
01694       template<typename _InputIterator,
01695                typename = std::_RequireInputIter<_InputIterator>>
01696         iterator
01697         insert(const_iterator __position, _InputIterator __first,
01698                _InputIterator __last)
01699         {
01700           difference_type __offset = __position - cbegin();
01701           _M_insert_dispatch(__position._M_const_cast(),
01702                              __first, __last, __false_type());
01703           return begin() + __offset;
01704         }
01705 #else
01706       /**
01707        *  @brief  Inserts a range into the %deque.
01708        *  @param  __position  An iterator into the %deque.
01709        *  @param  __first  An input iterator.
01710        *  @param  __last   An input iterator.
01711        *
01712        *  This function will insert copies of the data in the range
01713        *  [__first,__last) into the %deque before the location specified
01714        *  by @a __position.  This is known as <em>range insert</em>.
01715        */
01716       template<typename _InputIterator>
01717         void
01718         insert(iterator __position, _InputIterator __first,
01719                _InputIterator __last)
01720         {
01721           // Check whether it's an integral type.  If so, it's not an iterator.
01722           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
01723           _M_insert_dispatch(__position, __first, __last, _Integral());
01724         }
01725 #endif
01726 
01727       /**
01728        *  @brief  Remove element at given position.
01729        *  @param  __position  Iterator pointing to element to be erased.
01730        *  @return  An iterator pointing to the next element (or end()).
01731        *
01732        *  This function will erase the element at the given position and thus
01733        *  shorten the %deque by one.
01734        *
01735        *  The user is cautioned that
01736        *  this function only erases the element, and that if the element is
01737        *  itself a pointer, the pointed-to memory is not touched in any way.
01738        *  Managing the pointer is the user's responsibility.
01739        */
01740       iterator
01741 #if __cplusplus >= 201103L
01742       erase(const_iterator __position)
01743 #else
01744       erase(iterator __position)
01745 #endif
01746       { return _M_erase(__position._M_const_cast()); }
01747 
01748       /**
01749        *  @brief  Remove a range of elements.
01750        *  @param  __first  Iterator pointing to the first element to be erased.
01751        *  @param  __last  Iterator pointing to one past the last element to be
01752        *                erased.
01753        *  @return  An iterator pointing to the element pointed to by @a last
01754        *           prior to erasing (or end()).
01755        *
01756        *  This function will erase the elements in the range
01757        *  [__first,__last) and shorten the %deque accordingly.
01758        *
01759        *  The user is cautioned that
01760        *  this function only erases the elements, and that if the elements
01761        *  themselves are pointers, the pointed-to memory is not touched in any
01762        *  way.  Managing the pointer is the user's responsibility.
01763        */
01764       iterator
01765 #if __cplusplus >= 201103L
01766       erase(const_iterator __first, const_iterator __last)
01767 #else
01768       erase(iterator __first, iterator __last)
01769 #endif
01770       { return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
01771 
01772       /**
01773        *  @brief  Swaps data with another %deque.
01774        *  @param  __x  A %deque of the same element and allocator types.
01775        *
01776        *  This exchanges the elements between two deques in constant time.
01777        *  (Four pointers, so it should be quite fast.)
01778        *  Note that the global std::swap() function is specialized such that
01779        *  std::swap(d1,d2) will feed to this function.
01780        */
01781       void
01782       swap(deque& __x)
01783 #if __cplusplus >= 201103L
01784       noexcept(_Alloc_traits::_S_nothrow_swap())
01785 #endif
01786       {
01787         _M_impl._M_swap_data(__x._M_impl);
01788         _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
01789                                   __x._M_get_Tp_allocator());
01790       }
01791 
01792       /**
01793        *  Erases all the elements.  Note that this function only erases the
01794        *  elements, and that if the elements themselves are pointers, the
01795        *  pointed-to memory is not touched in any way.  Managing the pointer is
01796        *  the user's responsibility.
01797        */
01798       void
01799       clear() _GLIBCXX_NOEXCEPT
01800       { _M_erase_at_end(begin()); }
01801 
01802     protected:
01803       // Internal constructor functions follow.
01804 
01805       // called by the range constructor to implement [23.1.1]/9
01806 
01807       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01808       // 438. Ambiguity in the "do the right thing" clause
01809       template<typename _Integer>
01810         void
01811         _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
01812         {
01813           _M_initialize_map(static_cast<size_type>(__n));
01814           _M_fill_initialize(__x);
01815         }
01816 
01817       // called by the range constructor to implement [23.1.1]/9
01818       template<typename _InputIterator>
01819         void
01820         _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
01821                                __false_type)
01822         {
01823           typedef typename std::iterator_traits<_InputIterator>::
01824             iterator_category _IterCategory;
01825           _M_range_initialize(__first, __last, _IterCategory());
01826         }
01827 
01828       // called by the second initialize_dispatch above
01829       //@{
01830       /**
01831        *  @brief Fills the deque with whatever is in [first,last).
01832        *  @param  __first  An input iterator.
01833        *  @param  __last  An input iterator.
01834        *  @return   Nothing.
01835        *
01836        *  If the iterators are actually forward iterators (or better), then the
01837        *  memory layout can be done all at once.  Else we move forward using
01838        *  push_back on each value from the iterator.
01839        */
01840       template<typename _InputIterator>
01841         void
01842         _M_range_initialize(_InputIterator __first, _InputIterator __last,
01843                             std::input_iterator_tag);
01844 
01845       // called by the second initialize_dispatch above
01846       template<typename _ForwardIterator>
01847         void
01848         _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
01849                             std::forward_iterator_tag);
01850       //@}
01851 
01852       /**
01853        *  @brief Fills the %deque with copies of value.
01854        *  @param  __value  Initial value.
01855        *  @return   Nothing.
01856        *  @pre _M_start and _M_finish have already been initialized,
01857        *  but none of the %deque's elements have yet been constructed.
01858        *
01859        *  This function is called only when the user provides an explicit size
01860        *  (with or without an explicit exemplar value).
01861        */
01862       void
01863       _M_fill_initialize(const value_type& __value);
01864 
01865 #if __cplusplus >= 201103L
01866       // called by deque(n).
01867       void
01868       _M_default_initialize();
01869 #endif
01870 
01871       // Internal assign functions follow.  The *_aux functions do the actual
01872       // assignment work for the range versions.
01873 
01874       // called by the range assign to implement [23.1.1]/9
01875 
01876       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01877       // 438. Ambiguity in the "do the right thing" clause
01878       template<typename _Integer>
01879         void
01880         _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
01881         { _M_fill_assign(__n, __val); }
01882 
01883       // called by the range assign to implement [23.1.1]/9
01884       template<typename _InputIterator>
01885         void
01886         _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
01887                            __false_type)
01888         {
01889           typedef typename std::iterator_traits<_InputIterator>::
01890             iterator_category _IterCategory;
01891           _M_assign_aux(__first, __last, _IterCategory());
01892         }
01893 
01894       // called by the second assign_dispatch above
01895       template<typename _InputIterator>
01896         void
01897         _M_assign_aux(_InputIterator __first, _InputIterator __last,
01898                       std::input_iterator_tag);
01899 
01900       // called by the second assign_dispatch above
01901       template<typename _ForwardIterator>
01902         void
01903         _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
01904                       std::forward_iterator_tag)
01905         {
01906           const size_type __len = std::distance(__first, __last);
01907           if (__len > size())
01908             {
01909               _ForwardIterator __mid = __first;
01910               std::advance(__mid, size());
01911               std::copy(__first, __mid, begin());
01912               insert(end(), __mid, __last);
01913             }
01914           else
01915             _M_erase_at_end(std::copy(__first, __last, begin()));
01916         }
01917 
01918       // Called by assign(n,t), and the range assign when it turns out
01919       // to be the same thing.
01920       void
01921       _M_fill_assign(size_type __n, const value_type& __val)
01922       {
01923         if (__n > size())
01924           {
01925             std::fill(begin(), end(), __val);
01926             insert(end(), __n - size(), __val);
01927           }
01928         else
01929           {
01930             _M_erase_at_end(begin() + difference_type(__n));
01931             std::fill(begin(), end(), __val);
01932           }
01933       }
01934 
01935       //@{
01936       /// Helper functions for push_* and pop_*.
01937 #if __cplusplus < 201103L
01938       void _M_push_back_aux(const value_type&);
01939 
01940       void _M_push_front_aux(const value_type&);
01941 #else
01942       template<typename... _Args>
01943         void _M_push_back_aux(_Args&&... __args);
01944 
01945       template<typename... _Args>
01946         void _M_push_front_aux(_Args&&... __args);
01947 #endif
01948 
01949       void _M_pop_back_aux();
01950 
01951       void _M_pop_front_aux();
01952       //@}
01953 
01954       // Internal insert functions follow.  The *_aux functions do the actual
01955       // insertion work when all shortcuts fail.
01956 
01957       // called by the range insert to implement [23.1.1]/9
01958 
01959       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01960       // 438. Ambiguity in the "do the right thing" clause
01961       template<typename _Integer>
01962         void
01963         _M_insert_dispatch(iterator __pos,
01964                            _Integer __n, _Integer __x, __true_type)
01965         { _M_fill_insert(__pos, __n, __x); }
01966 
01967       // called by the range insert to implement [23.1.1]/9
01968       template<typename _InputIterator>
01969         void
01970         _M_insert_dispatch(iterator __pos,
01971                            _InputIterator __first, _InputIterator __last,
01972                            __false_type)
01973         {
01974           typedef typename std::iterator_traits<_InputIterator>::
01975             iterator_category _IterCategory;
01976           _M_range_insert_aux(__pos, __first, __last, _IterCategory());
01977         }
01978 
01979       // called by the second insert_dispatch above
01980       template<typename _InputIterator>
01981         void
01982         _M_range_insert_aux(iterator __pos, _InputIterator __first,
01983                             _InputIterator __last, std::input_iterator_tag);
01984 
01985       // called by the second insert_dispatch above
01986       template<typename _ForwardIterator>
01987         void
01988         _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
01989                             _ForwardIterator __last, std::forward_iterator_tag);
01990 
01991       // Called by insert(p,n,x), and the range insert when it turns out to be
01992       // the same thing.  Can use fill functions in optimal situations,
01993       // otherwise passes off to insert_aux(p,n,x).
01994       void
01995       _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
01996 
01997       // called by insert(p,x)
01998 #if __cplusplus < 201103L
01999       iterator
02000       _M_insert_aux(iterator __pos, const value_type& __x);
02001 #else
02002       template<typename... _Args>
02003         iterator
02004         _M_insert_aux(iterator __pos, _Args&&... __args);
02005 #endif
02006 
02007       // called by insert(p,n,x) via fill_insert
02008       void
02009       _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
02010 
02011       // called by range_insert_aux for forward iterators
02012       template<typename _ForwardIterator>
02013         void
02014         _M_insert_aux(iterator __pos,
02015                       _ForwardIterator __first, _ForwardIterator __last,
02016                       size_type __n);
02017 
02018 
02019       // Internal erase functions follow.
02020 
02021       void
02022       _M_destroy_data_aux(iterator __first, iterator __last);
02023 
02024       // Called by ~deque().
02025       // NB: Doesn't deallocate the nodes.
02026       template<typename _Alloc1>
02027         void
02028         _M_destroy_data(iterator __first, iterator __last, const _Alloc1&)
02029         { _M_destroy_data_aux(__first, __last); }
02030 
02031       void
02032       _M_destroy_data(iterator __first, iterator __last,
02033                       const std::allocator<_Tp>&)
02034       {
02035         if (!__has_trivial_destructor(value_type))
02036           _M_destroy_data_aux(__first, __last);
02037       }
02038 
02039       // Called by erase(q1, q2).
02040       void
02041       _M_erase_at_begin(iterator __pos)
02042       {
02043         _M_destroy_data(begin(), __pos, _M_get_Tp_allocator());
02044         _M_destroy_nodes(this->_M_impl._M_start._M_node, __pos._M_node);
02045         this->_M_impl._M_start = __pos;
02046       }
02047 
02048       // Called by erase(q1, q2), resize(), clear(), _M_assign_aux,
02049       // _M_fill_assign, operator=.
02050       void
02051       _M_erase_at_end(iterator __pos)
02052       {
02053         _M_destroy_data(__pos, end(), _M_get_Tp_allocator());
02054         _M_destroy_nodes(__pos._M_node + 1,
02055                          this->_M_impl._M_finish._M_node + 1);
02056         this->_M_impl._M_finish = __pos;
02057       }
02058 
02059       iterator
02060       _M_erase(iterator __pos);
02061 
02062       iterator
02063       _M_erase(iterator __first, iterator __last);
02064 
02065 #if __cplusplus >= 201103L
02066       // Called by resize(sz).
02067       void
02068       _M_default_append(size_type __n);
02069 
02070       bool
02071       _M_shrink_to_fit();
02072 #endif
02073 
02074       //@{
02075       /// Memory-handling helpers for the previous internal insert functions.
02076       iterator
02077       _M_reserve_elements_at_front(size_type __n)
02078       {
02079         const size_type __vacancies = this->_M_impl._M_start._M_cur
02080                                       - this->_M_impl._M_start._M_first;
02081         if (__n > __vacancies)
02082           _M_new_elements_at_front(__n - __vacancies);
02083         return this->_M_impl._M_start - difference_type(__n);
02084       }
02085 
02086       iterator
02087       _M_reserve_elements_at_back(size_type __n)
02088       {
02089         const size_type __vacancies = (this->_M_impl._M_finish._M_last
02090                                        - this->_M_impl._M_finish._M_cur) - 1;
02091         if (__n > __vacancies)
02092           _M_new_elements_at_back(__n - __vacancies);
02093         return this->_M_impl._M_finish + difference_type(__n);
02094       }
02095 
02096       void
02097       _M_new_elements_at_front(size_type __new_elements);
02098 
02099       void
02100       _M_new_elements_at_back(size_type __new_elements);
02101       //@}
02102 
02103 
02104       //@{
02105       /**
02106        *  @brief Memory-handling helpers for the major %map.
02107        *
02108        *  Makes sure the _M_map has space for new nodes.  Does not
02109        *  actually add the nodes.  Can invalidate _M_map pointers.
02110        *  (And consequently, %deque iterators.)
02111        */
02112       void
02113       _M_reserve_map_at_back(size_type __nodes_to_add = 1)
02114       {
02115         if (__nodes_to_add + 1 > this->_M_impl._M_map_size
02116             - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
02117           _M_reallocate_map(__nodes_to_add, false);
02118       }
02119 
02120       void
02121       _M_reserve_map_at_front(size_type __nodes_to_add = 1)
02122       {
02123         if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node
02124                                        - this->_M_impl._M_map))
02125           _M_reallocate_map(__nodes_to_add, true);
02126       }
02127 
02128       void
02129       _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
02130       //@}
02131 
02132 #if __cplusplus >= 201103L
02133       // Constant-time, nothrow move assignment when source object's memory
02134       // can be moved because the allocators are equal.
02135       void
02136       _M_move_assign1(deque&& __x, /* always equal: */ true_type) noexcept
02137       {
02138         this->_M_impl._M_swap_data(__x._M_impl);
02139         __x.clear();
02140         std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
02141       }
02142 
02143       void
02144       _M_move_assign1(deque&& __x, /* always equal: */ false_type)
02145       {
02146         constexpr bool __move_storage =
02147           _Alloc_traits::_S_propagate_on_move_assign();
02148         _M_move_assign2(std::move(__x),
02149                         integral_constant<bool, __move_storage>());
02150       }
02151 
02152       // Destroy all elements and deallocate all memory, then replace
02153       // with elements created from __args.
02154       template<typename... _Args>
02155       void
02156       _M_replace_map(_Args&&... __args)
02157       {
02158         // Create new data first, so if allocation fails there are no effects.
02159         deque __newobj(std::forward<_Args>(__args)...);
02160         // Free existing storage using existing allocator.
02161         clear();
02162         _M_deallocate_node(*begin()._M_node); // one node left after clear()
02163         _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
02164         this->_M_impl._M_map = nullptr;
02165         this->_M_impl._M_map_size = 0;
02166         // Take ownership of replacement memory.
02167         this->_M_impl._M_swap_data(__newobj._M_impl);
02168       }
02169 
02170       // Do move assignment when the allocator propagates.
02171       void
02172       _M_move_assign2(deque&& __x, /* propagate: */ true_type)
02173       {
02174         // Make a copy of the original allocator state.
02175         auto __alloc = __x._M_get_Tp_allocator();
02176         // The allocator propagates so storage can be moved from __x,
02177         // leaving __x in a valid empty state with a moved-from allocator.
02178         _M_replace_map(std::move(__x));
02179         // Move the corresponding allocator state too.
02180         _M_get_Tp_allocator() = std::move(__alloc);
02181       }
02182 
02183       // Do move assignment when it may not be possible to move source
02184       // object's memory, resulting in a linear-time operation.
02185       void
02186       _M_move_assign2(deque&& __x, /* propagate: */ false_type)
02187       {
02188         if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
02189           {
02190             // The allocators are equal so storage can be moved from __x,
02191             // leaving __x in a valid empty state with its current allocator.
02192             _M_replace_map(std::move(__x), __x.get_allocator());
02193           }
02194         else
02195           {
02196             // The rvalue's allocator cannot be moved and is not equal,
02197             // so we need to individually move each element.
02198             this->assign(std::__make_move_if_noexcept_iterator(__x.begin()),
02199                          std::__make_move_if_noexcept_iterator(__x.end()));
02200             __x.clear();
02201           }
02202       }
02203 #endif
02204     };
02205 
02206 
02207   /**
02208    *  @brief  Deque equality comparison.
02209    *  @param  __x  A %deque.
02210    *  @param  __y  A %deque of the same type as @a __x.
02211    *  @return  True iff the size and elements of the deques are equal.
02212    *
02213    *  This is an equivalence relation.  It is linear in the size of the
02214    *  deques.  Deques are considered equivalent if their sizes are equal,
02215    *  and if corresponding elements compare equal.
02216   */
02217   template<typename _Tp, typename _Alloc>
02218     inline bool
02219     operator==(const deque<_Tp, _Alloc>& __x,
02220                          const deque<_Tp, _Alloc>& __y)
02221     { return __x.size() == __y.size()
02222              && std::equal(__x.begin(), __x.end(), __y.begin()); }
02223 
02224   /**
02225    *  @brief  Deque ordering relation.
02226    *  @param  __x  A %deque.
02227    *  @param  __y  A %deque of the same type as @a __x.
02228    *  @return  True iff @a x is lexicographically less than @a __y.
02229    *
02230    *  This is a total ordering relation.  It is linear in the size of the
02231    *  deques.  The elements must be comparable with @c <.
02232    *
02233    *  See std::lexicographical_compare() for how the determination is made.
02234   */
02235   template<typename _Tp, typename _Alloc>
02236     inline bool
02237     operator<(const deque<_Tp, _Alloc>& __x,
02238               const deque<_Tp, _Alloc>& __y)
02239     { return std::lexicographical_compare(__x.begin(), __x.end(),
02240                                           __y.begin(), __y.end()); }
02241 
02242   /// Based on operator==
02243   template<typename _Tp, typename _Alloc>
02244     inline bool
02245     operator!=(const deque<_Tp, _Alloc>& __x,
02246                const deque<_Tp, _Alloc>& __y)
02247     { return !(__x == __y); }
02248 
02249   /// Based on operator<
02250   template<typename _Tp, typename _Alloc>
02251     inline bool
02252     operator>(const deque<_Tp, _Alloc>& __x,
02253               const deque<_Tp, _Alloc>& __y)
02254     { return __y < __x; }
02255 
02256   /// Based on operator<
02257   template<typename _Tp, typename _Alloc>
02258     inline bool
02259     operator<=(const deque<_Tp, _Alloc>& __x,
02260                const deque<_Tp, _Alloc>& __y)
02261     { return !(__y < __x); }
02262 
02263   /// Based on operator<
02264   template<typename _Tp, typename _Alloc>
02265     inline bool
02266     operator>=(const deque<_Tp, _Alloc>& __x,
02267                const deque<_Tp, _Alloc>& __y)
02268     { return !(__x < __y); }
02269 
02270   /// See std::deque::swap().
02271   template<typename _Tp, typename _Alloc>
02272     inline void
02273     swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y)
02274     { __x.swap(__y); }
02275 
02276 #undef _GLIBCXX_DEQUE_BUF_SIZE
02277 
02278 _GLIBCXX_END_NAMESPACE_CONTAINER
02279 } // namespace std
02280 
02281 #endif /* _STL_DEQUE_H */