- 顺序容器概述
- 一、顺序容器类型
- 二、选择容器的原则
- 确定使用哪种顺序容器
顺序容器概述
一个容器就是一些特定类型对象的集合，顺序容器为程序员提供了控制元素存储和访问顺序的能力。这种顺序不依赖于元素的值，而是与元素加入容器时的位置相对应。
一、顺序容器类型
除了固定大小的array外，其他容器都提供高效、灵活的内存管理。我们可以添加和删除元素，扩张和收缩容器的大小。容器保存元素的策略对容器操作的效率有着固有的，有时是重大的影响。在某些情况下，存储策略还会影响特定容器是否支持特定操作。
例如，string和vector将元素保存在连续的内存空间中。由于元素是连续存储的，由元素的下标来计算其地址是非常快速的。但是，在这两种容器中的中间位置添加或删除元素就会非常耗时：在一次插入或删除操作后，需要移动插入/删除的位置之后的所有元素，来保持连续存储。而且，添加一个元素有时可能还需要分配额外的存储空间。在这种情况下，每个元素都必须移动到新的存储空间。
list和forward_list两个容器的设计目的是令容器任何位置的添加和删除操作都很快速。作为代价，这两个容器不支持元素的随机访问：为了访问一个元素，我们只能遍历整个容器。而且，与vector、deque和array相比，这个容器的额外内存开销很大。
deque是一个更为复杂的数据结构。deque内部有个中控器，维护每段缓冲区中的内容，缓冲区中存放真实的数据，中控器维护的是每个缓冲区的地址，使得使用deque时像一边连续的内存空间。因此与string和vector类似，deque支持快速的随机访问。与string和vector一样，在deque的中间位置添加或删除元素的代价（可能）很高。但是，在deque的两端添加或删除元素都是很快的，与list或forward_list添加删除元素的速度相当。
forward_list和array是新C++标准增加的类型。与内置数组相比，array是一种更安全、更容易使用的数组类型。与内置数组类似，array对象的大小是固定的。因此，array不支持添加和删除元素以及改变容器大小的操作。forward_list的设计目标是达到与最好的手写的单向链表数据结构相当的性能。因此，forward_list没有size操作，因为保存或计算其大小就会比手写链表多出额外的开销，对其他容器而言，size保证是一个快速的常量时间的操作。 二、选择容器的原则 确定使用哪种顺序容器 通常，使用vector是最好的选择，除非你有很好的理由选择其他容器。
以下是一些容器的基本原则
- 除非你有很好的理由选择其他容器，否则应使用vector
- 如果你的程序有很多小的元素，且空间的额外开销很重要，则不要使用list或forward_list。
- 如果程序需要在头尾位置插入或删除元素，但不会在中间位置精选插入或删除元素操作，则使用deque
- 如果程序要求随机访问元素，应使用vector或deque
- 如果程序要求在容器的中间插入或删除元素，应使用list或forward_list。
- 如果程序只有在读取输入时才需要在容器中间位置插入元素，随后需要随机访问元素，则
- 首先，确定是否真的需要在容器中间位置添加元素。当处理输入数据时，通常可以很容易地向vector追加数据，然后再调用标准库的sort函数来重排容器中的元素，从而避免在中间位置添加元素。
- 如果必须在中间位置插入元素，考虑在输入阶段使用list，一旦输入完成，将list中的内容拷贝到一个vector中。
