表1 顺序容器的类型
| vector | 可变大小的数组. 支持文件快速随机访问. 在尾部之外的位置插入和删除元素的速度可能很慢 |
|---|---|
| deque | 双端队列. 支持快速随机访问. 在头尾插入和删除元素的速度很快. |
| list | 双向链表. 只支持双向顺序访问. 在list中任何位置插入和删除元素的操作都很快 |
| forward_list | 单向链表. 只支持单向顺序访问. 在链表任何位置进行插入和删除的操作都很快 |
| array | 固定大小的数组. 支持快速随机访问, 不能添加和删除元素 |
| string | 与vector相似的容器, 但专门用于保存字符. 随机快速访问速度快. 在尾部插入和删除的速度快 |
string和vector将元素保存在连续的内存空间中. 由于元素是连续存储的, 由元素的下标在来计算元素的地址非常快速. 但是在这两种容器中间插入和删除元素会非常耗时. 因为一次插入和删除操作之后, 需要移动插入/删除位置之后的所有元素, 来保持连续存储. 另外, 在添加一个元素时, 有时还可能需要额外分配内存, 这是可能需要将所有的元素移动到新的内存空间中.
list和forward_list两个容器的设计目的是令容器的插入删除操作都很快. 但是, 作为代价, 它们不支持随机访问. 并且由于这两个容器需要额外的指针域, 因此与vector, deque, array相比, 内存利用率较低.
deque是一种更加复杂的数据结构. 与string和vector类似, deque支持快速随机访问. 与string和vector一样, 在deque的中间位置添加/删除元素代价(可能)很高, 但是在两端进行插入和删除都是很快的, 速度与lisy和forward_lis添加和删除元素速度相当.