STL笔记1

顺序容器有vector、list、deque。
关联容器有map、set。
容器类自动申请和释放内存，无需new和delete操作。
但是需要连接STL各个容器的内存管理

STL六大组件：
容器，算法，迭代器，仿函数、适配器和空间配置器
容器：容纳一组元素的对象
迭代器：提供一种访问容器中每一个元素的方法
适配器：用来修饰容器，比如queue和stack，底层借助了deque。
空间适配器：负责空间配置和管理

空间配置器：
对象构造前的空间配置和对象析构后的空间释放，由负责。
设计哲学如下：
先system heap要求空间
考虑多线程状态
考虑内存不足时的应变措施
考虑碎片问题

对于碎片问题，有双层及配置器:
第一级直接使用allocate()调用malloc()、deallocate()调用free()，使用类似new_handler机制解决内存不足（抛出异常），配置无法满足的问题（如果在申请动态内存时找不到足够大的内存块，malloc 和new 将返回NULL 指针，宣告内存申请失败）。

第二级视情况使用不同的策略，当配置区块大于128bytes时，调用第一级配置器，当配置区块小于128bytes时，采用内存池的整理方式：配置器维护16个（128/8）自由链表，负责16种小型区块的此配置能力。内存池以malloc配置而得，如果内存不足转第一级配置器处理。

1、第一级配置器详解

2、第二级空间配置器详解
第二级空间配置器实际上是一个内存池，维护了16个自由链表。自由链表是一个指针数组，有点类似与hash桶，它的数组大小为16，每个数组元素代表所挂的区块大小，比如free list[0]代表下面挂的是8bytes的区块，free list[1]代表下面挂的是16bytes的区块…….依次类推，直到free _ list[15]代表下面挂的是128bytes的区块。

3、空间配置器存在的问题
自由链表所挂区块都是8的整数倍，因此当我们需要非8倍数的区块，往往会导致浪费。

由于配置器的所有方法，成员都是静态的，那么他们就是存放在静态区。释放时机就是程序结束，这样子会导致自由链表一直占用内存，自己进程可以用，其他进程却用不了。

各种容器的特点和适用情况：
vector:可变大小的数组，支持快速随机访问，在尾部之外的位置插入或删除元素会较慢。
deque：双端队列，支持快速随机访问，在头尾位置插入删除速度快。
list：双向链表，只支持双向顺序访问，在list任何位置插入/删除速度都很快。
forward_list：单向链表，只支持单向顺序访问
array：固定大小的数组支持随机访问，不能添加或者删除元素。
string：和vector相似，随机访问快，在尾位置插入/删除元素快。