再看STL源码剖析

时间:2021-03-12 05:38:40
  • 组件关系
    • container 通过容器allocator 获得数据空间
    • Algorithm 通过迭代器存取container 内容
    • functor 协助 Algorithm 完成不同的策略变化
    • Adaapter 可以修饰或者套接functor

      内存分配

  • STL的allocate类 基本是 new 和 delete 的简单包装
  • new 操作包含 operator new 配置内存 和 对象初始化
  • delete 操作包含 对象析构 和 operator delete 释放内存
    再看STL源码剖析
  • STL的二级内存分配机制
    再看STL源码剖析
  • 次级空间配置实现方式:
    • 多级链表实现内存池,从8 ~ 128 字节不等,且以8字节对齐的链表节点,形成16个链表
      再看STL源码剖析
      再看STL源码剖析
  • 内存处理基本函数:判断是否会POD,POD直接复制或者填充,non- POD则构造填充
    再看STL源码剖析

迭代器与traits技法

  • 迭代器主要内容是:dereference 和 member access,核心是对 operator * 和operator -> 重载
  • 原生指针没有能力定义自己的型别,class-type iterators 都有能力且应该定义自己的相应型别
  • iterator_traits 必须对传入的pointer 和 pointer to const 设计特化版本
  • traits 技法 : 利用标签和c++重载机制,实现自动调用相应高效算法版本

序列容器

vector

  • 存储空间连续,空间不足时扩充,复制,清理原空间
  • 内存不足时,空间加倍
  • 连续空间,原生指针可以作为迭代器
  • 插入操作引起空间再分配,将使得迭代器失效
  • 三个标签实现空间管理: start finish end_of_storage
  • vector 动态本质: 空间不足时,申请大空间,将原空间元素复制到新空间,释放原空间(新空间配置导致迭代器失效)

list

  • 插入删除复杂度简单,空间不连续,指针连接,本质是双向循环链表
  • 移动增删基于指针操作
  • 不能直接使用STL的sort算法,因为其迭代器不是random access iterater

deque

  • 双向开口连续空间,双端可增删操作
  • deque 不存在容量概念,动态非配空间,排序则是先转存成vector,用STL排序后,存回deque
  • deque 首位定量申请新空间维持整体连续
  • deque 使用map维护分段,分段空间实现整体连续,迭代器检查缓冲区边界确定下一位置从而实现连续
  • 插入和删除主要工作在缓冲区边界检查和元素跨区移动

  • stack:配接器,底层以连续空间或者链表实现,无迭代器
  • queue: 封装deque,不可遍历,无迭代器

    heap

  • 底层连续空间(array,vector)实现
  • 尾部插入,上调至根节点;删除时将根节点置于尾部,上移原尾节点后缩小空间

关联容器

  • 底层封装rb_tree 实现set和map,根据是否允许键值重复衍生multiset和multimap
  • hashtable: buckets 以质数个节点指针的vector实现,每个vector元素为一个list头,维持一个链表
  • 基于hashtable实现hashset和hashmap元素无序,转调hashtable操作即可实现
  • hashtable 实现:桶质数个,保证填充率保证小于0.5,SGI STL桶内开链存储

仿函数

  • 仿函数型别主要用来表现函数参数型别和回传值型别
  • 仿函数对象或者无名临时对象用来履行函数功能