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