顺序容器

本内容摘自c++ primer 第9章

概述

SGI STL各种容器（本表以‘*’方式表达基层与衍生层的关系）

序列容器	备注	关联容器	备注
array	build-in	RB-tree	非公开
vector	—	*set	—
*heap	以算法形式呈现（xxx_heap）	*map	—
**priority-queue	—	*multiset	—
list	—	*multimap	—
slist	非标准	hashtable	非标准
deque	—	*hash_set	非标准
*stack	容器适配器	*hash_map	非标准
*queue	容器适配器	*hash_multiset	非标准
—	—	*hash_multimap	非标准

这里缩胃的衍生，并非派生（inheritance）关系，而是内含（containment）关系，例如heap内含一个vector，priority-queue内含一个heap，stack和queue都含一个deque，set/map/multiset/multimap都内含一个RB-tree，hash_x都内含一个hashtable。

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

• string 和vector：元素保存在连续内存空间中，所以元素下表取址非常快速。在中间位置插入或删除后，需要移动插入/删除之后的所有元素，来保持连续存储。添加元素时若需要分配额外存储空间，则需要将所有元素移动到新的存储空间中。
• list和forward_list：目的是令容器任何位置添加和删除操作都很快速，作为代价，这两个容器不支持元素的随机访问。与vector、deque和array相比，这两个容器额外内存开销也很大。
• deque：一个复杂的数据结构。与string和vector类似，deque支持快速随机访问，同时，中间位置添加或删除元素的代价（可能）很高，但是在两端添加或删除元素都很快，与链表速度相当。
• array：新添加的类型，与内置数组相比，array是一个更安全、更容易使用的数组类型。由于其大小固定，不支持添加删除元素和改变容器大小的操作。
• forward_list：设计目的是达到与最好的手写的单向链表数据结构相当的性能，因此没有size操作（保存或计算其大小回比手写链表多出额外的开销）。对其它容器而言，size是一个常量时间的操作。

Tip:

• 除非有更好的理由选择其它容器，否则应使用vector;
• 如果程序有很多小的元素，且空间的额外开销很重要，则不要使用list或forward_list;
• 如果程序要求随机访问元素，应使用vector或deque；
• 如果程序要求在容器中间插入或删除元素，应使用list或forward_list；
• 如果程序需要在头尾位置插入或删除元素，但不会在中间位置进行插入或删除操作，则使用deque；
• 如果程序只有在读取输入时才需要在容器中间插入元素，随后需要随机访问元素，尽量避免在中间位置添加元素，否则，先用list保存再用vector随机访问。

如果不确定使用哪种容器，通过使用迭代器而非下标操作，可以避免随机访问

迭代器

除每个容器定义的迭代器之外，在标准库头文件iterator中还额外定义了几种迭代器，包括：

• 插入迭代器：这些迭代器被绑定到一个容器上，可用来向容器插入元素；（back_inserter、front_inserter、inserter）
• 流迭代器：这些迭代器被绑定到输入或输出流上，可用来遍历所关联的IO流；(istream_iterator、ostream_iterator)
• 反向迭代器：这些迭代器向后而不是向前移动，除了forward_list之外的标准库容器都有反向迭代器；(.rend、.rbegin、.crend、crbegin)
• 移动迭代器：这些专用的迭代器不是拷贝其中的元素，而是移动他们。

算法所要求的迭代器操作可以分为5个迭代器类别：

类别	特征
输入迭代器	只读不写：单遍扫描，只能递增
输出迭代器	只写不读：单遍扫描，只能递增
前向迭代器	可读写：多遍扫描，只能递增
双向迭代器	可读写：多遍扫描，可递增递减
随机访问迭代器	可读写，多遍扫描，支持全部迭代器运算