版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1338355
deque
,以及其与vector
的区别deque
迭代器的实现deque
的构造函数,从整体上理解deque
的实现STL
的 stack
默认使用deque
而不是vector
作为底层容器分析实现源码,其实我们只用实现,理解几个核心的函数就可以明白其中的原理,并不需要全部的实现。太多实现函数,会让我们分不清重点,而且看起来头大。
deque
,以及其与vector
的区别vector
deque
在插入数据(头部或者尾部), 如果缓冲区不足,那么为触发分配新的缓冲区,这和vector
不一样。deque
迭代器的实现deque
的主要变量定义如下:template <class T, class Ref, class Ptr, size_t buff_size>
struct __deque_iterator{
typedef __deque_iterator<T, T&, T*, buff_size> iterator;
typedef __deque_iterator<T, const T&, const T*, buff_size> const_iterator;
static size_t buffer_size() {return __deque_buf_size(buff_size, sizeof(T)); }
typedef T value_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef T** map_pointer;
typedef __deque_iterator self;
// 保持与容器的联结
T* cur; // 此迭代器所指之缓冲区中的现行元素
T* first; // 此迭代器所指之缓冲区的头
T* last; // 此迭代器所指之缓冲区的尾(含备用空间)
//由于,指针肯会遇到缓冲区边缘,因此需要跳到下一个缓冲区
//于是需要指向map回去下一个缓冲区地址
map_pointer node; // 指向管控中心
}
/* iterator中需要缓冲区的长度,当n不等于0,return n,表示buffer size使用指定值
*如果n==0,buffer size使用默认值
*/
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));
}
void set_node(map_pointer new_node){
node = new_node;
first = *new_node;
last = first + buffer_size();
}
reference operator*()const{
return *cur;
}
// prefix forms of increment
self& operator++(){
++cur;
if (cur == last){ //如果已达所在缓冲区的尾端
set_node(node + 1);//切换至下一个节点(缓冲区)
cur = first;
}
return *this;
}
//上面返回的是引用,下面返回的是临时对象
self operator++(int){ // postfix forms of increment
self tmp = *this;
++*this;//直接调用postfix forms
return tmp;
}
self& operator--(){
if(cur == first){ // 已经是缓冲区的头部
set_node(node - 1);//切换至前一个节点
cur = last;
}
--cur;
return *this;
}
self operator--(int){
self tmp = *this;
--*this;
return tmp;
}
self& operator+=(difference_type n){ // n 可正可负
difference_type offset = n + (cur - first);
if(offset >=0 && offset < difference_type(buffer_size())){
// 同一个缓冲区内
cur += n;
}else{//不在同一个缓冲区
difference_type node_offset;
if (offset > 0){
node_offset = offset / difference_type(buffer_size());
}else{
node_offset = -((-offset - 1) / difference_type(buffer_size())) - 1 ;
}
// 切换至正确的缓冲区
set_node(node + node_offset);
// 切换至正确的元素
cur = first + (offset - node_offset * buffer_size());
}
return *this;
}
// 返回的不是引用,因此const函数
self operator+(difference_type n)const{
self tmp = *this;
return tmp+= n; //直接调用operator +=
}
self& operator-=(difference_type n){
return *this += -n; //直接调用operator +=
}
// 返回的不是引用,因此const函数
self operator-(difference_type n)const{
self tmp = *this;
return tmp -= n; //直接调用operator +=
}
// 随机存取,迭代器可以直接跳跃 n 个距离
// 调用上面的 operator + ,以及operator *
reference operator[](difference_type n)const{
return *(*this + n);
}
bool operator==(const self& rhs)const{
return cur == rhs.cur;
}
bool operator!=(const self& rhs)const{
return !(*this == rhs);
}
bool operator<(const self& rhs)const{
return (node == rhs.node) ? (cur < rhs.cur) : (node < rhs.node);
}
deque
的构造函数,从整体上理解deque
的实现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, T&, T*, buff_size> iterator;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
protected:
typedef pointer* map_pointer;
// 实际的数据存储,分配器
typedef allocator<value_type> dataAllocator;
// map指针分配器
typedef allocator<pointer> mapAllocator;
private: //数据成员
iterator start;
iterator finish;
map_pointer map;
size_type map_size;
}
iterator begin(){return start;}
iterator end(){return finish;}
reference front(){
//调用的是__deque_iterator的 operator*
// 返回 start的成员 *cur
return *start;
}
reference back(){
// 此处不能直接 *finish
iterator tmp = finish;
--tmp; //调整使之指为
return *tmp; //返回的是finish 的 *cur
}
reference operator[](size_type n){
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){
// 分配map以及缓冲区的内存
// 初始化好对应的指针位置
create_map_and_nodes(n);
// 缓冲区每个节点设置初始值
for (map_pointer cur = start.node; cur < finish.node; ++cur) {
initialized_fill_n(*cur, buffer_size(), 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){
// 需要的节点数 = (元素个数 / 缓冲区可以容纳的元素个数) + 1
// 如果刚好整除,会多配置一个节点
size_type num_nodes = num_elements / buffer_size() + 1;
// 一个map要管理的节点的个数。最少是 8 个,最多是"所需节点数 + 2"
map_size = std::max(initial_map_size(), num_nodes + 2);
// 申请配置对应的数组
map = mapAllocator::allocate(map_size);
// tmp_start,tmp_finish 指向 map的最中央区域
// 保持在最中央使得两端的开展区域一样
map_pointer tmp_start = map + (map_size - num_nodes) / 2;
map_pointer tmp_finish = tmp_start + num_nodes - 1;
// 为map每个节点配置缓冲区
for (map_pointer cur = tmp_start; cur <= tmp_finish; ++cur) {
*cur = dataAllocator::allocate(buffer_size());
}
// 设置 start 和 end 两个迭代器
start.set_node(tmp_start);
start.cur = start.first;
finish.set_node(tmp_finish);
finish.cur = finish.first + num_elements % buffer_size();
}
deque<int, 8> i_deque2(10, 1);
// 一个map要管理的节点的个数。最少是 8 个,最多是"所需节点数 + 2"
map_size = std::max(initial_map_size(), num_nodes + 2);
// 申请配置对应的数组
map = mapAllocator::allocate(map_size);
// 为map每个节点配置缓冲区
for (map_pointer cur = tmp_start; cur <= tmp_finish; ++cur) {
*cur = dataAllocator::allocate(buffer_size());
}
deque
的实现原理了,剩下的难点就在于插入、删除元素是缓冲区的分配以及map节点的管理问题了。下面简单给出调用push_back
函数时deque
的缓冲区的变化。i_deque2.push_back(1);
i_deque2.push_back(2);
i_deque2.push_back(3);
STL
的 stack
默认使用deque
而不是vector
作为底层容器STL
的 stack
默认使用deque
而不是vector
作为底层容器? 这个问题来源于stackoverflow
https://stackoverflow.com/questions/102459/why-does-stdstack-use-stddeque-by-default?rq=1
vector
而言可能涉及到申请新的空间,复制原有的元素到新的空间,释放原有的旧空间。而deque
则没有这个问题。As the container grows, a reallocation for a vector requires copying all the elements into the new block of memory. Growing a deque allocates a new block and links it to the list of blocks - no copies are required.