- 组件关系
- container 通过容器allocator 获得数据空间
- Algorithm 通过迭代器存取container 内容
- functor 协助 Algorithm 完成不同的策略变化
-
Adaapter 可以修饰或者套接functor
内存分配
- STL的allocate类 基本是 new 和 delete 的简单包装
- new 操作包含 operator new 配置内存 和 对象初始化
- delete 操作包含 对象析构 和 operator delete 释放内存
- STL的二级内存分配机制
- 次级空间配置实现方式：
- 多级链表实现内存池，从8 ~ 128 字节不等，且以8字节对齐的链表节点，形成16个链表
- 多级链表实现内存池，从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桶内开链存储
仿函数
- 仿函数型别主要用来表现函数参数型别和回传值型别
- 仿函数对象或者无名临时对象用来履行函数功能