顺序容器概述

容器会在以下方面都有不同的性能折中

  • 向容器添加或容器中删除元素的代价
  • 非顺序访问容器中元素的代价

各种容器的特点

类型 特点
vector 可变大小数组。支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢
deque 双端队列。支持快速随机访问。在头尾位置插入/删除速度很快
list: 双向链表。只支持双向顺序访问。在list中任何位置进行插入/删除操作速度都很快
forward_list: 单向链表。只支持单向顺序访问。在链表任何位置进行插入/删除操作速度都很快
array 固定大小数组。支持快速随机访问。不能添加或删除元素
string 与vector相似的容器，但专门用于保存字符。随机访问快。在尾部插入

除了固定大小的array外，其他容器都提供高效，灵活的内存管理。

string和vector将元素保存在连续的内存空间中。由于元素是连续存储的，由元素的下标来计算其地址是非常快速的。但是，在这两种容易的中间位置添加或删除元素就会非常耗时：在一次插入或删除操作后，需要移动插入/删除位置之后的所有元素，来保持连续存储。而且，添加一个元素有时可能还需要分配额外的存储空间。在这种情况下，每个元素都必须移动到新的存储空间中。

list和forward_list两个容器的设计目的是令容器任何位置的添加和删除操作都很快速。作为代价，这两个容易不支持元素的随机访问：为了访问一个元素，我们只能遍历整个容器。而且，与vector、deque和array相比，这两个容器的额外内存开销也很大。

deque是一个更为复杂的数据结构。与string和vector类似，deque支持快速的随机访问。与string和vector一样，在deque的中间位置添加或删除元素的代价很高。但是，在deque的两端添加或删除元素都是很快的，与list或forward_list添加删除元素的速度相当。