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