stack的使用

stack是一种容器适配器，具有后进先出，只能从容器的一端进行元素的插入与提取操作
在这里插入图片描述

#include <iostream>
#include <vector>
#include <stack>
using namespace std;int main()
{stack<int, vector<int>> st;st.push(1);st.push(2);st.push(3);st.push(4);cout << st.size() << endl; //4while (!st.empty()){cout << st.top() << " ";st.pop();}cout << endl; //4 3 2 1return 0;
}

queue的使用

队列是一种容器适配器，具有先进先出，只能从容器的一端插入元素，另一端提取元素
在这里插入图片描述

#include <iostream>
#include <list>
#include <queue>
using namespace std;int main()
{queue<int, list<int>> q;q.push(1);q.push(2);q.push(3);q.push(4);cout << q.size() << endl; //4while (!q.empty()){cout << q.front() << " ";q.pop();}cout << endl; //1 2 3 4return 0;
}

适配器

stack和queue在STL中并没有将其划分在容器的行列，而是称为容器适配器
因为stack和queue对其他容器的接口进行了包装，STL中stack和queue默认使用deque容器。在这里插入图片描述

queue的模拟实现

核心接口

front：获取对列头部（第一个元素）
back：获取队列尾部（最后一个元素）
size：获取队列中的元素个数
pop：删除队列头部元素
push：队列尾部插入元素
empty：判空

