libstdc++
stl_deque.h
Go to the documentation of this file.
00001 // Deque implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2001-2016 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /*
00026  *
00027  * Copyright (c) 1994
00028  * Hewlett-Packard Company
00029  *
00030  * Permission to use, copy, modify, distribute and sell this software
00031  * and its documentation for any purpose is hereby granted without fee,
00032  * provided that the above copyright notice appear in all copies and
00033  * that both that copyright notice and this permission notice appear
00034  * in supporting documentation.  Hewlett-Packard Company makes no
00035  * representations about the suitability of this software for any
00036  * purpose.  It is provided "as is" without express or implied warranty.
00037  *
00038  *
00039  * Copyright (c) 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), typename _Alloc_traits::is_always_equal{})
00519       { }
00520 
00521       _Deque_base(_Deque_base&& __x, const allocator_type& __a, size_type __n)
00522       : _M_impl(__a)
00523       {
00524         if (__x.get_allocator() == __a)
00525           {
00526             if (__x._M_impl._M_map)
00527               {
00528                 _M_initialize_map(0);
00529                 this->_M_impl._M_swap_data(__x._M_impl);
00530               }
00531           }
00532         else
00533           {
00534             _M_initialize_map(__n);
00535           }
00536       }
00537 #endif
00538 
00539       ~_Deque_base() _GLIBCXX_NOEXCEPT;
00540 
00541     protected:
00542       typedef typename iterator::_Map_pointer _Map_pointer;
00543 
00544       //This struct encapsulates the implementation of the std::deque
00545       //standard container and at the same time makes use of the EBO
00546       //for empty allocators.
00547       struct _Deque_impl
00548       : public _Tp_alloc_type
00549       {
00550         _Map_pointer _M_map;
00551         size_t _M_map_size;
00552         iterator _M_start;
00553         iterator _M_finish;
00554 
00555         _Deque_impl()
00556         : _Tp_alloc_type(), _M_map(), _M_map_size(0),
00557           _M_start(), _M_finish()
00558         { }
00559 
00560         _Deque_impl(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
00561         : _Tp_alloc_type(__a), _M_map(), _M_map_size(0),
00562           _M_start(), _M_finish()
00563         { }
00564 
00565 #if __cplusplus >= 201103L
00566         _Deque_impl(_Deque_impl&&) = default;
00567 
00568         _Deque_impl(_Tp_alloc_type&& __a) noexcept
00569         : _Tp_alloc_type(std::move(__a)), _M_map(), _M_map_size(0),
00570           _M_start(), _M_finish()
00571         { }
00572 #endif
00573 
00574         void _M_swap_data(_Deque_impl& __x) _GLIBCXX_NOEXCEPT
00575         {
00576           using std::swap;
00577           swap(this->_M_start, __x._M_start);
00578           swap(this->_M_finish, __x._M_finish);
00579           swap(this->_M_map, __x._M_map);
00580           swap(this->_M_map_size, __x._M_map_size);
00581         }
00582       };
00583 
00584       _Tp_alloc_type&
00585       _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
00586       { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }
00587 
00588       const _Tp_alloc_type&
00589       _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT
00590       { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }
00591 
00592       _Map_alloc_type
00593       _M_get_map_allocator() const _GLIBCXX_NOEXCEPT
00594       { return _Map_alloc_type(_M_get_Tp_allocator()); }
00595 
00596       _Ptr
00597       _M_allocate_node()
00598       { 
00599         typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Traits;
00600         return _Traits::allocate(_M_impl, __deque_buf_size(sizeof(_Tp)));
00601       }
00602 
00603       void
00604       _M_deallocate_node(_Ptr __p) _GLIBCXX_NOEXCEPT
00605       {
00606         typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Traits;
00607         _Traits::deallocate(_M_impl, __p, __deque_buf_size(sizeof(_Tp)));
00608       }
00609 
00610       _Map_pointer
00611       _M_allocate_map(size_t __n)
00612       {
00613         _Map_alloc_type __map_alloc = _M_get_map_allocator();
00614         return _Map_alloc_traits::allocate(__map_alloc, __n);
00615       }
00616 
00617       void
00618       _M_deallocate_map(_Map_pointer __p, size_t __n) _GLIBCXX_NOEXCEPT
00619       {
00620         _Map_alloc_type __map_alloc = _M_get_map_allocator();
00621         _Map_alloc_traits::deallocate(__map_alloc, __p, __n);
00622       }
00623 
00624     protected:
00625       void _M_initialize_map(size_t);
00626       void _M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish);
00627       void _M_destroy_nodes(_Map_pointer __nstart,
00628                             _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT;
00629       enum { _S_initial_map_size = 8 };
00630 
00631       _Deque_impl _M_impl;
00632 
00633 #if __cplusplus >= 201103L
00634     private:
00635       _Deque_impl
00636       _M_move_impl()
00637       {
00638         if (!_M_impl._M_map)
00639           return std::move(_M_impl);
00640 
00641         // Create a copy of the current allocator.
00642         _Tp_alloc_type __alloc{_M_get_Tp_allocator()};
00643         // Put that copy in a moved-from state.
00644         _Tp_alloc_type __sink __attribute((__unused__)) {std::move(__alloc)};
00645         // Create an empty map that allocates using the moved-from allocator.
00646         _Deque_base __empty{__alloc};
00647         __empty._M_initialize_map(0);
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 #if __cplusplus < 201103L
00834       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00835 #endif
00836       __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
00837 
00838       typedef _Deque_base<_Tp, _Alloc>                  _Base;
00839       typedef typename _Base::_Tp_alloc_type            _Tp_alloc_type;
00840       typedef typename _Base::_Alloc_traits             _Alloc_traits;
00841       typedef typename _Base::_Map_pointer              _Map_pointer;
00842 
00843     public:
00844       typedef _Tp                                        value_type;
00845       typedef typename _Alloc_traits::pointer            pointer;
00846       typedef typename _Alloc_traits::const_pointer      const_pointer;
00847       typedef typename _Alloc_traits::reference          reference;
00848       typedef typename _Alloc_traits::const_reference    const_reference;
00849       typedef typename _Base::iterator                   iterator;
00850       typedef typename _Base::const_iterator             const_iterator;
00851       typedef std::reverse_iterator<const_iterator>      const_reverse_iterator;
00852       typedef std::reverse_iterator<iterator>            reverse_iterator;
00853       typedef size_t                             size_type;
00854       typedef ptrdiff_t                          difference_type;
00855       typedef _Alloc                             allocator_type;
00856 
00857     protected:
00858       static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
00859       { return __deque_buf_size(sizeof(_Tp)); }
00860 
00861       // Functions controlling memory layout, and nothing else.
00862       using _Base::_M_initialize_map;
00863       using _Base::_M_create_nodes;
00864       using _Base::_M_destroy_nodes;
00865       using _Base::_M_allocate_node;
00866       using _Base::_M_deallocate_node;
00867       using _Base::_M_allocate_map;
00868       using _Base::_M_deallocate_map;
00869       using _Base::_M_get_Tp_allocator;
00870 
00871       /** 
00872        *  A total of four data members accumulated down the hierarchy.
00873        *  May be accessed via _M_impl.*
00874        */
00875       using _Base::_M_impl;
00876 
00877     public:
00878       // [23.2.1.1] construct/copy/destroy
00879       // (assign() and get_allocator() are also listed in this section)
00880 
00881       /**
00882        *  @brief  Creates a %deque with no elements.
00883        */
00884       deque() : _Base() { }
00885 
00886       /**
00887        *  @brief  Creates a %deque with no elements.
00888        *  @param  __a  An allocator object.
00889        */
00890       explicit
00891       deque(const allocator_type& __a)
00892       : _Base(__a, 0) { }
00893 
00894 #if __cplusplus >= 201103L
00895       /**
00896        *  @brief  Creates a %deque with default constructed elements.
00897        *  @param  __n  The number of elements to initially create.
00898        *  @param  __a  An allocator.
00899        *
00900        *  This constructor fills the %deque with @a n default
00901        *  constructed elements.
00902        */
00903       explicit
00904       deque(size_type __n, const allocator_type& __a = allocator_type())
00905       : _Base(__a, __n)
00906       { _M_default_initialize(); }
00907 
00908       /**
00909        *  @brief  Creates a %deque with copies of an exemplar element.
00910        *  @param  __n  The number of elements to initially create.
00911        *  @param  __value  An element to copy.
00912        *  @param  __a  An allocator.
00913        *
00914        *  This constructor fills the %deque with @a __n copies of @a __value.
00915        */
00916       deque(size_type __n, const value_type& __value,
00917             const allocator_type& __a = allocator_type())
00918       : _Base(__a, __n)
00919       { _M_fill_initialize(__value); }
00920 #else
00921       /**
00922        *  @brief  Creates a %deque with copies of an exemplar element.
00923        *  @param  __n  The number of elements to initially create.
00924        *  @param  __value  An element to copy.
00925        *  @param  __a  An allocator.
00926        *
00927        *  This constructor fills the %deque with @a __n copies of @a __value.
00928        */
00929       explicit
00930       deque(size_type __n, const value_type& __value = value_type(),
00931             const allocator_type& __a = allocator_type())
00932       : _Base(__a, __n)
00933       { _M_fill_initialize(__value); }
00934 #endif
00935 
00936       /**
00937        *  @brief  %Deque copy constructor.
00938        *  @param  __x  A %deque of identical element and allocator types.
00939        *
00940        *  The newly-created %deque uses a copy of the allocation object used
00941        *  by @a __x.
00942        */
00943       deque(const deque& __x)
00944       : _Base(_Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator()),
00945               __x.size())
00946       { std::__uninitialized_copy_a(__x.begin(), __x.end(), 
00947                                     this->_M_impl._M_start,
00948                                     _M_get_Tp_allocator()); }
00949 
00950 #if __cplusplus >= 201103L
00951       /**
00952        *  @brief  %Deque move constructor.
00953        *  @param  __x  A %deque of identical element and allocator types.
00954        *
00955        *  The newly-created %deque contains the exact contents of @a __x.
00956        *  The contents of @a __x are a valid, but unspecified %deque.
00957        */
00958       deque(deque&& __x)
00959       : _Base(std::move(__x)) { }
00960 
00961       /// Copy constructor with alternative allocator
00962       deque(const deque& __x, const allocator_type& __a)
00963       : _Base(__a, __x.size())
00964       { std::__uninitialized_copy_a(__x.begin(), __x.end(),
00965                                     this->_M_impl._M_start,
00966                                     _M_get_Tp_allocator()); }
00967 
00968       /// Move constructor with alternative allocator
00969       deque(deque&& __x, const allocator_type& __a)
00970       : _Base(std::move(__x), __a, __x.size())
00971       {
00972         if (__x.get_allocator() != __a)
00973           {
00974             std::__uninitialized_move_a(__x.begin(), __x.end(),
00975                                         this->_M_impl._M_start,
00976                                         _M_get_Tp_allocator());
00977             __x.clear();
00978           }
00979       }
00980 
00981       /**
00982        *  @brief  Builds a %deque from an initializer list.
00983        *  @param  __l  An initializer_list.
00984        *  @param  __a  An allocator object.
00985        *
00986        *  Create a %deque consisting of copies of the elements in the
00987        *  initializer_list @a __l.
00988        *
00989        *  This will call the element type's copy constructor N times
00990        *  (where N is __l.size()) and do no memory reallocation.
00991        */
00992       deque(initializer_list<value_type> __l,
00993             const allocator_type& __a = allocator_type())
00994       : _Base(__a)
00995       {
00996         _M_range_initialize(__l.begin(), __l.end(),
00997                             random_access_iterator_tag());
00998       }
00999 #endif
01000 
01001       /**
01002        *  @brief  Builds a %deque from a range.
01003        *  @param  __first  An input iterator.
01004        *  @param  __last  An input iterator.
01005        *  @param  __a  An allocator object.
01006        *
01007        *  Create a %deque consisting of copies of the elements from [__first,
01008        *  __last).
01009        *
01010        *  If the iterators are forward, bidirectional, or random-access, then
01011        *  this will call the elements' copy constructor N times (where N is
01012        *  distance(__first,__last)) and do no memory reallocation.  But if only
01013        *  input iterators are used, then this will do at most 2N calls to the
01014        *  copy constructor, and logN memory reallocations.
01015        */
01016 #if __cplusplus >= 201103L
01017       template<typename _InputIterator,
01018                typename = std::_RequireInputIter<_InputIterator>>
01019         deque(_InputIterator __first, _InputIterator __last,
01020               const allocator_type& __a = allocator_type())
01021         : _Base(__a)
01022         { _M_initialize_dispatch(__first, __last, __false_type()); }
01023 #else
01024       template<typename _InputIterator>
01025         deque(_InputIterator __first, _InputIterator __last,
01026               const allocator_type& __a = allocator_type())
01027         : _Base(__a)
01028         {
01029           // Check whether it's an integral type.  If so, it's not an iterator.
01030           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
01031           _M_initialize_dispatch(__first, __last, _Integral());
01032         }
01033 #endif
01034 
01035       /**
01036        *  The dtor only erases the elements, and note that if the elements
01037        *  themselves are pointers, the pointed-to memory is not touched in any
01038        *  way.  Managing the pointer is the user's responsibility.
01039        */
01040       ~deque()
01041       { _M_destroy_data(begin(), end(), _M_get_Tp_allocator()); }
01042 
01043       /**
01044        *  @brief  %Deque assignment operator.
01045        *  @param  __x  A %deque of identical element and allocator types.
01046        *
01047        *  All the elements of @a x are copied, but unlike the copy constructor,
01048        *  the allocator object is not copied.
01049        */
01050       deque&
01051       operator=(const deque& __x);
01052 
01053 #if __cplusplus >= 201103L
01054       /**
01055        *  @brief  %Deque move assignment operator.
01056        *  @param  __x  A %deque of identical element and allocator types.
01057        *
01058        *  The contents of @a __x are moved into this deque (without copying,
01059        *  if the allocators permit it).
01060        *  @a __x is a valid, but unspecified %deque.
01061        */
01062       deque&
01063       operator=(deque&& __x) noexcept(_Alloc_traits::_S_always_equal())
01064       {
01065         using __always_equal = typename _Alloc_traits::is_always_equal;
01066         _M_move_assign1(std::move(__x), __always_equal{});
01067         return *this;
01068       }
01069 
01070       /**
01071        *  @brief  Assigns an initializer list to a %deque.
01072        *  @param  __l  An initializer_list.
01073        *
01074        *  This function fills a %deque with copies of the elements in the
01075        *  initializer_list @a __l.
01076        *
01077        *  Note that the assignment completely changes the %deque and that the
01078        *  resulting %deque's size is the same as the number of elements
01079        *  assigned.  Old data may be lost.
01080        */
01081       deque&
01082       operator=(initializer_list<value_type> __l)
01083       {
01084         this->assign(__l.begin(), __l.end());
01085         return *this;
01086       }
01087 #endif
01088 
01089       /**
01090        *  @brief  Assigns a given value to a %deque.
01091        *  @param  __n  Number of elements to be assigned.
01092        *  @param  __val  Value to be assigned.
01093        *
01094        *  This function fills a %deque with @a n copies of the given
01095        *  value.  Note that the assignment completely changes the
01096        *  %deque and that the resulting %deque's size is the same as
01097        *  the number of elements assigned.  Old data may be lost.
01098        */
01099       void
01100       assign(size_type __n, const value_type& __val)
01101       { _M_fill_assign(__n, __val); }
01102 
01103       /**
01104        *  @brief  Assigns a range to a %deque.
01105        *  @param  __first  An input iterator.
01106        *  @param  __last   An input iterator.
01107        *
01108        *  This function fills a %deque with copies of the elements in the
01109        *  range [__first,__last).
01110        *
01111        *  Note that the assignment completely changes the %deque and that the
01112        *  resulting %deque's size is the same as the number of elements
01113        *  assigned.  Old data may be lost.
01114        */
01115 #if __cplusplus >= 201103L
01116       template<typename _InputIterator,
01117                typename = std::_RequireInputIter<_InputIterator>>
01118         void
01119         assign(_InputIterator __first, _InputIterator __last)
01120         { _M_assign_dispatch(__first, __last, __false_type()); }
01121 #else
01122       template<typename _InputIterator>
01123         void
01124         assign(_InputIterator __first, _InputIterator __last)
01125         {
01126           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
01127           _M_assign_dispatch(__first, __last, _Integral());
01128         }
01129 #endif
01130 
01131 #if __cplusplus >= 201103L
01132       /**
01133        *  @brief  Assigns an initializer list to a %deque.
01134        *  @param  __l  An initializer_list.
01135        *
01136        *  This function fills a %deque with copies of the elements in the
01137        *  initializer_list @a __l.
01138        *
01139        *  Note that the assignment completely changes the %deque and that the
01140        *  resulting %deque's size is the same as the number of elements
01141        *  assigned.  Old data may be lost.
01142        */
01143       void
01144       assign(initializer_list<value_type> __l)
01145       { this->assign(__l.begin(), __l.end()); }
01146 #endif
01147 
01148       /// Get a copy of the memory allocation object.
01149       allocator_type
01150       get_allocator() const _GLIBCXX_NOEXCEPT
01151       { return _Base::get_allocator(); }
01152 
01153       // iterators
01154       /**
01155        *  Returns a read/write iterator that points to the first element in the
01156        *  %deque.  Iteration is done in ordinary element order.
01157        */
01158       iterator
01159       begin() _GLIBCXX_NOEXCEPT
01160       { return this->_M_impl._M_start; }
01161 
01162       /**
01163        *  Returns a read-only (constant) iterator that points to the first
01164        *  element in the %deque.  Iteration is done in ordinary element order.
01165        */
01166       const_iterator
01167       begin() const _GLIBCXX_NOEXCEPT
01168       { return this->_M_impl._M_start; }
01169 
01170       /**
01171        *  Returns a read/write iterator that points one past the last
01172        *  element in the %deque.  Iteration is done in ordinary
01173        *  element order.
01174        */
01175       iterator
01176       end() _GLIBCXX_NOEXCEPT
01177       { return this->_M_impl._M_finish; }
01178 
01179       /**
01180        *  Returns a read-only (constant) iterator that points one past
01181        *  the last element in the %deque.  Iteration is done in
01182        *  ordinary element order.
01183        */
01184       const_iterator
01185       end() const _GLIBCXX_NOEXCEPT
01186       { return this->_M_impl._M_finish; }
01187 
01188       /**
01189        *  Returns a read/write reverse iterator that points to the
01190        *  last element in the %deque.  Iteration is done in reverse
01191        *  element order.
01192        */
01193       reverse_iterator
01194       rbegin() _GLIBCXX_NOEXCEPT
01195       { return reverse_iterator(this->_M_impl._M_finish); }
01196 
01197       /**
01198        *  Returns a read-only (constant) reverse iterator that points
01199        *  to the last element in the %deque.  Iteration is done in
01200        *  reverse element order.
01201        */
01202       const_reverse_iterator
01203       rbegin() const _GLIBCXX_NOEXCEPT
01204       { return const_reverse_iterator(this->_M_impl._M_finish); }
01205 
01206       /**
01207        *  Returns a read/write reverse iterator that points to one
01208        *  before the first element in the %deque.  Iteration is done
01209        *  in reverse element order.
01210        */
01211       reverse_iterator
01212       rend() _GLIBCXX_NOEXCEPT
01213       { return reverse_iterator(this->_M_impl._M_start); }
01214 
01215       /**
01216        *  Returns a read-only (constant) reverse iterator that points
01217        *  to one before the first element in the %deque.  Iteration is
01218        *  done in reverse element order.
01219        */
01220       const_reverse_iterator
01221       rend() const _GLIBCXX_NOEXCEPT
01222       { return const_reverse_iterator(this->_M_impl._M_start); }
01223 
01224 #if __cplusplus >= 201103L
01225       /**
01226        *  Returns a read-only (constant) iterator that points to the first
01227        *  element in the %deque.  Iteration is done in ordinary element order.
01228        */
01229       const_iterator
01230       cbegin() const noexcept
01231       { return this->_M_impl._M_start; }
01232 
01233       /**
01234        *  Returns a read-only (constant) iterator that points one past
01235        *  the last element in the %deque.  Iteration is done in
01236        *  ordinary element order.
01237        */
01238       const_iterator
01239       cend() const noexcept
01240       { return this->_M_impl._M_finish; }
01241 
01242       /**
01243        *  Returns a read-only (constant) reverse iterator that points
01244        *  to the last element in the %deque.  Iteration is done in
01245        *  reverse element order.
01246        */
01247       const_reverse_iterator
01248       crbegin() const noexcept
01249       { return const_reverse_iterator(this->_M_impl._M_finish); }
01250 
01251       /**
01252        *  Returns a read-only (constant) reverse iterator that points
01253        *  to one before the first element in the %deque.  Iteration is
01254        *  done in reverse element order.
01255        */
01256       const_reverse_iterator
01257       crend() const noexcept
01258       { return const_reverse_iterator(this->_M_impl._M_start); }
01259 #endif
01260 
01261       // [23.2.1.2] capacity
01262       /**  Returns the number of elements in the %deque.  */
01263       size_type
01264       size() const _GLIBCXX_NOEXCEPT
01265       { return this->_M_impl._M_finish - this->_M_impl._M_start; }
01266 
01267       /**  Returns the size() of the largest possible %deque.  */
01268       size_type
01269       max_size() const _GLIBCXX_NOEXCEPT
01270       { return _Alloc_traits::max_size(_M_get_Tp_allocator()); }
01271 
01272 #if __cplusplus >= 201103L
01273       /**
01274        *  @brief  Resizes the %deque to the specified number of elements.
01275        *  @param  __new_size  Number of elements the %deque should contain.
01276        *
01277        *  This function will %resize the %deque to the specified
01278        *  number of elements.  If the number is smaller than the
01279        *  %deque's current size the %deque is truncated, otherwise
01280        *  default constructed elements are appended.
01281        */
01282       void
01283       resize(size_type __new_size)
01284       {
01285         const size_type __len = size();
01286         if (__new_size > __len)
01287           _M_default_append(__new_size - __len);
01288         else if (__new_size < __len)
01289           _M_erase_at_end(this->_M_impl._M_start
01290                           + difference_type(__new_size));
01291       }
01292 
01293       /**
01294        *  @brief  Resizes the %deque to the specified number of elements.
01295        *  @param  __new_size  Number of elements the %deque should contain.
01296        *  @param  __x  Data with which new elements should be populated.
01297        *
01298        *  This function will %resize the %deque to the specified
01299        *  number of elements.  If the number is smaller than the
01300        *  %deque's current size the %deque is truncated, otherwise the
01301        *  %deque is extended and new elements are populated with given
01302        *  data.
01303        */
01304       void
01305       resize(size_type __new_size, const value_type& __x)
01306       {
01307         const size_type __len = size();
01308         if (__new_size > __len)
01309           insert(this->_M_impl._M_finish, __new_size - __len, __x);
01310         else if (__new_size < __len)
01311           _M_erase_at_end(this->_M_impl._M_start
01312                           + difference_type(__new_size));
01313       }
01314 #else
01315       /**
01316        *  @brief  Resizes the %deque to the specified number of elements.
01317        *  @param  __new_size  Number of elements the %deque should contain.
01318        *  @param  __x  Data with which new elements should be populated.
01319        *
01320        *  This function will %resize the %deque to the specified
01321        *  number of elements.  If the number is smaller than the
01322        *  %deque's current size the %deque is truncated, otherwise the
01323        *  %deque is extended and new elements are populated with given
01324        *  data.
01325        */
01326       void
01327       resize(size_type __new_size, value_type __x = value_type())
01328       {
01329         const size_type __len = size();
01330         if (__new_size > __len)
01331           insert(this->_M_impl._M_finish, __new_size - __len, __x);
01332         else if (__new_size < __len)
01333           _M_erase_at_end(this->_M_impl._M_start
01334                           + difference_type(__new_size));
01335       }
01336 #endif
01337 
01338 #if __cplusplus >= 201103L
01339       /**  A non-binding request to reduce memory use.  */
01340       void
01341       shrink_to_fit() noexcept
01342       { _M_shrink_to_fit(); }
01343 #endif
01344 
01345       /**
01346        *  Returns true if the %deque is empty.  (Thus begin() would
01347        *  equal end().)
01348        */
01349       bool
01350       empty() const _GLIBCXX_NOEXCEPT
01351       { return this->_M_impl._M_finish == this->_M_impl._M_start; }
01352 
01353       // element access
01354       /**
01355        *  @brief Subscript access to the data contained in the %deque.
01356        *  @param __n The index of the element for which data should be
01357        *  accessed.
01358        *  @return  Read/write reference to data.
01359        *
01360        *  This operator allows for easy, array-style, data access.
01361        *  Note that data access with this operator is unchecked and
01362        *  out_of_range lookups are not defined. (For checked lookups
01363        *  see at().)
01364        */
01365       reference
01366       operator[](size_type __n) _GLIBCXX_NOEXCEPT
01367       { return this->_M_impl._M_start[difference_type(__n)]; }
01368 
01369       /**
01370        *  @brief Subscript access to the data contained in the %deque.
01371        *  @param __n The index of the element for which data should be
01372        *  accessed.
01373        *  @return  Read-only (constant) reference to data.
01374        *
01375        *  This operator allows for easy, array-style, data access.
01376        *  Note that data access with this operator is unchecked and
01377        *  out_of_range lookups are not defined. (For checked lookups
01378        *  see at().)
01379        */
01380       const_reference
01381       operator[](size_type __n) const _GLIBCXX_NOEXCEPT
01382       { return this->_M_impl._M_start[difference_type(__n)]; }
01383 
01384     protected:
01385       /// Safety check used only from at().
01386       void
01387       _M_range_check(size_type __n) const
01388       {
01389         if (__n >= this->size())
01390           __throw_out_of_range_fmt(__N("deque::_M_range_check: __n "
01391                                        "(which is %zu)>= this->size() "
01392                                        "(which is %zu)"),
01393                                    __n, this->size());
01394       }
01395 
01396     public:
01397       /**
01398        *  @brief  Provides access to the data contained in the %deque.
01399        *  @param __n The index of the element for which data should be
01400        *  accessed.
01401        *  @return  Read/write reference to data.
01402        *  @throw  std::out_of_range  If @a __n is an invalid index.
01403        *
01404        *  This function provides for safer data access.  The parameter
01405        *  is first checked that it is in the range of the deque.  The
01406        *  function throws out_of_range if the check fails.
01407        */
01408       reference
01409       at(size_type __n)
01410       {
01411         _M_range_check(__n);
01412         return (*this)[__n];
01413       }
01414 
01415       /**
01416        *  @brief  Provides access to the data contained in the %deque.
01417        *  @param __n The index of the element for which data should be
01418        *  accessed.
01419        *  @return  Read-only (constant) reference to data.
01420        *  @throw  std::out_of_range  If @a __n is an invalid index.
01421        *
01422        *  This function provides for safer data access.  The parameter is first
01423        *  checked that it is in the range of the deque.  The function throws
01424        *  out_of_range if the check fails.
01425        */
01426       const_reference
01427       at(size_type __n) const
01428       {
01429         _M_range_check(__n);
01430         return (*this)[__n];
01431       }
01432 
01433       /**
01434        *  Returns a read/write reference to the data at the first
01435        *  element of the %deque.
01436        */
01437       reference
01438       front() _GLIBCXX_NOEXCEPT
01439       { return *begin(); }
01440 
01441       /**
01442        *  Returns a read-only (constant) reference to the data at the first
01443        *  element of the %deque.
01444        */
01445       const_reference
01446       front() const _GLIBCXX_NOEXCEPT
01447       { return *begin(); }
01448 
01449       /**
01450        *  Returns a read/write reference to the data at the last element of the
01451        *  %deque.
01452        */
01453       reference
01454       back() _GLIBCXX_NOEXCEPT
01455       {
01456         iterator __tmp = end();
01457         --__tmp;
01458         return *__tmp;
01459       }
01460 
01461       /**
01462        *  Returns a read-only (constant) reference to the data at the last
01463        *  element of the %deque.
01464        */
01465       const_reference
01466       back() const _GLIBCXX_NOEXCEPT
01467       {
01468         const_iterator __tmp = end();
01469         --__tmp;
01470         return *__tmp;
01471       }
01472 
01473       // [23.2.1.2] modifiers
01474       /**
01475        *  @brief  Add data to the front of the %deque.
01476        *  @param  __x  Data to be added.
01477        *
01478        *  This is a typical stack operation.  The function creates an
01479        *  element at the front of the %deque and assigns the given
01480        *  data to it.  Due to the nature of a %deque this operation
01481        *  can be done in constant time.
01482        */
01483       void
01484       push_front(const value_type& __x)
01485       {
01486         if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
01487           {
01488             _Alloc_traits::construct(this->_M_impl,
01489                                      this->_M_impl._M_start._M_cur - 1,
01490                                      __x);
01491             --this->_M_impl._M_start._M_cur;
01492           }
01493         else
01494           _M_push_front_aux(__x);
01495       }
01496 
01497 #if __cplusplus >= 201103L
01498       void
01499       push_front(value_type&& __x)
01500       { emplace_front(std::move(__x)); }
01501 
01502       template<typename... _Args>
01503         void
01504         emplace_front(_Args&&... __args);
01505 #endif
01506 
01507       /**
01508        *  @brief  Add data to the end of the %deque.
01509        *  @param  __x  Data to be added.
01510        *
01511        *  This is a typical stack operation.  The function creates an
01512        *  element at the end of the %deque and assigns the given data
01513        *  to it.  Due to the nature of a %deque this operation can be
01514        *  done in constant time.
01515        */
01516       void
01517       push_back(const value_type& __x)
01518       {
01519         if (this->_M_impl._M_finish._M_cur
01520             != this->_M_impl._M_finish._M_last - 1)
01521           {
01522             _Alloc_traits::construct(this->_M_impl,
01523                                      this->_M_impl._M_finish._M_cur, __x);
01524             ++this->_M_impl._M_finish._M_cur;
01525           }
01526         else
01527           _M_push_back_aux(__x);
01528       }
01529 
01530 #if __cplusplus >= 201103L
01531       void
01532       push_back(value_type&& __x)
01533       { emplace_back(std::move(__x)); }
01534 
01535       template<typename... _Args>
01536         void
01537         emplace_back(_Args&&... __args);
01538 #endif
01539 
01540       /**
01541        *  @brief  Removes first element.
01542        *
01543        *  This is a typical stack operation.  It shrinks the %deque by one.
01544        *
01545        *  Note that no data is returned, and if the first element's data is
01546        *  needed, it should be retrieved before pop_front() is called.
01547        */
01548       void
01549       pop_front() _GLIBCXX_NOEXCEPT
01550       {
01551         if (this->_M_impl._M_start._M_cur
01552             != this->_M_impl._M_start._M_last - 1)
01553           {
01554             _Alloc_traits::destroy(this->_M_impl,
01555                                    this->_M_impl._M_start._M_cur);
01556             ++this->_M_impl._M_start._M_cur;
01557           }
01558         else
01559           _M_pop_front_aux();
01560       }
01561 
01562       /**
01563        *  @brief  Removes last element.
01564        *
01565        *  This is a typical stack operation.  It shrinks the %deque by one.
01566        *
01567        *  Note that no data is returned, and if the last element's data is
01568        *  needed, it should be retrieved before pop_back() is called.
01569        */
01570       void
01571       pop_back() _GLIBCXX_NOEXCEPT
01572       {
01573         if (this->_M_impl._M_finish._M_cur
01574             != this->_M_impl._M_finish._M_first)
01575           {
01576             --this->_M_impl._M_finish._M_cur;
01577             _Alloc_traits::destroy(this->_M_impl,
01578                                    this->_M_impl._M_finish._M_cur);
01579           }
01580         else
01581           _M_pop_back_aux();
01582       }
01583 
01584 #if __cplusplus >= 201103L
01585       /**
01586        *  @brief  Inserts an object in %deque before specified iterator.
01587        *  @param  __position  A const_iterator into the %deque.
01588        *  @param  __args  Arguments.
01589        *  @return  An iterator that points to the inserted data.
01590        *
01591        *  This function will insert an object of type T constructed
01592        *  with T(std::forward<Args>(args)...) before the specified location.
01593        */
01594       template<typename... _Args>
01595         iterator
01596         emplace(const_iterator __position, _Args&&... __args);
01597 
01598       /**
01599        *  @brief  Inserts given value into %deque before specified iterator.
01600        *  @param  __position  A const_iterator into the %deque.
01601        *  @param  __x  Data to be inserted.
01602        *  @return  An iterator that points to the inserted data.
01603        *
01604        *  This function will insert a copy of the given value before the
01605        *  specified location.
01606        */
01607       iterator
01608       insert(const_iterator __position, const value_type& __x);
01609 #else
01610       /**
01611        *  @brief  Inserts given value into %deque before specified iterator.
01612        *  @param  __position  An iterator into the %deque.
01613        *  @param  __x  Data to be inserted.
01614        *  @return  An iterator that points to the inserted data.
01615        *
01616        *  This function will insert a copy of the given value before the
01617        *  specified location.
01618        */
01619       iterator
01620       insert(iterator __position, const value_type& __x);
01621 #endif
01622 
01623 #if __cplusplus >= 201103L
01624       /**
01625        *  @brief  Inserts given rvalue into %deque before specified iterator.
01626        *  @param  __position  A const_iterator into the %deque.
01627        *  @param  __x  Data to be inserted.
01628        *  @return  An iterator that points to the inserted data.
01629        *
01630        *  This function will insert a copy of the given rvalue before the
01631        *  specified location.
01632        */
01633       iterator
01634       insert(const_iterator __position, value_type&& __x)
01635       { return emplace(__position, std::move(__x)); }
01636 
01637       /**
01638        *  @brief  Inserts an initializer list into the %deque.
01639        *  @param  __p  An iterator into the %deque.
01640        *  @param  __l  An initializer_list.
01641        *
01642        *  This function will insert copies of the data in the
01643        *  initializer_list @a __l into the %deque before the location
01644        *  specified by @a __p.  This is known as <em>list insert</em>.
01645        */
01646       iterator
01647       insert(const_iterator __p, initializer_list<value_type> __l)
01648       { return this->insert(__p, __l.begin(), __l.end()); }
01649 #endif
01650 
01651 #if __cplusplus >= 201103L
01652       /**
01653        *  @brief  Inserts a number of copies of given data into the %deque.
01654        *  @param  __position  A const_iterator into the %deque.
01655        *  @param  __n  Number of elements to be inserted.
01656        *  @param  __x  Data to be inserted.
01657        *  @return  An iterator that points to the inserted data.
01658        *
01659        *  This function will insert a specified number of copies of the given
01660        *  data before the location specified by @a __position.
01661        */
01662       iterator
01663       insert(const_iterator __position, size_type __n, const value_type& __x)
01664       {
01665         difference_type __offset = __position - cbegin();
01666         _M_fill_insert(__position._M_const_cast(), __n, __x);
01667         return begin() + __offset;
01668       }
01669 #else
01670       /**
01671        *  @brief  Inserts a number of copies of given data into the %deque.
01672        *  @param  __position  An iterator into the %deque.
01673        *  @param  __n  Number of elements to be inserted.
01674        *  @param  __x  Data to be inserted.
01675        *
01676        *  This function will insert a specified number of copies of the given
01677        *  data before the location specified by @a __position.
01678        */
01679       void
01680       insert(iterator __position, size_type __n, const value_type& __x)
01681       { _M_fill_insert(__position, __n, __x); }
01682 #endif
01683 
01684 #if __cplusplus >= 201103L
01685       /**
01686        *  @brief  Inserts a range into the %deque.
01687        *  @param  __position  A const_iterator into the %deque.
01688        *  @param  __first  An input iterator.
01689        *  @param  __last   An input iterator.
01690        *  @return  An iterator that points to the inserted data.
01691        *
01692        *  This function will insert copies of the data in the range
01693        *  [__first,__last) into the %deque before the location specified
01694        *  by @a __position.  This is known as <em>range insert</em>.
01695        */
01696       template<typename _InputIterator,
01697                typename = std::_RequireInputIter<_InputIterator>>
01698         iterator
01699         insert(const_iterator __position, _InputIterator __first,
01700                _InputIterator __last)
01701         {
01702           difference_type __offset = __position - cbegin();
01703           _M_insert_dispatch(__position._M_const_cast(),
01704                              __first, __last, __false_type());
01705           return begin() + __offset;
01706         }
01707 #else
01708       /**
01709        *  @brief  Inserts a range into the %deque.
01710        *  @param  __position  An iterator into the %deque.
01711        *  @param  __first  An input iterator.
01712        *  @param  __last   An input iterator.
01713        *
01714        *  This function will insert copies of the data in the range
01715        *  [__first,__last) into the %deque before the location specified
01716        *  by @a __position.  This is known as <em>range insert</em>.
01717        */
01718       template<typename _InputIterator>
01719         void
01720         insert(iterator __position, _InputIterator __first,
01721                _InputIterator __last)
01722         {
01723           // Check whether it's an integral type.  If so, it's not an iterator.
01724           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
01725           _M_insert_dispatch(__position, __first, __last, _Integral());
01726         }
01727 #endif
01728 
01729       /**
01730        *  @brief  Remove element at given position.
01731        *  @param  __position  Iterator pointing to element to be erased.
01732        *  @return  An iterator pointing to the next element (or end()).
01733        *
01734        *  This function will erase the element at the given position and thus
01735        *  shorten the %deque by one.
01736        *
01737        *  The user is cautioned that
01738        *  this function only erases the element, and that if the element is
01739        *  itself a pointer, the pointed-to memory is not touched in any way.
01740        *  Managing the pointer is the user's responsibility.
01741        */
01742       iterator
01743 #if __cplusplus >= 201103L
01744       erase(const_iterator __position)
01745 #else
01746       erase(iterator __position)
01747 #endif
01748       { return _M_erase(__position._M_const_cast()); }
01749 
01750       /**
01751        *  @brief  Remove a range of elements.
01752        *  @param  __first  Iterator pointing to the first element to be erased.
01753        *  @param  __last  Iterator pointing to one past the last element to be
01754        *                erased.
01755        *  @return  An iterator pointing to the element pointed to by @a last
01756        *           prior to erasing (or end()).
01757        *
01758        *  This function will erase the elements in the range
01759        *  [__first,__last) and shorten the %deque accordingly.
01760        *
01761        *  The user is cautioned that
01762        *  this function only erases the elements, and that if the elements
01763        *  themselves are pointers, the pointed-to memory is not touched in any
01764        *  way.  Managing the pointer is the user's responsibility.
01765        */
01766       iterator
01767 #if __cplusplus >= 201103L
01768       erase(const_iterator __first, const_iterator __last)
01769 #else
01770       erase(iterator __first, iterator __last)
01771 #endif
01772       { return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
01773 
01774       /**
01775        *  @brief  Swaps data with another %deque.
01776        *  @param  __x  A %deque of the same element and allocator types.
01777        *
01778        *  This exchanges the elements between two deques in constant time.
01779        *  (Four pointers, so it should be quite fast.)
01780        *  Note that the global std::swap() function is specialized such that
01781        *  std::swap(d1,d2) will feed to this function.
01782        */
01783       void
01784       swap(deque& __x) _GLIBCXX_NOEXCEPT
01785       {
01786         _M_impl._M_swap_data(__x._M_impl);
01787         _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
01788                                   __x._M_get_Tp_allocator());
01789       }
01790 
01791       /**
01792        *  Erases all the elements.  Note that this function only erases the
01793        *  elements, and that if the elements themselves are pointers, the
01794        *  pointed-to memory is not touched in any way.  Managing the pointer is
01795        *  the user's responsibility.
01796        */
01797       void
01798       clear() _GLIBCXX_NOEXCEPT
01799       { _M_erase_at_end(begin()); }
01800 
01801     protected:
01802       // Internal constructor functions follow.
01803 
01804       // called by the range constructor to implement [23.1.1]/9
01805 
01806       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01807       // 438. Ambiguity in the "do the right thing" clause
01808       template<typename _Integer>
01809         void
01810         _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
01811         {
01812           _M_initialize_map(static_cast<size_type>(__n));
01813           _M_fill_initialize(__x);
01814         }
01815 
01816       // called by the range constructor to implement [23.1.1]/9
01817       template<typename _InputIterator>
01818         void
01819         _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
01820                                __false_type)
01821         {
01822           typedef typename std::iterator_traits<_InputIterator>::
01823             iterator_category _IterCategory;
01824           _M_range_initialize(__first, __last, _IterCategory());
01825         }
01826 
01827       // called by the second initialize_dispatch above
01828       //@{
01829       /**
01830        *  @brief Fills the deque with whatever is in [first,last).
01831        *  @param  __first  An input iterator.
01832        *  @param  __last  An input iterator.
01833        *  @return   Nothing.
01834        *
01835        *  If the iterators are actually forward iterators (or better), then the
01836        *  memory layout can be done all at once.  Else we move forward using
01837        *  push_back on each value from the iterator.
01838        */
01839       template<typename _InputIterator>
01840         void
01841         _M_range_initialize(_InputIterator __first, _InputIterator __last,
01842                             std::input_iterator_tag);
01843 
01844       // called by the second initialize_dispatch above
01845       template<typename _ForwardIterator>
01846         void
01847         _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
01848                             std::forward_iterator_tag);
01849       //@}
01850 
01851       /**
01852        *  @brief Fills the %deque with copies of value.
01853        *  @param  __value  Initial value.
01854        *  @return   Nothing.
01855        *  @pre _M_start and _M_finish have already been initialized,
01856        *  but none of the %deque's elements have yet been constructed.
01857        *
01858        *  This function is called only when the user provides an explicit size
01859        *  (with or without an explicit exemplar value).
01860        */
01861       void
01862       _M_fill_initialize(const value_type& __value);
01863 
01864 #if __cplusplus >= 201103L
01865       // called by deque(n).
01866       void
01867       _M_default_initialize();
01868 #endif
01869 
01870       // Internal assign functions follow.  The *_aux functions do the actual
01871       // assignment work for the range versions.
01872 
01873       // called by the range assign to implement [23.1.1]/9
01874 
01875       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01876       // 438. Ambiguity in the "do the right thing" clause
01877       template<typename _Integer>
01878         void
01879         _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
01880         { _M_fill_assign(__n, __val); }
01881 
01882       // called by the range assign to implement [23.1.1]/9
01883       template<typename _InputIterator>
01884         void
01885         _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
01886                            __false_type)
01887         {
01888           typedef typename std::iterator_traits<_InputIterator>::
01889             iterator_category _IterCategory;
01890           _M_assign_aux(__first, __last, _IterCategory());
01891         }
01892 
01893       // called by the second assign_dispatch above
01894       template<typename _InputIterator>
01895         void
01896         _M_assign_aux(_InputIterator __first, _InputIterator __last,
01897                       std::input_iterator_tag);
01898 
01899       // called by the second assign_dispatch above
01900       template<typename _ForwardIterator>
01901         void
01902         _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
01903                       std::forward_iterator_tag)
01904         {
01905           const size_type __len = std::distance(__first, __last);
01906           if (__len > size())
01907             {
01908               _ForwardIterator __mid = __first;
01909               std::advance(__mid, size());
01910               std::copy(__first, __mid, begin());
01911               insert(end(), __mid, __last);
01912             }
01913           else
01914             _M_erase_at_end(std::copy(__first, __last, begin()));
01915         }
01916 
01917       // Called by assign(n,t), and the range assign when it turns out
01918       // to be the same thing.
01919       void
01920       _M_fill_assign(size_type __n, const value_type& __val)
01921       {
01922         if (__n > size())
01923           {
01924             std::fill(begin(), end(), __val);
01925             insert(end(), __n - size(), __val);
01926           }
01927         else
01928           {
01929             _M_erase_at_end(begin() + difference_type(__n));
01930             std::fill(begin(), end(), __val);
01931           }
01932       }
01933 
01934       //@{
01935       /// Helper functions for push_* and pop_*.
01936 #if __cplusplus < 201103L
01937       void _M_push_back_aux(const value_type&);
01938 
01939       void _M_push_front_aux(const value_type&);
01940 #else
01941       template<typename... _Args>
01942         void _M_push_back_aux(_Args&&... __args);
01943 
01944       template<typename... _Args>
01945         void _M_push_front_aux(_Args&&... __args);
01946 #endif
01947 
01948       void _M_pop_back_aux();
01949 
01950       void _M_pop_front_aux();
01951       //@}
01952 
01953       // Internal insert functions follow.  The *_aux functions do the actual
01954       // insertion work when all shortcuts fail.
01955 
01956       // called by the range insert to implement [23.1.1]/9
01957 
01958       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01959       // 438. Ambiguity in the "do the right thing" clause
01960       template<typename _Integer>
01961         void
01962         _M_insert_dispatch(iterator __pos,
01963                            _Integer __n, _Integer __x, __true_type)
01964         { _M_fill_insert(__pos, __n, __x); }
01965 
01966       // called by the range insert to implement [23.1.1]/9
01967       template<typename _InputIterator>
01968         void
01969         _M_insert_dispatch(iterator __pos,
01970                            _InputIterator __first, _InputIterator __last,
01971                            __false_type)
01972         {
01973           typedef typename std::iterator_traits<_InputIterator>::
01974             iterator_category _IterCategory;
01975           _M_range_insert_aux(__pos, __first, __last, _IterCategory());
01976         }
01977 
01978       // called by the second insert_dispatch above
01979       template<typename _InputIterator>
01980         void
01981         _M_range_insert_aux(iterator __pos, _InputIterator __first,
01982                             _InputIterator __last, std::input_iterator_tag);
01983 
01984       // called by the second insert_dispatch above
01985       template<typename _ForwardIterator>
01986         void
01987         _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
01988                             _ForwardIterator __last, std::forward_iterator_tag);
01989 
01990       // Called by insert(p,n,x), and the range insert when it turns out to be
01991       // the same thing.  Can use fill functions in optimal situations,
01992       // otherwise passes off to insert_aux(p,n,x).
01993       void
01994       _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
01995 
01996       // called by insert(p,x)
01997 #if __cplusplus < 201103L
01998       iterator
01999       _M_insert_aux(iterator __pos, const value_type& __x);
02000 #else
02001       template<typename... _Args>
02002         iterator
02003         _M_insert_aux(iterator __pos, _Args&&... __args);
02004 #endif
02005 
02006       // called by insert(p,n,x) via fill_insert
02007       void
02008       _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
02009 
02010       // called by range_insert_aux for forward iterators
02011       template<typename _ForwardIterator>
02012         void
02013         _M_insert_aux(iterator __pos,
02014                       _ForwardIterator __first, _ForwardIterator __last,
02015                       size_type __n);
02016 
02017 
02018       // Internal erase functions follow.
02019 
02020       void
02021       _M_destroy_data_aux(iterator __first, iterator __last);
02022 
02023       // Called by ~deque().
02024       // NB: Doesn't deallocate the nodes.
02025       template<typename _Alloc1>
02026         void
02027         _M_destroy_data(iterator __first, iterator __last, const _Alloc1&)
02028         { _M_destroy_data_aux(__first, __last); }
02029 
02030       void
02031       _M_destroy_data(iterator __first, iterator __last,
02032                       const std::allocator<_Tp>&)
02033       {
02034         if (!__has_trivial_destructor(value_type))
02035           _M_destroy_data_aux(__first, __last);
02036       }
02037 
02038       // Called by erase(q1, q2).
02039       void
02040       _M_erase_at_begin(iterator __pos)
02041       {
02042         _M_destroy_data(begin(), __pos, _M_get_Tp_allocator());
02043         _M_destroy_nodes(this->_M_impl._M_start._M_node, __pos._M_node);
02044         this->_M_impl._M_start = __pos;
02045       }
02046 
02047       // Called by erase(q1, q2), resize(), clear(), _M_assign_aux,
02048       // _M_fill_assign, operator=.
02049       void
02050       _M_erase_at_end(iterator __pos)
02051       {
02052         _M_destroy_data(__pos, end(), _M_get_Tp_allocator());
02053         _M_destroy_nodes(__pos._M_node + 1,
02054                          this->_M_impl._M_finish._M_node + 1);
02055         this->_M_impl._M_finish = __pos;
02056       }
02057 
02058       iterator
02059       _M_erase(iterator __pos);
02060 
02061       iterator
02062       _M_erase(iterator __first, iterator __last);
02063 
02064 #if __cplusplus >= 201103L
02065       // Called by resize(sz).
02066       void
02067       _M_default_append(size_type __n);
02068 
02069       bool
02070       _M_shrink_to_fit();
02071 #endif
02072 
02073       //@{
02074       /// Memory-handling helpers for the previous internal insert functions.
02075       iterator
02076       _M_reserve_elements_at_front(size_type __n)
02077       {
02078         const size_type __vacancies = this->_M_impl._M_start._M_cur
02079                                       - this->_M_impl._M_start._M_first;
02080         if (__n > __vacancies)
02081           _M_new_elements_at_front(__n - __vacancies);
02082         return this->_M_impl._M_start - difference_type(__n);
02083       }
02084 
02085       iterator
02086       _M_reserve_elements_at_back(size_type __n)
02087       {
02088         const size_type __vacancies = (this->_M_impl._M_finish._M_last
02089                                        - this->_M_impl._M_finish._M_cur) - 1;
02090         if (__n > __vacancies)
02091           _M_new_elements_at_back(__n - __vacancies);
02092         return this->_M_impl._M_finish + difference_type(__n);
02093       }
02094 
02095       void
02096       _M_new_elements_at_front(size_type __new_elements);
02097 
02098       void
02099       _M_new_elements_at_back(size_type __new_elements);
02100       //@}
02101 
02102 
02103       //@{
02104       /**
02105        *  @brief Memory-handling helpers for the major %map.
02106        *
02107        *  Makes sure the _M_map has space for new nodes.  Does not
02108        *  actually add the nodes.  Can invalidate _M_map pointers.
02109        *  (And consequently, %deque iterators.)
02110        */
02111       void
02112       _M_reserve_map_at_back(size_type __nodes_to_add = 1)
02113       {
02114         if (__nodes_to_add + 1 > this->_M_impl._M_map_size
02115             - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
02116           _M_reallocate_map(__nodes_to_add, false);
02117       }
02118 
02119       void
02120       _M_reserve_map_at_front(size_type __nodes_to_add = 1)
02121       {
02122         if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node
02123                                        - this->_M_impl._M_map))
02124           _M_reallocate_map(__nodes_to_add, true);
02125       }
02126 
02127       void
02128       _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
02129       //@}
02130 
02131 #if __cplusplus >= 201103L
02132       // Constant-time, nothrow move assignment when source object's memory
02133       // can be moved because the allocators are equal.
02134       void
02135       _M_move_assign1(deque&& __x, /* always equal: */ true_type) noexcept
02136       {
02137         this->_M_impl._M_swap_data(__x._M_impl);
02138         __x.clear();
02139         std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
02140       }
02141 
02142       // When the allocators are not equal the operation could throw, because
02143       // we might need to allocate a new map for __x after moving from it
02144       // or we might need to allocate new elements for *this.
02145       void
02146       _M_move_assign1(deque&& __x, /* always equal: */ false_type)
02147       {
02148         constexpr bool __move_storage =
02149           _Alloc_traits::_S_propagate_on_move_assign();
02150         _M_move_assign2(std::move(__x), __bool_constant<__move_storage>());
02151       }
02152 
02153       // Destroy all elements and deallocate all memory, then replace
02154       // with elements created from __args.
02155       template<typename... _Args>
02156       void
02157       _M_replace_map(_Args&&... __args)
02158       {
02159         // Create new data first, so if allocation fails there are no effects.
02160         deque __newobj(std::forward<_Args>(__args)...);
02161         // Free existing storage using existing allocator.
02162         clear();
02163         _M_deallocate_node(*begin()._M_node); // one node left after clear()
02164         _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
02165         this->_M_impl._M_map = nullptr;
02166         this->_M_impl._M_map_size = 0;
02167         // Take ownership of replacement memory.
02168         this->_M_impl._M_swap_data(__newobj._M_impl);
02169       }
02170 
02171       // Do move assignment when the allocator propagates.
02172       void
02173       _M_move_assign2(deque&& __x, /* propagate: */ true_type)
02174       {
02175         // Make a copy of the original allocator state.
02176         auto __alloc = __x._M_get_Tp_allocator();
02177         // The allocator propagates so storage can be moved from __x,
02178         // leaving __x in a valid empty state with a moved-from allocator.
02179         _M_replace_map(std::move(__x));
02180         // Move the corresponding allocator state too.
02181         _M_get_Tp_allocator() = std::move(__alloc);
02182       }
02183 
02184       // Do move assignment when it may not be possible to move source
02185       // object's memory, resulting in a linear-time operation.
02186       void
02187       _M_move_assign2(deque&& __x, /* propagate: */ false_type)
02188       {
02189         if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
02190           {
02191             // The allocators are equal so storage can be moved from __x,
02192             // leaving __x in a valid empty state with its current allocator.
02193             _M_replace_map(std::move(__x), __x.get_allocator());
02194           }
02195         else
02196           {
02197             // The rvalue's allocator cannot be moved and is not equal,
02198             // so we need to individually move each element.
02199             this->assign(std::__make_move_if_noexcept_iterator(__x.begin()),
02200                          std::__make_move_if_noexcept_iterator(__x.end()));
02201             __x.clear();
02202           }
02203       }
02204 #endif
02205     };
02206 
02207 
02208   /**
02209    *  @brief  Deque equality comparison.
02210    *  @param  __x  A %deque.
02211    *  @param  __y  A %deque of the same type as @a __x.
02212    *  @return  True iff the size and elements of the deques are equal.
02213    *
02214    *  This is an equivalence relation.  It is linear in the size of the
02215    *  deques.  Deques are considered equivalent if their sizes are equal,
02216    *  and if corresponding elements compare equal.
02217   */
02218   template<typename _Tp, typename _Alloc>
02219     inline bool
02220     operator==(const deque<_Tp, _Alloc>& __x,
02221                          const deque<_Tp, _Alloc>& __y)
02222     { return __x.size() == __y.size()
02223              && std::equal(__x.begin(), __x.end(), __y.begin()); }
02224 
02225   /**
02226    *  @brief  Deque ordering relation.
02227    *  @param  __x  A %deque.
02228    *  @param  __y  A %deque of the same type as @a __x.
02229    *  @return  True iff @a x is lexicographically less than @a __y.
02230    *
02231    *  This is a total ordering relation.  It is linear in the size of the
02232    *  deques.  The elements must be comparable with @c <.
02233    *
02234    *  See std::lexicographical_compare() for how the determination is made.
02235   */
02236   template<typename _Tp, typename _Alloc>
02237     inline bool
02238     operator<(const deque<_Tp, _Alloc>& __x,
02239               const deque<_Tp, _Alloc>& __y)
02240     { return std::lexicographical_compare(__x.begin(), __x.end(),
02241                                           __y.begin(), __y.end()); }
02242 
02243   /// Based on operator==
02244   template<typename _Tp, typename _Alloc>
02245     inline bool
02246     operator!=(const deque<_Tp, _Alloc>& __x,
02247                const deque<_Tp, _Alloc>& __y)
02248     { return !(__x == __y); }
02249 
02250   /// Based on operator<
02251   template<typename _Tp, typename _Alloc>
02252     inline bool
02253     operator>(const deque<_Tp, _Alloc>& __x,
02254               const deque<_Tp, _Alloc>& __y)
02255     { return __y < __x; }
02256 
02257   /// Based on operator<
02258   template<typename _Tp, typename _Alloc>
02259     inline bool
02260     operator<=(const deque<_Tp, _Alloc>& __x,
02261                const deque<_Tp, _Alloc>& __y)
02262     { return !(__y < __x); }
02263 
02264   /// Based on operator<
02265   template<typename _Tp, typename _Alloc>
02266     inline bool
02267     operator>=(const deque<_Tp, _Alloc>& __x,
02268                const deque<_Tp, _Alloc>& __y)
02269     { return !(__x < __y); }
02270 
02271   /// See std::deque::swap().
02272   template<typename _Tp, typename _Alloc>
02273     inline void
02274     swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y)
02275     _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
02276     { __x.swap(__y); }
02277 
02278 #undef _GLIBCXX_DEQUE_BUF_SIZE
02279 
02280 _GLIBCXX_END_NAMESPACE_CONTAINER
02281 } // namespace std
02282 
02283 #endif /* _STL_DEQUE_H */