从头至尾实现deque
从头到尾实现deque
关于deque内部数据结构的说明：
deque是能够同时在收尾进行插入和删除的数据结构。其表现形式看起来和vector差不多，但是在处理队头插入时，其表现的时间复杂度要远远地优越于vector。这个得益于deque的内部数据结构地实现。deque使用分段的连续空间组成。为了管理这个分段的连续空间，所以必须要有一个中控器来记录各个分段空间的首地址，然后需要一个长度来记录该中控器的大小。为了表现和vector相似，所以需要包含2个迭代器分别用来指向首尾元素。关于迭代器的内存元素：首先要有一个指针指向我们待表示的数据。然后就是该数据在那一个缓冲区上，为了在外面上表现为连续的空间，我们必须要记录该缓冲区的首尾地址，这样重载++的时候，能够方便的找到下一块地址。
容器deque代码如下：
测试结果为：
关于deque内部数据结构的说明：
deque是能够同时在收尾进行插入和删除的数据结构。其表现形式看起来和vector差不多，但是在处理队头插入时，其表现的时间复杂度要远远地优越于vector。这个得益于deque的内部数据结构地实现。deque使用分段的连续空间组成。为了管理这个分段的连续空间，所以必须要有一个中控器来记录各个分段空间的首地址，然后需要一个长度来记录该中控器的大小。为了表现和vector相似，所以需要包含2个迭代器分别用来指向首尾元素。关于迭代器的内存元素：首先要有一个指针指向我们待表示的数据。然后就是该数据在那一个缓冲区上，为了在外面上表现为连续的空间，我们必须要记录该缓冲区的首尾地址，这样重载++的时候，能够方便的找到下一块地址。
其结构示意图如下：
其代码实现如下：
//deque的特性:（这段话中别人那copy过来的，因为感觉写的还不错）
// 对于任何一个迭代器i
// i.node是map array中的某元素的地址. i.node的内容是一个指向某个结点的头的指针
// i.first == *(i.node)
// i.last == i.first + node_size
// i.cur是一个指向[i.first, i.last)之间的指针
// 注意: 这意味着i.cur永远是一个可以解引用的指针,
// 即使其是一个指向结尾后元素的迭代器
//
// 起点和终点总是非奇异(nonsingular)的迭代器.
// 注意: 这意味着空deque一定有一个node, 而一个具有N个元素的deque
// (N是Buffer Size)一定有有两个nodes
//
// 对于除了start.node和finish.node之外的每一个node, 每一个node中的元素
// 都是一个初始化过的对象. 如果start.node == finish.node,
// 那么[start.cur, finish.cur)都是未初始化的空间.
// 否则, [start.cur, start.last)和[finish.first, finish.cur)都是初始化的对象,
// 而[start.first, start.cur)和[finish.cur, finish.last)是未初始化的空间
//
// [map, map + map_size)是一个合法的非空区间
// [start.node, finish.node]是内含在[map, map + map_size)区间的合法区间
// 一个在[map, map + map_size)区间内的指针指向一个分配过的node,
// 当且仅当此指针在[start.node, finish.node]区间内
#ifndef ITERATOR_DEQUE_H_INCLUDED
#define ITERATOR_DEQUE_H_INCLUDED
#include"my_iterator_base.h"
namespace juine
{
//用来决定缓存区的大小
inline size_t __deque_buf_size(size_t n, size_t sz)
{
return n!=0?n:(sz<512?size_t(512/sz):size_t(1));
}
template<class T,size_t buf_size=0>
class Iterator_deque
{
public:
typedef T value_type;
typedef value_type* pointer;
typedef value_type& reference;
typedef ptrdiff_t difference_type;
typedef random_access_iterator_tag iterator_category;
typedef T** map_pointer;
pointer data; //所要表示节点的位置
pointer first; //所在分区的起始位置
pointer last; //所在分区的末尾位置
map_pointer node; //所在分区
public:
size_t buff_size() { return __deque_buf_size(buf_size,64); }
//设定节点的位置
void set_node(map_pointer new_node)
{
node=new_node;
first=0;
last=0;
if(new_node!=0)
{
first=*new_node;
last=*new_node+difference_type(buff_size()); //表明又是左闭右开区间
}
}
//construct
Iterator_deque(pointer _data=0,map_pointer _node=0):data(_data){ set_node(_node); }
Iterator_deque(const Iterator_deque& iter):data(iter.data),first(iter.first),last(iter.last),node(iter.node){}
Iterator_deque& operator=(const Iterator_deque& iter)
{
data=iter.data;
first=iter.first;
last=iter.last;
node=iter.node;
return *this;
}
//重载解引用,==,!=
reference operator*() { return *data;}
pointer operator->() { return &(operator*());}
bool operator==(Iterator_deque iter){ return data==iter.data;}
bool operator!=(Iterator_deque iter){ return data!=iter.data; }
bool operator<=(Iterator_deque iter)
{
if(node==iter.node)
return data<=iter.data;
return node<=iter.node;
}
//随机迭代器必须重载++,--
Iterator_deque operator++()
{
data++;
if(data==last)
{
set_node(node+1);
data=first;
}
return *this;
}
Iterator_deque operator++(int) //后置式的标准写法
{
Iterator_deque iter=*this;
++*this;
return iter;
}
Iterator_deque operator--()
{
if(data==first)
{
set_node(node-1);
data=last; //左闭右开
}
data--;
return *this;
}
Iterator_deque operator--(int)
{
Iterator_deque iter=*this;
--*this;
return iter;
}
////////////////////////////////////////////////////////////////////////////////
// 将迭代器向前移动n个元素, n可以为负
////////////////////////////////////////////////////////////////////////////////
// operator+=(difference_type n)
// ↓
// offset = n + (cur - first)
// |
// |---------- offset > 0 ? &&
// | 移动后是否超出当前缓冲区?
// ----------------------------
// No | | Yes
// | |
// ↓ |---------- offset > 0?
// cur += n; |
// ----------------------------
// Yes | | No
// | |
// ↓ |
// 计算要向后移动多少个缓冲区 |
// node_offset = |
// offset / difference_type |
// (buffer_size()); ↓
// | 计算要向前移动多少个缓冲区
// | node_offset = -difference_type
// | ((-offset - 1) / buffer_size()) - 1;
// | |
// ----------------------------
// |
// |
// ↓
// 调整缓冲区
// set_node(node + node_offset);
// 计算并调整cur指针
////////////////////////////////////////////////////////////////////////////////
// 以下实现随机存取。迭代器可以直接跳跃n个距离
Iterator_deque operator+=(difference_type n)
{
difference_type offset=n+(data-first);
if(offset>=0&&offset<difference_type(buff_size()))
//目标位置在同一个缓冲区内
data+=n;
else
{
//目标位置不在同一个缓冲区中
difference_type node_offset=
offset>0?offset/difference_type(buff_size()):-difference_type((-offset-1)/buff_size())-1;
//切换所在缓冲区
set_node(node+node_offset);
//切换所在目录
data=first+(offset-node_offset*difference_type(buff_size()));
}
return *this;
}
Iterator_deque operator+(size_t n)
{
Iterator_deque iter=*this;
return iter+=n;
}
/*
自己写的，发现效率还是比STL的低,而且STL中是将其+=，-=一起处理的
Iterator_deque operator-=(size_t n)
{
if(size_t(data-first)>=n)
data-=n;
else
{
//表示已经越界了该缓存区。
set_node(node-1);
n-=data-first;
data=last;
while(n>buff_size())
{
set_node(node-1);
n-=buff_size();
data=last;
}
data-=n;
}
return *this;
}*/
Iterator_deque operator-=(size_t n) { return *this+=-n;}
Iterator_deque operator-(size_t n)
{
Iterator_deque iter=*this;
iter-=n;
return iter;
}
difference_type operator-(Iterator_deque iter)
{
difference_type offet=(node==iter.node)?data-iter.data:((data-first)+(iter.last-iter.data));
if(node-iter.node>1)
offet+=(node-iter.node-1)*buff_size();
return offet;
}
};
}
#endif // ITERATOR_DEQUE_H_INCLUDED
容器deque代码如下：
#ifndef MY_DEQUE_H_INCLUDED
#define MY_DEQUE_H_INCLUDED
#include"iterator_deque.h"
#include<algorithm>
#include<cstdlib>
#include"simple_allocator.h"
using std::cout;
using std::endl;
namespace juine
{
template<class T,class Alloc=my_alloc,size_t buf_size=0>
class my_deque
{
public:
typedef T value_type;
typedef T* pointer;
typedef T& reference;
typedef size_t size_type;
typedef T** map_pointer;
typedef simple_allocator<T,Alloc> data_container;
typedef simple_allocator<pointer,Alloc> map_container;
typedef Iterator_deque<T,buf_size> iterator;
protected:
size_t map_size; //申请map_node节点个数，再根据_map能获得map_node的尾节点
map_pointer _map; //_map是申请的map_node节点的首地址
iterator start;
iterator finish;
size_t buff_size() { return __deque_buf_size(buf_size,64); }
size_type initial_map_size() { return 8 ;}
//构造函数时，将deque的结构安排好,初始化deque数据结构
void set_null(map_pointer first,map_pointer last)
{
//map节点是用来保存缓冲区地起始地址，
//但是占为使用的map节点应该保存NULL
map_pointer cur;
for(cur=first;cur<last;cur++)
*cur=NULL;
}
void create_map_and_nodes(size_t n)
{
cout<<"buff_size:"<<buff_size()<<endl;
size_type num_nodes=n/buff_size()+1;//当整除时也是要加1的
//map中控器的大小
//map_size=std::max(initial_map_size(),num_nodes+2);
//为了测试，map_size特殊化
map_size=num_nodes;
_map=map_container::alloc(map_size);
//以下是令nstart和nfinish指向map所拥有之全部节点的最中央区段
//保持在最中央，可使头尾两端扩充的能量一样大，每一节点可对应一个缓冲区
//（出现这种情况是因为，我们申请的节点数，是大于初始化时所需要的节点数，
//因此，需要将节点移动中间，使首尾平衡）
map_pointer nstart=_map+(map_size-num_nodes)/2;
map_pointer nfinish=nstart+num_nodes-1;
//申请缓冲区空间，申请节点为刚才所找到的平衡位置
map_pointer cur;
//申请到的node，暂时不指向缓冲区的应该将其值为NULL
set_null(_map,nstart);
set_null(nfinish,_map+map_size);
for(cur=nstart;cur<=nfinish;cur++)
*cur=data_container::alloc(buff_size());
//接下来是配置迭代器start，finish
start.set_node(nstart);
finish.set_node(nfinish);
start.data=*nstart;
finish.data=*nfinish+n%buff_size();
}
void fill_uninitialized()
{
//默认设定20个指针
_map=map_container::alloc(20);
map_size=20;
}
void fill_uninitialized(size_t n,value_type value)
{
//构造deque时，首先是产生deque的结构并安排组织好
create_map_and_nodes(n);
/*
以下注释部分自己写的，考虑不充分：自己强制规定map的大小，
当所需数据刚好为buf_size时，处理地方式也与STL不一样
_map=map_container::alloc(20);
map_size=20;
map_pointer temp=_map;
int remainder=n%buf_size;
int num=(remainder==0?n/bufsize:(n/buf_size+1));
while(num)
{
pointer p=data_container::alloc(buf_size);
if(num==1)
uninitialized_fill_n(p,remainder==0?buf_size:remainder,value); //最后一组只能填充remainder个元素
else
uninitialized_fill_n(p,buf_size,value);
num--;
*temp=p; //将容器整个结构连接起来
temp++;
}
//对迭代器first,last进行初始化
iterator temp(*_map,*_map,*_map+buf_size-1,_map);
first=temp;
if(remainder!=0)
{
iterator temp1(*(_map+n/buf_size)+remainder-1,*(_map+n/buf_size),*(_map+n/buf_size)+remainder-1,_map+n/buf_size );
last=temp1;
}
else
{
iterator temp1(*(_map+n/buf_size-1)+buf_size-1,*(_map+n/buf_size),*(_map+n/buf_size-1)+buf_size-1,_map+n/buf_size-1 );
last=temp1;
}*/
//开始对申请到的节点进行初始化
map_pointer cur;
for(cur=start.node;cur<finish.node;cur++)
uninitialized_fill_n(*cur,buff_size(),value);
uninitialized_fill_n(finish.first,n%buff_size(),value);
}
template<class InputIterator>
void fill_uninitialized(InputIterator first,InputIterator last)
{
size_type num=last-first;
create_map_and_nodes(num);
//deque结构体已构造好，然后需要赋值
iterator iter=start;
while(first!=last)
{
construct(iter.data,*first);
iter++;
first++;
}
}
//释放内存
void dealloc()
{
cout<<"deque容器已释放"<<endl;
//先遍历map释放所有缓冲区
size_t i;
for(i=0;i<map_size;i++)
if(*(_map+i)) //当节点值为空时，表示其所指向缓冲区为空，不需要释放
{
map_pointer temp=_map+i;
destroy(*temp,*temp+buff_size());
data_container::dealloc(*(_map+i));
}
//删除_map
map_container::dealloc(_map);
}
public:
//construct
my_deque(){ fill_uninitialized();}
my_deque(size_t n,value_type value) { fill_uninitialized(n,value);}
template<class InputIterator>
my_deque(InputIterator first,InputIterator last){ fill_uninitialized(first,last);}
~my_deque(){ dealloc() ;}
iterator begin(){ return start; }
iterator end(){ return finish; }
reference operator[](size_type n)
{
iterator iter=start+n;
return *iter;
}
reference at(size_type n)
{
iterator iter=start+n;
if(finish<=iter)
{
cout<<"out of memory"<<endl;
exit(1);
}
return iter;
}
reference front(){ return *start; }
reference back(){ return *(finish-1); }
size_type size() { return finish-start; }
bool empty(){ return start==finish; }
void push_front(value_type value){ insert(start,value); }
void push_back(value_type value){ insert(finish,value);}
//插入函数（考虑缓冲区大小够不，Map大小够不，还有效率-左移还是右移）
void insert(iterator position,value_type value)
{
if(position-start<=finish-position) //表示需要左移动
{
iterator temp,new_start;
temp=new_start=insert_aux_left(1,position);
iterator temp1=start;
//这个地方赋值，利用了迭代器重载函数++,使其能够自动在片段连续空间上移动
while(temp1!=position) //移动元素
*temp++=*temp1++;
*temp=value; //最后插入元素
start=new_start; //插入之后，迭代器要更新，Temp保存的就是最新的位子
}
else
{
iterator temp,new_finish;
temp=new_finish=insert_aux_right(1,position);
iterator temp1=finish;
//这个地方赋值，利用了迭代器重载函数++,使其能够自动在片段连续空间上移动
while(temp1!=position) //移动元素
*--temp=*--temp1;
*position=value; //最后插入元素
finish=new_finish; //插入之后，迭代器要更新，Temp保
}
}
template<class InputIterator>
void insert(iterator position,InputIterator first,InputIterator last)
{
int n=last-first;
if(position-start<=finish-position) //表示需要左移动
{
iterator temp,new_start;
temp=new_start=insert_aux_left(n,position);
iterator temp1=start;
//这个地方赋值，利用了迭代器重载函数++,使其能够自动在片段连续空间上移动
while(temp1!=position) //移动元素
*temp++=*temp1++;
while(temp!=position)
*temp++=*first++; //最后插入元素
start=new_start;
}
else
{
iterator temp,new_finish;
temp=new_finish=insert_aux_right(n,position);
iterator temp1=finish;
//这个地方赋值，利用了迭代器重载函数++,使其能够自动在片段连续空间上移动
while(temp1!=position) //移动元素
*--temp=*--temp1;
while(first!=last)
*position++=*first++; //最后插入元素
finish=new_finish;
}
}
//该函数功能：如容量不够，则扩充容量然后更新该deque结构
//该函数返回值，是表示在插入后，start迭代器所在正确位置
iterator insert_aux_left(size_t number,iterator& position) //number表示插入的数据,而且该数据是左移的。
{
iterator result;
if(start.data-number<=start.first-1) //表示前端缓冲区已满,因此要增加缓冲区
{
//要增加的缓冲区
int left_need_size=number-(start.data-start.first);
int need_map_nodes=left_need_size/buff_size()+1;
if(start.node-_map<need_map_nodes) //表示中控器前端node节点不够了
{
//虽然前面的不够，但是整个_map空余空间够，可以通过移动_map节点来实现
//不用重新分配新的节点。
if(size_t(finish.node-start.node+1+need_map_nodes)<=map_size)
{
cout<<"移动map达到要求"<<endl;
//offset为map移动偏移量
int offset=need_map_nodes-(start.node-_map);
map_pointer temp=finish.node;
while(temp>=start.node)
{
*(temp+offset)=*temp;
temp--;
}
//前面_map移动后，finish中所存的Node，已经不是最后一个节点所在位置
//故要移动，更新finish
finish.node=finish.node+offset;
//map前端node节点已够用，现在是要申请缓冲区内存
map_pointer malloc_node=_map;
while(malloc_node<(start.node+offset))
{
*malloc_node=data_container::alloc(buff_size());
malloc_node++;
}
result.set_node(_map);
result.data= *_map+buff_size()-left_need_size%buff_size();
}
else //map节点不够，需要重新分配其map_nodea
{
//map大小，简单以2倍来扩充
map_pointer new_malloc_map=map_container::alloc(map_size*2);
map_pointer item=new_malloc_map+map_size/2;
map_pointer old_node=start.node;
set_null(new_malloc_map,item);
set_null(new_malloc_map+map_size,new_malloc_map+map_size*2);
//将旧的map复制过来
while(old_node<=finish.node)
*item++=*old_node++;
//因为map重新申请了，所以position也应该换到新map对应的位置上
position.node=new_malloc_map+map_size/2+(position.node-start.node);
//删除旧的map，释放内存
map_container::dealloc(_map);
start.node=new_malloc_map+map_size/2;
finish.node=item-1;
_map=new_malloc_map;
map_size*=2;
//需要申请内存
map_pointer new_node=start.node-1;
while(new_node>=start.node-need_map_nodes)
{
*new_node=data_container::alloc(buff_size());
new_node--;
}
result.set_node(start.node-need_map_nodes);
result.data= *result.node+buff_size()-left_need_size%buff_size();
}
}
else //缓冲区不够，但是map前端所需node是够的
{
//需要申请内存
map_pointer new_node=start.node-1;
while(new_node>=start.node-need_map_nodes)
{
*new_node=data_container::alloc(buff_size());
new_node--;
}
result.set_node(start.node-need_map_nodes);
result.data= *result.node+buff_size()-left_need_size%buff_size();
}
}
else //缓冲区是够的
{
result.data=start.data-number;
result.set_node(start.node);
}
return result;
}
iterator insert_aux_right(size_t number,iterator& position) //number表示插入的数据,而且该数据是右移的。
{
iterator result;
if(finish.data+number>=finish.last) //表示前端缓冲区已满,因此要增加缓冲区
{
//要增加的缓冲区
int left_need_size=number-(finish.last-finish.data-1);
int need_map_nodes=left_need_size/buff_size()+1;
if(_map+map_size-finish.node<need_map_nodes) //表示中控器后端node节点不够了
{
//虽然前面的不够，但是整个_map空余空间够，可以通过移动_map节点来实现
//不用重新分配新的节点。
if(size_t(finish.node-start.node+1+need_map_nodes)<=map_size)
{
cout<<"移动map达到要求"<<endl;
//offset为map移动偏移量
int offset=need_map_nodes-(_map-finish.node);
map_pointer temp=start.node;
while(temp<=finish.node)
{
*(temp-offset)=*temp;
temp++;
}
//前面_map移动后，finish中所存的Node，已经不是最后一个节点所在位置
//故要移动，更新finish
start.node=start.node-offset;
//map前端node节点已够用，现在是要申请缓冲区内存
map_pointer malloc_node=_map+map_size;
while(malloc_node>(finish.node-offset))
{
*malloc_node=data_container::alloc(buff_size());
malloc_node--;
}
result.set_node(_map+map_size);
result.data= *(_map+map_size)+left_need_size%buff_size();
}
else //map节点不够，需要重新分配其map_nodea
{
//map大小，简单以2倍来扩充
map_pointer new_malloc_map=map_container::alloc(map_size*2);
map_pointer item=new_malloc_map+map_size/2;
map_pointer old_node=start.node;
set_null(new_malloc_map,item);
set_null(new_malloc_map+map_size,new_malloc_map+map_size*2);
//将旧的map复制过来
while(old_node<=finish.node)
*item++=*old_node++;
//因为map重新申请了，所以position也应该换到新map对应的位置上
position.node=new_malloc_map+map_size/2+(position.node-start.node);
//删除旧的map，释放内存
map_container::dealloc(_map);
start.node=new_malloc_map+map_size/2;
finish.node=item-1;
_map=new_malloc_map;
map_size*=2;
//需要申请内存
map_pointer new_node=finish.node+1;
while(new_node<=finish.node+need_map_nodes)
{
*new_node=data_container::alloc(buff_size());
new_node++;
}
result.set_node(finish.node+need_map_nodes);
result.data= *result.node+left_need_size%buff_size();
}
}
else //缓冲区不够，但是map前端所需node是够的
{
//需要申请内存
map_pointer new_node=finish.node+1;
while(new_node<=finish.node+need_map_nodes)
{
*new_node=data_container::alloc(buff_size());
new_node++;
}
result.set_node(finish.node+need_map_nodes);
result.data= *result.node+left_need_size%buff_size();
}
}
else //缓冲区是够的
{
result.data=finish.data+number;
result.set_node(finish.node);
}
return result;
}
//删除元素（为了简单，只写一种）
void erase(iterator position)
{
iterator temp;
if(position-start<=finish-position) //左边的元素右移动
{
temp=position-1;
while(start<=temp)
{
*(temp+1)=*temp;
temp--;
}
start++;
if((start-1).node!=start.node)
*(start-1).node=NULL;
}
else
{
temp=position+1;
while(temp!=finish)
{
*(temp-1)=*temp;
temp++;
}
finish--;
if((finish+1).node!=finish.node)
*(finish+1).node=NULL;
}
}
void pop_back(){ erase(finish-1);}
void pop_front(){ erase(start); }
};
}
#endif // MY_DEQUE_H_INCLUDED
测试代码如下：
#include<iostream>
#include<cstdlib>
#include<vector>
#include"my_deque.h"
using namespace std;
using namespace juine;
int main()
{
int a[9]={1,2,3,4,5,6,7,8,9};
my_deque<int> tt(a,a+9);
tt.front()+=tt.back();
tt.back()+=tt.front();
my_deque<int>::iterator iter=tt.begin()+2;
tt.insert(iter,a,a+9);
tt.insert(tt.begin(),11);
tt.push_front(12);
tt.push_back(25);
tt.erase(tt.begin()+4);
tt.pop_front();
for(iter=tt.begin();iter!=tt.end();iter++)
cout<<*iter<<endl;
cout<<"size:"<<tt.size()<<endl;
return 0;
}
测试结果为：
已基本达到要求，下一章实现序列容器。
- 1楼zaizai09昨天 09:33
- 大神，不错，学习学习