【deque容器系列一】基于STL源码分析deque容器整体实现及内存结构

cpp加油站
• 阅读 1880

本篇文章基于gcc中stl的源码介绍deque容器的整体实现和它的内存结构。

说明一下,我用的是gcc7.1.0编译器,标准库源代码也是这个版本的。

首先呢,还是看一下思维导图,如下:

【deque容器系列一】基于STL源码分析deque容器整体实现及内存结构

1. deque容器整体源码实现介绍

deque容器是stl中顺序容器的一种,之前已经介绍过array和vector了,今天介绍deque容器,deque的本质是一个类模板,它的声明位于头文件bits/stl_deque.h,实现位于bits/deque.tcc,接下来我们就围绕这两个文件来介绍一下deque容器的实现原理。

先看一下deque容器相关的一个整体类图:

【deque容器系列一】基于STL源码分析deque容器整体实现及内存结构

下面对这个类图进行一个简单的解读:

  • deque容器保护继承于类模板_Deque_base,也就是_Deque_base是deque的基类,并且内存分配和释放都是通过基类来完成的;
  • 容器首地址和迭代器等保存在结构体成员变量_M_impl中,它继承于别名类型_Tp_alloc_type,最终的内存分配其实就是通过它完成的;
  • deque容器使用了它自己的迭代器_Deque_iterator,没有直接使用stl中的公共迭代器,且迭代器里面保存了当前地址、首地址、尾地址以及当前节点。

这里有几个类型是不好理解的,第一个是_Tp_alloc_type,这是一个别名,关于这个类型的解读,我之前专门写过一篇文章:三张图带你弄懂STL中内存分配器

然后就是_Elt_pointer_Map_pointer这两个类型,他们的原型如下:

//这里_Tp是模板类型
#if __cplusplus < 201103L
      typedef _Deque_iterator<_Tp, _Tp&, _Tp*>         iterator;
      typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
      typedef _Tp*                     _Elt_pointer;
      typedef _Tp**                    _Map_pointer;
#else
    private:
      template<typename _Up>
    using __ptr_to = typename pointer_traits<_Ptr>::template rebind<_Up>;
      template<typename _CvTp>
    using __iter = _Deque_iterator<_Tp, _CvTp&, __ptr_to<_CvTp>>;
    public:
      typedef __iter<_Tp>        iterator;
      typedef __iter<const _Tp>        const_iterator;
      typedef __ptr_to<_Tp>        _Elt_pointer;
      typedef __ptr_to<_Elt_pointer>    _Map_pointer;
#endif

在c++11以前,它们之前就直接是指针类型,在c++11以后,使用了类模板pointer_traits的rebind类型属性,有关pointer_traits的详细说明,请看下面这篇文章:

从c++标准库指针萃取器谈一下traits技法

仔细看一下,其实最终pointer_traits的rebind得到的类型同样也是指针类型哈,结果是一致的,只是可能代码这么写更加的清新脱俗一点,哈哈,开个玩笑,估计是因为模板类型这么写更加规范一点。

2. deque容器构造时内存结构是怎样的

在源代码里面,deque容器构造函数重载了很多,我们选取其中一种典型的类型看一下,构造函数原型如下:

//构造一个大小为n的deque容器,容器中所有元素的值为value,__a是默认分配器
deque(size_type __n, const value_type& __value, const allocator_type& __a = allocator_type())
      : _Base(__a, __n)
      { _M_fill_initialize(__value); }

整个构造的调用过程,我们看下面这张图:

【deque容器系列一】基于STL源码分析deque容器整体实现及内存结构

通过图片,我们可以看到三个构造函数只是对分配器和其他成员变量等做了一下初始化,而真正申请内存的是模板函数_M_initialize_map,然后给容器填充数据的模板函数_M_fill_initialize,我们主要看下这两个函数的实现。

先看下模板函数_M_initialize_map,源代码如下:

//deque容器初始化元素个数
template<typename _Tp, typename _Alloc>
    void _Deque_base<_Tp, _Alloc>::_M_initialize_map(size_t __num_elements)
    {
     //如果sizeof(_Tp)<512,那么__deque_buf_size返回512/sizeof(_Tp),否则返回1,_Tp是容器的元素类型,所以这里返回的是一个默认块内存的元素数量,也就是一个buffer里面包含的元素个数,后续以buffer代指一块内存
     //__num_nodes = 元素个数/块内存元素数量 + 1,得到的是总共有多少个buffer,为什么要加1,防止有余数,所以需要加1
      const size_t __num_nodes = (__num_elements/ __deque_buf_size(sizeof(_Tp))
                  + 1);
     //_S_initial_map_size默认为8,根据max调用得到最终的块内存个数
      this->_M_impl._M_map_size = std::max((size_t) _S_initial_map_size,
                       size_t(__num_nodes + 2));
     //这里根据buffer类型和buffer个数申请动态内存,说白了这里申请节点的动态内存,并没有申请真正保存元素的块内存的动态空间
      this->_M_impl._M_map = _M_allocate_map(this->_M_impl._M_map_size);
     //根据以下两行可知,_M_map的第一个和最后一个节点其实是保留的,暂时不会使用
      _Map_pointer __nstart = (this->_M_impl._M_map
                   + (this->_M_impl._M_map_size - __num_nodes) / 2);
      _Map_pointer __nfinish = __nstart + __num_nodes;
      __try
    { 
        //该函数根据节点循环对每一块buffer申请动态空间,一个节点指向一个buffer
          _M_create_nodes(__nstart, __nfinish); }
      __catch(...)
    {
      _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
      this->_M_impl._M_map = _Map_pointer();
      this->_M_impl._M_map_size = 0;
      __throw_exception_again;
    }
    //_M_set_node对节点所对应的位置和迭代器位置进行初始化,并使用成员变量保存节点开始和结束位置
      this->_M_impl._M_start._M_set_node(__nstart);
      this->_M_impl._M_finish._M_set_node(__nfinish - 1);
      this->_M_impl._M_start._M_cur = _M_impl._M_start._M_first;
      this->_M_impl._M_finish._M_cur = (this->_M_impl._M_finish._M_first
                    + __num_elements
                    % __deque_buf_size(sizeof(_Tp)));
    }

