外贸平台自建站,青岛开发区网站建设,怎么做网络游戏,非经营备案网站能贴放广告么文章目录 stack的使用queue的使用适配器queue的模拟实现stack的模拟实现deque stack的使用
stack是一种容器适配器#xff0c;具有后进先出#xff0c;只能从容器的一端进行元素的插入与提取操作
#include iostream
#include vector
#include stack具有后进先出只能从容器的一端进行元素的插入与提取操作
#include iostream
#include vector
#include stack
using namespace std;int main()
{stackint, vectorint 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()
{queueint, listint 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
{templateclass T ,class Container dequeT 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(){queueint, listint 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
{templateclass T , class Container dequeT 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(){stackint st1;st1.push(1);st1.push(2);st1.push(3);st1.push(4);while (!st1.empty()){cout st1.top() ;st1.pop();}cout endl;stackint ,listint 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和listdeque的应用并不多而目前能看到的一个应用就是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.hnamespace 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.*/templatetypename _Tp, typename _Ref, typename _Ptrstruct _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:templatetypename _Upusing __ptr_to typename pointer_traits_Ptr::template rebind_Up;templatetypename _CvTpusing __iter _Deque_iterator_Tp, _CvTp, __ptr_to_CvTp;public:typedef __iter_Tp iterator;typedef __iterconst _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; }_Selfoperator() _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;}_Selfoperator--() _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;}_Selfoperator(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;}_Selfoperator-(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)templatetypename _Tp, typename _Ref, typename _Ptrinline booloperator(const _Deque_iterator_Tp, _Ref, _Ptr __x,const _Deque_iterator_Tp, _Ref, _Ptr __y) _GLIBCXX_NOEXCEPT{ return __x._M_cur __y._M_cur; }templatetypename _Tp, typename _RefL, typename _PtrL,typename _RefR, typename _PtrRinline booloperator(const _Deque_iterator_Tp, _RefL, _PtrL __x,const _Deque_iterator_Tp, _RefR, _PtrR __y) _GLIBCXX_NOEXCEPT{ return __x._M_cur __y._M_cur; }templatetypename _Tp, typename _Ref, typename _Ptrinline booloperator!(const _Deque_iterator_Tp, _Ref, _Ptr __x,const _Deque_iterator_Tp, _Ref, _Ptr __y) _GLIBCXX_NOEXCEPT{ return !(__x __y); }templatetypename _Tp, typename _RefL, typename _PtrL,typename _RefR, typename _PtrRinline booloperator!(const _Deque_iterator_Tp, _RefL, _PtrL __x,const _Deque_iterator_Tp, _RefR, _PtrR __y) _GLIBCXX_NOEXCEPT{ return !(__x __y); }templatetypename _Tp, typename _Ref, typename _Ptrinline 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); }templatetypename _Tp, typename _RefL, typename _PtrL,typename _RefR, typename _PtrRinline 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); }templatetypename _Tp, typename _Ref, typename _Ptrinline booloperator(const _Deque_iterator_Tp, _Ref, _Ptr __x,const _Deque_iterator_Tp, _Ref, _Ptr __y) _GLIBCXX_NOEXCEPT{ return __y __x; }templatetypename _Tp, typename _RefL, typename _PtrL,typename _RefR, typename _PtrRinline booloperator(const _Deque_iterator_Tp, _RefL, _PtrL __x,const _Deque_iterator_Tp, _RefR, _PtrR __y) _GLIBCXX_NOEXCEPT{ return __y __x; }templatetypename _Tp, typename _Ref, typename _Ptrinline booloperator(const _Deque_iterator_Tp, _Ref, _Ptr __x,const _Deque_iterator_Tp, _Ref, _Ptr __y) _GLIBCXX_NOEXCEPT{ return !(__y __x); }templatetypename _Tp, typename _RefL, typename _PtrL,typename _RefR, typename _PtrRinline booloperator(const _Deque_iterator_Tp, _RefL, _PtrL __x,const _Deque_iterator_Tp, _RefR, _PtrR __y) _GLIBCXX_NOEXCEPT{ return !(__y __x); }templatetypename _Tp, typename _Ref, typename _Ptrinline booloperator(const _Deque_iterator_Tp, _Ref, _Ptr __x,const _Deque_iterator_Tp, _Ref, _Ptr __y) _GLIBCXX_NOEXCEPT{ return !(__x __y); }templatetypename _Tp, typename _RefL, typename _PtrL,typename _RefR, typename _PtrRinline 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.templatetypename _Tp, typename _Ref, typename _Ptrinline 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);}templatetypename _Tp, typename _RefL, typename _PtrL,typename _RefR, typename _PtrRinline 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);}templatetypename _Tp, typename _Ref, typename _Ptrinline _Deque_iterator_Tp, _Ref, _Ptroperator(ptrdiff_t __n, const _Deque_iterator_Tp, _Ref, _Ptr __x)_GLIBCXX_NOEXCEPT{ return __x __n; }templatetypename _Tpvoidfill(const _Deque_iterator_Tp, _Tp, _Tp*,const _Deque_iterator_Tp, _Tp, _Tp*, const _Tp);templatetypename _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*);templatetypename _Tpinline _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); }templatetypename _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*);templatetypename _Tpinline _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 201103Ltemplatetypename _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*);templatetypename _Tpinline _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); }templatetypename _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*);templatetypename _Tpinline _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 %deques* allocation. This classs 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.*/templatetypename _Tp, typename _Allocclass _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_castconst _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};templatetypename _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 Ts for which to allocate space* at first.* return Nothing.** The initial underlying memory layout is a bit complicated...*/templatetypename _Tp, typename _Allocvoid_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_map3._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)));}templatetypename _Tp, typename _Allocvoid_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;}}templatetypename _Tp, typename _Allocvoid_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 hreftables.html#65container/a, a* a hreftables.html#66reversible container/a, and a* a hreftables.html#67sequence/a, including the* a hreftables.html#68optional 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.** Heres how a dequeTp 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::lists 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 Tps, node size is inversely* related to Tp size: the larger the Tp, the fewer Tps will fit* in a node. The goal here is to keep the total size of a node* relatively small and constant over different Tps, 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 %maps 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].** Heres 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.*/templatetypename _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_sametypename remove_cv_Tp::type, _Tp::value,std::deque must have a non-const, non-volatile value_type);
# ifdef __STRICT_ANSI__static_assert(is_sametypename _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_iteratorconst_iterator const_reverse_iterator;typedef std::reverse_iteratoriterator 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 types copy constructor N times* (where N is __l.size()) and do no memory reallocation.*/deque(initializer_listvalue_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 201103Ltemplatetypename _InputIterator,typename std::_RequireInputIter_InputIteratordeque(_InputIterator __first, _InputIterator __last,const allocator_type __a allocator_type()): _Base(__a){ _M_initialize_dispatch(__first, __last, __false_type()); }
#elsetemplatetypename _InputIteratordeque(_InputIterator __first, _InputIterator __last,const allocator_type __a allocator_type()): _Base(__a){// Check whether its an integral type. If so, its 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 users 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).*/dequeoperator(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.*/dequeoperator(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 %deques size is the same as the number of elements* assigned.*/dequeoperator(initializer_listvalue_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 %deques 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 %deques size is the same as the number of elements* assigned.*/
#if __cplusplus 201103Ltemplatetypename _InputIterator,typename std::_RequireInputIter_InputIteratorvoidassign(_InputIterator __first, _InputIterator __last){ _M_assign_dispatch(__first, __last, __false_type()); }
#elsetemplatetypename _InputIteratorvoidassign(_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 %deques size is the same as the number of elements* assigned.*/voidassign(initializer_listvalue_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* %deques 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* %deques 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* %deques 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)); }templatetypename... _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)); }templatetypename... _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 elements 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 elements 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::forwardArgs(args)...) before the specified location.*/templatetypename... _Argsiteratoremplace(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 emlist insert/em.*/iteratorinsert(const_iterator __p, initializer_listvalue_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 emrange insert/em.*/templatetypename _InputIterator,typename std::_RequireInputIter_InputIteratoriteratorinsert(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 emrange insert/em.*/templatetypename _InputIteratorvoidinsert(iterator __position, _InputIterator __first,_InputIterator __last){// Check whether its an integral type. If so, its 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 users 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 users 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 users 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 clausetemplatetypename _Integervoid_M_initialize_dispatch(_Integer __n, _Integer __x, __true_type){_M_initialize_map(static_castsize_type(__n));_M_fill_initialize(__x);}// called by the range constructor to implement [23.1.1]/9templatetypename _InputIteratorvoid_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.*/templatetypename _InputIteratorvoid_M_range_initialize(_InputIterator __first, _InputIterator __last,std::input_iterator_tag);// called by the second initialize_dispatch abovetemplatetypename _ForwardIteratorvoid_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 %deques 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 clausetemplatetypename _Integervoid_M_assign_dispatch(_Integer __n, _Integer __val, __true_type){ _M_fill_assign(__n, __val); }// called by the range assign to implement [23.1.1]/9templatetypename _InputIteratorvoid_M_assign_dispatch(_InputIterator __first, _InputIterator __last,__false_type){ _M_assign_aux(__first, __last, std::__iterator_category(__first)); }// called by the second assign_dispatch abovetemplatetypename _InputIteratorvoid_M_assign_aux(_InputIterator __first, _InputIterator __last,std::input_iterator_tag);// called by the second assign_dispatch abovetemplatetypename _ForwardIteratorvoid_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);
#elsetemplatetypename... _Argsvoid _M_push_back_aux(_Args... __args);templatetypename... _Argsvoid _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 clausetemplatetypename _Integervoid_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]/9templatetypename _InputIteratorvoid_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 abovetemplatetypename _InputIteratorvoid_M_range_insert_aux(iterator __pos, _InputIterator __first,_InputIterator __last, std::input_iterator_tag);// called by the second insert_dispatch abovetemplatetypename _ForwardIteratorvoid_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);
#elsetemplatetypename... _Argsiterator_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 iteratorstemplatetypename _ForwardIteratorvoid_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: Doesnt deallocate the nodes.templatetypename _Alloc1void_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 objects 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.templatetypename... _Argsvoid_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// objects 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 rvalues 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 201606templatetypename _InputIterator, typename _ValT typename iterator_traits_InputIterator::value_type,typename _Allocator allocator_ValT,typename _RequireInputIter_InputIterator,typename _RequireAllocator_Allocatordeque(_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.*/templatetypename _Tp, typename _Allocinline 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.*/templatetypename _Tp, typename _Allocinline 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 operatortemplatetypename _Tp, typename _Allocinline booloperator!(const deque_Tp, _Alloc __x,const deque_Tp, _Alloc __y){ return !(__x __y); }/// Based on operatortemplatetypename _Tp, typename _Allocinline booloperator(const deque_Tp, _Alloc __x,const deque_Tp, _Alloc __y){ return __y __x; }/// Based on operatortemplatetypename _Tp, typename _Allocinline booloperator(const deque_Tp, _Alloc __x,const deque_Tp, _Alloc __y){ return !(__y __x); }/// Based on operatortemplatetypename _Tp, typename _Allocinline booloperator(const deque_Tp, _Alloc __x,const deque_Tp, _Alloc __y){ return !(__x __y); }/// See std::deque::swap().templatetypename _Tp, typename _Allocinline 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 */
如果你觉得这篇文章对你有帮助不妨动动手指给点赞收藏加转发给鄃鳕一个大大的关注你们的每一次支持都将转化为我前进的动力
