我看着STL容器,试图弄清楚它们到底是什么(即使用的数据结构),这让我停住了脚步:我一开始以为它是一个双向链表,它允许在固定时间内从两端插入和删除,但我被操作符[]的the promise made在固定时间内完成而困扰。在链表中,任意访问应该是O(n),对吗?
如果它是一个动态数组,它怎么能在固定时间内add elements呢?值得一提的是,可能会发生重新分配,O(1)是摊销成本,like for a vector。
所以我想知道这个结构是什么,允许在固定的时间内任意访问,同时永远不需要移动到一个新的更大的地方。
发布于 2011-06-09 20:00:22
deque在某种程度上是递归定义的:在内部,它维护一个固定大小的块的双端队列。每个组块都是一个向量,组块的队列(下图中的“map”)本身也是一个向量。
在CodeProject上有很好的性能特征分析,以及它与vector
的比较。
GCC标准库实现在内部使用T**
来表示地图。每个数据块都是一个T*
,它被分配了一些固定大小的__deque_buf_size
(取决于sizeof(T)
)。
发布于 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
的
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
。
发布于 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
复制相似问题