我们根据以上的代码和注释可以得出一个结论,deque容器首先申请一段连续内存,然后连续内存里面每一个节点指向一个buffer,如下图所示:

【deque容器系列一】基于STL源码分析deque容器整体实现及内存结构

上图中node代表节点,这些节点是一段连续内存,每一个节点指向一块独立的buffer,从数据结构的层面讲,deque容器其实就是一个双端队列。

接下来我们看下另外一个模板函数_M_fill_initialize,它的源代码如下:

template <typename _Tp, typename _Alloc>
    void
    deque<_Tp, _Alloc>::
    _M_fill_initialize(const value_type& __value)
    {
      _Map_pointer __cur;
      __try
        {
          //循环填充容器每一个元素的值为__value
          for (__cur = this->_M_impl._M_start._M_node;
           __cur < this->_M_impl._M_finish._M_node;
           ++__cur)
           //__uninitialized_fill_a函数会根据值对每一个元素进行构造,它其实相当于一个placement new的作用
            std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(),
                    __value, _M_get_Tp_allocator());
          std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first,
                      this->_M_impl._M_finish._M_cur,
                      __value, _M_get_Tp_allocator());
        }
      __catch(...)
        {
          std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur),
            _M_get_Tp_allocator());
          __throw_exception_again;
        }
    }

这个函数比较简单,注释也说的比较清楚了,这里不再多说。

接下来我们给一个使用案例,如下所示:

#include <deque>

int main()
{
    std::deque<int> deq(1024, 100);
    return 0;
}

简单的定义了一个deque,元素个数为1024,每一个元素值为100。

好了,本篇文章就为大家介绍到这里,觉得内容对你有用的话,记得顺手点个赞哦~

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
cpp加油站 cpp加油站
3年前
c++11增加的变参数模板,今天总算整明白了
本篇文章介绍一下c11中增加的变参数模板template<typename...Args到底是咋回事,以及它的具体用法。说明一下,我用的是gcc7.1.0编译器,标准库源代码也是这个版本的。按照惯例,还是先看一下本文大纲,如下:在之前写vector和deque容器源码剖析的过程中,经常发现这样的代码,如下:cpptemplate<typename..
cpp加油站 cpp加油站
3年前
【deque容器系列二】基于STL源码分析deque容器插入和删除时内存都是怎么变动的
上篇文章我们介绍了deque容器整体结构和构造实现,链接如下:本篇文章接上篇,继续基于gcc中stl的源码剖析deque容器插入、删除、取值的实现原理,以提问者的角度去深入分析这些操作过程中发生了什么,并对deque容器适合使用的场景和使用时的注意事项进行说明。说明一下,我用的是gcc7.1.0编译器,标准库源代码也是这个版本的。按照惯例,还是先看一下本文
cpp加油站 cpp加油站
3年前
【STL源码拆解】基于源码分析forward_lsit容器实现(详细!)
本篇文章介绍一下c11中新增的顺序容器forwardlist,基于stl的源码分析一下该容器的整体实现及数据结构。说明一下,我用的是gcc7.1.0编译器,标准库源代码也是这个版本的。按照惯例,还是先看一下本文大纲,如下:1.forwardlist是什么forwardlist是c11为STL新增加的一种顺序容器,使用的时候包含头文件forwar
Stella981 Stella981
3年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置1、virsheditcentos7找到“memory”和“vcpu”标签,将<namecentos7</name<uuid2220a6d1a36a4fbb8523e078b3dfe795</uuid
Easter79 Easter79
3年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Stella981 Stella981
3年前
C++STL容器deque
deque简介deque属于序列式容器,和vector十分相似,采用dynamicarray来管理元素,提供随机访问,但是deque的dynamicarray头尾两端都开放,可以在头尾两端快速安插和删除。!(https://img2018.cnblogs.com/blog/1520224/201902/15202242019
Python进阶者 Python进阶者
10个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这