9.1 顺序容器概述

一个容器就是一些特定类型对象的集合。顺序容器提供了控制元素和存储和访问的能力。这种顺序不依赖于元素的值，而是与元素加入容器时的顺序相对应。标准库提供了三种容器适配器，分别为容器操作定义不同的接口，来与容器类型适配。

不同容器类型在一下方面会有不同的性能折中：

1. 向容器添加或从容器中删除元素的代价。
2. 非顺序访问容器中元素的代价。

string和vector将元素保存在连续的内存空间中。

list、forward_list不支持随机发访问，只能遍历整个容器来访问元素，内存开销也很大。

deque支持随机访问，但在两端插入/删除元素的速度和list、forward_list相当。

array与内置数组相比，是一种更安全、更容易使用的数组类型。

forward_list的设计目标是达到与最好的手写单向链表数据结构相当的性能，因此它没有size操作，因为保存或计算其大小会比手写链表多出额外的开销。对其他容器而言，size保证是一个快速的常量时间的操作。

• 确定使用哪种顺序容器

1. 除非你有充分的理由使用别的容器，否则应使用vector。
2. 如果程序有很多小的元素，而且空间的额外开销极为重要，则不要使用list、forward_list。
3. 如果程序要求随机访问元素，应使用vector、deque。
4. 如果程序要求在容器的中间插入或删除元素，应使用list、forward_list。
5. 如果程序需要在头尾插入或删除元素，但不会在容器的中间插入或删除元素，则使用deque。
6. 如果程序只有在读取输入时才需要在容器的中间位置插入元素，最后需要随机访问元素，则：

• 首先，确定是否真的需要在容器中间位置添加元素。当处理数据时，通常可以很容易的向vector追加数据，然后再调用标准库的sort函数来重排容器中元素，从而避免中间位置添加元素。
• 如果必须在中间位置插入元素，考虑在输入阶段使用list，一旦输入完成，将list中的内容拷贝到vector中。 如果程序即需要随机访问元素，又要在容器中间位置插入元素，可以用不同容器分别测试应用的性能。