namespace cxq
{template<class T ,class Container = deque<T> >class queue{public:void push(const T & x){_con.push_back(x);}void pop(){_con.pop_front();}T&	front(){return _con.front();}T& back(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};void test_queue1(){queue<int, list<int> > q ;q.push(1);q.push(2);q.push(3);q.push(4);while (!q.empty()){cout << q.front() << " ";q.pop();}cout << endl;}
}

stack的模拟实现

核心接口

top：获取尾部元素
size：获取栈中的元素个数
pop：删除栈顶元素
push：栈顶插入元素
empty：判空

namespace cxq
{template<class T  , class Container = deque<T> >class Stack{public:void push( const T & x ){_con.push_back(x);}T &  top(){return _con.back();}void pop(){_con.pop_back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};void test_Stack1(){stack<int> st1;st1.push(1);st1.push(2);st1.push(3);st1.push(4);while (!st1.empty()){cout << st1.top() << " ";st1.pop();}cout << endl;stack<int ,list<int> > st2;st2.push(1);st2.push(2);st2.push(3);st2.push(4);while (!st2.empty()){cout << st2.top() << " ";st2.pop();}cout << endl;}
}

deque

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

在这里插入图片描述

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组。
双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上

在这里插入图片描述

deque 与vector比较:
deque的头插和头删时，不需要挪动元素，效率特别高，而且在扩容时，也不需要移动大量的元素。
deque与list比较:
其底层是连续空间，空间利用率比较高，不需要存储额外字段。

但是，deque不适合遍历
因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

为什么STL选择deque作为stack和queue的底层默认容器

stack是一种后进先出的数据结构，因此只要具有push_back()和pop_back()操作的结构，都可以作为stack的底层容器，比如vector和list都可以。
queue是先进先出的数据结构，只要具有 push_back和pop_front操作的结构，都可以作为queue的底层容器，比如list。但是STL中对stack和 queue默认选择deque作为其底层容器，主要是因为：
1、stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
2、在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。
结合了deque的优点，而完美的避开了其缺陷。

如果想要对deque有比较深入的了解，可以阅读STL库的源码

// Deque implementation -*- C++ -*-// Copyright (C) 2001-2018 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>./*** Copyright (c) 1994* Hewlett-Packard Company** Permission to use, copy, modify, distribute and sell this software* and its documentation for any purpose is hereby granted without fee,* provided that the above copyright notice appear in all copies and* that both that copyright notice and this permission notice appear* in supporting documentation.  Hewlett-Packard Company makes no* representations about the suitability of this software for any* purpose.  It is provided "as is" without express or implied warranty.*** Copyright (c) 1997* Silicon Graphics Computer Systems, Inc.** Permission to use, copy, modify, distribute and sell this software* and its documentation for any purpose is hereby granted without fee,* provided that the above copyright notice appear in all copies and* that both that copyright notice and this permission notice appear* in supporting documentation.  Silicon Graphics makes no* representations about the suitability of this software for any* purpose.  It is provided "as is" without express or implied warranty.*//** @file bits/stl_deque.h*  This is an internal header file, included by other library headers.*  Do not attempt to use it directly. @headername{deque}*/#ifndef _STL_DEQUE_H
#define _STL_DEQUE_H 1#include <bits/concept_check.h>
#include <bits/stl_iterator_base_types.h>
#include <bits/stl_iterator_base_funcs.h>
#if __cplusplus >= 201103L
#include <initializer_list>
#endif#include <debug/assertions.h>namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
_GLIBCXX_BEGIN_NAMESPACE_CONTAINER/***  @brief This function controls the size of memory nodes.*  @param  __size  The size of an element.*  @return   The number (not byte size) of elements per node.**  This function started off as a compiler kludge from SGI, but*  seems to be a useful wrapper around a repeated constant*  expression.  The @b 512 is tunable (and no other code needs to*  change), but no investigation has been done since inheriting the*  SGI code.  Touch _GLIBCXX_DEQUE_BUF_SIZE only if you know what*  you are doing, however: changing it breaks the binary*  compatibility!!*/#ifndef _GLIBCXX_DEQUE_BUF_SIZE
#define _GLIBCXX_DEQUE_BUF_SIZE 512
#endif_GLIBCXX_CONSTEXPR inline size_t__deque_buf_size(size_t __size){ return (__size < _GLIBCXX_DEQUE_BUF_SIZE? size_t(_GLIBCXX_DEQUE_BUF_SIZE / __size) : size_t(1)); }/***  @brief A deque::iterator.**  Quite a bit of intelligence here.  Much of the functionality of*  deque is actually passed off to this class.  A deque holds two*  of these internally, marking its valid range.  Access to*  elements is done as offsets of either of those two, relying on*  operator overloading in this class.**  All the functions are op overloads except for _M_set_node.*/template<typename _Tp, typename _Ref, typename _Ptr>struct _Deque_iterator{
#if __cplusplus < 201103Ltypedef _Deque_iterator<_Tp, _Tp&, _Tp*>	     iterator;typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;typedef _Tp*					 _Elt_pointer;typedef _Tp**					_Map_pointer;
#elseprivate:template<typename _Up>using __ptr_to = typename pointer_traits<_Ptr>::template rebind<_Up>;template<typename _CvTp>using __iter = _Deque_iterator<_Tp, _CvTp&, __ptr_to<_CvTp>>;public:typedef __iter<_Tp>		iterator;typedef __iter<const _Tp>		const_iterator;typedef __ptr_to<_Tp>		_Elt_pointer;typedef __ptr_to<_Elt_pointer>	_Map_pointer;
#endifstatic size_t _S_buffer_size() _GLIBCXX_NOEXCEPT{ return __deque_buf_size(sizeof(_Tp)); }typedef std::random_access_iterator_tag	iterator_category;typedef _Tp				value_type;typedef _Ptr				pointer;typedef _Ref				reference;typedef size_t				size_type;typedef ptrdiff_t				difference_type;typedef _Deque_iterator			_Self;_Elt_pointer _M_cur;_Elt_pointer _M_first;_Elt_pointer _M_last;_Map_pointer _M_node;_Deque_iterator(_Elt_pointer __x, _Map_pointer __y) _GLIBCXX_NOEXCEPT: _M_cur(__x), _M_first(*__y),_M_last(*__y + _S_buffer_size()), _M_node(__y) { }_Deque_iterator() _GLIBCXX_NOEXCEPT: _M_cur(), _M_first(), _M_last(), _M_node() { }_Deque_iterator(const iterator& __x) _GLIBCXX_NOEXCEPT: _M_cur(__x._M_cur), _M_first(__x._M_first),_M_last(__x._M_last), _M_node(__x._M_node) { }iterator_M_const_cast() const _GLIBCXX_NOEXCEPT{ return iterator(_M_cur, _M_node); }referenceoperator*() const _GLIBCXX_NOEXCEPT{ return *_M_cur; }pointeroperator->() const _GLIBCXX_NOEXCEPT{ return _M_cur; }_Self&operator++() _GLIBCXX_NOEXCEPT{++_M_cur;if (_M_cur == _M_last){_M_set_node(_M_node + 1);_M_cur = _M_first;}return *this;}_Selfoperator++(int) _GLIBCXX_NOEXCEPT{_Self __tmp = *this;++*this;return __tmp;}_Self&operator--() _GLIBCXX_NOEXCEPT{if (_M_cur == _M_first){_M_set_node(_M_node - 1);_M_cur = _M_last;}--_M_cur;return *this;}_Selfoperator--(int) _GLIBCXX_NOEXCEPT{_Self __tmp = *this;--*this;return __tmp;}_Self&operator+=(difference_type __n) _GLIBCXX_NOEXCEPT{const difference_type __offset = __n + (_M_cur - _M_first);if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))_M_cur += __n;else{const difference_type __node_offset =__offset > 0 ? __offset / difference_type(_S_buffer_size()): -difference_type((-__offset - 1)/ _S_buffer_size()) - 1;_M_set_node(_M_node + __node_offset);_M_cur = _M_first + (__offset - __node_offset* difference_type(_S_buffer_size()));}return *this;}_Selfoperator+(difference_type __n) const _GLIBCXX_NOEXCEPT{_Self __tmp = *this;return __tmp += __n;}_Self&operator-=(difference_type __n) _GLIBCXX_NOEXCEPT{ return *this += -__n; }_Selfoperator-(difference_type __n) const _GLIBCXX_NOEXCEPT{_Self __tmp = *this;return __tmp -= __n;}referenceoperator[](difference_type __n) const _GLIBCXX_NOEXCEPT{ return *(*this + __n); }/***  Prepares to traverse new_node.  Sets everything except*  _M_cur, which should therefore be set by the caller*  immediately afterwards, based on _M_first and _M_last.*/void_M_set_node(_Map_pointer __new_node) _GLIBCXX_NOEXCEPT{_M_node = __new_node;_M_first = *__new_node;_M_last = _M_first + difference_type(_S_buffer_size());}};// Note: we also provide overloads whose operands are of the same type in// order to avoid ambiguous overload resolution when std::rel_ops operators// are in scope (for additional details, see libstdc++/3628)template<typename _Tp, typename _Ref, typename _Ptr>inline booloperator==(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT{ return __x._M_cur == __y._M_cur; }template<typename _Tp, typename _RefL, typename _PtrL,typename _RefR, typename _PtrR>inline booloperator==(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT{ return __x._M_cur == __y._M_cur; }template<typename _Tp, typename _Ref, typename _Ptr>inline booloperator!=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT{ return !(__x == __y); }template<typename _Tp, typename _RefL, typename _PtrL,typename _RefR, typename _PtrR>inline booloperator!=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT{ return !(__x == __y); }template<typename _Tp, typename _Ref, typename _Ptr>inline booloperator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT{ return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur): (__x._M_node < __y._M_node); }template<typename _Tp, typename _RefL, typename _PtrL,typename _RefR, typename _PtrR>inline booloperator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT{ return (__x._M_node == __y._M_node) ? (__x._M_cur < __y._M_cur): (__x._M_node < __y._M_node); }template<typename _Tp, typename _Ref, typename _Ptr>inline booloperator>(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT{ return __y < __x; }template<typename _Tp, typename _RefL, typename _PtrL,typename _RefR, typename _PtrR>inline booloperator>(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT{ return __y < __x; }template<typename _Tp, typename _Ref, typename _Ptr>inline booloperator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT{ return !(__y < __x); }template<typename _Tp, typename _RefL, typename _PtrL,typename _RefR, typename _PtrR>inline booloperator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT{ return !(__y < __x); }template<typename _Tp, typename _Ref, typename _Ptr>inline booloperator>=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT{ return !(__x < __y); }template<typename _Tp, typename _RefL, typename _PtrL,typename _RefR, typename _PtrR>inline booloperator>=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT{ return !(__x < __y); }// _GLIBCXX_RESOLVE_LIB_DEFECTS// According to the resolution of DR179 not only the various comparison// operators but also operator- must accept mixed iterator/const_iterator// parameters.template<typename _Tp, typename _Ref, typename _Ptr>inline typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_typeoperator-(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,const _Deque_iterator<_Tp, _Ref, _Ptr>& __y) _GLIBCXX_NOEXCEPT{return typename _Deque_iterator<_Tp, _Ref, _Ptr>::difference_type(_Deque_iterator<_Tp, _Ref, _Ptr>::_S_buffer_size())* (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)+ (__y._M_last - __y._M_cur);}template<typename _Tp, typename _RefL, typename _PtrL,typename _RefR, typename _PtrR>inline typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_typeoperator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,const _Deque_iterator<_Tp, _RefR, _PtrR>& __y) _GLIBCXX_NOEXCEPT{return typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type(_Deque_iterator<_Tp, _RefL, _PtrL>::_S_buffer_size())* (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first)+ (__y._M_last - __y._M_cur);}template<typename _Tp, typename _Ref, typename _Ptr>inline _Deque_iterator<_Tp, _Ref, _Ptr>operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x)_GLIBCXX_NOEXCEPT{ return __x + __n; }template<typename _Tp>voidfill(const _Deque_iterator<_Tp, _Tp&, _Tp*>&,const _Deque_iterator<_Tp, _Tp&, _Tp*>&, const _Tp&);template<typename _Tp>_Deque_iterator<_Tp, _Tp&, _Tp*>copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,_Deque_iterator<_Tp, const _Tp&, const _Tp*>,_Deque_iterator<_Tp, _Tp&, _Tp*>);template<typename _Tp>inline _Deque_iterator<_Tp, _Tp&, _Tp*>copy(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,_Deque_iterator<_Tp, _Tp&, _Tp*> __last,_Deque_iterator<_Tp, _Tp&, _Tp*> __result){ return std::copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last),__result); }template<typename _Tp>_Deque_iterator<_Tp, _Tp&, _Tp*>copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,_Deque_iterator<_Tp, const _Tp&, const _Tp*>,_Deque_iterator<_Tp, _Tp&, _Tp*>);template<typename _Tp>inline _Deque_iterator<_Tp, _Tp&, _Tp*>copy_backward(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,_Deque_iterator<_Tp, _Tp&, _Tp*> __last,_Deque_iterator<_Tp, _Tp&, _Tp*> __result){ return std::copy_backward(_Deque_iterator<_Tp,const _Tp&, const _Tp*>(__first),_Deque_iterator<_Tp,const _Tp&, const _Tp*>(__last),__result); }#if __cplusplus >= 201103Ltemplate<typename _Tp>_Deque_iterator<_Tp, _Tp&, _Tp*>move(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,_Deque_iterator<_Tp, const _Tp&, const _Tp*>,_Deque_iterator<_Tp, _Tp&, _Tp*>);template<typename _Tp>inline _Deque_iterator<_Tp, _Tp&, _Tp*>move(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,_Deque_iterator<_Tp, _Tp&, _Tp*> __last,_Deque_iterator<_Tp, _Tp&, _Tp*> __result){ return std::move(_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__first),_Deque_iterator<_Tp, const _Tp&, const _Tp*>(__last),__result); }template<typename _Tp>_Deque_iterator<_Tp, _Tp&, _Tp*>move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,_Deque_iterator<_Tp, const _Tp&, const _Tp*>,_Deque_iterator<_Tp, _Tp&, _Tp*>);template<typename _Tp>inline _Deque_iterator<_Tp, _Tp&, _Tp*>move_backward(_Deque_iterator<_Tp, _Tp&, _Tp*> __first,_Deque_iterator<_Tp, _Tp&, _Tp*> __last,_Deque_iterator<_Tp, _Tp&, _Tp*> __result){ return std::move_backward(_Deque_iterator<_Tp,const _Tp&, const _Tp*>(__first),_Deque_iterator<_Tp,const _Tp&, const _Tp*>(__last),__result); }
#endif/***  Deque base class.  This class provides the unified face for %deque's*  allocation.  This class's constructor and destructor allocate and*  deallocate (but do not initialize) storage.  This makes %exception*  safety easier.**  Nothing in this class ever constructs or destroys an actual Tp element.*  (Deque handles that itself.)  Only/All memory management is performed*  here.*/template<typename _Tp, typename _Alloc>class _Deque_base{protected:typedef typename __gnu_cxx::__alloc_traits<_Alloc>::templaterebind<_Tp>::other _Tp_alloc_type;typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type>	 _Alloc_traits;#if __cplusplus < 201103Ltypedef _Tp*					_Ptr;typedef const _Tp*				_Ptr_const;
#elsetypedef typename _Alloc_traits::pointer		_Ptr;typedef typename _Alloc_traits::const_pointer	_Ptr_const;
#endiftypedef typename _Alloc_traits::template rebind<_Ptr>::other_Map_alloc_type;typedef __gnu_cxx::__alloc_traits<_Map_alloc_type> _Map_alloc_traits;public:typedef _Alloc		  allocator_type;typedef typename _Alloc_traits::size_type size_type;allocator_typeget_allocator() const _GLIBCXX_NOEXCEPT{ return allocator_type(_M_get_Tp_allocator()); }typedef _Deque_iterator<_Tp, _Tp&, _Ptr>	  iterator;typedef _Deque_iterator<_Tp, const _Tp&, _Ptr_const>   const_iterator;_Deque_base(): _M_impl(){ _M_initialize_map(0); }_Deque_base(size_t __num_elements): _M_impl(){ _M_initialize_map(__num_elements); }_Deque_base(const allocator_type& __a, size_t __num_elements): _M_impl(__a){ _M_initialize_map(__num_elements); }_Deque_base(const allocator_type& __a): _M_impl(__a){ /* Caller must initialize map. */ }#if __cplusplus >= 201103L_Deque_base(_Deque_base&& __x, false_type): _M_impl(__x._M_move_impl()){ }_Deque_base(_Deque_base&& __x, true_type): _M_impl(std::move(__x._M_get_Tp_allocator())){_M_initialize_map(0);if (__x._M_impl._M_map)this->_M_impl._M_swap_data(__x._M_impl);}_Deque_base(_Deque_base&& __x): _Deque_base(std::move(__x), typename _Alloc_traits::is_always_equal{}){ }_Deque_base(_Deque_base&& __x, const allocator_type& __a, size_type __n): _M_impl(__a){if (__x.get_allocator() == __a){if (__x._M_impl._M_map){_M_initialize_map(0);this->_M_impl._M_swap_data(__x._M_impl);}}else{_M_initialize_map(__n);}}
#endif~_Deque_base() _GLIBCXX_NOEXCEPT;protected:typedef typename iterator::_Map_pointer _Map_pointer;//This struct encapsulates the implementation of the std::deque//standard container and at the same time makes use of the EBO//for empty allocators.struct _Deque_impl: public _Tp_alloc_type{_Map_pointer _M_map;size_t _M_map_size;iterator _M_start;iterator _M_finish;_Deque_impl(): _Tp_alloc_type(), _M_map(), _M_map_size(0),_M_start(), _M_finish(){ }_Deque_impl(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT: _Tp_alloc_type(__a), _M_map(), _M_map_size(0),_M_start(), _M_finish(){ }#if __cplusplus >= 201103L_Deque_impl(_Deque_impl&&) = default;_Deque_impl(_Tp_alloc_type&& __a) noexcept: _Tp_alloc_type(std::move(__a)), _M_map(), _M_map_size(0),_M_start(), _M_finish(){ }
#endifvoid _M_swap_data(_Deque_impl& __x) _GLIBCXX_NOEXCEPT{using std::swap;swap(this->_M_start, __x._M_start);swap(this->_M_finish, __x._M_finish);swap(this->_M_map, __x._M_map);swap(this->_M_map_size, __x._M_map_size);}};_Tp_alloc_type&_M_get_Tp_allocator() _GLIBCXX_NOEXCEPT{ return *static_cast<_Tp_alloc_type*>(&this->_M_impl); }const _Tp_alloc_type&_M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT{ return *static_cast<const _Tp_alloc_type*>(&this->_M_impl); }_Map_alloc_type_M_get_map_allocator() const _GLIBCXX_NOEXCEPT{ return _Map_alloc_type(_M_get_Tp_allocator()); }_Ptr_M_allocate_node(){typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Traits;return _Traits::allocate(_M_impl, __deque_buf_size(sizeof(_Tp)));}void_M_deallocate_node(_Ptr __p) _GLIBCXX_NOEXCEPT{typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Traits;_Traits::deallocate(_M_impl, __p, __deque_buf_size(sizeof(_Tp)));}_Map_pointer_M_allocate_map(size_t __n){_Map_alloc_type __map_alloc = _M_get_map_allocator();return _Map_alloc_traits::allocate(__map_alloc, __n);}void_M_deallocate_map(_Map_pointer __p, size_t __n) _GLIBCXX_NOEXCEPT{_Map_alloc_type __map_alloc = _M_get_map_allocator();_Map_alloc_traits::deallocate(__map_alloc, __p, __n);}protected:void _M_initialize_map(size_t);void _M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish);void _M_destroy_nodes(_Map_pointer __nstart,_Map_pointer __nfinish) _GLIBCXX_NOEXCEPT;enum { _S_initial_map_size = 8 };_Deque_impl _M_impl;#if __cplusplus >= 201103Lprivate:_Deque_impl_M_move_impl(){if (!_M_impl._M_map)return std::move(_M_impl);// Create a copy of the current allocator._Tp_alloc_type __alloc{_M_get_Tp_allocator()};// Put that copy in a moved-from state._Tp_alloc_type __sink __attribute((__unused__)) {std::move(__alloc)};// Create an empty map that allocates using the moved-from allocator._Deque_base __empty{__alloc};__empty._M_initialize_map(0);// Now safe to modify current allocator and perform non-throwing swaps._Deque_impl __ret{std::move(_M_get_Tp_allocator())};_M_impl._M_swap_data(__ret);_M_impl._M_swap_data(__empty._M_impl);return __ret;}
#endif};template<typename _Tp, typename _Alloc>_Deque_base<_Tp, _Alloc>::~_Deque_base() _GLIBCXX_NOEXCEPT{if (this->_M_impl._M_map){_M_destroy_nodes(this->_M_impl._M_start._M_node,this->_M_impl._M_finish._M_node + 1);_M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);}}/***  @brief Layout storage.*  @param  __num_elements  The count of T's for which to allocate space*                          at first.*  @return   Nothing.**  The initial underlying memory layout is a bit complicated...*/template<typename _Tp, typename _Alloc>void_Deque_base<_Tp, _Alloc>::_M_initialize_map(size_t __num_elements){const size_t __num_nodes = (__num_elements/ __deque_buf_size(sizeof(_Tp))+ 1);this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size,size_t(__num_nodes + 2));this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);// For "small" maps (needing less than _M_map_size nodes), allocation// starts in the middle elements and grows outwards.  So nstart may be// the beginning of _M_map, but for small maps it may be as far in as// _M_map+3._Map_pointer __nstart = (this->_M_impl._M_map+ (this->_M_impl._M_map_size - __num_nodes) / 2);_Map_pointer __nfinish = __nstart + __num_nodes;__try{ _M_create_nodes(__nstart, __nfinish); }__catch(...){_M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);this->_M_impl._M_map = _Map_pointer();this->_M_impl._M_map_size = 0;__throw_exception_again;}this->_M_impl._M_start._M_set_node(__nstart);this->_M_impl._M_finish._M_set_node(__nfinish - 1);this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first+ __num_elements% __deque_buf_size(sizeof(_Tp)));}template<typename _Tp, typename _Alloc>void_Deque_base<_Tp, _Alloc>::_M_create_nodes(_Map_pointer __nstart, _Map_pointer __nfinish){_Map_pointer __cur;__try{for (__cur = __nstart; __cur < __nfinish; ++__cur)*__cur = this->_M_allocate_node();}__catch(...){_M_destroy_nodes(__nstart, __cur);__throw_exception_again;}}template<typename _Tp, typename _Alloc>void_Deque_base<_Tp, _Alloc>::_M_destroy_nodes(_Map_pointer __nstart,_Map_pointer __nfinish) _GLIBCXX_NOEXCEPT{for (_Map_pointer __n = __nstart; __n < __nfinish; ++__n)_M_deallocate_node(*__n);}/***  @brief  A standard container using fixed-size memory allocation and*  constant-time manipulation of elements at either end.**  @ingroup sequences**  @tparam _Tp  Type of element.*  @tparam _Alloc  Allocator type, defaults to allocator<_Tp>.**  Meets the requirements of a <a href="tables.html#65">container</a>, a*  <a href="tables.html#66">reversible container</a>, and a*  <a href="tables.html#67">sequence</a>, including the*  <a href="tables.html#68">optional sequence requirements</a>.**  In previous HP/SGI versions of deque, there was an extra template*  parameter so users could control the node size.  This extension turned*  out to violate the C++ standard (it can be detected using template*  template parameters), and it was removed.**  Here's how a deque<Tp> manages memory.  Each deque has 4 members:**  - Tp**        _M_map*  - size_t      _M_map_size*  - iterator    _M_start, _M_finish**  map_size is at least 8.  %map is an array of map_size*  pointers-to-@a nodes.  (The name %map has nothing to do with the*  std::map class, and @b nodes should not be confused with*  std::list's usage of @a node.)**  A @a node has no specific type name as such, but it is referred*  to as @a node in this file.  It is a simple array-of-Tp.  If Tp*  is very large, there will be one Tp element per node (i.e., an*  @a array of one).  For non-huge Tp's, node size is inversely*  related to Tp size: the larger the Tp, the fewer Tp's will fit*  in a node.  The goal here is to keep the total size of a node*  relatively small and constant over different Tp's, to improve*  allocator efficiency.**  Not every pointer in the %map array will point to a node.  If*  the initial number of elements in the deque is small, the*  /middle/ %map pointers will be valid, and the ones at the edges*  will be unused.  This same situation will arise as the %map*  grows: available %map pointers, if any, will be on the ends.  As*  new nodes are created, only a subset of the %map's pointers need*  to be copied @a outward.**  Class invariants:* - For any nonsingular iterator i:*    - i.node points to a member of the %map array.  (Yes, you read that*      correctly:  i.node does not actually point to a node.)  The member of*      the %map array is what actually points to the node.*    - i.first == *(i.node)    (This points to the node (first Tp element).)*    - i.last  == i.first + node_size*    - i.cur is a pointer in the range [i.first, i.last).  NOTE:*      the implication of this is that i.cur is always a dereferenceable*      pointer, even if i is a past-the-end iterator.* - Start and Finish are always nonsingular iterators.  NOTE: this* means that an empty deque must have one node, a deque with <N* elements (where N is the node buffer size) must have one node, a* deque with N through (2N-1) elements must have two nodes, etc.* - For every node other than start.node and finish.node, every* element in the node is an initialized object.  If start.node ==* finish.node, then [start.cur, finish.cur) are initialized* objects, and the elements outside that range are uninitialized* storage.  Otherwise, [start.cur, start.last) and [finish.first,* finish.cur) are initialized objects, and [start.first, start.cur)* and [finish.cur, finish.last) are uninitialized storage.* - [%map, %map + map_size) is a valid, non-empty range.* - [start.node, finish.node] is a valid range contained within*   [%map, %map + map_size).* - A pointer in the range [%map, %map + map_size) points to an allocated*   node if and only if the pointer is in the range*   [start.node, finish.node].**  Here's the magic:  nothing in deque is @b aware of the discontiguous*  storage!**  The memory setup and layout occurs in the parent, _Base, and the iterator*  class is entirely responsible for @a leaping from one node to the next.*  All the implementation routines for deque itself work only through the*  start and finish iterators.  This keeps the routines simple and sane,*  and we can use other standard algorithms as well.*/template<typename _Tp, typename _Alloc = std::allocator<_Tp> >class deque : protected _Deque_base<_Tp, _Alloc>{
#ifdef _GLIBCXX_CONCEPT_CHECKS// concept requirementstypedef typename _Alloc::value_type	_Alloc_value_type;
# if __cplusplus < 201103L__glibcxx_class_requires(_Tp, _SGIAssignableConcept)
# endif__glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
#endif#if __cplusplus >= 201103Lstatic_assert(is_same<typename remove_cv<_Tp>::type, _Tp>::value,"std::deque must have a non-const, non-volatile value_type");
# ifdef __STRICT_ANSI__static_assert(is_same<typename _Alloc::value_type, _Tp>::value,"std::deque must have the same value_type as its allocator");
# endif
#endiftypedef _Deque_base<_Tp, _Alloc>			_Base;typedef typename _Base::_Tp_alloc_type		_Tp_alloc_type;typedef typename _Base::_Alloc_traits		_Alloc_traits;typedef typename _Base::_Map_pointer		_Map_pointer;public:typedef _Tp					value_type;typedef typename _Alloc_traits::pointer		pointer;typedef typename _Alloc_traits::const_pointer	const_pointer;typedef typename _Alloc_traits::reference		reference;typedef typename _Alloc_traits::const_reference	const_reference;typedef typename _Base::iterator			iterator;typedef typename _Base::const_iterator		const_iterator;typedef std::reverse_iterator<const_iterator>	const_reverse_iterator;typedef std::reverse_iterator<iterator>		reverse_iterator;typedef size_t					size_type;typedef ptrdiff_t					difference_type;typedef _Alloc					allocator_type;protected:static size_t _S_buffer_size() _GLIBCXX_NOEXCEPT{ return __deque_buf_size(sizeof(_Tp)); }// Functions controlling memory layout, and nothing else.using _Base::_M_initialize_map;using _Base::_M_create_nodes;using _Base::_M_destroy_nodes;using _Base::_M_allocate_node;using _Base::_M_deallocate_node;using _Base::_M_allocate_map;using _Base::_M_deallocate_map;using _Base::_M_get_Tp_allocator;/***  A total of four data members accumulated down the hierarchy.*  May be accessed via _M_impl.**/using _Base::_M_impl;public:// [23.2.1.1] construct/copy/destroy// (assign() and get_allocator() are also listed in this section)/***  @brief  Creates a %deque with no elements.*/deque() : _Base() { }/***  @brief  Creates a %deque with no elements.*  @param  __a  An allocator object.*/explicitdeque(const allocator_type& __a): _Base(__a, 0) { }#if __cplusplus >= 201103L/***  @brief  Creates a %deque with default constructed elements.*  @param  __n  The number of elements to initially create.*  @param  __a  An allocator.**  This constructor fills the %deque with @a n default*  constructed elements.*/explicitdeque(size_type __n, const allocator_type& __a = allocator_type()): _Base(__a, __n){ _M_default_initialize(); }/***  @brief  Creates a %deque with copies of an exemplar element.*  @param  __n  The number of elements to initially create.*  @param  __value  An element to copy.*  @param  __a  An allocator.**  This constructor fills the %deque with @a __n copies of @a __value.*/deque(size_type __n, const value_type& __value,const allocator_type& __a = allocator_type()): _Base(__a, __n){ _M_fill_initialize(__value); }
#else/***  @brief  Creates a %deque with copies of an exemplar element.*  @param  __n  The number of elements to initially create.*  @param  __value  An element to copy.*  @param  __a  An allocator.**  This constructor fills the %deque with @a __n copies of @a __value.*/explicitdeque(size_type __n, const value_type& __value = value_type(),const allocator_type& __a = allocator_type()): _Base(__a, __n){ _M_fill_initialize(__value); }
#endif/***  @brief  %Deque copy constructor.*  @param  __x  A %deque of identical element and allocator types.**  The newly-created %deque uses a copy of the allocator object used*  by @a __x (unless the allocator traits dictate a different object).*/deque(const deque& __x): _Base(_Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator()),__x.size()){ std::__uninitialized_copy_a(__x.begin(), __x.end(),this->_M_impl._M_start,_M_get_Tp_allocator()); }#if __cplusplus >= 201103L/***  @brief  %Deque move constructor.*  @param  __x  A %deque of identical element and allocator types.**  The newly-created %deque contains the exact contents of @a __x.*  The contents of @a __x are a valid, but unspecified %deque.*/deque(deque&& __x): _Base(std::move(__x)) { }/// Copy constructor with alternative allocatordeque(const deque& __x, const allocator_type& __a): _Base(__a, __x.size()){ std::__uninitialized_copy_a(__x.begin(), __x.end(),this->_M_impl._M_start,_M_get_Tp_allocator()); }/// Move constructor with alternative allocatordeque(deque&& __x, const allocator_type& __a): _Base(std::move(__x), __a, __x.size()){if (__x.get_allocator() != __a){std::__uninitialized_move_a(__x.begin(), __x.end(),this->_M_impl._M_start,_M_get_Tp_allocator());__x.clear();}}/***  @brief  Builds a %deque from an initializer list.*  @param  __l  An initializer_list.*  @param  __a  An allocator object.**  Create a %deque consisting of copies of the elements in the*  initializer_list @a __l.**  This will call the element type's copy constructor N times*  (where N is __l.size()) and do no memory reallocation.*/deque(initializer_list<value_type> __l,const allocator_type& __a = allocator_type()): _Base(__a){_M_range_initialize(__l.begin(), __l.end(),random_access_iterator_tag());}
#endif/***  @brief  Builds a %deque from a range.*  @param  __first  An input iterator.*  @param  __last  An input iterator.*  @param  __a  An allocator object.**  Create a %deque consisting of copies of the elements from [__first,*  __last).**  If the iterators are forward, bidirectional, or random-access, then*  this will call the elements' copy constructor N times (where N is*  distance(__first,__last)) and do no memory reallocation.  But if only*  input iterators are used, then this will do at most 2N calls to the*  copy constructor, and logN memory reallocations.*/
#if __cplusplus >= 201103Ltemplate<typename _InputIterator,typename = std::_RequireInputIter<_InputIterator>>deque(_InputIterator __first, _InputIterator __last,const allocator_type& __a = allocator_type()): _Base(__a){ _M_initialize_dispatch(__first, __last, __false_type()); }
#elsetemplate<typename _InputIterator>deque(_InputIterator __first, _InputIterator __last,const allocator_type& __a = allocator_type()): _Base(__a){// Check whether it's an integral type.  If so, it's not an iterator.typedef typename std::__is_integer<_InputIterator>::__type _Integral;_M_initialize_dispatch(__first, __last, _Integral());}
#endif/***  The dtor only erases the elements, and note that if the elements*  themselves are pointers, the pointed-to memory is not touched in any*  way.  Managing the pointer is the user's responsibility.*/~deque(){ _M_destroy_data(begin(), end(), _M_get_Tp_allocator()); }/***  @brief  %Deque assignment operator.*  @param  __x  A %deque of identical element and allocator types.**  All the elements of @a x are copied.**  The newly-created %deque uses a copy of the allocator object used*  by @a __x (unless the allocator traits dictate a different object).*/deque&operator=(const deque& __x);#if __cplusplus >= 201103L/***  @brief  %Deque move assignment operator.*  @param  __x  A %deque of identical element and allocator types.**  The contents of @a __x are moved into this deque (without copying,*  if the allocators permit it).*  @a __x is a valid, but unspecified %deque.*/deque&operator=(deque&& __x) noexcept(_Alloc_traits::_S_always_equal()){using __always_equal = typename _Alloc_traits::is_always_equal;_M_move_assign1(std::move(__x), __always_equal{});return *this;}/***  @brief  Assigns an initializer list to a %deque.*  @param  __l  An initializer_list.**  This function fills a %deque with copies of the elements in the*  initializer_list @a __l.**  Note that the assignment completely changes the %deque and that the*  resulting %deque's size is the same as the number of elements*  assigned.*/deque&operator=(initializer_list<value_type> __l){_M_assign_aux(__l.begin(), __l.end(),random_access_iterator_tag());return *this;}
#endif/***  @brief  Assigns a given value to a %deque.*  @param  __n  Number of elements to be assigned.*  @param  __val  Value to be assigned.**  This function fills a %deque with @a n copies of the given*  value.  Note that the assignment completely changes the*  %deque and that the resulting %deque's size is the same as*  the number of elements assigned.*/voidassign(size_type __n, const value_type& __val){ _M_fill_assign(__n, __val); }/***  @brief  Assigns a range to a %deque.*  @param  __first  An input iterator.*  @param  __last   An input iterator.**  This function fills a %deque with copies of the elements in the*  range [__first,__last).**  Note that the assignment completely changes the %deque and that the*  resulting %deque's size is the same as the number of elements*  assigned.*/
#if __cplusplus >= 201103Ltemplate<typename _InputIterator,typename = std::_RequireInputIter<_InputIterator>>voidassign(_InputIterator __first, _InputIterator __last){ _M_assign_dispatch(__first, __last, __false_type()); }
#elsetemplate<typename _InputIterator>voidassign(_InputIterator __first, _InputIterator __last){typedef typename std::__is_integer<_InputIterator>::__type _Integral;_M_assign_dispatch(__first, __last, _Integral());}
#endif#if __cplusplus >= 201103L/***  @brief  Assigns an initializer list to a %deque.*  @param  __l  An initializer_list.**  This function fills a %deque with copies of the elements in the*  initializer_list @a __l.**  Note that the assignment completely changes the %deque and that the*  resulting %deque's size is the same as the number of elements*  assigned.*/voidassign(initializer_list<value_type> __l){ _M_assign_aux(__l.begin(), __l.end(), random_access_iterator_tag()); }
#endif/// Get a copy of the memory allocation object.allocator_typeget_allocator() const _GLIBCXX_NOEXCEPT{ return _Base::get_allocator(); }// iterators/***  Returns a read/write iterator that points to the first element in the*  %deque.  Iteration is done in ordinary element order.*/iteratorbegin() _GLIBCXX_NOEXCEPT{ return this->_M_impl._M_start; }/***  Returns a read-only (constant) iterator that points to the first*  element in the %deque.  Iteration is done in ordinary element order.*/const_iteratorbegin() const _GLIBCXX_NOEXCEPT{ return this->_M_impl._M_start; }/***  Returns a read/write iterator that points one past the last*  element in the %deque.  Iteration is done in ordinary*  element order.*/iteratorend() _GLIBCXX_NOEXCEPT{ return this->_M_impl._M_finish; }/***  Returns a read-only (constant) iterator that points one past*  the last element in the %deque.  Iteration is done in*  ordinary element order.*/const_iteratorend() const _GLIBCXX_NOEXCEPT{ return this->_M_impl._M_finish; }/***  Returns a read/write reverse iterator that points to the*  last element in the %deque.  Iteration is done in reverse*  element order.*/reverse_iteratorrbegin() _GLIBCXX_NOEXCEPT{ return reverse_iterator(this->_M_impl._M_finish); }/***  Returns a read-only (constant) reverse iterator that points*  to the last element in the %deque.  Iteration is done in*  reverse element order.*/const_reverse_iteratorrbegin() const _GLIBCXX_NOEXCEPT{ return const_reverse_iterator(this->_M_impl._M_finish); }/***  Returns a read/write reverse iterator that points to one*  before the first element in the %deque.  Iteration is done*  in reverse element order.*/reverse_iteratorrend() _GLIBCXX_NOEXCEPT{ return reverse_iterator(this->_M_impl._M_start); }/***  Returns a read-only (constant) reverse iterator that points*  to one before the first element in the %deque.  Iteration is*  done in reverse element order.*/const_reverse_iteratorrend() const _GLIBCXX_NOEXCEPT{ return const_reverse_iterator(this->_M_impl._M_start); }#if __cplusplus >= 201103L/***  Returns a read-only (constant) iterator that points to the first*  element in the %deque.  Iteration is done in ordinary element order.*/const_iteratorcbegin() const noexcept{ return this->_M_impl._M_start; }/***  Returns a read-only (constant) iterator that points one past*  the last element in the %deque.  Iteration is done in*  ordinary element order.*/const_iteratorcend() const noexcept{ return this->_M_impl._M_finish; }/***  Returns a read-only (constant) reverse iterator that points*  to the last element in the %deque.  Iteration is done in*  reverse element order.*/const_reverse_iteratorcrbegin() const noexcept{ return const_reverse_iterator(this->_M_impl._M_finish); }/***  Returns a read-only (constant) reverse iterator that points*  to one before the first element in the %deque.  Iteration is*  done in reverse element order.*/const_reverse_iteratorcrend() const noexcept{ return const_reverse_iterator(this->_M_impl._M_start); }
#endif// [23.2.1.2] capacity/**  Returns the number of elements in the %deque.  */size_typesize() const _GLIBCXX_NOEXCEPT{ return this->_M_impl._M_finish - this->_M_impl._M_start; }/**  Returns the size() of the largest possible %deque.  */size_typemax_size() const _GLIBCXX_NOEXCEPT{ return _Alloc_traits::max_size(_M_get_Tp_allocator()); }#if __cplusplus >= 201103L/***  @brief  Resizes the %deque to the specified number of elements.*  @param  __new_size  Number of elements the %deque should contain.**  This function will %resize the %deque to the specified*  number of elements.  If the number is smaller than the*  %deque's current size the %deque is truncated, otherwise*  default constructed elements are appended.*/voidresize(size_type __new_size){const size_type __len = size();if (__new_size > __len)_M_default_append(__new_size - __len);else if (__new_size < __len)_M_erase_at_end(this->_M_impl._M_start+ difference_type(__new_size));}/***  @brief  Resizes the %deque to the specified number of elements.*  @param  __new_size  Number of elements the %deque should contain.*  @param  __x  Data with which new elements should be populated.**  This function will %resize the %deque to the specified*  number of elements.  If the number is smaller than the*  %deque's current size the %deque is truncated, otherwise the*  %deque is extended and new elements are populated with given*  data.*/voidresize(size_type __new_size, const value_type& __x){const size_type __len = size();if (__new_size > __len)_M_fill_insert(this->_M_impl._M_finish, __new_size - __len, __x);else if (__new_size < __len)_M_erase_at_end(this->_M_impl._M_start+ difference_type(__new_size));}
#else/***  @brief  Resizes the %deque to the specified number of elements.*  @param  __new_size  Number of elements the %deque should contain.*  @param  __x  Data with which new elements should be populated.**  This function will %resize the %deque to the specified*  number of elements.  If the number is smaller than the*  %deque's current size the %deque is truncated, otherwise the*  %deque is extended and new elements are populated with given*  data.*/voidresize(size_type __new_size, value_type __x = value_type()){const size_type __len = size();if (__new_size > __len)_M_fill_insert(this->_M_impl._M_finish, __new_size - __len, __x);else if (__new_size < __len)_M_erase_at_end(this->_M_impl._M_start+ difference_type(__new_size));}
#endif#if __cplusplus >= 201103L/**  A non-binding request to reduce memory use.  */voidshrink_to_fit() noexcept{ _M_shrink_to_fit(); }
#endif/***  Returns true if the %deque is empty.  (Thus begin() would*  equal end().)*/boolempty() const _GLIBCXX_NOEXCEPT{ return this->_M_impl._M_finish == this->_M_impl._M_start; }// element access/***  @brief Subscript access to the data contained in the %deque.*  @param __n The index of the element for which data should be*  accessed.*  @return  Read/write reference to data.**  This operator allows for easy, array-style, data access.*  Note that data access with this operator is unchecked and*  out_of_range lookups are not defined. (For checked lookups*  see at().)*/referenceoperator[](size_type __n) _GLIBCXX_NOEXCEPT{__glibcxx_requires_subscript(__n);return this->_M_impl._M_start[difference_type(__n)];}/***  @brief Subscript access to the data contained in the %deque.*  @param __n The index of the element for which data should be*  accessed.*  @return  Read-only (constant) reference to data.**  This operator allows for easy, array-style, data access.*  Note that data access with this operator is unchecked and*  out_of_range lookups are not defined. (For checked lookups*  see at().)*/const_referenceoperator[](size_type __n) const _GLIBCXX_NOEXCEPT{__glibcxx_requires_subscript(__n);return this->_M_impl._M_start[difference_type(__n)];}protected:/// Safety check used only from at().void_M_range_check(size_type __n) const{if (__n >= this->size())__throw_out_of_range_fmt(__N("deque::_M_range_check: __n ""(which is %zu)>= this->size() ""(which is %zu)"),__n, this->size());}public:/***  @brief  Provides access to the data contained in the %deque.*  @param __n The index of the element for which data should be*  accessed.*  @return  Read/write reference to data.*  @throw  std::out_of_range  If @a __n is an invalid index.**  This function provides for safer data access.  The parameter*  is first checked that it is in the range of the deque.  The*  function throws out_of_range if the check fails.*/referenceat(size_type __n){_M_range_check(__n);return (*this)[__n];}/***  @brief  Provides access to the data contained in the %deque.*  @param __n The index of the element for which data should be*  accessed.*  @return  Read-only (constant) reference to data.*  @throw  std::out_of_range  If @a __n is an invalid index.**  This function provides for safer data access.  The parameter is first*  checked that it is in the range of the deque.  The function throws*  out_of_range if the check fails.*/const_referenceat(size_type __n) const{_M_range_check(__n);return (*this)[__n];}/***  Returns a read/write reference to the data at the first*  element of the %deque.*/referencefront() _GLIBCXX_NOEXCEPT{__glibcxx_requires_nonempty();return *begin();}/***  Returns a read-only (constant) reference to the data at the first*  element of the %deque.*/const_referencefront() const _GLIBCXX_NOEXCEPT{__glibcxx_requires_nonempty();return *begin();}/***  Returns a read/write reference to the data at the last element of the*  %deque.*/referenceback() _GLIBCXX_NOEXCEPT{__glibcxx_requires_nonempty();iterator __tmp = end();--__tmp;return *__tmp;}/***  Returns a read-only (constant) reference to the data at the last*  element of the %deque.*/const_referenceback() const _GLIBCXX_NOEXCEPT{__glibcxx_requires_nonempty();const_iterator __tmp = end();--__tmp;return *__tmp;}// [23.2.1.2] modifiers/***  @brief  Add data to the front of the %deque.*  @param  __x  Data to be added.**  This is a typical stack operation.  The function creates an*  element at the front of the %deque and assigns the given*  data to it.  Due to the nature of a %deque this operation*  can be done in constant time.*/voidpush_front(const value_type& __x){if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first){_Alloc_traits::construct(this->_M_impl,this->_M_impl._M_start._M_cur - 1,__x);--this->_M_impl._M_start._M_cur;}else_M_push_front_aux(__x);}#if __cplusplus >= 201103Lvoidpush_front(value_type&& __x){ emplace_front(std::move(__x)); }template<typename... _Args>
#if __cplusplus > 201402Lreference
#elsevoid
#endifemplace_front(_Args&&... __args);
#endif/***  @brief  Add data to the end of the %deque.*  @param  __x  Data to be added.**  This is a typical stack operation.  The function creates an*  element at the end of the %deque and assigns the given data*  to it.  Due to the nature of a %deque this operation can be*  done in constant time.*/voidpush_back(const value_type& __x){if (this->_M_impl._M_finish._M_cur!= this->_M_impl._M_finish._M_last - 1){_Alloc_traits::construct(this->_M_impl,this->_M_impl._M_finish._M_cur, __x);++this->_M_impl._M_finish._M_cur;}else_M_push_back_aux(__x);}#if __cplusplus >= 201103Lvoidpush_back(value_type&& __x){ emplace_back(std::move(__x)); }template<typename... _Args>
#if __cplusplus > 201402Lreference
#elsevoid
#endifemplace_back(_Args&&... __args);
#endif/***  @brief  Removes first element.**  This is a typical stack operation.  It shrinks the %deque by one.**  Note that no data is returned, and if the first element's data is*  needed, it should be retrieved before pop_front() is called.*/voidpop_front() _GLIBCXX_NOEXCEPT{__glibcxx_requires_nonempty();if (this->_M_impl._M_start._M_cur!= this->_M_impl._M_start._M_last - 1){_Alloc_traits::destroy(this->_M_impl,this->_M_impl._M_start._M_cur);++this->_M_impl._M_start._M_cur;}else_M_pop_front_aux();}/***  @brief  Removes last element.**  This is a typical stack operation.  It shrinks the %deque by one.**  Note that no data is returned, and if the last element's data is*  needed, it should be retrieved before pop_back() is called.*/voidpop_back() _GLIBCXX_NOEXCEPT{__glibcxx_requires_nonempty();if (this->_M_impl._M_finish._M_cur!= this->_M_impl._M_finish._M_first){--this->_M_impl._M_finish._M_cur;_Alloc_traits::destroy(this->_M_impl,this->_M_impl._M_finish._M_cur);}else_M_pop_back_aux();}#if __cplusplus >= 201103L/***  @brief  Inserts an object in %deque before specified iterator.*  @param  __position  A const_iterator into the %deque.*  @param  __args  Arguments.*  @return  An iterator that points to the inserted data.**  This function will insert an object of type T constructed*  with T(std::forward<Args>(args)...) before the specified location.*/template<typename... _Args>iteratoremplace(const_iterator __position, _Args&&... __args);/***  @brief  Inserts given value into %deque before specified iterator.*  @param  __position  A const_iterator into the %deque.*  @param  __x  Data to be inserted.*  @return  An iterator that points to the inserted data.**  This function will insert a copy of the given value before the*  specified location.*/iteratorinsert(const_iterator __position, const value_type& __x);
#else/***  @brief  Inserts given value into %deque before specified iterator.*  @param  __position  An iterator into the %deque.*  @param  __x  Data to be inserted.*  @return  An iterator that points to the inserted data.**  This function will insert a copy of the given value before the*  specified location.*/iteratorinsert(iterator __position, const value_type& __x);
#endif#if __cplusplus >= 201103L/***  @brief  Inserts given rvalue into %deque before specified iterator.*  @param  __position  A const_iterator into the %deque.*  @param  __x  Data to be inserted.*  @return  An iterator that points to the inserted data.**  This function will insert a copy of the given rvalue before the*  specified location.*/iteratorinsert(const_iterator __position, value_type&& __x){ return emplace(__position, std::move(__x)); }/***  @brief  Inserts an initializer list into the %deque.*  @param  __p  An iterator into the %deque.*  @param  __l  An initializer_list.**  This function will insert copies of the data in the*  initializer_list @a __l into the %deque before the location*  specified by @a __p.  This is known as <em>list insert</em>.*/iteratorinsert(const_iterator __p, initializer_list<value_type> __l){auto __offset = __p - cbegin();_M_range_insert_aux(__p._M_const_cast(), __l.begin(), __l.end(),std::random_access_iterator_tag());return begin() + __offset;}
#endif#if __cplusplus >= 201103L/***  @brief  Inserts a number of copies of given data into the %deque.*  @param  __position  A const_iterator into the %deque.*  @param  __n  Number of elements to be inserted.*  @param  __x  Data to be inserted.*  @return  An iterator that points to the inserted data.**  This function will insert a specified number of copies of the given*  data before the location specified by @a __position.*/iteratorinsert(const_iterator __position, size_type __n, const value_type& __x){difference_type __offset = __position - cbegin();_M_fill_insert(__position._M_const_cast(), __n, __x);return begin() + __offset;}
#else/***  @brief  Inserts a number of copies of given data into the %deque.*  @param  __position  An iterator into the %deque.*  @param  __n  Number of elements to be inserted.*  @param  __x  Data to be inserted.**  This function will insert a specified number of copies of the given*  data before the location specified by @a __position.*/voidinsert(iterator __position, size_type __n, const value_type& __x){ _M_fill_insert(__position, __n, __x); }
#endif#if __cplusplus >= 201103L/***  @brief  Inserts a range into the %deque.*  @param  __position  A const_iterator into the %deque.*  @param  __first  An input iterator.*  @param  __last   An input iterator.*  @return  An iterator that points to the inserted data.**  This function will insert copies of the data in the range*  [__first,__last) into the %deque before the location specified*  by @a __position.  This is known as <em>range insert</em>.*/template<typename _InputIterator,typename = std::_RequireInputIter<_InputIterator>>iteratorinsert(const_iterator __position, _InputIterator __first,_InputIterator __last){difference_type __offset = __position - cbegin();_M_insert_dispatch(__position._M_const_cast(),__first, __last, __false_type());return begin() + __offset;}
#else/***  @brief  Inserts a range into the %deque.*  @param  __position  An iterator into the %deque.*  @param  __first  An input iterator.*  @param  __last   An input iterator.**  This function will insert copies of the data in the range*  [__first,__last) into the %deque before the location specified*  by @a __position.  This is known as <em>range insert</em>.*/template<typename _InputIterator>voidinsert(iterator __position, _InputIterator __first,_InputIterator __last){// Check whether it's an integral type.  If so, it's not an iterator.typedef typename std::__is_integer<_InputIterator>::__type _Integral;_M_insert_dispatch(__position, __first, __last, _Integral());}
#endif/***  @brief  Remove element at given position.*  @param  __position  Iterator pointing to element to be erased.*  @return  An iterator pointing to the next element (or end()).**  This function will erase the element at the given position and thus*  shorten the %deque by one.**  The user is cautioned that*  this function only erases the element, and that if the element is*  itself a pointer, the pointed-to memory is not touched in any way.*  Managing the pointer is the user's responsibility.*/iterator
#if __cplusplus >= 201103Lerase(const_iterator __position)
#elseerase(iterator __position)
#endif{ return _M_erase(__position._M_const_cast()); }/***  @brief  Remove a range of elements.*  @param  __first  Iterator pointing to the first element to be erased.*  @param  __last  Iterator pointing to one past the last element to be*                erased.*  @return  An iterator pointing to the element pointed to by @a last*           prior to erasing (or end()).**  This function will erase the elements in the range*  [__first,__last) and shorten the %deque accordingly.**  The user is cautioned that*  this function only erases the elements, and that if the elements*  themselves are pointers, the pointed-to memory is not touched in any*  way.  Managing the pointer is the user's responsibility.*/iterator
#if __cplusplus >= 201103Lerase(const_iterator __first, const_iterator __last)
#elseerase(iterator __first, iterator __last)
#endif{ return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }/***  @brief  Swaps data with another %deque.*  @param  __x  A %deque of the same element and allocator types.**  This exchanges the elements between two deques in constant time.*  (Four pointers, so it should be quite fast.)*  Note that the global std::swap() function is specialized such that*  std::swap(d1,d2) will feed to this function.**  Whether the allocators are swapped depends on the allocator traits.*/voidswap(deque& __x) _GLIBCXX_NOEXCEPT{
#if __cplusplus >= 201103L__glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value|| _M_get_Tp_allocator() == __x._M_get_Tp_allocator());
#endif_M_impl._M_swap_data(__x._M_impl);_Alloc_traits::_S_on_swap(_M_get_Tp_allocator(),__x._M_get_Tp_allocator());}/***  Erases all the elements.  Note that this function only erases the*  elements, and that if the elements themselves are pointers, the*  pointed-to memory is not touched in any way.  Managing the pointer is*  the user's responsibility.*/voidclear() _GLIBCXX_NOEXCEPT{ _M_erase_at_end(begin()); }protected:// Internal constructor functions follow.// called by the range constructor to implement [23.1.1]/9// _GLIBCXX_RESOLVE_LIB_DEFECTS// 438. Ambiguity in the "do the right thing" clausetemplate<typename _Integer>void_M_initialize_dispatch(_Integer __n, _Integer __x, __true_type){_M_initialize_map(static_cast<size_type>(__n));_M_fill_initialize(__x);}// called by the range constructor to implement [23.1.1]/9template<typename _InputIterator>void_M_initialize_dispatch(_InputIterator __first, _InputIterator __last,__false_type){_M_range_initialize(__first, __last,std::__iterator_category(__first));}// called by the second initialize_dispatch above//@{/***  @brief Fills the deque with whatever is in [first,last).*  @param  __first  An input iterator.*  @param  __last  An input iterator.*  @return   Nothing.**  If the iterators are actually forward iterators (or better), then the*  memory layout can be done all at once.  Else we move forward using*  push_back on each value from the iterator.*/template<typename _InputIterator>void_M_range_initialize(_InputIterator __first, _InputIterator __last,std::input_iterator_tag);// called by the second initialize_dispatch abovetemplate<typename _ForwardIterator>void_M_range_initialize(_ForwardIterator __first, _ForwardIterator __last,std::forward_iterator_tag);//@}/***  @brief Fills the %deque with copies of value.*  @param  __value  Initial value.*  @return   Nothing.*  @pre _M_start and _M_finish have already been initialized,*  but none of the %deque's elements have yet been constructed.**  This function is called only when the user provides an explicit size*  (with or without an explicit exemplar value).*/void_M_fill_initialize(const value_type& __value);#if __cplusplus >= 201103L// called by deque(n).void_M_default_initialize();
#endif// Internal assign functions follow.  The *_aux functions do the actual// assignment work for the range versions.// called by the range assign to implement [23.1.1]/9// _GLIBCXX_RESOLVE_LIB_DEFECTS// 438. Ambiguity in the "do the right thing" clausetemplate<typename _Integer>void_M_assign_dispatch(_Integer __n, _Integer __val, __true_type){ _M_fill_assign(__n, __val); }// called by the range assign to implement [23.1.1]/9template<typename _InputIterator>void_M_assign_dispatch(_InputIterator __first, _InputIterator __last,__false_type){ _M_assign_aux(__first, __last, std::__iterator_category(__first)); }// called by the second assign_dispatch abovetemplate<typename _InputIterator>void_M_assign_aux(_InputIterator __first, _InputIterator __last,std::input_iterator_tag);// called by the second assign_dispatch abovetemplate<typename _ForwardIterator>void_M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,std::forward_iterator_tag){const size_type __len = std::distance(__first, __last);if (__len > size()){_ForwardIterator __mid = __first;std::advance(__mid, size());std::copy(__first, __mid, begin());_M_range_insert_aux(end(), __mid, __last,std::__iterator_category(__first));}else_M_erase_at_end(std::copy(__first, __last, begin()));}// Called by assign(n,t), and the range assign when it turns out// to be the same thing.void_M_fill_assign(size_type __n, const value_type& __val){if (__n > size()){std::fill(begin(), end(), __val);_M_fill_insert(end(), __n - size(), __val);}else{_M_erase_at_end(begin() + difference_type(__n));std::fill(begin(), end(), __val);}}//@{/// Helper functions for push_* and pop_*.
#if __cplusplus < 201103Lvoid _M_push_back_aux(const value_type&);void _M_push_front_aux(const value_type&);
#elsetemplate<typename... _Args>void _M_push_back_aux(_Args&&... __args);template<typename... _Args>void _M_push_front_aux(_Args&&... __args);
#endifvoid _M_pop_back_aux();void _M_pop_front_aux();//@}// Internal insert functions follow.  The *_aux functions do the actual// insertion work when all shortcuts fail.// called by the range insert to implement [23.1.1]/9// _GLIBCXX_RESOLVE_LIB_DEFECTS// 438. Ambiguity in the "do the right thing" clausetemplate<typename _Integer>void_M_insert_dispatch(iterator __pos,_Integer __n, _Integer __x, __true_type){ _M_fill_insert(__pos, __n, __x); }// called by the range insert to implement [23.1.1]/9template<typename _InputIterator>void_M_insert_dispatch(iterator __pos,_InputIterator __first, _InputIterator __last,__false_type){_M_range_insert_aux(__pos, __first, __last,std::__iterator_category(__first));}// called by the second insert_dispatch abovetemplate<typename _InputIterator>void_M_range_insert_aux(iterator __pos, _InputIterator __first,_InputIterator __last, std::input_iterator_tag);// called by the second insert_dispatch abovetemplate<typename _ForwardIterator>void_M_range_insert_aux(iterator __pos, _ForwardIterator __first,_ForwardIterator __last, std::forward_iterator_tag);// Called by insert(p,n,x), and the range insert when it turns out to be// the same thing.  Can use fill functions in optimal situations,// otherwise passes off to insert_aux(p,n,x).void_M_fill_insert(iterator __pos, size_type __n, const value_type& __x);// called by insert(p,x)
#if __cplusplus < 201103Literator_M_insert_aux(iterator __pos, const value_type& __x);
#elsetemplate<typename... _Args>iterator_M_insert_aux(iterator __pos, _Args&&... __args);
#endif// called by insert(p,n,x) via fill_insertvoid_M_insert_aux(iterator __pos, size_type __n, const value_type& __x);// called by range_insert_aux for forward iteratorstemplate<typename _ForwardIterator>void_M_insert_aux(iterator __pos,_ForwardIterator __first, _ForwardIterator __last,size_type __n);// Internal erase functions follow.void_M_destroy_data_aux(iterator __first, iterator __last);// Called by ~deque().// NB: Doesn't deallocate the nodes.template<typename _Alloc1>void_M_destroy_data(iterator __first, iterator __last, const _Alloc1&){ _M_destroy_data_aux(__first, __last); }void_M_destroy_data(iterator __first, iterator __last,const std::allocator<_Tp>&){if (!__has_trivial_destructor(value_type))_M_destroy_data_aux(__first, __last);}// Called by erase(q1, q2).void_M_erase_at_begin(iterator __pos){_M_destroy_data(begin(), __pos, _M_get_Tp_allocator());_M_destroy_nodes(this->_M_impl._M_start._M_node, __pos._M_node);this->_M_impl._M_start = __pos;}// Called by erase(q1, q2), resize(), clear(), _M_assign_aux,// _M_fill_assign, operator=.void_M_erase_at_end(iterator __pos){_M_destroy_data(__pos, end(), _M_get_Tp_allocator());_M_destroy_nodes(__pos._M_node + 1,this->_M_impl._M_finish._M_node + 1);this->_M_impl._M_finish = __pos;}iterator_M_erase(iterator __pos);iterator_M_erase(iterator __first, iterator __last);#if __cplusplus >= 201103L// Called by resize(sz).void_M_default_append(size_type __n);bool_M_shrink_to_fit();
#endif//@{/// Memory-handling helpers for the previous internal insert functions.iterator_M_reserve_elements_at_front(size_type __n){const size_type __vacancies = this->_M_impl._M_start._M_cur- this->_M_impl._M_start._M_first;if (__n > __vacancies)_M_new_elements_at_front(__n - __vacancies);return this->_M_impl._M_start - difference_type(__n);}iterator_M_reserve_elements_at_back(size_type __n){const size_type __vacancies = (this->_M_impl._M_finish._M_last- this->_M_impl._M_finish._M_cur) - 1;if (__n > __vacancies)_M_new_elements_at_back(__n - __vacancies);return this->_M_impl._M_finish + difference_type(__n);}void_M_new_elements_at_front(size_type __new_elements);void_M_new_elements_at_back(size_type __new_elements);//@}//@{/***  @brief Memory-handling helpers for the major %map.**  Makes sure the _M_map has space for new nodes.  Does not*  actually add the nodes.  Can invalidate _M_map pointers.*  (And consequently, %deque iterators.)*/void_M_reserve_map_at_back(size_type __nodes_to_add = 1){if (__nodes_to_add + 1 > this->_M_impl._M_map_size- (this->_M_impl._M_finish._M_node - this->_M_impl._M_map))_M_reallocate_map(__nodes_to_add, false);}void_M_reserve_map_at_front(size_type __nodes_to_add = 1){if (__nodes_to_add > size_type(this->_M_impl._M_start._M_node- this->_M_impl._M_map))_M_reallocate_map(__nodes_to_add, true);}void_M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);//@}#if __cplusplus >= 201103L// Constant-time, nothrow move assignment when source object's memory// can be moved because the allocators are equal.void_M_move_assign1(deque&& __x, /* always equal: */ true_type) noexcept{this->_M_impl._M_swap_data(__x._M_impl);__x.clear();std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator());}// When the allocators are not equal the operation could throw, because// we might need to allocate a new map for __x after moving from it// or we might need to allocate new elements for *this.void_M_move_assign1(deque&& __x, /* always equal: */ false_type){constexpr bool __move_storage =_Alloc_traits::_S_propagate_on_move_assign();_M_move_assign2(std::move(__x), __bool_constant<__move_storage>());}// Destroy all elements and deallocate all memory, then replace// with elements created from __args.template<typename... _Args>void_M_replace_map(_Args&&... __args){// Create new data first, so if allocation fails there are no effects.deque __newobj(std::forward<_Args>(__args)...);// Free existing storage using existing allocator.clear();_M_deallocate_node(*begin()._M_node); // one node left after clear()_M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);this->_M_impl._M_map = nullptr;this->_M_impl._M_map_size = 0;// Take ownership of replacement memory.this->_M_impl._M_swap_data(__newobj._M_impl);}// Do move assignment when the allocator propagates.void_M_move_assign2(deque&& __x, /* propagate: */ true_type){// Make a copy of the original allocator state.auto __alloc = __x._M_get_Tp_allocator();// The allocator propagates so storage can be moved from __x,// leaving __x in a valid empty state with a moved-from allocator._M_replace_map(std::move(__x));// Move the corresponding allocator state too._M_get_Tp_allocator() = std::move(__alloc);}// Do move assignment when it may not be possible to move source// object's memory, resulting in a linear-time operation.void_M_move_assign2(deque&& __x, /* propagate: */ false_type){if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator()){// The allocators are equal so storage can be moved from __x,// leaving __x in a valid empty state with its current allocator._M_replace_map(std::move(__x), __x.get_allocator());}else{// The rvalue's allocator cannot be moved and is not equal,// so we need to individually move each element._M_assign_aux(std::__make_move_if_noexcept_iterator(__x.begin()),std::__make_move_if_noexcept_iterator(__x.end()),std::random_access_iterator_tag());__x.clear();}}
#endif};#if __cpp_deduction_guides >= 201606template<typename _InputIterator, typename _ValT= typename iterator_traits<_InputIterator>::value_type,typename _Allocator = allocator<_ValT>,typename = _RequireInputIter<_InputIterator>,typename = _RequireAllocator<_Allocator>>deque(_InputIterator, _InputIterator, _Allocator = _Allocator())-> deque<_ValT, _Allocator>;
#endif/***  @brief  Deque equality comparison.*  @param  __x  A %deque.*  @param  __y  A %deque of the same type as @a __x.*  @return  True iff the size and elements of the deques are equal.**  This is an equivalence relation.  It is linear in the size of the*  deques.  Deques are considered equivalent if their sizes are equal,*  and if corresponding elements compare equal.*/template<typename _Tp, typename _Alloc>inline booloperator==(const deque<_Tp, _Alloc>& __x,const deque<_Tp, _Alloc>& __y){ return __x.size() == __y.size()&& std::equal(__x.begin(), __x.end(), __y.begin()); }/***  @brief  Deque ordering relation.*  @param  __x  A %deque.*  @param  __y  A %deque of the same type as @a __x.*  @return  True iff @a x is lexicographically less than @a __y.**  This is a total ordering relation.  It is linear in the size of the*  deques.  The elements must be comparable with @c <.**  See std::lexicographical_compare() for how the determination is made.*/template<typename _Tp, typename _Alloc>inline booloperator<(const deque<_Tp, _Alloc>& __x,const deque<_Tp, _Alloc>& __y){ return std::lexicographical_compare(__x.begin(), __x.end(),__y.begin(), __y.end()); }/// Based on operator==template<typename _Tp, typename _Alloc>inline booloperator!=(const deque<_Tp, _Alloc>& __x,const deque<_Tp, _Alloc>& __y){ return !(__x == __y); }/// Based on operator<template<typename _Tp, typename _Alloc>inline booloperator>(const deque<_Tp, _Alloc>& __x,const deque<_Tp, _Alloc>& __y){ return __y < __x; }/// Based on operator<template<typename _Tp, typename _Alloc>inline booloperator<=(const deque<_Tp, _Alloc>& __x,const deque<_Tp, _Alloc>& __y){ return !(__y < __x); }/// Based on operator<template<typename _Tp, typename _Alloc>inline booloperator>=(const deque<_Tp, _Alloc>& __x,const deque<_Tp, _Alloc>& __y){ return !(__x < __y); }/// See std::deque::swap().template<typename _Tp, typename _Alloc>inline voidswap(deque<_Tp,_Alloc>& __x, deque<_Tp,_Alloc>& __y)_GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y))){ __x.swap(__y); }#undef _GLIBCXX_DEQUE_BUF_SIZE_GLIBCXX_END_NAMESPACE_CONTAINER
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std#endif /* _STL_DEQUE_H */