C++ 常见容器

迭代器。

顺序容器。

通用概念。

　　顺序容器基本理解：按照顺序储存元素，并提供 元素具体操作(迭代器或其他) 和 顺序访问元素 的能力。

　　个人理解：

　　　　1）顺序：按照添加的先后次序排序。但，先进优先，还是后进优先取决于具体容器。

　　个人应用：

　　　　1）在可以使用容器时，尽量使用容器。因为你无法保证自己的算法优于整个开发组。

　　　　2）选择容器的基本原则（from C+ primer）：

　　　　　　1，在不知道如何选择时，使用vector。

　　　　　　2，单个元素需求内存很小，内存紧缺时，不要使用list/forward_list。

　　　　　　3，已知添加操作时，尽量使用符合 原设计思想 的容器。例如：频繁的随机插入/删除，使用list/forward_list,而尽量不使用vector,deque。

　　　　　　4，举一反三：混合添加操作时，选择最频繁的添加操作，作为选择容器的标准。例如：100次后置添加 + 一次随机操作时，选择vector,deque。反之：list/forward_list。

　　　　　　5，举一反三：添加操作在某些阶段存在统一，则可以进行容器替换。例如：输入元素使用 list。输入结束后，使用vector储存(copy list)，再进行读取操作。

　　　　3）尽量使用迭代器来操作容器——虽然有些容器支持下标。

vector容器：

　　一些细节：

　　　　1）使用连续内存保存元素。

　　　　2）可以下标访问元素（速度快）。可是当作动态数组使用。

　　　　3）中间添加/删除元素耗时。因，需要重新调整内存。同时会导致迭代器失效(大概率)。

　　　　4）添加新元素时（push_back），也可能重新分配内存。导致迭代器失效（中概率）。

　　　　5）容器存在增长方式：超出时，按照一定量增加内存，以保证添加数个元素后，才需要再次分配内存。量值可通过函数设定（不建议）。

deque容器：

　　一些细节：

　　　　1）使用连续内存保存元素。

　　　　2）不确定是否可以使用下标访问。

list容器：双向链表。

　　一些细节：

　　　　1）使用链表的思想。

　　　　2）额外内存开销相对较大。

　　　　3）不支持下标。

forward_list容器：

　　一些细节：

　　　　1）和list容器类似。

　　　　2）主要特征：单向链表。

array容器：

　　一些细节：

　　　　1）对数组的封装。加强安全性。

　　　　2）有数组的特性。

string容器：

　　一些细节：

　　　　1）使用连续内存保存元素。

　　　　2）用来保存字符串。

适配器：

　　概念：一个适配器是一种机制。通过适配器，可以使容器从行为上模仿其他数据结构。

　　顺序容器可用适配器：stack, queue, priority_queue。

　　个人理解：用来模拟一些通用的数据结构。如上：堆栈，队列。

　　疑惑：为何不直接做成容器？

无序容器。

基本常识：

　　1）主要为：map 和 set。衍生型：multi和unorder.例如：multimap, unorder_multimap.

　　2）使用pair作为单位元素。

　　　　1，key-value组成一个pair.

　　　　2，first成员：key。second成员：value。

　　　　3，key为const类型不可改变。

　　3）关联容器的构成：key-pair.

基本要点：

　　1）通常不对关联容器使用 泛型算法。

　　2）有序关联容器，有 严格弱序 的要求。默认使用 [<=]。当然，也可以使用谓词或lambda表达式来自定义。