什么是STL中的deque？
我看着STL容器，试图弄清楚它们到底是什么(即使用的数据结构)，这让我停住了脚步:我一开始以为它是一个双向链表，它允许在固定时间内从两端插入和删除，但我被操作符[]的the promise made在固定时间内完成而困扰。在链表中，任意访问应该是O(n)，对吗？
如果它是一个动态数组，它怎么能在固定时间内add elements呢？值得一提的是，可能会发生重新分配，O(1)是摊销成本，like for a vector。
所以我想知道这个结构是什么，允许在固定的时间内任意访问，同时永远不需要移动到一个新的更大的地方。
回答 8
Stack Overflow用户
发布于 2011-06-09 20:00:22
deque在某种程度上是递归定义的:在内部，它维护一个固定大小的块的双端队列。每个组块都是一个向量，组块的队列(下图中的“map”)本身也是一个向量。
在CodeProject上有很好的性能特征分析，以及它与vector的比较。
GCC标准库实现在内部使用T**来表示地图。每个数据块都是一个T*，它被分配了一些固定大小的__deque_buf_size (取决于sizeof(T))。
Stack Overflow用户
发布于 2018-06-21 11:07:51
从概述中，您可以将deque看作一个double-ended queue
deque中的数据由固定大小的向量块存储，这些向量块是
由map(也是向量块，但其大小可能会改变)指向
deque iterator的主要部分代码如下：
/*
buff_size is the length of the chunk
*/
template <class T, size_t buff_size>
struct __deque_iterator{
typedef __deque_iterator<T, buff_size> iterator;
typedef T** map_pointer;
// pointer to the chunk
T* cur;
T* first; // the begin of the chunk
T* last; // the end of the chunk
//because the pointer may skip to other chunk
//so this pointer to the map
map_pointer node; // pointer to the map
}deque的主要部分代码如下：
/*
buff_size is the length of the chunk
*/
template<typename T, size_t buff_size = 0>
class deque{
public:
typedef T value_type;
typedef T& reference;
typedef T* pointer;
typedef __deque_iterator<T, buff_size> iterator;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
protected:
typedef pointer* map_pointer;
// allocate memory for the chunk
typedef allocator<value_type> dataAllocator;
// allocate memory for map
typedef allocator<pointer> mapAllocator;
private:
//data members
iterator start;
iterator finish;
map_pointer map;
size_type map_size;
}下面我将给出deque的核心代码，主要分为三个部分：
用于构建deque的
- iterator
- How
1.迭代程序(__deque_iterator)
迭代器的主要问题是，当++，-- iterator时，它可能会跳到其他块(如果它指向块的边缘)。例如，有三个数据块：chunk 1、chunk 2和chunk 3。
pointer1指向chunk 2的开头，当运算符--pointer时，它将指针指向chunk 1的末尾，从而指向pointer2。
下面我将给出__deque_iterator的主要功能
首先，跳到任意块：
void set_node(map_pointer new_node){
node = new_node;
first = *new_node;
last = first + chunk_size();
}注意，计算块大小的chunk_size()函数，您可以认为它在这里返回8表示简化。
operator*获取区块中的数据
reference operator*()const{
return *cur;
}operator++, --
//前缀形式的增量
self& operator++(){
++cur;
if (cur == last){ //if it reach the end of the chunk
set_node(node + 1);//skip to the next chunk
cur = first;
}
return *this;
}
// postfix forms of increment
self operator++(int){
self tmp = *this;
++*this;//invoke prefix ++
return tmp;
}
self& operator--(){
if(cur == first){ // if it pointer to the begin of the chunk
set_node(node - 1);//skip to the prev chunk
cur = last;
}
--cur;
return *this;
}
self operator--(int){
self tmp = *this;
--*this;
return tmp;
}迭代器跳过n步/随机访问
self& operator+=(difference_type n){ // n can be postive or negative
difference_type offset = n + (cur - first);
if(offset >=0 && offset < difference_type(buffer_size())){
// in the same chunk
cur += n;
}else{//not in the same chunk
difference_type node_offset;
if (offset > 0){
node_offset = offset / difference_type(chunk_size());
}else{
node_offset = -((-offset - 1) / difference_type(chunk_size())) - 1 ;
}
// skip to the new chunk
set_node(node + node_offset);
// set new cur
cur = first + (offset - node_offset * chunk_size());
}
return *this;
}
// skip n steps
self operator+(difference_type n)const{
self tmp = *this;
return tmp+= n; //reuse operator +=
}
self& operator-=(difference_type n){
return *this += -n; //reuse operator +=
}
self operator-(difference_type n)const{
self tmp = *this;
return tmp -= n; //reuse operator +=
}
// random access (iterator can skip n steps)
// invoke operator + ,operator *
reference operator[](difference_type n)const{
return *(*this + n);
}2.如何构建deque
deque的常用功能
iterator begin(){return start;}
iterator end(){return finish;}
reference front(){
//invoke __deque_iterator operator*
// return start's member *cur
return *start;
}
reference back(){
// cna't use *finish
iterator tmp = finish;
--tmp;
return *tmp; //return finish's *cur
}
reference operator[](size_type n){
//random access, use __deque_iterator operator[]
return start[n];
}
template<typename T, size_t buff_size>
deque<T, buff_size>::deque(size_t n, const value_type& value){
fill_initialize(n, value);
}
template<typename T, size_t buff_size>
void deque<T, buff_size>::fill_initialize(size_t n, const value_type& value){
// allocate memory for map and chunk
// initialize pointer
create_map_and_nodes(n);
// initialize value for the chunks
for (map_pointer cur = start.node; cur < finish.node; ++cur) {
initialized_fill_n(*cur, chunk_size(), value);
}
// the end chunk may have space node, which don't need have initialize value
initialized_fill_n(finish.first, finish.cur - finish.first, value);
}
template<typename T, size_t buff_size>
void deque<T, buff_size>::create_map_and_nodes(size_t num_elements){
// the needed map node = (elements nums / chunk length) + 1
size_type num_nodes = num_elements / chunk_size() + 1;
// map node num。min num is 8 ，max num is "needed size + 2"
map_size = std::max(8, num_nodes + 2);
// allocate map array
map = mapAllocator::allocate(map_size);
// tmp_start，tmp_finish poniters to the center range of map
map_pointer tmp_start = map + (map_size - num_nodes) / 2;
map_pointer tmp_finish = tmp_start + num_nodes - 1;
// allocate memory for the chunk pointered by map node
for (map_pointer cur = tmp_start; cur <= tmp_finish; ++cur) {
*cur = dataAllocator::allocate(chunk_size());
}
// set start and end iterator
start.set_node(tmp_start);
start.cur = start.first;
finish.set_node(tmp_finish);
finish.cur = finish.first + num_elements % chunk_size();
}让我们假设i_deque有20个int元素0~19，它的块大小是8，现在push_back 3个元素(0，1，2)到i_deque
i_deque.push_back(0);
i_deque.push_back(1);
i_deque.push_back(2);它的内部结构如下：
然后再次分配新块，它将调用push_back：
push_back(3)
如果我们使用push_front，它将在前一个start之前分配新的区块
注意当push_back元素进入deque时，如果所有的地图和区块都填满了，就会导致分配新的地图，并调整chunks.But上面的代码可能足以让你理解deque。
Stack Overflow用户
发布于 2014-06-30 13:23:56
把它想象成一个向量的向量。只是它们不是标准的std::vector。
外部向量包含指向内部向量的指针。当它的容量通过重新分配而改变时，而不是像std::vector那样将所有的空空间分配到结尾处，它在向量的开始和结尾处将空空间拆分成相等的部分。这允许这个向量上的push_front和push_back都在O(1)时间内发生。
内部向量的行为需要根据它是在deque的前面还是后面而改变。在后面，它可以表现为一个标准的std::vector，它在结束时增长，而push_back发生在O(1)时间内。在前端，它需要做相反的事情，在开始时随着每个push_front而增长。在实践中，这很容易实现，通过添加一个指针到前面的元素和增长方向以及大小。通过这个简单的修改，push_front也可以是O(1)时间。
对任何元素的访问都需要偏移和除以O(1)中出现的适当的外部向量索引，并索引到也是O(1)的内部向量。这假设内部向量都是固定大小的，除了位于deque开头或结尾的向量。
https://stackoverflow.com/questions/6292332
复制相似问题
腾讯云开发者
