Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. // Deque implementation -*- C++ -*-
  2.  
  3. // Copyright (C) 2001-2015 Free Software Foundation, Inc.
  4. //
  5. // This file is part of the GNU ISO C++ Library.  This library is free
  6. // software; you can redistribute it and/or modify it under the
  7. // terms of the GNU General Public License as published by the
  8. // Free Software Foundation; either version 3, or (at your option)
  9. // any later version.
  10.  
  11. // This library is distributed in the hope that it will be useful,
  12. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. // GNU General Public License for more details.
  15.  
  16. // Under Section 7 of GPL version 3, you are granted additional
  17. // permissions described in the GCC Runtime Library Exception, version
  18. // 3.1, as published by the Free Software Foundation.
  19.  
  20. // You should have received a copy of the GNU General Public License and
  21. // a copy of the GCC Runtime Library Exception along with this program;
  22. // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23. // <http://www.gnu.org/licenses/>.
  24.  
  25. /*
  26.  *
  27.  * Copyright (c) 1994
  28.  * Hewlett-Packard Company
  29.  *
  30.  * Permission to use, copy, modify, distribute and sell this software
  31.  * and its documentation for any purpose is hereby granted without fee,
  32.  * provided that the above copyright notice appear in all copies and
  33.  * that both that copyright notice and this permission notice appear
  34.  * in supporting documentation.  Hewlett-Packard Company makes no
  35.  * representations about the suitability of this software for any
  36.  * purpose.  It is provided "as is" without express or implied warranty.
  37.  *
  38.  *
  39.  * Copyright (c) 1997
  40.  * Silicon Graphics Computer Systems, Inc.
  41.  *
  42.  * Permission to use, copy, modify, distribute and sell this software
  43.  * and its documentation for any purpose is hereby granted without fee,
  44.  * provided that the above copyright notice appear in all copies and
  45.  * that both that copyright notice and this permission notice appear
  46.  * in supporting documentation.  Silicon Graphics makes no
  47.  * representations about the suitability of this software for any
  48.  * purpose.  It is provided "as is" without express or implied warranty.
  49.  */
  50.  
  51. /** @file bits/stl_deque.h
  52.  *  This is an internal header file, included by other library headers.
  53.  *  Do not attempt to use it directly. @headername{deque}
  54.  */
  55.  
  56. #ifndef _STL_DEQUE_H
  57. #define _STL_DEQUE_H 1
  58.  
  59. #include <bits/concept_check.h>
  60. #include <bits/stl_iterator_base_types.h>
  61. #include <bits/stl_iterator_base_funcs.h>
  62. #if __cplusplus >= 201103L
  63. #include <initializer_list>
  64. #endif
  65.  
  66. namespace std _GLIBCXX_VISIBILITY(default)
  67. {
  68. _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
  69.  
  70.   /**
  71.    *  @brief This function controls the size of memory nodes.
  72.    *  @param  __size  The size of an element.
  73.    *  @return   The number (not byte size) of elements per node.
  74.    *
  75.    *  This function started off as a compiler kludge from SGI, but
  76.    *  seems to be a useful wrapper around a repeated constant
  77.    *  expression.  The @b 512 is tunable (and no other code needs to
  78.    *  change), but no investigation has been done since inheriting the
  79.    *  SGI code.  Touch _GLIBCXX_DEQUE_BUF_SIZE only if you know what
  80.    *  you are doing, however: changing it breaks the binary
  81.    *  compatibility!!
  82.   */
  83.  
  84. #ifndef _GLIBCXX_DEQUE_BUF_SIZE
  85. #define _GLIBCXX_DEQUE_BUF_SIZE 512
  86. #endif
  87.  
  88.   _GLIBCXX_CONSTEXPR inline size_t
  89.   __deque_buf_size(size_t __size)
  90.   { return (__size < _GLIBCXX_DEQUE_BUF_SIZE
  91.             ? size_t(_GLIBCXX_DEQUE_BUF_SIZE / __size) : size_t(1)); }
  92.  
  93.  
  94.   /**
  95.    *  @brief A deque::iterator.
  96.    *
  97.    *  Quite a bit of intelligence here.  Much of the functionality of
  98.    *  deque is actually passed off to this class.  A deque holds two
  99.    *  of these internally, marking its valid range.  Access to
  100.    *  elements is done as offsets of either of those two, relying on
  101.    *  operator overloading in this class.
  102.    *
  103.    *  All the functions are op overloads except for _M_set_node.
  104.   */
  105.   template<typename _Tp, typename _Ref, typename _Ptr>
  106.     struct _Deque_iterator
  107.     {
  108. #if __cplusplus < 201103L
  109.       typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;
  110.       typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
  111.       typedef _Tp*                                         _Elt_pointer;
  112.       typedef _Tp**                                        _Map_pointer;
  113. #else
  114.     private:
  115.       template<typename _Up>
  116.         using __ptr_to = typename pointer_traits<_Ptr>::template rebind<_Up>;
  117.       template<typename _CvTp>
  118.         using __iter = _Deque_iterator<_Tp, _CvTp&, __ptr_to<_CvTp>>;
  119.     public:
  120.       typedef __iter<_Tp>               iterator;
  121.       typedef __iter<const _Tp>         const_iterator;
  122.       typedef __ptr_to<_Tp>             _Elt_pointer;
  123.       typedef __ptr_to<_Elt_pointer>    _Map_pointer;
  124. #endif
  125.  
  126.       static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
  127.       { return __deque_buf_size(sizeof(_Tp)); }
  128.  
  129.       typedef std::random_access_iterator_tag iterator_category;
  130.       typedef _Tp                             value_type;
  131.       typedef _Ptr                            pointer;
  132.       typedef _Ref                            reference;
  133.       typedef size_t                          size_type;
  134.       typedef ptrdiff_t                       difference_type;
  135.       typedef _Deque_iterator                 _Self;
  136.  
  137.       _Elt_pointer _M_cur;
  138.       _Elt_pointer _M_first;
  139.       _Elt_pointer _M_last;
  140.       _Map_pointer _M_node;
  141.  
  142.       _Deque_iterator(_Elt_pointer __x, _Map_pointer __y) _GLIBCXX_NOEXCEPT
  143.       : _M_cur(__x), _M_first(*__y),
  144.         _M_last(*__y + _S_buffer_size()), _M_node(__y) { }
  145.  
  146.       _Deque_iterator() _GLIBCXX_NOEXCEPT
  147.       : _M_cur(), _M_first(), _M_last(), _M_node() { }
  148.  
  149.       _Deque_iterator(const iterator& __x) _GLIBCXX_NOEXCEPT
  150.       : _M_cur(__x._M_cur), _M_first(__x._M_first),
  151.         _M_last(__x._M_last), _M_node(__x._M_node) { }
  152.  
  153.       iterator
  154.       _M_const_cast() const _GLIBCXX_NOEXCEPT
  155.       { return iterator(_M_cur, _M_node); }
  156.  
  157.       reference
  158.       operator*() const _GLIBCXX_NOEXCEPT
  159.       { return *_M_cur; }
  160.  
  161.       pointer
  162.       operator->() const _GLIBCXX_NOEXCEPT
  163.       { return _M_cur; }
  164.  
  165.       _Self&
  166.       operator++() _GLIBCXX_NOEXCEPT
  167.       {
  168.         ++_M_cur;
  169.         if (_M_cur == _M_last)
  170.           {
  171.             _M_set_node(_M_node + 1);
  172.             _M_cur = _M_first;
  173.           }
  174.         return *this;
  175.       }
  176.  
  177.       _Self
  178.       operator++(int) _GLIBCXX_NOEXCEPT
  179.       {
  180.         _Self __tmp = *this;
  181.         ++*this;
  182.         return __tmp;
  183.       }
  184.  
  185.       _Self&
  186.       operator--() _GLIBCXX_NOEXCEPT
  187.       {
  188.         if (_M_cur == _M_first)
  189.           {
  190.             _M_set_node(_M_node - 1);
  191.             _M_cur = _M_last;
  192.           }
  193.         --_M_cur;
  194.         return *this;
  195.       }
  196.  
  197.       _Self
  198.       operator--(int) _GLIBCXX_NOEXCEPT
  199.       {
  200.         _Self __tmp = *this;
  201.         --*this;
  202.         return __tmp;
  203.       }
  204.  
  205.       _Self&
  206.       operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
  207.       {
  208.         const difference_type __offset = __n + (_M_cur - _M_first);
  209.         if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
  210.           _M_cur += __n;
  211.         else
  212.           {
  213.             const difference_type __node_offset =
  214.               __offset > 0 ? __offset / difference_type(_S_buffer_size())
  215.                            : -difference_type((-__offset - 1)
  216.                                               / _S_buffer_size()) - 1;
  217.             _M_set_node(_M_node + __node_offset);
  218.             _M_cur = _M_first + (__offset - __node_offset
  219.                                  * difference_type(_S_buffer_size()));
  220.           }
  221.         return *this;
  222.       }
  223.  
  224.       _Self
  225.       operator+(difference_type __n) const _GLIBCXX_NOEXCEPT
  226.       {
  227.         _Self __tmp = *this;
  228.         return __tmp += __n;
  229.       }
  230.  
  231.       _Self&
  232.       operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
  233.       { return *this += -__n; }
  234.  
  235.       _Self
  236.       operator-(difference_type __n) const _GLIBCXX_NOEXCEPT
  237.       {
  238.         _Self __tmp = *this;
  239.         return __tmp -= __n;
  240.       }
  241.  
  242.       reference
  243.       operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
  244.       { return *(*this + __n); }
  245.  
  246.       /**
  247.        *  Prepares to traverse new_node.  Sets everything except
  248.        *  _M_cur, which should therefore be set by the caller
  249.        *  immediately afterwards, based on _M_first and _M_last.
  250.        */
  251.       void
  252.       _M_set_node(_Map_pointer __new_node) _GLIBCXX_NOEXCEPT
  253.       {
  254.         _M_node = __new_node;
  255.         _M_first = *__new_node;
  256.         _M_last = _M_first + difference_type(_S_buffer_size());
  257.       }
  258.     };
  259.  
  260.   // Note: we also provide overloads whose operands are of the same type in
  261.   // order to avoid ambiguous overload resolution when std::rel_ops operators
  262.   // are in scope (for additional details, see libstdc++/3628)
  263.   template<typename _Tp, typename _Ref, typename _Ptr>
  264.     inline bool
  265.     operator==(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
  266.                const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT
  267.     { return __x._M_cur == __y._M_cur; }
  268.  
  269.   template<typename _Tp, typename _RefL, typename _PtrL,
  270.            typename _RefR, typename _PtrR>
  271.     inline bool
  272.     operator==(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
  273.                const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
  274.     { return __x._M_cur == __y._M_cur; }
  275.  
  276.   template<typename _Tp, typename _Ref, typename _Ptr>
  277.     inline bool
  278.     operator!=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
  279.                const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT
  280.     { return !(__x == __y); }
  281.  
  282.   template<typename _Tp, typename _RefL, typename _PtrL,
  283.            typename _RefR, typename _PtrR>
  284.     inline bool
  285.     operator!=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
  286.                const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
  287.     { return !(__x == __y); }
  288.  
  289.   template<typename _Tp, typename _Ref, typename _Ptr>
  290.     inline bool
  291.     operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
  292.               const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT
  293.     { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)
  294.                                           : (__x._M_node < __y._M_node); }
  295.  
  296.   template<typename _Tp, typename _RefL, typename _PtrL,
  297.            typename _RefR, typename _PtrR>
  298.     inline bool
  299.     operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
  300.               const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
  301.     { return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur)
  302.                                           : (__x._M_node < __y._M_node); }
  303.  
  304.   template<typename _Tp, typename _Ref, typename _Ptr>
  305.     inline bool
  306.     operator>(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
  307.               const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT
  308.     { return __y < __x; }
  309.  
  310.   template<typename _Tp, typename _RefL, typename _PtrL,
  311.            typename _RefR, typename _PtrR>
  312.     inline bool
  313.     operator>(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
  314.               const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
  315.     { return __y < __x; }
  316.  
  317.   template<typename _Tp, typename _Ref, typename _Ptr>
  318.     inline bool
  319.     operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
  320.                const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT
  321.     { return !(__y < __x); }
  322.  
  323.   template<typename _Tp, typename _RefL, typename _PtrL,
  324.            typename _RefR, typename _PtrR>
  325.     inline bool
  326.     operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
  327.                const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
  328.     { return !(__y < __x); }
  329.  
  330.   template<typename _Tp, typename _Ref, typename _Ptr>
  331.     inline bool
  332.     operator>=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
  333.                const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT
  334.     { return !(__x < __y); }
  335.  
  336.   template<typename _Tp, typename _RefL, typename _PtrL,
  337.            typename _RefR, typename _PtrR>
  338.     inline bool
  339.     operator>=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
  340.                const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
  341.     { return !(__x < __y); }
  342.  
  343.   // _GLIBCXX_RESOLVE_LIB_DEFECTS
  344.   // According to the resolution of DR179 not only the various comparison
  345.   // operators but also operator- must accept mixed iterator/const_iterator
  346.   // parameters.
  347.   template<typename _Tp, typename _Ref, typename _Ptr>
  348.     inline typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type
  349.     operator-(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
  350.               const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT
  351.     {
  352.       return typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type
  353.         (_Deque_iterator<_Tp, _Ref, _Ptr>::_S_buffer_size())
  354.         * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
  355.         + (__y._M_last - __y._M_cur);
  356.     }
  357.  
  358.   template<typename _Tp, typename _RefL, typename _PtrL,
  359.            typename _RefR, typename _PtrR>
  360.     inline typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
  361.     operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
  362.               const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT
  363.     {
  364.       return typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
  365.         (_Deque_iterator<_Tp, _RefL, _PtrL>::_S_buffer_size())
  366.         * (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)
  367.         + (__y._M_last - __y._M_cur);
  368.     }
  369.  
  370.   template<typename _Tp, typename _Ref, typename _Ptr>
  371.     inline _Deque_iterator<_Tp, _Ref, _Ptr>
  372.     operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x)
  373.     _GLIBCXX_NOEXCEPT
  374.     { return __x + __n; }
  375.  
  376.   template<typename _Tp>
  377.     void
  378.     fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>&,
  379.          const _Deque_iterator<_Tp, _Tp&, _Tp*>&, const _Tp&);
  380.  
  381.   template<typename _Tp>
  382.     _Deque_iterator<_Tp, _Tp&, _Tp*>
  383.     copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
  384.          _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
  385.          _Deque_iterator<_Tp, _Tp&, _Tp*>);
  386.  
  387.   template<typename _Tp>
  388.     inline _Deque_iterator<_Tp, _Tp&, _Tp*>
  389.     copy(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
  390.          _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
  391.          _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
  392.     { return std::copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),
  393.                        _Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last),
  394.                        __result); }
  395.  
  396.   template<typename _Tp>
  397.     _Deque_iterator<_Tp, _Tp&, _Tp*>
  398.     copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
  399.                   _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
  400.                   _Deque_iterator<_Tp, _Tp&, _Tp*>);
  401.  
  402.   template<typename _Tp>
  403.     inline _Deque_iterator<_Tp, _Tp&, _Tp*>
  404.     copy_backward(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
  405.                   _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
  406.                   _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
  407.     { return std::copy_backward(_Deque_iterator<_Tp,
  408.                                 const _Tp&, const _Tp*>(__first),
  409.                                 _Deque_iterator<_Tp,
  410.                                 const _Tp&, const _Tp*>(__last),
  411.                                 __result); }
  412.  
  413. #if __cplusplus >= 201103L
  414.   template<typename _Tp>
  415.     _Deque_iterator<_Tp, _Tp&, _Tp*>
  416.     move(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
  417.          _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
  418.          _Deque_iterator<_Tp, _Tp&, _Tp*>);
  419.  
  420.   template<typename _Tp>
  421.     inline _Deque_iterator<_Tp, _Tp&, _Tp*>
  422.     move(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
  423.          _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
  424.          _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
  425.     { return std::move(_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),
  426.                        _Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last),
  427.                        __result); }
  428.  
  429.   template<typename _Tp>
  430.     _Deque_iterator<_Tp, _Tp&, _Tp*>
  431.     move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
  432.                   _Deque_iterator<_Tp, const _Tp&, const _Tp*>,
  433.                   _Deque_iterator<_Tp, _Tp&, _Tp*>);
  434.  
  435.   template<typename _Tp>
  436.     inline _Deque_iterator<_Tp, _Tp&, _Tp*>
  437.     move_backward(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,
  438.                   _Deque_iterator<_Tp, _Tp&, _Tp*> __last,
  439.                   _Deque_iterator<_Tp, _Tp&, _Tp*> __result)
  440.     { return std::move_backward(_Deque_iterator<_Tp,
  441.                                 const _Tp&, const _Tp*>(__first),
  442.                                 _Deque_iterator<_Tp,
  443.                                 const _Tp&, const _Tp*>(__last),
  444.                                 __result); }
  445. #endif
  446.  
  447.   /**
  448.    *  Deque base class.  This class provides the unified face for %deque's
  449.    *  allocation.  This class's constructor and destructor allocate and
  450.    *  deallocate (but do not initialize) storage.  This makes %exception
  451.    *  safety easier.
  452.    *
  453.    *  Nothing in this class ever constructs or destroys an actual Tp element.
  454.    *  (Deque handles that itself.)  Only/All memory management is performed
  455.    *  here.
  456.   */
  457.   template<typename _Tp, typename _Alloc>
  458.     class _Deque_base
  459.     {
  460.     protected:
  461.       typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
  462.         rebind<_Tp>::other _Tp_alloc_type;
  463.       typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type>  _Alloc_traits;
  464.  
  465. #if __cplusplus < 201103L
  466.       typedef _Tp*                                      _Ptr;
  467.       typedef const _Tp*                                _Ptr_const;
  468. #else
  469.       typedef typename _Alloc_traits::pointer           _Ptr;
  470.       typedef typename _Alloc_traits::const_pointer     _Ptr_const;
  471. #endif
  472.  
  473.       typedef typename _Alloc_traits::template rebind<_Ptr>::other
  474.         _Map_alloc_type;
  475.       typedef __gnu_cxx::__alloc_traits<_Map_alloc_type> _Map_alloc_traits;
  476.  
  477.     public:
  478.       typedef _Alloc                  allocator_type;
  479.       typedef typename _Alloc_traits::size_type size_type;
  480.  
  481.       allocator_type
  482.       get_allocator() const _GLIBCXX_NOEXCEPT
  483.       { return allocator_type(_M_get_Tp_allocator()); }
  484.  
  485.       typedef _Deque_iterator<_Tp, _Tp&, _Ptr>          iterator;
  486.       typedef _Deque_iterator<_Tp, const _Tp&, _Ptr_const>   const_iterator;
  487.  
  488.       _Deque_base()
  489.       : _M_impl()
  490.       { _M_initialize_map(0); }
  491.  
  492.       _Deque_base(size_t __num_elements)
  493.       : _M_impl()
  494.       { _M_initialize_map(__num_elements); }
  495.  
  496.       _Deque_base(const allocator_type& __a, size_t __num_elements)
  497.       : _M_impl(__a)
  498.       { _M_initialize_map(__num_elements); }
  499.  
  500.       _Deque_base(const allocator_type& __a)
  501.       : _M_impl(__a)
  502.       { /* Caller must initialize map. */ }
  503.  
  504. #if __cplusplus >= 201103L
  505.       _Deque_base(_Deque_base&& __x, false_type)
  506.       : _M_impl(__x._M_move_impl())
  507.       { }
  508.  
  509.       _Deque_base(_Deque_base&& __x, true_type)
  510.       : _M_impl(std::move(__x._M_get_Tp_allocator()))
  511.       {
  512.         _M_initialize_map(0);
  513.         if (__x._M_impl._M_map)
  514.           this->_M_impl._M_swap_data(__x._M_impl);
  515.       }
  516.  
  517.       _Deque_base(_Deque_base&& __x)
  518.       : _Deque_base(std::move(__x),
  519.                     __gnu_cxx::__allocator_always_compares_equal<_Alloc>{})
  520.       { }
  521.  
  522.       _Deque_base(_Deque_base&& __x, const allocator_type& __a, size_type __n)
  523.       : _M_impl(__a)
  524.       {
  525.         if (__x.get_allocator() == __a)
  526.           {
  527.             if (__x._M_impl._M_map)
  528.               {
  529.                 _M_initialize_map(0);
  530.                 this->_M_impl._M_swap_data(__x._M_impl);
  531.               }
  532.           }
  533.         else
  534.           {
  535.             _M_initialize_map(__n);
  536.           }
  537.       }
  538. #endif
  539.  
  540.       ~_Deque_base() _GLIBCXX_NOEXCEPT;
  541.  
  542.     protected:
  543.       typedef typename iterator::_Map_pointer _Map_pointer;
  544.  
  545.       //This struct encapsulates the implementation of the std::deque
  546.       //standard container and at the same time makes use of the EBO
  547.       //for empty allocators.
  548.       struct _Deque_impl
  549.       : public _Tp_alloc_type
  550.       {
  551.         _Map_pointer _M_map;
  552.         size_t _M_map_size;
  553.         iterator _M_start;
  554.         iterator _M_finish;
  555.  
  556.         _Deque_impl()
  557.         : _Tp_alloc_type(), _M_map(), _M_map_size(0),
  558.           _M_start(), _M_finish()
  559.         { }
  560.  
  561.         _Deque_impl(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT
  562.         : _Tp_alloc_type(__a), _M_map(), _M_map_size(0),
  563.           _M_start(), _M_finish()
  564.         { }
  565.  
  566. #if __cplusplus >= 201103L
  567.         _Deque_impl(_Deque_impl&&) = default;
  568.  
  569.         _Deque_impl(_Tp_alloc_type&& __a) noexcept
  570.         : _Tp_alloc_type(std::move(__a)), _M_map(), _M_map_size(0),
  571.           _M_start(), _M_finish()
  572.         { }
  573. #endif
  574.  
  575.         void _M_swap_data(_Deque_impl& __x) _GLIBCXX_NOEXCEPT
  576.         {
  577.           using std::swap;
  578.           swap(this->_M_start, __x._M_start);
  579.           swap(this->_M_finish, __x._M_finish);
  580.           swap(this->_M_map, __x._M_map);
  581.           swap(this->_M_map_size, __x._M_map_size);
  582.         }
  583.       };
  584.  
  585.       _Tp_alloc_type&
  586.       _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT
  587.       { return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }
  588.  
  589.       const _Tp_alloc_type&
  590.       _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT
  591.       { return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }
  592.  
  593.       _Map_alloc_type
  594.       _M_get_map_allocator() const _GLIBCXX_NOEXCEPT
  595.       { return _Map_alloc_type(_M_get_Tp_allocator()); }
  596.  
  597.       _Ptr
  598.       _M_allocate_node()
  599.       {
  600.         typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Traits;
  601.         return _Traits::allocate(_M_impl, __deque_buf_size(sizeof(_Tp)));
  602.       }
  603.  
  604.       void
  605.       _M_deallocate_node(_Ptr __p) _GLIBCXX_NOEXCEPT
  606.       {
  607.         typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Traits;
  608.         _Traits::deallocate(_M_impl, __p, __deque_buf_size(sizeof(_Tp)));
  609.       }
  610.  
  611.       _Map_pointer
  612.       _M_allocate_map(size_t __n)
  613.       {
  614.         _Map_alloc_type __map_alloc = _M_get_map_allocator();
  615.         return _Map_alloc_traits::allocate(__map_alloc, __n);
  616.       }
  617.  
  618.       void
  619.       _M_deallocate_map(_Map_pointer __p, size_t __n) _GLIBCXX_NOEXCEPT
  620.       {
  621.         _Map_alloc_type __map_alloc = _M_get_map_allocator();
  622.         _Map_alloc_traits::deallocate(__map_alloc, __p, __n);
  623.       }
  624.  
  625.     protected:
  626.       void _M_initialize_map(size_t);
  627.       void _M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish);
  628.       void _M_destroy_nodes(_Map_pointer __nstart,
  629.                             _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT;
  630.       enum { _S_initial_map_size = 8 };
  631.  
  632.       _Deque_impl _M_impl;
  633.  
  634. #if __cplusplus >= 201103L
  635.     private:
  636.       _Deque_impl
  637.       _M_move_impl()
  638.       {
  639.         if (!_M_impl._M_map)
  640.           return std::move(_M_impl);
  641.  
  642.         // Create a copy of the current allocator.
  643.         _Tp_alloc_type __alloc{_M_get_Tp_allocator()};
  644.         // Put that copy in a moved-from state.
  645.         _Tp_alloc_type __sink __attribute((__unused__)) {std::move(__alloc)};
  646.         // Create an empty map that allocates using the moved-from allocator.
  647.         _Deque_base __empty{__alloc};
  648.         __empty._M_initialize_map(0);
  649.         // Now safe to modify current allocator and perform non-throwing swaps.
  650.         _Deque_impl __ret{std::move(_M_get_Tp_allocator())};
  651.         _M_impl._M_swap_data(__ret);
  652.         _M_impl._M_swap_data(__empty._M_impl);
  653.         return __ret;
  654.       }
  655. #endif
  656.     };
  657.  
  658.   template<typename _Tp, typename _Alloc>
  659.     _Deque_base<_Tp, _Alloc>::
  660.     ~_Deque_base() _GLIBCXX_NOEXCEPT
  661.     {
  662.       if (this->_M_impl._M_map)
  663.         {
  664.           _M_destroy_nodes(this->_M_impl._M_start._M_node,
  665.                            this->_M_impl._M_finish._M_node + 1);
  666.           _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
  667.         }
  668.     }
  669.  
  670.   /**
  671.    *  @brief Layout storage.
  672.    *  @param  __num_elements  The count of T's for which to allocate space
  673.    *                          at first.
  674.    *  @return   Nothing.
  675.    *
  676.    *  The initial underlying memory layout is a bit complicated...
  677.   */
  678.   template<typename _Tp, typename _Alloc>
  679.     void
  680.     _Deque_base<_Tp, _Alloc>::
  681.     _M_initialize_map(size_t __num_elements)
  682.     {
  683.       const size_t __num_nodes = (__num_elements/ __deque_buf_size(sizeof(_Tp))
  684.                                   + 1);
  685.  
  686.       this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size,
  687.                                            size_t(__num_nodes + 2));
  688.       this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
  689.  
  690.       // For "small" maps (needing less than _M_map_size nodes), allocation
  691.       // starts in the middle elements and grows outwards.  So nstart may be
  692.       // the beginning of _M_map, but for small maps it may be as far in as
  693.       // _M_map+3.
  694.  
  695.       _Map_pointer __nstart = (this->_M_impl._M_map
  696.                                + (this->_M_impl._M_map_size - __num_nodes) / 2);
  697.       _Map_pointer __nfinish = __nstart + __num_nodes;
  698.  
  699.       __try
  700.         { _M_create_nodes(__nstart, __nfinish); }
  701.       __catch(...)
  702.         {
  703.           _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
  704.           this->_M_impl._M_map = _Map_pointer();
  705.           this->_M_impl._M_map_size = 0;
  706.           __throw_exception_again;
  707.         }
  708.  
  709.       this->_M_impl._M_start._M_set_node(__nstart);
  710.       this->_M_impl._M_finish._M_set_node(__nfinish - 1);
  711.       this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
  712.       this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
  713.                                         + __num_elements
  714.                                         % __deque_buf_size(sizeof(_Tp)));
  715.     }
  716.  
  717.   template<typename _Tp, typename _Alloc>
  718.     void
  719.     _Deque_base<_Tp, _Alloc>::
  720.     _M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish)
  721.     {
  722.       _Map_pointer __cur;
  723.       __try
  724.         {
  725.           for (__cur = __nstart; __cur < __nfinish; ++__cur)
  726.             *__cur = this->_M_allocate_node();
  727.         }
  728.       __catch(...)
  729.         {
  730.           _M_destroy_nodes(__nstart, __cur);
  731.           __throw_exception_again;
  732.         }
  733.     }
  734.  
  735.   template<typename _Tp, typename _Alloc>
  736.     void
  737.     _Deque_base<_Tp, _Alloc>::
  738.     _M_destroy_nodes(_Map_pointer __nstart,
  739.                      _Map_pointer __nfinish) _GLIBCXX_NOEXCEPT
  740.     {
  741.       for (_Map_pointer __n = __nstart; __n < __nfinish; ++__n)
  742.         _M_deallocate_node(*__n);
  743.     }
  744.  
  745.   /**
  746.    *  @brief  A standard container using fixed-size memory allocation and
  747.    *  constant-time manipulation of elements at either end.
  748.    *
  749.    *  @ingroup sequences
  750.    *
  751.    *  @tparam _Tp  Type of element.
  752.    *  @tparam _Alloc  Allocator type, defaults to allocator<_Tp>.
  753.    *
  754.    *  Meets the requirements of a <a href="tables.html#65">container</a>, a
  755.    *  <a href="tables.html#66">reversible container</a>, and a
  756.    *  <a href="tables.html#67">sequence</a>, including the
  757.    *  <a href="tables.html#68">optional sequence requirements</a>.
  758.    *
  759.    *  In previous HP/SGI versions of deque, there was an extra template
  760.    *  parameter so users could control the node size.  This extension turned
  761.    *  out to violate the C++ standard (it can be detected using template
  762.    *  template parameters), and it was removed.
  763.    *
  764.    *  Here's how a deque<Tp> manages memory.  Each deque has 4 members:
  765.    *
  766.    *  - Tp**        _M_map
  767.    *  - size_t      _M_map_size
  768.    *  - iterator    _M_start, _M_finish
  769.    *
  770.    *  map_size is at least 8.  %map is an array of map_size
  771.    *  pointers-to-@a nodes.  (The name %map has nothing to do with the
  772.    *  std::map class, and @b nodes should not be confused with
  773.    *  std::list's usage of @a node.)
  774.    *
  775.    *  A @a node has no specific type name as such, but it is referred
  776.    *  to as @a node in this file.  It is a simple array-of-Tp.  If Tp
  777.    *  is very large, there will be one Tp element per node (i.e., an
  778.    *  @a array of one).  For non-huge Tp's, node size is inversely
  779.    *  related to Tp size: the larger the Tp, the fewer Tp's will fit
  780.    *  in a node.  The goal here is to keep the total size of a node
  781.    *  relatively small and constant over different Tp's, to improve
  782.    *  allocator efficiency.
  783.    *
  784.    *  Not every pointer in the %map array will point to a node.  If
  785.    *  the initial number of elements in the deque is small, the
  786.    *  /middle/ %map pointers will be valid, and the ones at the edges
  787.    *  will be unused.  This same situation will arise as the %map
  788.    *  grows: available %map pointers, if any, will be on the ends.  As
  789.    *  new nodes are created, only a subset of the %map's pointers need
  790.    *  to be copied @a outward.
  791.    *
  792.    *  Class invariants:
  793.    * - For any nonsingular iterator i:
  794.    *    - i.node points to a member of the %map array.  (Yes, you read that
  795.    *      correctly:  i.node does not actually point to a node.)  The member of
  796.    *      the %map array is what actually points to the node.
  797.    *    - i.first == *(i.node)    (This points to the node (first Tp element).)
  798.    *    - i.last  == i.first + node_size
  799.    *    - i.cur is a pointer in the range [i.first, i.last).  NOTE:
  800.    *      the implication of this is that i.cur is always a dereferenceable
  801.    *      pointer, even if i is a past-the-end iterator.
  802.    * - Start and Finish are always nonsingular iterators.  NOTE: this
  803.    * means that an empty deque must have one node, a deque with <N
  804.    * elements (where N is the node buffer size) must have one node, a
  805.    * deque with N through (2N-1) elements must have two nodes, etc.
  806.    * - For every node other than start.node and finish.node, every
  807.    * element in the node is an initialized object.  If start.node ==
  808.    * finish.node, then [start.cur, finish.cur) are initialized
  809.    * objects, and the elements outside that range are uninitialized
  810.    * storage.  Otherwise, [start.cur, start.last) and [finish.first,
  811.    * finish.cur) are initialized objects, and [start.first, start.cur)
  812.    * and [finish.cur, finish.last) are uninitialized storage.
  813.    * - [%map, %map + map_size) is a valid, non-empty range.
  814.    * - [start.node, finish.node] is a valid range contained within
  815.    *   [%map, %map + map_size).
  816.    * - A pointer in the range [%map, %map + map_size) points to an allocated
  817.    *   node if and only if the pointer is in the range
  818.    *   [start.node, finish.node].
  819.    *
  820.    *  Here's the magic:  nothing in deque is @b aware of the discontiguous
  821.    *  storage!
  822.    *
  823.    *  The memory setup and layout occurs in the parent, _Base, and the iterator
  824.    *  class is entirely responsible for @a leaping from one node to the next.
  825.    *  All the implementation routines for deque itself work only through the
  826.    *  start and finish iterators.  This keeps the routines simple and sane,
  827.    *  and we can use other standard algorithms as well.
  828.   */
  829.   template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
  830.     class deque : protected _Deque_base<_Tp, _Alloc>
  831.     {
  832.       // concept requirements
  833.       typedef typename _Alloc::value_type        _Alloc_value_type;
  834.       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
  835.       __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
  836.  
  837.       typedef _Deque_base<_Tp, _Alloc>                  _Base;
  838.       typedef typename _Base::_Tp_alloc_type            _Tp_alloc_type;
  839.       typedef typename _Base::_Alloc_traits             _Alloc_traits;
  840.       typedef typename _Base::_Map_pointer              _Map_pointer;
  841.  
  842.     public:
  843.       typedef _Tp                                        value_type;
  844.       typedef typename _Alloc_traits::pointer            pointer;
  845.       typedef typename _Alloc_traits::const_pointer      const_pointer;
  846.       typedef typename _Alloc_traits::reference          reference;
  847.       typedef typename _Alloc_traits::const_reference    const_reference;
  848.       typedef typename _Base::iterator                   iterator;
  849.       typedef typename _Base::const_iterator             const_iterator;
  850.       typedef std::reverse_iterator<const_iterator>      const_reverse_iterator;
  851.       typedef std::reverse_iterator<iterator>            reverse_iterator;
  852.       typedef size_t                             size_type;
  853.       typedef ptrdiff_t                          difference_type;
  854.       typedef _Alloc                             allocator_type;
  855.  
  856.     protected:
  857.       static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT
  858.       { return __deque_buf_size(sizeof(_Tp)); }
  859.  
  860.       // Functions controlling memory layout, and nothing else.
  861.       using _Base::_M_initialize_map;
  862.       using _Base::_M_create_nodes;
  863.       using _Base::_M_destroy_nodes;
  864.       using _Base::_M_allocate_node;
  865.       using _Base::_M_deallocate_node;
  866.       using _Base::_M_allocate_map;
  867.       using _Base::_M_deallocate_map;
  868.       using _Base::_M_get_Tp_allocator;
  869.  
  870.       /**
  871.        *  A total of four data members accumulated down the hierarchy.
  872.        *  May be accessed via _M_impl.*
  873.        */
  874.       using _Base::_M_impl;
  875.  
  876.     public:
  877.       // [23.2.1.1] construct/copy/destroy
  878.       // (assign() and get_allocator() are also listed in this section)
  879.  
  880.       /**
  881.        *  @brief  Creates a %deque with no elements.
  882.        */
  883.       deque() : _Base() { }
  884.  
  885.       /**
  886.        *  @brief  Creates a %deque with no elements.
  887.        *  @param  __a  An allocator object.
  888.        */
  889.       explicit
  890.       deque(const allocator_type& __a)
  891.       : _Base(__a, 0) { }
  892.  
  893. #if __cplusplus >= 201103L
  894.       /**
  895.        *  @brief  Creates a %deque with default constructed elements.
  896.        *  @param  __n  The number of elements to initially create.
  897.        *
  898.        *  This constructor fills the %deque with @a n default
  899.        *  constructed elements.
  900.        */
  901.       explicit
  902.       deque(size_type __n, const allocator_type& __a = allocator_type())
  903.       : _Base(__a, __n)
  904.       { _M_default_initialize(); }
  905.  
  906.       /**
  907.        *  @brief  Creates a %deque with copies of an exemplar element.
  908.        *  @param  __n  The number of elements to initially create.
  909.        *  @param  __value  An element to copy.
  910.        *  @param  __a  An allocator.
  911.        *
  912.        *  This constructor fills the %deque with @a __n copies of @a __value.
  913.        */
  914.       deque(size_type __n, const value_type& __value,
  915.             const allocator_type& __a = allocator_type())
  916.       : _Base(__a, __n)
  917.       { _M_fill_initialize(__value); }
  918. #else
  919.       /**
  920.        *  @brief  Creates a %deque with copies of an exemplar element.
  921.        *  @param  __n  The number of elements to initially create.
  922.        *  @param  __value  An element to copy.
  923.        *  @param  __a  An allocator.
  924.        *
  925.        *  This constructor fills the %deque with @a __n copies of @a __value.
  926.        */
  927.       explicit
  928.       deque(size_type __n, const value_type& __value = value_type(),
  929.             const allocator_type& __a = allocator_type())
  930.       : _Base(__a, __n)
  931.       { _M_fill_initialize(__value); }
  932. #endif
  933.  
  934.       /**
  935.        *  @brief  %Deque copy constructor.
  936.        *  @param  __x  A %deque of identical element and allocator types.
  937.        *
  938.        *  The newly-created %deque uses a copy of the allocation object used
  939.        *  by @a __x.
  940.        */
  941.       deque(const deque& __x)
  942.       : _Base(_Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator()),
  943.               __x.size())
  944.       { std::__uninitialized_copy_a(__x.begin(), __x.end(),
  945.                                     this->_M_impl._M_start,
  946.                                     _M_get_Tp_allocator()); }
  947.  
  948. #if __cplusplus >= 201103L
  949.       /**
  950.        *  @brief  %Deque move constructor.
  951.        *  @param  __x  A %deque of identical element and allocator types.
  952.        *
  953.        *  The newly-created %deque contains the exact contents of @a __x.
  954.        *  The contents of @a __x are a valid, but unspecified %deque.
  955.        */
  956.       deque(deque&& __x)
  957.       : _Base(std::move(__x)) { }
  958.  
  959.       /// Copy constructor with alternative allocator
  960.       deque(const deque& __x, const allocator_type& __a)
  961.       : _Base(__a, __x.size())
  962.       { std::__uninitialized_copy_a(__x.begin(), __x.end(),
  963.                                     this->_M_impl._M_start,
  964.                                     _M_get_Tp_allocator()); }
  965.  
  966.       /// Move constructor with alternative allocator
  967.       deque(deque&& __x, const allocator_type& __a)
  968.       : _Base(std::move(__x), __a, __x.size())
  969.       {
  970.         if (__x.get_allocator() != __a)
  971.           {
  972.             std::__uninitialized_move_a(__x.begin(), __x.end(),
  973.                                         this->_M_impl._M_start,
  974.                                         _M_get_Tp_allocator());
  975.             __x.clear();
  976.           }
  977.       }
  978.  
  979.       /**
  980.        *  @brief  Builds a %deque from an initializer list.
  981.        *  @param  __l  An initializer_list.
  982.        *  @param  __a  An allocator object.
  983.        *
  984.        *  Create a %deque consisting of copies of the elements in the
  985.        *  initializer_list @a __l.
  986.        *
  987.        *  This will call the element type's copy constructor N times
  988.        *  (where N is __l.size()) and do no memory reallocation.
  989.        */
  990.       deque(initializer_list<value_type> __l,
  991.             const allocator_type& __a = allocator_type())
  992.       : _Base(__a)
  993.       {
  994.         _M_range_initialize(__l.begin(), __l.end(),
  995.                             random_access_iterator_tag());
  996.       }
  997. #endif
  998.  
  999.       /**
  1000.        *  @brief  Builds a %deque from a range.
  1001.        *  @param  __first  An input iterator.
  1002.        *  @param  __last  An input iterator.
  1003.        *  @param  __a  An allocator object.
  1004.        *
  1005.        *  Create a %deque consisting of copies of the elements from [__first,
  1006.        *  __last).
  1007.        *
  1008.        *  If the iterators are forward, bidirectional, or random-access, then
  1009.        *  this will call the elements' copy constructor N times (where N is
  1010.        *  distance(__first,__last)) and do no memory reallocation.  But if only
  1011.        *  input iterators are used, then this will do at most 2N calls to the
  1012.        *  copy constructor, and logN memory reallocations.
  1013.        */
  1014. #if __cplusplus >= 201103L
  1015.       template<typename _InputIterator,
  1016.                typename = std::_RequireInputIter<_InputIterator>>
  1017.         deque(_InputIterator __first, _InputIterator __last,
  1018.               const allocator_type& __a = allocator_type())
  1019.         : _Base(__a)
  1020.         { _M_initialize_dispatch(__first, __last, __false_type()); }
  1021. #else
  1022.       template<typename _InputIterator>
  1023.         deque(_InputIterator __first, _InputIterator __last,
  1024.               const allocator_type& __a = allocator_type())
  1025.         : _Base(__a)
  1026.         {
  1027.           // Check whether it's an integral type.  If so, it's not an iterator.
  1028.           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
  1029.           _M_initialize_dispatch(__first, __last, _Integral());
  1030.         }
  1031. #endif
  1032.  
  1033.       /**
  1034.        *  The dtor only erases the elements, and note that if the elements
  1035.        *  themselves are pointers, the pointed-to memory is not touched in any
  1036.        *  way.  Managing the pointer is the user's responsibility.
  1037.        */
  1038.       ~deque()
  1039.       { _M_destroy_data(begin(), end(), _M_get_Tp_allocator()); }
  1040.  
  1041.       /**
  1042.        *  @brief  %Deque assignment operator.
  1043.        *  @param  __x  A %deque of identical element and allocator types.
  1044.        *
  1045.        *  All the elements of @a x are copied, but unlike the copy constructor,
  1046.        *  the allocator object is not copied.
  1047.        */
  1048.       deque&
  1049.       operator=(const deque& __x);
  1050.  
  1051. #if __cplusplus >= 201103L
  1052.       /**
  1053.        *  @brief  %Deque move assignment operator.
  1054.        *  @param  __x  A %deque of identical element and allocator types.
  1055.        *
  1056.        *  The contents of @a __x are moved into this deque (without copying,
  1057.        *  if the allocators permit it).
  1058.        *  @a __x is a valid, but unspecified %deque.
  1059.        */
  1060.       deque&
  1061.       operator=(deque&& __x) noexcept(_Alloc_traits::_S_always_equal())
  1062.       {
  1063.         constexpr bool __always_equal = _Alloc_traits::_S_always_equal();
  1064.         _M_move_assign1(std::move(__x),
  1065.                         integral_constant<bool, __always_equal>());
  1066.         return *this;
  1067.       }
  1068.  
  1069.       /**
  1070.        *  @brief  Assigns an initializer list to a %deque.
  1071.        *  @param  __l  An initializer_list.
  1072.        *
  1073.        *  This function fills a %deque with copies of the elements in the
  1074.        *  initializer_list @a __l.
  1075.        *
  1076.        *  Note that the assignment completely changes the %deque and that the
  1077.        *  resulting %deque's size is the same as the number of elements
  1078.        *  assigned.  Old data may be lost.
  1079.        */
  1080.       deque&
  1081.       operator=(initializer_list<value_type> __l)
  1082.       {
  1083.         this->assign(__l.begin(), __l.end());
  1084.         return *this;
  1085.       }
  1086. #endif
  1087.  
  1088.       /**
  1089.        *  @brief  Assigns a given value to a %deque.
  1090.        *  @param  __n  Number of elements to be assigned.
  1091.        *  @param  __val  Value to be assigned.
  1092.        *
  1093.        *  This function fills a %deque with @a n copies of the given
  1094.        *  value.  Note that the assignment completely changes the
  1095.        *  %deque and that the resulting %deque's size is the same as
  1096.        *  the number of elements assigned.  Old data may be lost.
  1097.        */
  1098.       void
  1099.       assign(size_type __n, const value_type& __val)
  1100.       { _M_fill_assign(__n, __val); }
  1101.  
  1102.       /**
  1103.        *  @brief  Assigns a range to a %deque.
  1104.        *  @param  __first  An input iterator.
  1105.        *  @param  __last   An input iterator.
  1106.        *
  1107.        *  This function fills a %deque with copies of the elements in the
  1108.        *  range [__first,__last).
  1109.        *
  1110.        *  Note that the assignment completely changes the %deque and that the
  1111.        *  resulting %deque's size is the same as the number of elements
  1112.        *  assigned.  Old data may be lost.
  1113.        */
  1114. #if __cplusplus >= 201103L
  1115.       template<typename _InputIterator,
  1116.                typename = std::_RequireInputIter<_InputIterator>>
  1117.         void
  1118.         assign(_InputIterator __first, _InputIterator __last)
  1119.         { _M_assign_dispatch(__first, __last, __false_type()); }
  1120. #else
  1121.       template<typename _InputIterator>
  1122.         void
  1123.         assign(_InputIterator __first, _InputIterator __last)
  1124.         {
  1125.           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
  1126.           _M_assign_dispatch(__first, __last, _Integral());
  1127.         }
  1128. #endif
  1129.  
  1130. #if __cplusplus >= 201103L
  1131.       /**
  1132.        *  @brief  Assigns an initializer list to a %deque.
  1133.        *  @param  __l  An initializer_list.
  1134.        *
  1135.        *  This function fills a %deque with copies of the elements in the
  1136.        *  initializer_list @a __l.
  1137.        *
  1138.        *  Note that the assignment completely changes the %deque and that the
  1139.        *  resulting %deque's size is the same as the number of elements
  1140.        *  assigned.  Old data may be lost.
  1141.        */
  1142.       void
  1143.       assign(initializer_list<value_type> __l)
  1144.       { this->assign(__l.begin(), __l.end()); }
  1145. #endif
  1146.  
  1147.       /// Get a copy of the memory allocation object.
  1148.       allocator_type
  1149.       get_allocator() const _GLIBCXX_NOEXCEPT
  1150.       { return _Base::get_allocator(); }
  1151.  
  1152.       // iterators
  1153.       /**
  1154.        *  Returns a read/write iterator that points to the first element in the
  1155.        *  %deque.  Iteration is done in ordinary element order.
  1156.        */
  1157.       iterator
  1158.       begin() _GLIBCXX_NOEXCEPT
  1159.       { return this->_M_impl._M_start; }
  1160.  
  1161.       /**
  1162.        *  Returns a read-only (constant) iterator that points to the first
  1163.        *  element in the %deque.  Iteration is done in ordinary element order.
  1164.        */
  1165.       const_iterator
  1166.       begin() const _GLIBCXX_NOEXCEPT
  1167.       { return this->_M_impl._M_start; }
  1168.  
  1169.       /**
  1170.        *  Returns a read/write iterator that points one past the last
  1171.        *  element in the %deque.  Iteration is done in ordinary
  1172.        *  element order.
  1173.        */
  1174.       iterator
  1175.       end() _GLIBCXX_NOEXCEPT
  1176.       { return this->_M_impl._M_finish; }
  1177.  
  1178.       /**
  1179.        *  Returns a read-only (constant) iterator that points one past
  1180.        *  the last element in the %deque.  Iteration is done in
  1181.        *  ordinary element order.
  1182.        */
  1183.       const_iterator
  1184.       end() const _GLIBCXX_NOEXCEPT
  1185.       { return this->_M_impl._M_finish; }
  1186.  
  1187.       /**
  1188.        *  Returns a read/write reverse iterator that points to the
  1189.        *  last element in the %deque.  Iteration is done in reverse
  1190.        *  element order.
  1191.        */
  1192.       reverse_iterator
  1193.       rbegin() _GLIBCXX_NOEXCEPT
  1194.       { return reverse_iterator(this->_M_impl._M_finish); }
  1195.  
  1196.       /**
  1197.        *  Returns a read-only (constant) reverse iterator that points
  1198.        *  to the last element in the %deque.  Iteration is done in
  1199.        *  reverse element order.
  1200.        */
  1201.       const_reverse_iterator
  1202.       rbegin() const _GLIBCXX_NOEXCEPT
  1203.       { return const_reverse_iterator(this->_M_impl._M_finish); }
  1204.  
  1205.       /**
  1206.        *  Returns a read/write reverse iterator that points to one
  1207.        *  before the first element in the %deque.  Iteration is done
  1208.        *  in reverse element order.
  1209.        */
  1210.       reverse_iterator
  1211.       rend() _GLIBCXX_NOEXCEPT
  1212.       { return reverse_iterator(this->_M_impl._M_start); }
  1213.  
  1214.       /**
  1215.        *  Returns a read-only (constant) reverse iterator that points
  1216.        *  to one before the first element in the %deque.  Iteration is
  1217.        *  done in reverse element order.
  1218.        */
  1219.       const_reverse_iterator
  1220.       rend() const _GLIBCXX_NOEXCEPT
  1221.       { return const_reverse_iterator(this->_M_impl._M_start); }
  1222.  
  1223. #if __cplusplus >= 201103L
  1224.       /**
  1225.        *  Returns a read-only (constant) iterator that points to the first
  1226.        *  element in the %deque.  Iteration is done in ordinary element order.
  1227.        */
  1228.       const_iterator
  1229.       cbegin() const noexcept
  1230.       { return this->_M_impl._M_start; }
  1231.  
  1232.       /**
  1233.        *  Returns a read-only (constant) iterator that points one past
  1234.        *  the last element in the %deque.  Iteration is done in
  1235.        *  ordinary element order.
  1236.        */
  1237.       const_iterator
  1238.       cend() const noexcept
  1239.       { return this->_M_impl._M_finish; }
  1240.  
  1241.       /**
  1242.        *  Returns a read-only (constant) reverse iterator that points
  1243.        *  to the last element in the %deque.  Iteration is done in
  1244.        *  reverse element order.
  1245.        */
  1246.       const_reverse_iterator
  1247.       crbegin() const noexcept
  1248.       { return const_reverse_iterator(this->_M_impl._M_finish); }
  1249.  
  1250.       /**
  1251.        *  Returns a read-only (constant) reverse iterator that points
  1252.        *  to one before the first element in the %deque.  Iteration is
  1253.        *  done in reverse element order.
  1254.        */
  1255.       const_reverse_iterator
  1256.       crend() const noexcept
  1257.       { return const_reverse_iterator(this->_M_impl._M_start); }
  1258. #endif
  1259.  
  1260.       // [23.2.1.2] capacity
  1261.       /**  Returns the number of elements in the %deque.  */
  1262.       size_type
  1263.       size() const _GLIBCXX_NOEXCEPT
  1264.       { return this->_M_impl._M_finish - this->_M_impl._M_start; }
  1265.  
  1266.       /**  Returns the size() of the largest possible %deque.  */
  1267.       size_type
  1268.       max_size() const _GLIBCXX_NOEXCEPT
  1269.       { return _Alloc_traits::max_size(_M_get_Tp_allocator()); }
  1270.  
  1271. #if __cplusplus >= 201103L
  1272.       /**
  1273.        *  @brief  Resizes the %deque to the specified number of elements.
  1274.        *  @param  __new_size  Number of elements the %deque should contain.
  1275.        *
  1276.        *  This function will %resize the %deque to the specified
  1277.        *  number of elements.  If the number is smaller than the
  1278.        *  %deque's current size the %deque is truncated, otherwise
  1279.        *  default constructed elements are appended.
  1280.        */
  1281.       void
  1282.       resize(size_type __new_size)
  1283.       {
  1284.         const size_type __len = size();
  1285.         if (__new_size > __len)
  1286.           _M_default_append(__new_size - __len);
  1287.         else if (__new_size < __len)
  1288.           _M_erase_at_end(this->_M_impl._M_start
  1289.                           + difference_type(__new_size));
  1290.       }
  1291.  
  1292.       /**
  1293.        *  @brief  Resizes the %deque to the specified number of elements.
  1294.        *  @param  __new_size  Number of elements the %deque should contain.
  1295.        *  @param  __x  Data with which new elements should be populated.
  1296.        *
  1297.        *  This function will %resize the %deque to the specified
  1298.        *  number of elements.  If the number is smaller than the
  1299.        *  %deque's current size the %deque is truncated, otherwise the
  1300.        *  %deque is extended and new elements are populated with given
  1301.        *  data.
  1302.        */
  1303.       void
  1304.       resize(size_type __new_size, const value_type& __x)
  1305.       {
  1306.         const size_type __len = size();
  1307.         if (__new_size > __len)
  1308.           insert(this->_M_impl._M_finish, __new_size - __len, __x);
  1309.         else if (__new_size < __len)
  1310.           _M_erase_at_end(this->_M_impl._M_start
  1311.                           + difference_type(__new_size));
  1312.       }
  1313. #else
  1314.       /**
  1315.        *  @brief  Resizes the %deque to the specified number of elements.
  1316.        *  @param  __new_size  Number of elements the %deque should contain.
  1317.        *  @param  __x  Data with which new elements should be populated.
  1318.        *
  1319.        *  This function will %resize the %deque to the specified
  1320.        *  number of elements.  If the number is smaller than the
  1321.        *  %deque's current size the %deque is truncated, otherwise the
  1322.        *  %deque is extended and new elements are populated with given
  1323.        *  data.
  1324.        */
  1325.       void
  1326.       resize(size_type __new_size, value_type __x = value_type())
  1327.       {
  1328.         const size_type __len = size();
  1329.         if (__new_size > __len)
  1330.           insert(this->_M_impl._M_finish, __new_size - __len, __x);
  1331.         else if (__new_size < __len)
  1332.           _M_erase_at_end(this->_M_impl._M_start
  1333.                           + difference_type(__new_size));
  1334.       }
  1335. #endif
  1336.  
  1337. #if __cplusplus >= 201103L
  1338.       /**  A non-binding request to reduce memory use.  */
  1339.       void
  1340.       shrink_to_fit() noexcept
  1341.       { _M_shrink_to_fit(); }
  1342. #endif
  1343.  
  1344.       /**
  1345.        *  Returns true if the %deque is empty.  (Thus begin() would
  1346.        *  equal end().)
  1347.        */
  1348.       bool
  1349.       empty() const _GLIBCXX_NOEXCEPT
  1350.       { return this->_M_impl._M_finish == this->_M_impl._M_start; }
  1351.  
  1352.       // element access
  1353.       /**
  1354.        *  @brief Subscript access to the data contained in the %deque.
  1355.        *  @param __n The index of the element for which data should be
  1356.        *  accessed.
  1357.        *  @return  Read/write reference to data.
  1358.        *
  1359.        *  This operator allows for easy, array-style, data access.
  1360.        *  Note that data access with this operator is unchecked and
  1361.        *  out_of_range lookups are not defined. (For checked lookups
  1362.        *  see at().)
  1363.        */
  1364.       reference
  1365.       operator[](size_type __n) _GLIBCXX_NOEXCEPT
  1366.       { return this->_M_impl._M_start[difference_type(__n)]; }
  1367.  
  1368.       /**
  1369.        *  @brief Subscript access to the data contained in the %deque.
  1370.        *  @param __n The index of the element for which data should be
  1371.        *  accessed.
  1372.        *  @return  Read-only (constant) reference to data.
  1373.        *
  1374.        *  This operator allows for easy, array-style, data access.
  1375.        *  Note that data access with this operator is unchecked and
  1376.        *  out_of_range lookups are not defined. (For checked lookups
  1377.        *  see at().)
  1378.        */
  1379.       const_reference
  1380.       operator[](size_type __n) const _GLIBCXX_NOEXCEPT
  1381.       { return this->_M_impl._M_start[difference_type(__n)]; }
  1382.  
  1383.     protected:
  1384.       /// Safety check used only from at().
  1385.       void
  1386.       _M_range_check(size_type __n) const
  1387.       {
  1388.         if (__n >= this->size())
  1389.           __throw_out_of_range_fmt(__N("deque::_M_range_check: __n "
  1390.                                        "(which is %zu)>= this->size() "
  1391.                                        "(which is %zu)"),
  1392.                                    __n, this->size());
  1393.       }
  1394.  
  1395.     public:
  1396.       /**
  1397.        *  @brief  Provides access to the data contained in the %deque.
  1398.        *  @param __n The index of the element for which data should be
  1399.        *  accessed.
  1400.        *  @return  Read/write reference to data.
  1401.        *  @throw  std::out_of_range  If @a __n is an invalid index.
  1402.        *
  1403.        *  This function provides for safer data access.  The parameter
  1404.        *  is first checked that it is in the range of the deque.  The
  1405.        *  function throws out_of_range if the check fails.
  1406.        */
  1407.       reference
  1408.       at(size_type __n)
  1409.       {
  1410.         _M_range_check(__n);
  1411.         return (*this)[__n];
  1412.       }
  1413.  
  1414.       /**
  1415.        *  @brief  Provides access to the data contained in the %deque.
  1416.        *  @param __n The index of the element for which data should be
  1417.        *  accessed.
  1418.        *  @return  Read-only (constant) reference to data.
  1419.        *  @throw  std::out_of_range  If @a __n is an invalid index.
  1420.        *
  1421.        *  This function provides for safer data access.  The parameter is first
  1422.        *  checked that it is in the range of the deque.  The function throws
  1423.        *  out_of_range if the check fails.
  1424.        */
  1425.       const_reference
  1426.       at(size_type __n) const
  1427.       {
  1428.         _M_range_check(__n);
  1429.         return (*this)[__n];
  1430.       }
  1431.  
  1432.       /**
  1433.        *  Returns a read/write reference to the data at the first
  1434.        *  element of the %deque.
  1435.        */
  1436.       reference
  1437.       front() _GLIBCXX_NOEXCEPT
  1438.       { return *begin(); }
  1439.  
  1440.       /**
  1441.        *  Returns a read-only (constant) reference to the data at the first
  1442.        *  element of the %deque.
  1443.        */
  1444.       const_reference
  1445.       front() const _GLIBCXX_NOEXCEPT
  1446.       { return *begin(); }
  1447.  
  1448.       /**
  1449.        *  Returns a read/write reference to the data at the last element of the
  1450.        *  %deque.
  1451.        */
  1452.       reference
  1453.       back() _GLIBCXX_NOEXCEPT
  1454.       {
  1455.         iterator __tmp = end();
  1456.         --__tmp;
  1457.         return *__tmp;
  1458.       }
  1459.  
  1460.       /**
  1461.        *  Returns a read-only (constant) reference to the data at the last
  1462.        *  element of the %deque.
  1463.        */
  1464.       const_reference
  1465.       back() const _GLIBCXX_NOEXCEPT
  1466.       {
  1467.         const_iterator __tmp = end();
  1468.         --__tmp;
  1469.         return *__tmp;
  1470.       }
  1471.  
  1472.       // [23.2.1.2] modifiers
  1473.       /**
  1474.        *  @brief  Add data to the front of the %deque.
  1475.        *  @param  __x  Data to be added.
  1476.        *
  1477.        *  This is a typical stack operation.  The function creates an
  1478.        *  element at the front of the %deque and assigns the given
  1479.        *  data to it.  Due to the nature of a %deque this operation
  1480.        *  can be done in constant time.
  1481.        */
  1482.       void
  1483.       push_front(const value_type& __x)
  1484.       {
  1485.         if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first)
  1486.           {
  1487.             _Alloc_traits::construct(this->_M_impl,
  1488.                                      this->_M_impl._M_start._M_cur - 1,
  1489.                                      __x);
  1490.             --this->_M_impl._M_start._M_cur;
  1491.           }
  1492.         else
  1493.           _M_push_front_aux(__x);
  1494.       }
  1495.  
  1496. #if __cplusplus >= 201103L
  1497.       void
  1498.       push_front(value_type&& __x)
  1499.       { emplace_front(std::move(__x)); }
  1500.  
  1501.       template<typename... _Args>
  1502.         void
  1503.         emplace_front(_Args&&... __args);
  1504. #endif
  1505.  
  1506.       /**
  1507.        *  @brief  Add data to the end of the %deque.
  1508.        *  @param  __x  Data to be added.
  1509.        *
  1510.        *  This is a typical stack operation.  The function creates an
  1511.        *  element at the end of the %deque and assigns the given data
  1512.        *  to it.  Due to the nature of a %deque this operation can be
  1513.        *  done in constant time.
  1514.        */
  1515.       void
  1516.       push_back(const value_type& __x)
  1517.       {
  1518.         if (this->_M_impl._M_finish._M_cur
  1519.             != this->_M_impl._M_finish._M_last - 1)
  1520.           {
  1521.             _Alloc_traits::construct(this->_M_impl,
  1522.                                      this->_M_impl._M_finish._M_cur, __x);
  1523.             ++this->_M_impl._M_finish._M_cur;
  1524.           }
  1525.         else
  1526.           _M_push_back_aux(__x);
  1527.       }
  1528.  
  1529. #if __cplusplus >= 201103L
  1530.       void
  1531.       push_back(value_type&& __x)
  1532.       { emplace_back(std::move(__x)); }
  1533.  
  1534.       template<typename... _Args>
  1535.         void
  1536.         emplace_back(_Args&&... __args);
  1537. #endif
  1538.  
  1539.       /**
  1540.        *  @brief  Removes first element.
  1541.        *
  1542.        *  This is a typical stack operation.  It shrinks the %deque by one.
  1543.        *
  1544.        *  Note that no data is returned, and if the first element's data is
  1545.        *  needed, it should be retrieved before pop_front() is called.
  1546.        */
  1547.       void
  1548.       pop_front() _GLIBCXX_NOEXCEPT
  1549.       {
  1550.         if (this->_M_impl._M_start._M_cur
  1551.             != this->_M_impl._M_start._M_last - 1)
  1552.           {
  1553.             _Alloc_traits::destroy(this->_M_impl,
  1554.                                    this->_M_impl._M_start._M_cur);
  1555.             ++this->_M_impl._M_start._M_cur;
  1556.           }
  1557.         else
  1558.           _M_pop_front_aux();
  1559.       }
  1560.  
  1561.       /**
  1562.        *  @brief  Removes last element.
  1563.        *
  1564.        *  This is a typical stack operation.  It shrinks the %deque by one.
  1565.        *
  1566.        *  Note that no data is returned, and if the last element's data is
  1567.        *  needed, it should be retrieved before pop_back() is called.
  1568.        */
  1569.       void
  1570.       pop_back() _GLIBCXX_NOEXCEPT
  1571.       {
  1572.         if (this->_M_impl._M_finish._M_cur
  1573.             != this->_M_impl._M_finish._M_first)
  1574.           {
  1575.             --this->_M_impl._M_finish._M_cur;
  1576.             _Alloc_traits::destroy(this->_M_impl,
  1577.                                    this->_M_impl._M_finish._M_cur);
  1578.           }
  1579.         else
  1580.           _M_pop_back_aux();
  1581.       }
  1582.  
  1583. #if __cplusplus >= 201103L
  1584.       /**
  1585.        *  @brief  Inserts an object in %deque before specified iterator.
  1586.        *  @param  __position  A const_iterator into the %deque.
  1587.        *  @param  __args  Arguments.
  1588.        *  @return  An iterator that points to the inserted data.
  1589.        *
  1590.        *  This function will insert an object of type T constructed
  1591.        *  with T(std::forward<Args>(args)...) before the specified location.
  1592.        */
  1593.       template<typename... _Args>
  1594.         iterator
  1595.         emplace(const_iterator __position, _Args&&... __args);
  1596.  
  1597.       /**
  1598.        *  @brief  Inserts given value into %deque before specified iterator.
  1599.        *  @param  __position  A const_iterator into the %deque.
  1600.        *  @param  __x  Data to be inserted.
  1601.        *  @return  An iterator that points to the inserted data.
  1602.        *
  1603.        *  This function will insert a copy of the given value before the
  1604.        *  specified location.
  1605.        */
  1606.       iterator
  1607.       insert(const_iterator __position, const value_type& __x);
  1608. #else
  1609.       /**
  1610.        *  @brief  Inserts given value into %deque before specified iterator.
  1611.        *  @param  __position  An iterator into the %deque.
  1612.        *  @param  __x  Data to be inserted.
  1613.        *  @return  An iterator that points to the inserted data.
  1614.        *
  1615.        *  This function will insert a copy of the given value before the
  1616.        *  specified location.
  1617.        */
  1618.       iterator
  1619.       insert(iterator __position, const value_type& __x);
  1620. #endif
  1621.  
  1622. #if __cplusplus >= 201103L
  1623.       /**
  1624.        *  @brief  Inserts given rvalue into %deque before specified iterator.
  1625.        *  @param  __position  A const_iterator into the %deque.
  1626.        *  @param  __x  Data to be inserted.
  1627.        *  @return  An iterator that points to the inserted data.
  1628.        *
  1629.        *  This function will insert a copy of the given rvalue before the
  1630.        *  specified location.
  1631.        */
  1632.       iterator
  1633.       insert(const_iterator __position, value_type&& __x)
  1634.       { return emplace(__position, std::move(__x)); }
  1635.  
  1636.       /**
  1637.        *  @brief  Inserts an initializer list into the %deque.
  1638.        *  @param  __p  An iterator into the %deque.
  1639.        *  @param  __l  An initializer_list.
  1640.        *
  1641.        *  This function will insert copies of the data in the
  1642.        *  initializer_list @a __l into the %deque before the location
  1643.        *  specified by @a __p.  This is known as <em>list insert</em>.
  1644.        */
  1645.       iterator
  1646.       insert(const_iterator __p, initializer_list<value_type> __l)
  1647.       { return this->insert(__p, __l.begin(), __l.end()); }
  1648. #endif
  1649.  
  1650. #if __cplusplus >= 201103L
  1651.       /**
  1652.        *  @brief  Inserts a number of copies of given data into the %deque.
  1653.        *  @param  __position  A const_iterator into the %deque.
  1654.        *  @param  __n  Number of elements to be inserted.
  1655.        *  @param  __x  Data to be inserted.
  1656.        *  @return  An iterator that points to the inserted data.
  1657.        *
  1658.        *  This function will insert a specified number of copies of the given
  1659.        *  data before the location specified by @a __position.
  1660.        */
  1661.       iterator
  1662.       insert(const_iterator __position, size_type __n, const value_type& __x)
  1663.       {
  1664.         difference_type __offset = __position - cbegin();
  1665.         _M_fill_insert(__position._M_const_cast(), __n, __x);
  1666.         return begin() + __offset;
  1667.       }
  1668. #else
  1669.       /**
  1670.        *  @brief  Inserts a number of copies of given data into the %deque.
  1671.        *  @param  __position  An iterator into the %deque.
  1672.        *  @param  __n  Number of elements to be inserted.
  1673.        *  @param  __x  Data to be inserted.
  1674.        *
  1675.        *  This function will insert a specified number of copies of the given
  1676.        *  data before the location specified by @a __position.
  1677.        */
  1678.       void
  1679.       insert(iterator __position, size_type __n, const value_type& __x)
  1680.       { _M_fill_insert(__position, __n, __x); }
  1681. #endif
  1682.  
  1683. #if __cplusplus >= 201103L
  1684.       /**
  1685.        *  @brief  Inserts a range into the %deque.
  1686.        *  @param  __position  A const_iterator into the %deque.
  1687.        *  @param  __first  An input iterator.
  1688.        *  @param  __last   An input iterator.
  1689.        *  @return  An iterator that points to the inserted data.
  1690.        *
  1691.        *  This function will insert copies of the data in the range
  1692.        *  [__first,__last) into the %deque before the location specified
  1693.        *  by @a __position.  This is known as <em>range insert</em>.
  1694.        */
  1695.       template<typename _InputIterator,
  1696.                typename = std::_RequireInputIter<_InputIterator>>
  1697.         iterator
  1698.         insert(const_iterator __position, _InputIterator __first,
  1699.                _InputIterator __last)
  1700.         {
  1701.           difference_type __offset = __position - cbegin();
  1702.           _M_insert_dispatch(__position._M_const_cast(),
  1703.                              __first, __last, __false_type());
  1704.           return begin() + __offset;
  1705.         }
  1706. #else
  1707.       /**
  1708.        *  @brief  Inserts a range into the %deque.
  1709.        *  @param  __position  An iterator into the %deque.
  1710.        *  @param  __first  An input iterator.
  1711.        *  @param  __last   An input iterator.
  1712.        *
  1713.        *  This function will insert copies of the data in the range
  1714.        *  [__first,__last) into the %deque before the location specified
  1715.        *  by @a __position.  This is known as <em>range insert</em>.
  1716.        */
  1717.       template<typename _InputIterator>
  1718.         void
  1719.         insert(iterator __position, _InputIterator __first,
  1720.                _InputIterator __last)
  1721.         {
  1722.           // Check whether it's an integral type.  If so, it's not an iterator.
  1723.           typedef typename std::__is_integer<_InputIterator>::__type _Integral;
  1724.           _M_insert_dispatch(__position, __first, __last, _Integral());
  1725.         }
  1726. #endif
  1727.  
  1728.       /**
  1729.        *  @brief  Remove element at given position.
  1730.        *  @param  __position  Iterator pointing to element to be erased.
  1731.        *  @return  An iterator pointing to the next element (or end()).
  1732.        *
  1733.        *  This function will erase the element at the given position and thus
  1734.        *  shorten the %deque by one.
  1735.        *
  1736.        *  The user is cautioned that
  1737.        *  this function only erases the element, and that if the element is
  1738.        *  itself a pointer, the pointed-to memory is not touched in any way.
  1739.        *  Managing the pointer is the user's responsibility.
  1740.        */
  1741.       iterator
  1742. #if __cplusplus >= 201103L
  1743.       erase(const_iterator __position)
  1744. #else
  1745.       erase(iterator __position)
  1746. #endif
  1747.       { return _M_erase(__position._M_const_cast()); }
  1748.  
  1749.       /**
  1750.        *  @brief  Remove a range of elements.
  1751.        *  @param  __first  Iterator pointing to the first element to be erased.
  1752.        *  @param  __last  Iterator pointing to one past the last element to be
  1753.        *                erased.
  1754.        *  @return  An iterator pointing to the element pointed to by @a last
  1755.        *           prior to erasing (or end()).
  1756.        *
  1757.        *  This function will erase the elements in the range
  1758.        *  [__first,__last) and shorten the %deque accordingly.
  1759.        *
  1760.        *  The user is cautioned that
  1761.        *  this function only erases the elements, and that if the elements
  1762.        *  themselves are pointers, the pointed-to memory is not touched in any
  1763.        *  way.  Managing the pointer is the user's responsibility.
  1764.        */
  1765.       iterator
  1766. #if __cplusplus >= 201103L
  1767.       erase(const_iterator __first, const_iterator __last)
  1768. #else
  1769.       erase(iterator __first, iterator __last)
  1770. #endif
  1771.       { return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
  1772.  
  1773.       /**
  1774.        *  @brief  Swaps data with another %deque.
  1775.        *  @param  __x  A %deque of the same element and allocator types.
  1776.        *
  1777.        *  This exchanges the elements between two deques in constant time.
  1778.        *  (Four pointers, so it should be quite fast.)
  1779.        *  Note that the global std::swap() function is specialized such that
  1780.        *  std::swap(d1,d2) will feed to this function.
  1781.        */
  1782.       void
  1783.       swap(deque& __x)
  1784. #if __cplusplus >= 201103L
  1785.       noexcept(_Alloc_traits::_S_nothrow_swap())
  1786. #endif
  1787.       {
  1788.         _M_impl._M_swap_data(__x._M_impl);
  1789.         _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),
  1790.                                   __x._M_get_Tp_allocator());
  1791.       }
  1792.  
  1793.       /**
  1794.        *  Erases all the elements.  Note that this function only erases the
  1795.        *  elements, and that if the elements themselves are pointers, the
  1796.        *  pointed-to memory is not touched in any way.  Managing the pointer is
  1797.        *  the user's responsibility.
  1798.        */
  1799.       void
  1800.       clear() _GLIBCXX_NOEXCEPT
  1801.       { _M_erase_at_end(begin()); }
  1802.  
  1803.     protected:
  1804.       // Internal constructor functions follow.
  1805.  
  1806.       // called by the range constructor to implement [23.1.1]/9
  1807.  
  1808.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  1809.       // 438. Ambiguity in the "do the right thing" clause
  1810.       template<typename _Integer>
  1811.         void
  1812.         _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
  1813.         {
  1814.           _M_initialize_map(static_cast<size_type>(__n));
  1815.           _M_fill_initialize(__x);
  1816.         }
  1817.  
  1818.       // called by the range constructor to implement [23.1.1]/9
  1819.       template<typename _InputIterator>
  1820.         void
  1821.         _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
  1822.                                __false_type)
  1823.         {
  1824.           typedef typename std::iterator_traits<_InputIterator>::
  1825.             iterator_category _IterCategory;
  1826.           _M_range_initialize(__first, __last, _IterCategory());
  1827.         }
  1828.  
  1829.       // called by the second initialize_dispatch above
  1830.       //@{
  1831.       /**
  1832.        *  @brief Fills the deque with whatever is in [first,last).
  1833.        *  @param  __first  An input iterator.
  1834.        *  @param  __last  An input iterator.
  1835.        *  @return   Nothing.
  1836.        *
  1837.        *  If the iterators are actually forward iterators (or better), then the
  1838.        *  memory layout can be done all at once.  Else we move forward using
  1839.        *  push_back on each value from the iterator.
  1840.        */
  1841.       template<typename _InputIterator>
  1842.         void
  1843.         _M_range_initialize(_InputIterator __first, _InputIterator __last,
  1844.                             std::input_iterator_tag);
  1845.  
  1846.       // called by the second initialize_dispatch above
  1847.       template<typename _ForwardIterator>
  1848.         void
  1849.         _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,
  1850.                             std::forward_iterator_tag);
  1851.       //@}
  1852.  
  1853.       /**
  1854.        *  @brief Fills the %deque with copies of value.
  1855.        *  @param  __value  Initial value.
  1856.        *  @return   Nothing.
  1857.        *  @pre _M_start and _M_finish have already been initialized,
  1858.        *  but none of the %deque's elements have yet been constructed.
  1859.        *
  1860.        *  This function is called only when the user provides an explicit size
  1861.        *  (with or without an explicit exemplar value).
  1862.        */
  1863.       void
  1864.       _M_fill_initialize(const value_type& __value);
  1865.  
  1866. #if __cplusplus >= 201103L
  1867.       // called by deque(n).
  1868.       void
  1869.       _M_default_initialize();
  1870. #endif
  1871.  
  1872.       // Internal assign functions follow.  The *_aux functions do the actual
  1873.       // assignment work for the range versions.
  1874.  
  1875.       // called by the range assign to implement [23.1.1]/9
  1876.  
  1877.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  1878.       // 438. Ambiguity in the "do the right thing" clause
  1879.       template<typename _Integer>
  1880.         void
  1881.         _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
  1882.         { _M_fill_assign(__n, __val); }
  1883.  
  1884.       // called by the range assign to implement [23.1.1]/9
  1885.       template<typename _InputIterator>
  1886.         void
  1887.         _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
  1888.                            __false_type)
  1889.         {
  1890.           typedef typename std::iterator_traits<_InputIterator>::
  1891.             iterator_category _IterCategory;
  1892.           _M_assign_aux(__first, __last, _IterCategory());
  1893.         }
  1894.  
  1895.       // called by the second assign_dispatch above
  1896.       template<typename _InputIterator>
  1897.         void
  1898.         _M_assign_aux(_InputIterator __first, _InputIterator __last,
  1899.                       std::input_iterator_tag);
  1900.  
  1901.       // called by the second assign_dispatch above
  1902.       template<typename _ForwardIterator>
  1903.         void
  1904.         _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
  1905.                       std::forward_iterator_tag)
  1906.         {
  1907.           const size_type __len = std::distance(__first, __last);
  1908.           if (__len > size())
  1909.             {
  1910.               _ForwardIterator __mid = __first;
  1911.               std::advance(__mid, size());
  1912.               std::copy(__first, __mid, begin());
  1913.               insert(end(), __mid, __last);
  1914.             }
  1915.           else
  1916.             _M_erase_at_end(std::copy(__first, __last, begin()));
  1917.         }
  1918.  
  1919.       // Called by assign(n,t), and the range assign when it turns out
  1920.       // to be the same thing.
  1921.       void
  1922.       _M_fill_assign(size_type __n, const value_type& __val)
  1923.       {
  1924.         if (__n > size())
  1925.           {
  1926.             std::fill(begin(), end(), __val);
  1927.             insert(end(), __n - size(), __val);
  1928.           }
  1929.         else
  1930.           {
  1931.             _M_erase_at_end(begin() + difference_type(__n));
  1932.             std::fill(begin(), end(), __val);
  1933.           }
  1934.       }
  1935.  
  1936.       //@{
  1937.       /// Helper functions for push_* and pop_*.
  1938. #if __cplusplus < 201103L
  1939.       void _M_push_back_aux(const value_type&);
  1940.  
  1941.       void _M_push_front_aux(const value_type&);
  1942. #else
  1943.       template<typename... _Args>
  1944.         void _M_push_back_aux(_Args&&... __args);
  1945.  
  1946.       template<typename... _Args>
  1947.         void _M_push_front_aux(_Args&&... __args);
  1948. #endif
  1949.  
  1950.       void _M_pop_back_aux();
  1951.  
  1952.       void _M_pop_front_aux();
  1953.       //@}
  1954.  
  1955.       // Internal insert functions follow.  The *_aux functions do the actual
  1956.       // insertion work when all shortcuts fail.
  1957.  
  1958.       // called by the range insert to implement [23.1.1]/9
  1959.  
  1960.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  1961.       // 438. Ambiguity in the "do the right thing" clause
  1962.       template<typename _Integer>
  1963.         void
  1964.         _M_insert_dispatch(iterator __pos,
  1965.                            _Integer __n, _Integer __x, __true_type)
  1966.         { _M_fill_insert(__pos, __n, __x); }
  1967.  
  1968.       // called by the range insert to implement [23.1.1]/9
  1969.       template<typename _InputIterator>
  1970.         void
  1971.         _M_insert_dispatch(iterator __pos,
  1972.                            _InputIterator __first, _InputIterator __last,
  1973.                            __false_type)
  1974.         {
  1975.           typedef typename std::iterator_traits<_InputIterator>::
  1976.             iterator_category _IterCategory;
  1977.           _M_range_insert_aux(__pos, __first, __last, _IterCategory());
  1978.         }
  1979.  
  1980.       // called by the second insert_dispatch above
  1981.       template<typename _InputIterator>
  1982.         void
  1983.         _M_range_insert_aux(iterator __pos, _InputIterator __first,
  1984.                             _InputIterator __last, std::input_iterator_tag);
  1985.  
  1986.       // called by the second insert_dispatch above
  1987.       template<typename _ForwardIterator>
  1988.         void
  1989.         _M_range_insert_aux(iterator __pos, _ForwardIterator __first,
  1990.                             _ForwardIterator __last, std::forward_iterator_tag);
  1991.  
  1992.       // Called by insert(p,n,x), and the range insert when it turns out to be
  1993.       // the same thing.  Can use fill functions in optimal situations,
  1994.       // otherwise passes off to insert_aux(p,n,x).
  1995.       void
  1996.       _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
  1997.  
  1998.       // called by insert(p,x)
  1999. #if __cplusplus < 201103L
  2000.       iterator
  2001.       _M_insert_aux(iterator __pos, const value_type& __x);
  2002. #else
  2003.       template<typename... _Args>
  2004.         iterator
  2005.         _M_insert_aux(iterator __pos, _Args&&... __args);
  2006. #endif
  2007.  
  2008.       // called by insert(p,n,x) via fill_insert
  2009.       void
  2010.       _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
  2011.  
  2012.       // called by range_insert_aux for forward iterators
  2013.       template<typename _ForwardIterator>
  2014.         void
  2015.         _M_insert_aux(iterator __pos,
  2016.                       _ForwardIterator __first, _ForwardIterator __last,
  2017.                       size_type __n);
  2018.  
  2019.  
  2020.       // Internal erase functions follow.
  2021.  
  2022.       void
  2023.       _M_destroy_data_aux(iterator __first, iterator __last);
  2024.  
  2025.       // Called by ~deque().
  2026.       // NB: Doesn't deallocate the nodes.
  2027.       template<typename _Alloc1>
  2028.         void
  2029.         _M_destroy_data(iterator __first, iterator __last, const _Alloc1&)
  2030.         { _M_destroy_data_aux(__first, __last); }
  2031.  
  2032.       void
  2033.       _M_destroy_data(iterator __first, iterator __last,
  2034.                       const std::allocator<_Tp>&)
  2035.       {
  2036.         if (!__has_trivial_destructor(value_type))
  2037.           _M_destroy_data_aux(__first, __last);
  2038.       }
  2039.  
  2040.       // Called by erase(q1, q2).
  2041.       void
  2042.       _M_erase_at_begin(iterator __pos)
  2043.       {
  2044.         _M_destroy_data(begin(), __pos, _M_get_Tp_allocator());
  2045.         _M_destroy_nodes(this->_M_impl._M_start._M_node, __pos._M_node);
  2046.         this->_M_impl._M_start = __pos;
  2047.       }
  2048.  
  2049.       // Called by erase(q1, q2), resize(), clear(), _M_assign_aux,
  2050.       // _M_fill_assign, operator=.
  2051.       void
  2052.       _M_erase_at_end(iterator __pos)
  2053.       {
  2054.         _M_destroy_data(__pos, end(), _M_get_Tp_allocator());
  2055.         _M_destroy_nodes(__pos._M_node + 1,
  2056.                          this->_M_impl._M_finish._M_node + 1);
  2057.         this->_M_impl._M_finish = __pos;
  2058.       }
  2059.  
  2060.       iterator
  2061.       _M_erase(iterator __pos);
  2062.  
  2063.       iterator
  2064.       _M_erase(iterator __first, iterator __last);
  2065.  
  2066. #if __cplusplus >= 201103L
  2067.       // Called by resize(sz).
  2068.       void
  2069.       _M_default_append(size_type __n);
  2070.  
  2071.       bool
  2072.       _M_shrink_to_fit();
  2073. #endif
  2074.  
  2075.       //@{
  2076.       /// Memory-handling helpers for the previous internal insert functions.
  2077.       iterator
  2078.       _M_reserve_elements_at_front(size_type __n)
  2079.       {
  2080.         const size_type __vacancies = this->_M_impl._M_start._M_cur
  2081.                                       - this->_M_impl._M_start._M_first;
  2082.         if (__n > __vacancies)
  2083.           _M_new_elements_at_front(__n - __vacancies);
  2084.         return this->_M_impl._M_start - difference_type(__n);
  2085.       }
  2086.  
  2087.       iterator
  2088.       _M_reserve_elements_at_back(size_type __n)
  2089.       {
  2090.         const size_type __vacancies = (this->_M_impl._M_finish._M_last
  2091.                                        - this->_M_impl._M_finish._M_cur) - 1;
  2092.         if (__n > __vacancies)
  2093.           _M_new_elements_at_back(__n - __vacancies);
  2094.         return this->_M_impl._M_finish + difference_type(__n);
  2095.       }
  2096.  
  2097.       void
  2098.       _M_new_elements_at_front(size_type __new_elements);
  2099.  
  2100.       void
  2101.       _M_new_elements_at_back(size_type __new_elements);
  2102.       //@}
  2103.  
  2104.  
  2105.       //@{
  2106.       /**
  2107.        *  @brief Memory-handling helpers for the major %map.
  2108.        *
  2109.        *  Makes sure the _M_map has space for new nodes.  Does not
  2110.        *  actually add the nodes.  Can invalidate _M_map pointers.
  2111.        *  (And consequently, %deque iterators.)
  2112.        */
  2113.       void
  2114.       _M_reserve_map_at_back(size_type __nodes_to_add = 1)
  2115.       {
  2116.         if (__nodes_to_add + 1 > this->_M_impl._M_map_size
  2117.             - (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))
  2118.           _M_reallocate_map(__nodes_to_add, false);
  2119.       }
  2120.  
  2121.       void
  2122.       _M_reserve_map_at_front(size_type __nodes_to_add = 1)
  2123.       {
  2124.         if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node
  2125.                                        - this->_M_impl._M_map))
  2126.           _M_reallocate_map(__nodes_to_add, true);
  2127.       }
  2128.  
  2129.       void
  2130.       _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
  2131.       //@}
  2132.  
  2133. #if __cplusplus >= 201103L
  2134.       // Constant-time, nothrow move assignment when source object's memory
  2135.       // can be moved because the allocators are equal.
  2136.       void
  2137.       _M_move_assign1(deque&& __x, /* always equal: */ true_type) noexcept
  2138.       {
  2139.         this->_M_impl._M_swap_data(__x._M_impl);
  2140.         __x.clear();
  2141.         std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());
  2142.       }
  2143.  
  2144.       void
  2145.       _M_move_assign1(deque&& __x, /* always equal: */ false_type)
  2146.       {
  2147.         constexpr bool __move_storage =
  2148.           _Alloc_traits::_S_propagate_on_move_assign();
  2149.         _M_move_assign2(std::move(__x),
  2150.                         integral_constant<bool, __move_storage>());
  2151.       }
  2152.  
  2153.       // Destroy all elements and deallocate all memory, then replace
  2154.       // with elements created from __args.
  2155.       template<typename... _Args>
  2156.       void
  2157.       _M_replace_map(_Args&&... __args)
  2158.       {
  2159.         // Create new data first, so if allocation fails there are no effects.
  2160.         deque __newobj(std::forward<_Args>(__args)...);
  2161.         // Free existing storage using existing allocator.
  2162.         clear();
  2163.         _M_deallocate_node(*begin()._M_node); // one node left after clear()
  2164.         _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
  2165.         this->_M_impl._M_map = nullptr;
  2166.         this->_M_impl._M_map_size = 0;
  2167.         // Take ownership of replacement memory.
  2168.         this->_M_impl._M_swap_data(__newobj._M_impl);
  2169.       }
  2170.  
  2171.       // Do move assignment when the allocator propagates.
  2172.       void
  2173.       _M_move_assign2(deque&& __x, /* propagate: */ true_type)
  2174.       {
  2175.         // Make a copy of the original allocator state.
  2176.         auto __alloc = __x._M_get_Tp_allocator();
  2177.         // The allocator propagates so storage can be moved from __x,
  2178.         // leaving __x in a valid empty state with a moved-from allocator.
  2179.         _M_replace_map(std::move(__x));
  2180.         // Move the corresponding allocator state too.
  2181.         _M_get_Tp_allocator() = std::move(__alloc);
  2182.       }
  2183.  
  2184.       // Do move assignment when it may not be possible to move source
  2185.       // object's memory, resulting in a linear-time operation.
  2186.       void
  2187.       _M_move_assign2(deque&& __x, /* propagate: */ false_type)
  2188.       {
  2189.         if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator())
  2190.           {
  2191.             // The allocators are equal so storage can be moved from __x,
  2192.             // leaving __x in a valid empty state with its current allocator.
  2193.             _M_replace_map(std::move(__x), __x.get_allocator());
  2194.           }
  2195.         else
  2196.           {
  2197.             // The rvalue's allocator cannot be moved and is not equal,
  2198.             // so we need to individually move each element.
  2199.             this->assign(std::__make_move_if_noexcept_iterator(__x.begin()),
  2200.                          std::__make_move_if_noexcept_iterator(__x.end()));
  2201.             __x.clear();
  2202.           }
  2203.       }
  2204. #endif
  2205.     };
  2206.  
  2207.  
  2208.   /**
  2209.    *  @brief  Deque equality comparison.
  2210.    *  @param  __x  A %deque.
  2211.    *  @param  __y  A %deque of the same type as @a __x.
  2212.    *  @return  True iff the size and elements of the deques are equal.
  2213.    *
  2214.    *  This is an equivalence relation.  It is linear in the size of the
  2215.    *  deques.  Deques are considered equivalent if their sizes are equal,
  2216.    *  and if corresponding elements compare equal.
  2217.   */
  2218.   template<typename _Tp, typename _Alloc>
  2219.     inline bool
  2220.     operator==(const deque<_Tp, _Alloc>& __x,
  2221.                          const deque<_Tp, _Alloc>& __y)
  2222.     { return __x.size() == __y.size()
  2223.              && std::equal(__x.begin(), __x.end(), __y.begin()); }
  2224.  
  2225.   /**
  2226.    *  @brief  Deque ordering relation.
  2227.    *  @param  __x  A %deque.
  2228.    *  @param  __y  A %deque of the same type as @a __x.
  2229.    *  @return  True iff @a x is lexicographically less than @a __y.
  2230.    *
  2231.    *  This is a total ordering relation.  It is linear in the size of the
  2232.    *  deques.  The elements must be comparable with @c <.
  2233.    *
  2234.    *  See std::lexicographical_compare() for how the determination is made.
  2235.   */
  2236.   template<typename _Tp, typename _Alloc>
  2237.     inline bool
  2238.     operator<(const deque<_Tp, _Alloc>& __x,
  2239.               const deque<_Tp, _Alloc>& __y)
  2240.     { return std::lexicographical_compare(__x.begin(), __x.end(),
  2241.                                           __y.begin(), __y.end()); }
  2242.  
  2243.   /// Based on operator==
  2244.   template<typename _Tp, typename _Alloc>
  2245.     inline bool
  2246.     operator!=(const deque<_Tp, _Alloc>& __x,
  2247.                const deque<_Tp, _Alloc>& __y)
  2248.     { return !(__x == __y); }
  2249.  
  2250.   /// Based on operator<
  2251.   template<typename _Tp, typename _Alloc>
  2252.     inline bool
  2253.     operator>(const deque<_Tp, _Alloc>& __x,
  2254.               const deque<_Tp, _Alloc>& __y)
  2255.     { return __y < __x; }
  2256.  
  2257.   /// Based on operator<
  2258.   template<typename _Tp, typename _Alloc>
  2259.     inline bool
  2260.     operator<=(const deque<_Tp, _Alloc>& __x,
  2261.                const deque<_Tp, _Alloc>& __y)
  2262.     { return !(__y < __x); }
  2263.  
  2264.   /// Based on operator<
  2265.   template<typename _Tp, typename _Alloc>
  2266.     inline bool
  2267.     operator>=(const deque<_Tp, _Alloc>& __x,
  2268.                const deque<_Tp, _Alloc>& __y)
  2269.     { return !(__x < __y); }
  2270.  
  2271.   /// See std::deque::swap().
  2272.   template<typename _Tp, typename _Alloc>
  2273.     inline void
  2274.     swap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y)
  2275.     { __x.swap(__y); }
  2276.  
  2277. #undef _GLIBCXX_DEQUE_BUF_SIZE
  2278.  
  2279. _GLIBCXX_END_NAMESPACE_CONTAINER
  2280. } // namespace std
  2281.  
  2282. #endif /* _STL_DEQUE_H */
  2283.