顺序容器有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相似,随机访问快,在尾位置插入/删除元素快。