昌平网站开发,公司建网站需要多少钱,网站开发和设计,嘉定企业网站开发建设deque的结构类似于哈希表#xff0c;使用一个指针数组存储固定大小的数组首地址#xff0c;当数据分布不均匀时将指针数组内的数据进行偏移#xff0c;桶不够用的时候会像vector一样扩容然后将之前数组中存储的指针拷贝过来#xff0c;从原理可以看出deque的性能是非常高的… deque的结构类似于哈希表使用一个指针数组存储固定大小的数组首地址当数据分布不均匀时将指针数组内的数据进行偏移桶不够用的时候会像vector一样扩容然后将之前数组中存储的指针拷贝过来从原理可以看出deque的性能是非常高的它不存咋像vector那样大规模的数据拷贝和大批量连续空间的需求同时也弥补了像list不支持随机访问的缺点可以说deque集中了list和vector的大部分优点当然缺点很致命在中间节点插入数据的时候会异常复杂高效的前后端插入机制使得stack和queue都适配于deque。 vector动态数组
支持随机访问可以自动扩容只支持末端插入
list双向链表
不支持随机访问支持任意位置插入无需扩容
deque双端队列vector Array
支持随机访问伪随机微量扩容支持前后端插入
看下面一段代码
#includeiostream
#includedeque
using namespace std;
struct T{~T(){coutT析构;}}
void Add_head(dequeintq){q.push_front(1);coutq.front() endl;
}void Add_tail(dequeintq){q.push_back(1);coutq.back() endl;
}int main(){dequeintq;for(int i0;i10;i) Add_head(q);for(int i0;i10;i) Add_tail(q);
}从地址大概可以看出这个东西是一块一块的块的大小是固定的而且块内地址是连续的想要获取更多的信息的话还要结合源码网上有说deque是数组链表的但如果简单的理解为链表的话就大错特错了这么理解的话随机访问是实现不了的我觉得理解为一种特殊的二维数组比较好。
下面看具体一些功能的实现
看下_Deque_val模板_Block_size 表示单个数组元素个数这里是根据元素的大小决定单个数组的大小_Mapptr 是桶里面装一维数组的指针_Mapsize桶的大小根据注释可以看到桶的扩容是指数级的_Myoff存储偏移量_Mysize存储元素个数 注意这个偏移量是针对_Mapptr 的头部开始到当前元素的偏移量此外单个数组的大小受限于数据大小所以很多时候双端队列会表现的像维护在指针数组上的链表
// CLASS TEMPLATE _Deque_val
template class _Val_types
class _Deque_val : public _Container_base12 {
public:using value_type typename _Val_types::value_type;using size_type typename _Val_types::size_type;using difference_type typename _Val_types::difference_type;using pointer typename _Val_types::pointer;using const_pointer typename _Val_types::const_pointer;using reference value_type;using const_reference const value_type;using _Mapptr typename _Val_types::_Mapptr;
private:static constexpr size_t _Bytes sizeof(value_type);
public:static constexpr int _Block_size _Bytes 1 ? 16 : _Bytes 2 ? 8 : _Bytes 4 ? 4 : _Bytes 8 ? 2 : 1; // elements per block (a power of 2)_Deque_val() noexcept : _Map(), _Mapsize(0), _Myoff(0), _Mysize(0) {}size_type _Getblock(size_type _Off) const noexcept {// NB: _Mapsize and _Block_size are guaranteed to be powers of 2return (_Off / _Block_size) (_Mapsize - 1);}_Mapptr _Map; // pointer to array of pointers to blockssize_type _Mapsize; // size of map array, zero or 2^Nsize_type _Myoff; // offset of initial elementsize_type _Mysize; // current length of sequence
};这个是_Mapptr 这个桶的基类可以看到使用的是二级指针它的作用就是维护一种二维的结构这时候可能好奇了它作为一个单独的模板是如何适配作为_Deque_val 模板类型的一部分的。
template class _Ty
struct _Deque_simple_types : _Simple_types_Ty {using _Mapptr _Ty**;
};这个适配器完成了适配工作将多个类适配为一个类很大程度上提高了代码的可读性使得代码可以更高的遵循开闭原则。
template bool _Test, class _Ty1, class _Ty2
struct conditional { // Choose _Ty1 if _Test is true, and _Ty2 otherwiseusing type _Ty1;
};
template class _Ty1, class _Ty2
struct conditionalfalse, _Ty1, _Ty2 {using type _Ty2;
};
template bool _Test, class _Ty1, class _Ty2
using conditional_t typename conditional_Test, _Ty1, _Ty2::type;deque中迭代器访问元素使用偏移量获取存储的行和列。
_NODISCARD reference operator*() const noexcept {const auto _Mycont static_castconst _Mydeque*(this-_Getcont());
#if _ITERATOR_DEBUG_LEVEL ! 0_STL_VERIFY(_Mycont, cannot dereference value-initialized deque iterator);_STL_VERIFY(_Mycont-_Myoff this-_Myoff this-_Myoff _Mycont-_Myoff _Mycont-_Mysize,cannot deference out of range deque iterator);
#endif // _ITERATOR_DEBUG_LEVEL ! 0_Size_type _Block _Mycont-_Getblock(_Myoff);_Size_type _Off _Myoff % _Block_size;return _Mycont-_Map[_Block][_Off];}那么现在就有一个问题如果插入元素时集中在头部或者尾部时它会直接扩容吗带着问题接着分析。
首先看一下emplace_back函数
template class... _Tysvoid _Emplace_back_internal(_Tys... _Vals) {if ((_Myoff() _Mysize()) % _Block_size 0 _Mapsize() (_Mysize() _Block_size) / _Block_size) {_Growmap(1);}_Myoff() _Mapsize() * _Block_size - 1;size_type _Newoff _Myoff() _Mysize();size_type _Block _Getblock(_Newoff);if (_Map()[_Block] nullptr) {_Map()[_Block] _Getal().allocate(_Block_size);}_Alty_traits::construct(_Getal(), _Unfancy(_Map()[_Block] _Newoff % _Block_size), _STD forward_Tys(_Vals)...);_Mysize();}可以看到整体逻辑和vector差不多emplace_front也差不多就不看了因为站在函数角度它的不需要关注是头插还是尾插。 这里的策略依旧是可以插入时插入不能插入时进行处理直接看扩容处理函数和直接注释的一样如果没有可插入的空间时桶的大小变为原来的二倍然后将指针挪到新的数组的中间即可偏移量这些重新计算这个环节虽然看起来很麻烦但是注意这里是针对指针的而不是针对元素的所以说效率还是蛮高的。
void _Growmap(size_type _Count) { // grow map by at least _Count pointers, _Mapsize() a power of 2static_assert(1 _Minimum_map_size, The _Xlen() test should always be performed.);_Alpty _Almap(_Getal());size_type _Newsize 0 _Mapsize() ? _Mapsize() : 1;while (_Newsize - _Mapsize() _Count || _Newsize _Minimum_map_size) {// scale _Newsize to 2^N _Mapsize() _Countif (max_size() / _Block_size - _Newsize _Newsize) {_Xlen(); // result too long}_Newsize * 2;}_Count _Newsize - _Mapsize();size_type _Myboff _Myoff() / _Block_size;_Mapptr _Newmap _Almap.allocate(_Mapsize() _Count);_Mapptr _Myptr _Newmap _Myboff;_Myptr _STD uninitialized_copy(_Map() _Myboff, _Map() _Mapsize(), _Myptr); // copy initial to endif (_Myboff _Count) { // increment greater than offset of initial block_Myptr _STD uninitialized_copy(_Map(), _Map() _Myboff, _Myptr); // copy rest of old_Uninitialized_value_construct_n_unchecked1(_Myptr, _Count - _Myboff); // clear suffix of new_Uninitialized_value_construct_n_unchecked1(_Newmap, _Myboff); // clear prefix of new} else { // increment not greater than offset of initial block_STD uninitialized_copy(_Map(), _Map() _Count, _Myptr); // copy more old_Myptr _STD uninitialized_copy(_Map() _Count, _Map() _Myboff, _Newmap); // copy rest of old_Uninitialized_value_construct_n_unchecked1(_Myptr, _Count); // clear rest to initial block}_Destroy_range(_Map() _Myboff, _Map() _Mapsize());if (_Map() ! _Mapptr()) {_Almap.deallocate(_Map(), _Mapsize()); // free storage for old}_Map() _Newmap; // point at new_Mapsize() _Count;}stack和queue其实都是deque的适配器类下面举个例子
templateclass T,class dqdequeT
class stk{
protected:dq d;
public:void pop(){d.pop_back();}void push(const T val){d.push_back(val);}const T top()const{return d.back();}
};
