首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >STL deque源码实现及分析

STL deque源码实现及分析

作者头像
bear_fish
发布2018-09-14 09:54:38
2.7K0
发布2018-09-14 09:54:38
举报

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1338355

本文主要内容如下:
1. 从整体上介绍STL deque,以及其与vector的区别
2. deque迭代器的实现
3. 通过分析deque的构造函数,从整体上理解deque的实现
4. 分析为什么STLstack 默认使用deque而不是vector作为底层容器

分析实现源码,其实我们只用实现,理解几个核心的函数就可以明白其中的原理,并不需要全部的实现。太多实现函数,会让我们分不清重点,而且看起来头大。

1. 整体上介绍STL deque,以及其与vector的区别

1.1 overview
std::deque ( double-ended queue ,双端队列)是可以进行下标访问的顺序容器,它允许在其首尾两端快速插入及删除元素。
deque系由一段一段的定量连续空间构成。一旦有必要在deque的前端或尾端增加新空间,便配置一段定量连续空间,串接在整个deque的头端或尾端。deque的最大任务,便是在这些分段的定量连续空间上,维护其整体连续的假象,并提供随机存取的借口。避开了“重新配置、复制、释放”的轮回,代价则是复杂的迭代器架构。
deque采用一块所谓的map(注意,不是STL的map容器)作为主控。这里所谓map是一小块连续空间,其中每个元素(此处称为一个节点,node)都是指针,指向另一段(较大的)连续线性空间,称为缓冲区。缓冲区才是deque的储存空间主体。如下图所示:缓冲区的大小为 8。
1.2 简单对比vector
deque 在插入数据(头部或者尾部), 如果缓冲区不足,那么为触发分配新的缓冲区,这和vector不一样。
vector插入数据:
1. 另觅更大空间(检测现有的capacity是否满足需求,若不满足会分配新的空间);
2. 将原数据复制过去;
3. 释放原空间三部曲。
如果不是vector每次配置新空间时都有留下一些余裕,其成长假象所带来的代价将是相当高昂。

2. deque迭代器的实现
deque迭代器设计的最大问题在于:当指针++ ,–,+n 不能简单的指针前进,后退。因为迭代器可能会遇到缓冲区的边缘,一旦遇到缓冲区边缘,要特别当心,视前进或后退而定,可能需要调用set_node函数跳一个缓冲区。
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));
}
set_node函数跳一个缓冲区
void set_node(map_pointer new_node){
    node = new_node;
    first = *new_node;
    last = first + buffer_size();
}
重载*(显然返回的是引用):
reference operator*()const{
    return *cur;
}
下面重点看下迭代器的++, –的重载,指针的前进后退可能涉及到缓冲区的切换:
注意两点:
1. 后置++直接调用前置++
2. 前置返回的是引用,后置返回的是临时对象
// 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;
}
接下来指针移动n步(n可正可负):
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);
}

3. 通过分析deque的构造函数,从整体上理解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;
}
核心成员:
1. 两个迭代器:start,finish,一个map节点,以及map_size
2. map(其实是个动态的数组,例如当缓冲区不够的时候,大小会扩展),因此有mapAllocator以及dataAllocator缓冲区分配
迭代器以及back/front函数:
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
}
O(1)的方式获取 第n个元素:
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();
}
接下来看下内存分配问题,创建含有10个int元素的deque:
deque<int, 8> i_deque2(10, 1);
输出如下:
1. 首先是map的缓冲区,使用的是默认的8个,指针大小(win64下位8)因此向空间配置申请 大小为64的内存,最终返回20个填充到free_list中去
// 一个map要管理的节点的个数。最少是 8 个,最多是"所需节点数 + 2"
map_size = std::max(initial_map_size(), num_nodes + 2);
// 申请配置对应的数组
map = mapAllocator::allocate(map_size);
2. 配置缓冲区内存,这里只需要配置2个缓冲区即可:
// 为map每个节点配置缓冲区
for (map_pointer cur = tmp_start; cur <= tmp_finish; ++cur) {
    *cur = dataAllocator::allocate(buffer_size());
}
输出如下:
通过上面的构造函数,我们基本可以理解deque的实现原理了,剩下的难点就在于插入、删除元素是缓冲区的分配以及map节点的管理问题了。下面简单给出调用push_back函数时deque的缓冲区的变化。
现假设deque有20个元素0~19,缓冲区大小为8,现在
i_deque2.push_back(1);
i_deque2.push_back(2);
i_deque2.push_back(3);
deque的状态图如下:
接着在push_back(3),会引发新的缓冲区配置:
如果我们push_front,map的原来的start的前一个节点会配置新的缓冲区,并插入元素

4. 分析为什么STLstack 默认使用deque而不是vector作为底层容器
分析为什么STLstack 默认使用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.

这个系列的blog主要参考 《STL源码剖析》by 侯捷
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018年06月21日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 本文主要内容如下:
  • 1. 整体上介绍STL deque,以及其与vector的区别
    • 1.1 overview
      • 1.2 简单对比vector
        • 如果不是vector每次配置新空间时都有留下一些余裕,其成长假象所带来的代价将是相当高昂。
        • 3. 通过分析deque的构造函数,从整体上理解deque的实现
          • 4. 分析为什么STL的 stack 默认使用deque而不是vector作为底层容器
          相关产品与服务
          容器服务
          腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档