再看STL源码剖析

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

内存分配

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

迭代器与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桶内开链存储

仿函数

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