【STL源码拆解】基于源码分析forward_lsit容器实现(详细!)

cpp加油站
• 阅读 1286

本篇文章介绍一下c++11中新增的顺序容器forward_list,基于stl的源码分析一下该容器的整体实现及数据结构。

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

按照惯例,还是先看一下本文大纲,如下:

【STL源码拆解】基于源码分析forward_lsit容器实现(详细!)

1. forward_list是什么

forward_list是c++11为STL新增加的一种顺序容器,使用的时候包含头文件forward_list即可,真实的类声明位于头文件bits/forward_list.h中,类forward_list是一个类模板,基于单链表结构实现,下面我们就来基于forward_list的源码来看下它的具体实现。

2. forward_list周边类介绍

在正式开始介绍类模板forward_list之前,我们先了解下它所使用到的其他类型的介绍,这些类型是理解forward_list源码实现的前置条件。

2.1 类模板_Fwd_list_node和它的基类_Fwd_list_node_base

类模板_Fwd_list_node声明同样位于头文件bits/forward_list.h中,先看下类声明,如下:

template<typename _Tp>
    struct _Fwd_list_node
    : public _Fwd_list_node_base
    {
      _Fwd_list_node() = default;

      __gnu_cxx::__aligned_buffer<_Tp> _M_storage;

      _Tp*
      _M_valptr() noexcept
      { return _M_storage._M_ptr(); }

      const _Tp*
      _M_valptr() const noexcept
      { return _M_storage._M_ptr(); }
    };

该类定义了一个成员变量_M_storage,这个成员变量类型是__gnu_cxx::__aligned_buffer<_Tp>,同样是一个类模板,看看类模板__aligned_buffer的类声明,如下:

template<typename _Tp>
    struct __aligned_buffer
    : std::aligned_storage<sizeof(_Tp), std::alignment_of<_Tp>::value>
    {
      typename
    std::aligned_storage<sizeof(_Tp), std::alignment_of<_Tp>::value>::type _M_storage;
        ......  
    };

可以看到其实它是基于另外一个类aligned_storage实现的,且以这个基类中声明的类型type定义了一个同样的成员变量_M_storage,接着看类aligned_storage实现:

template<std::size_t _Len, std::size_t _Align =
       __alignof__(typename __aligned_storage_msa<_Len>::__type)>
    struct aligned_storage
    {
      union type
      {
    unsigned char __data[_Len];
    struct __attribute__((__aligned__((_Align)))) { } __align;
      };
    };

基于以上代码,可以看出类型aligned_storage::type其实是一个联合体类型,该联合体的第一个字段很明朗,就是以模板类型_Tp的长度定义了一个无符号字符数组,但第二个字段__align就比较奇怪了,他的类型是struct __attribute__((__aligned__((_Align)))) { },整体而言这是一个结构体,但大括号里面为空,说明该结构体是没有字段的,那么它到底是什么呢?

其实__attribute__是gcc的一个扩展用法,它允许在该关键字后面的双括号里面指定某些特殊属性,这里的__aligned__((_Align))就是指定了按多少个字节对齐,其中的_Align是通过非类型模板形参传入的对齐字节数。

我们在看下,这里的使用场景下类模板aligned_storage的实参是sizeof(_Tp), std::alignment_of<_Tp>::value,第一个实参就是模板类型_Tp的长度,第二个实参是基于alignment_of实现的,其实就是告诉编译器,根据模板类型_Tp的字节对齐规则去对齐。

所以简单来说,其实_Fwd_list_node::_M_storage就是一个结构体变量而已,它的大小是模板类型_Tp的大小。

接下来我们再看看基类_Fwd_list_node_base的实现,它的源码如下:

struct _Fwd_list_node_base
  {
    _Fwd_list_node_base() = default;

    _Fwd_list_node_base* _M_next = nullptr;
    ......

  };

这个类就比较简单哈,就是定义了一个成员指针而已,这里不再多说。

2.2 forward_list的基类_Fwd_list_base

forward_list的基类_Fwd_list_base声明同样位于头文件bits/forward_list.h中,同样的,先看看它有哪些成员变量,我们截取一段源码,如下

  template<typename _Tp, typename _Alloc>
    struct _Fwd_list_base
    {
    protected:
    typedef __alloc_rebind<_Alloc, _Tp>           _Tp_alloc_type;
      typedef __alloc_rebind<_Alloc, _Fwd_list_node<_Tp>> _Node_alloc_type;
      typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits;
      struct _Fwd_list_impl 
      : public _Node_alloc_type
      {
        _Fwd_list_node_base _M_head;
       ......
      };
      _Fwd_list_impl _M_impl;
      ......
    };

_Fwd_list_base也是一个类模板,它只有一个成员变量_M_impl,该成员变量类型也是在这个类模板中定义的结构体类型_Fwd_list_impl,它的基类是_Node_alloc_type,这个类型比较复杂,但结合我们之前写的内存萃取器和内存分配器的说明,经过一番推导,可知这个基类真正的类型是allocator<_Fwd_list_node<_Tp>>,这是一个内存分配器,所以实际上_Fwd_list_impl它可以说是类模板_Fwd_list_base里面定义的一个内存萃取器,它根据模板类型取得一个内存分配器,只不过它多保存了一个成员变量_M_head而已,_M_head的类型我们在上一小节里面说了,这里不再多说。

3. forward_list框架实现

前面介绍了forward_list周边的一些类实现,接下来我们看看怎么把这些类与forward_list关联起来。

首先呢,我们还是来看一下forward_list的整体类图,如下:

【STL源码拆解】基于源码分析forward_lsit容器实现(详细!)

