容器¶
该笔记基于课程CS106L的学习，用于记录一些cpp的重要特性以及先前不曾了解的cpp特性。
容器（container），在C++中指一种能将其他对象聚合在一起，并能够通过某些方式与它们交互的对象。在前面的章节中，我们在程序中使用的vector就是容器的一种。
通常情况下，容器会提供一些标准、基本的功能：
-
允许储存相同类型的多个对象
-
允许使用某种方式访问容器内的元素，同时允许对所有元素进行迭代操作
-
可以对元素进行编辑/删除操作
容器在形式上可分为两种：序列容器和关联容器
序列容器¶
在序列容器中，元素能够按顺序访问。我们通常将具有线性规律的数据存放在序列容器中。
在实际开发中，我们最常使用的序列容器通常有std::vector和std::deque
std::vector¶
vector是由若干相同数据类型元素组成的大小可变的有序集合。本质上，vector就是一个大小可变的数组。
STL为vector提供了以下常用方法：
| 语法 | 效果 |
|---|---|
std::vector<int> nums | 创建一个int型空向量nums |
std::vector<int> nums(n) | 创建包含n个int型默认值的向量 |
std::vector<int> nums(n, e) | 创建包含n个int型，且数值为e的向量 |
nums.push_back(e) | 在nums的末端追加元素e |
nums.pop_back() | 删除nums的最后一个元素，但并不会返回这个元素 |
nums.empty() | 检查nums是否为空，并返回一个bool值 |
int e = nums[i] nums[i] = e | 访问或写入引索为i的元素。不进行边界检查（若超出边界则直接返回默认值或添加写入元素） |
int e = nums.at(i) nums.at(i) = e | 同上，但执行边界检查，超出边界则抛出错误 |
nums.clear() | 清空nums的所有元素 |
std::deque¶
与std::vector类似，但可从两端进行元素的插入或删除操作。
关于std::vector与std::deque的底层原理可直接参考CS106L的textbook
有关序列容器应用场景/特性与实现效率之间的关系，可使用以下表格概括：
| 使用场景 | std::vector | std::deque | std::list |
|---|---|---|---|
| 在前端插入/删除元素 | slow | fast | fast |
| 在末端插入/删除元素 | super fast | very fast | fast |
| 访问元素 | super fast | fast | x |
| 在内部插入/删除元素 | slow | fast | very fast |
| 内存占用率 | low | high | high |
| 组合操作（拼接/连接） | slow | very slow | fast |
| 稳定性（用于迭代/并发操作） | bad | very bad | good |
以上表格来源于CS106L的课程幻灯片。
对于序列容器，请记住以下几个要点：
-
需要对数据强制设定某种顺序时使用
-
std::vector可解决大多数应用场景 -
需要在容器开头插入元素时，
std::deque可能会是高效的选择 -
若需要将数据进行连接或与多个列表进行关联操作，考虑使用
std::list（这种情况非常少见）
关联容器¶
与序列容器不同，关联容器中并没有强制的线性顺序。同时，“关联”意味着其中的数据存在某种映射关系，这也使得其中的数据更加容易查找。在概念上，关联容器类似于Python中的dict和set，即存在唯一键值对的数据。
常用的关联容器有std::map<type1, type2>和std::set<type>。还需留意他们的无序版本：std::unordered_map<type1, type2>、std::unordered_set<type1>。注意，不要将这里的有序与无序（存储有序，按照键值进行排序）与序列容器中的线性有序（按照元素插入顺序进行排序）混淆。
std::map<type1, type2>¶
map基于成对的数据结构实现，在C++中即std::pair<type1, type2>。
需要特别注意，键的值必须是const的，即不可变的。对map进行引索操作（mapName[key]）会首先在成对的数据（std::pair）集合中查找第一个属性，即key，随后返回它的第二个属性value。
unordered_map/set¶
这里的无序并不是真正意义上的“无序”，而是将映射关系或元素比较的定义交由用户进行自定义——通常是一个哈希函数。在性能方面，一般情况下无序也比有序的要快。
哈希函数本质上就是将一些复杂对象映射为一串数字。对这个数字的计算过程就是所谓的“哈希”。
一个良好的哈希函数通常需要具备以下特征：
-
能够被快速计算
-
输入与输出具有唯一映射性
-
尽可能避免碰撞发生
无序容器的运行速度快，但似乎也就只有“快”而已。在处理嵌套容器/集合时，无序容器的复杂度较高。如需使用复杂的数据类型，或是不熟悉哈希函数，那么建议使用有序容器。