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