基于以上类图以及上一章对于forward_list周边类的介绍,我们对类模板forward_list的整体类框架实现总结如下:

  • forward_list本身不保存数据,只实现了插入、删除、查询、构造等接口,供程序员们使用;
  • forward_list的基类是_Fwd_list_base,保存数据的成员变量_M_impl声明于该基类中,真正对数据的操作也都是基于该基类完成的;
  • 成员变量_M_impl中保存了头结点_M_head,头结点是链表的入口;
  • 头结点_M_head类型是_Fwd_list_node_base,该类型只包含一个成员变量_M_next_M_next是一个基类指针,它指向下一个链表节点,每个节点类型是_Fwd_list_node<_Tp>,该类型含两个成员变量,一个是继承于基类的_M_head,还有一个是该类本身定义的成员变量_M_storage

到这里,对forward_list我们就有了一些整体的认知了,但此时我们还是对于它的内存结构实现不是特别清晰,接下来就以forward_list的构造为一条线来详细看下最后它的内存结构是怎样的。

4. forward_list构造实现及内存结构

forward_list有很多种构造函数,包括拷贝构造、默认无参构造、有参构造、移动构造等,这里我们以其中一种有参构造为例,该构造函数声明如下:

//第一个参数为容器需构造的元素数量,第二个参数为每个元素的值,第三个参数是分配器,其中分配器是类的模板参数指定,这里我们使用默认的即可
forward_list(size_type __n, const _Tp& __value,
                   const _Alloc& __al = _Alloc())
      : _Base(_Node_alloc_type(__al))
      { _M_fill_initialize(__n, __value); }

该函数首先调用基类构造函数指定内存分配器,关于这一点我们使用默认的即可,这里不再多说。

然后调用了函数_M_fill_initialize进行动态内存申请及元素赋值等操作,该函数源码实现如下:

template<typename _Tp, typename _Alloc>
    void
    forward_list<_Tp, _Alloc>::
    _M_fill_initialize(size_type __n, const value_type& __value)
    {
        //头节点是类对象,地址固定,这里取头节点地址赋给临时指针__to
      _Node_base* __to = &this->_M_impl._M_head;
      for (; __n; --__n)
        {
          //创建一个节点,且将节点地址赋给上一节点的_M_next
          __to->_M_next = this->_M_create_node(__value);
          //__to指向上一行代码新创建的节点
          __to = __to->_M_next;
        }
    }

该函数就比较简单了,具体作用注释也写明了,我们接下来看看具体创建节点是怎么样的,节点创建使用函数_M_create_node,该函数实现在forward_list基类中,源码如下:

_Node* _M_get_node()
{
    //这里使用指定内存分配器申请一个_Fwd_list_node大小的空间,并返回指向该空间的地址给__ptr
    auto __ptr = _Node_alloc_traits::allocate(_M_get_Node_allocator(), 1);
    //获取__ptr的地址并返回
    return std::__addressof(*__ptr);
}
//这里使用了变参数模板,关于变参数模板的详细说明,我在上一篇文章中详细说明了,这里不再多说
template<typename... _Args>
_Node* _M_create_node(_Args&&... __args)
{
    _Node* __node = this->_M_get_node();
    __try
      {
    _Tp_alloc_type __a(_M_get_Node_allocator());
    typedef allocator_traits<_Tp_alloc_type> _Alloc_traits;
        //这里是placement new的用法,做了二次分配
    ::new ((void*)__node) _Node;
        //这里会根据函数入参调用元素类型的构造函数并进行赋值
    _Alloc_traits::construct(__a, __node->_M_valptr(),
               std::forward<_Args>(__args)...);
      }
    __catch(...)
      {
        this->_M_put_node(__node);
        __throw_exception_again;
      }
    return __node;
}

详细的说明,在上面代码的注释中都写明了,那么根据构造函数的调用路线,我们可以画出forward_list内存结构如下:

【STL源码拆解】基于源码分析forward_lsit容器实现(详细!)

这是一个典型的头节点不存储数据的单链表结构,这里就不再多说啦。 好了,本篇文章就为大家介绍到这里,觉得内容对你有用的话,记得顺手点个赞和关注哦~

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
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
Jacquelyn38 Jacquelyn38
2年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
cpp加油站 cpp加油站
2年前
【deque容器系列一】基于STL源码分析deque容器整体实现及内存结构
本篇文章基于gcc中stl的源码介绍deque容器的整体实现和它的内存结构。说明一下,我用的是gcc7.1.0编译器,标准库源代码也是这个版本的。首先呢,还是看一下思维导图,如下:1.deque容器整体源码实现介绍deque容器是stl中顺序容器的一种,之前已经介绍过array和vector了,今天介绍deque容器,deque的本质是一个类模板,它的
cpp加油站 cpp加油站
2年前
【deque容器系列二】基于STL源码分析deque容器插入和删除时内存都是怎么变动的
上篇文章我们介绍了deque容器整体结构和构造实现,链接如下:本篇文章接上篇,继续基于gcc中stl的源码剖析deque容器插入、删除、取值的实现原理,以提问者的角度去深入分析这些操作过程中发生了什么,并对deque容器适合使用的场景和使用时的注意事项进行说明。说明一下,我用的是gcc7.1.0编译器,标准库源代码也是这个版本的。按照惯例,还是先看一下本文
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Stella981 Stella981
2年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置1、virsheditcentos7找到“memory”和“vcpu”标签,将<namecentos7</name<uuid2220a6d1a36a4fbb8523e078b3dfe795</uuid
Easter79 Easter79
2年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Stella981 Stella981
2年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
2个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这