第三部分：容器

# 第三部分：容器

储存和管理多个数据元素的各类集合型的数据结构，也称为容器(container)或者集合(collection)。

常见的容器类型：

数组(array)：连续存储数据的集合，使用索引存取元素。数组尺寸通常是在编译器静态定义的。数组可以是多维度的。
动态数组(dynamic array)：运行期可以动态改变长度的数组。(例如std::vector)
链表(linked list)：有序集合，但是数据是非连续储存的。（例如std::list）
堆栈(stack)：后进先出的数据集合。
队列(queue)：先进先出的数据集合。
双端队列(deque)：可以在两端高效地插入移除数据元素的队列。
优先队列(priority queue)：可以优先弹出队列中最高优先值元素的队列，通常使用二叉堆实现。(例如std:priority_queue)
树(tree)：使用层级结构的数据结构。每个数据元素有0个或者1个父节点以及0个或者多个子节点。树是一种有向非循环图。
字典(dictionary)：由键值对组成的表通过键可以高效地查找到对应的值。字典实现方式一般是散列表(hash table)。字典又称为映射(map)。
图(graph)：元素节点之间可任意以单向或者双向连接。

一、容器操作

插入(insert)：在容器中新增元素。

移除(remove)：从容器移除元素。

顺序访问/迭代(seq-access/iteration)：按照次序访问容器内每个元素。

随机访问(random access)：以任意次序访问元素。

查找(find)：查找合乎条件的元素。

排序(sort)：把元素以某种方式排序。

二、迭代器

迭代器是一种轻量的对象。用于高效访问容器元素，每次它都会指向某个元素，并且可以移至下一元素。

迭代器相比直接访问的优点：

直接访问会破坏类的封装。而迭代器通常是容器类的友元，因此可以高效地迭代访问容器，而不会暴露容器类的实现。（多数容器会隐藏内部细节，不使用迭代器无法访问）
迭代器简化了迭代过程。使一些复杂的遍历算法使用起来像数组迭代一样简单。

迭代中的前置递增和后置递增：

后置递增p++需要传回未递增的值。所以后置递增必须先备份旧值，然后递增，然后传回之前的备份。（对于指针或者整数索引问题不大，但是对于迭代器来说备份过程涉及对象构造和复制）
前置递增++p只需简单地递增后，再传回其值。（最好尽量任何时候都使用前置递增）

三、容器的算法复杂度和内存布局

复杂度：

选择容器时，应当考虑容器各种操作(插入/移除/查找/排序)算法的复杂度。（用大O表示算法复杂度数量级）

由最快到最慢排序：$O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(N^k)$

内存布局：

数组把元素连续地置于内存中(连续内存是缓存友好的)，而且没有额外的内存开销。（动态数组需要很小的固定额外开销）

链表把元素置于节点结构中，结构中含指向其他元素的指针，所以会有额外内存开销。而且链表节点一般在内存中不连续。

数组相比链表有更好的缓存性能。但是如果插入移除元素的速度更重要，则应该使用链表。

四、使用自定义的容器数据结构还是第三方实现？

第三方库和实现：

STL:

STL功能丰富并且几乎所有C++编译器都带有STL。缺点是通常比自定义数据结构慢。并且内存占用多，会进行很多动态内存分配。（例如如果把一个网格所有顶点加进std:list或者给网格每个顶点都加一个std:list的情况都应该避免）

所以STL更适合PC游戏，不适合主机游戏，因为PC有高效的虚拟内存。所以使用了STL的游戏不好移植。

若要支持多平台，可以使用STLport。兼容多个平台，比STL更高效并且功能更丰富。

Boost:

Boost提供很多STL没有的功能，能处理很多复杂的问题。缺点不适合小型项目，因为可能会生成很大的lib文件。（使用Boost应该注意许可证问题）

Loki:

著名的C++模板元编程(TMP)库。

动态数组：

数组是缓存友好的数据类型。当数组的大小不能再编译时决定时，如果想维持固定大小数组的效能，可以使用动态数组。（STL的std:vector就是动态数组）

动态数组的最简单实现方法是开始时就分配n个元素的缓冲区，当缓冲区满的时候就扩大换大缓冲区。扩大的方法是分配一个更大的缓冲区，把原来的数据复制过去，再释放原缓冲区。

动态数组也有很多问题，分配内存和复制数据有很多效能代价，释放就缓冲区也会产生内存碎片。能使用固定大小数组就尽量使用固定大小数组。

链表：

如不用考虑内存连续性，只希望在任何位置高校插入和移除元素，则可以使用链表。

链表是由节点组成的，每个节点都有指向下一节点的指针（如果是双向链表则还有指向前一节点的指针）。完整的链表一般还包含指向链表头尾的指针。

⭐外露式链表：

外露式链表的节点数据结构和元素数据结构是独立分离的。外露式链表不负责元素数据结构的内存分配。节点仅包含指针指向元素。
元素能置于多个外露链表。
建议使用池分配器分配节点。（节点大小是一样的）

节点数据结构示例：

template<typename ELEMENT>
struct Node{
    Node<ELEMENT>* prev;
    Node<ELEMENT>* next;
    ELEMENT * ele;
}

⭐侵入式链表：

节点数据结构直接嵌入元素数据结构。
实现一：定义为元素数据结构的成员。
实现二：元素类继承自节点类。（两种方法几乎等同，但是第二种实现可以把节点指针直接转型为元素指针）。
优点是不用再单独为节点数据结构分配内存。
一个元素只能对应一个节点数据，所以不能置于多个链表中。
侵入链表需要修改元素数据结构。如果元素的类来自第三方库，就必须修改库的源代码。

节点数据结构示例：

template<typename ELEMENT>
struct Node{
    Node<ELEMENT>* prev;
    Node<ELEMENT>* next;
}

⭐一种含头节点的循环链表：

循环链表把链表的头指针和尾指针放进一个头节点。next指向第一个元素，prev指向最后一个元素，形成一个循环的结构。

⭐单向链表：

单链表的节点只存储指向后节点的指针。节省了一些内存，但是使得插入元素和移除元素更耗时。（除非是在头部插入和移除）

字典和散列表：

⭐字典的二叉排序树实现：

键值对储存在二叉树的节点里，而整棵树则是按照键值排序节点的。（二叉查找复杂度O(logn)）

⭐字典的散列表实现：

所有值存储在固定大小的表里，表的每个位置对应到一个或者多个键。

查找键值方式：

把键用散列算法转换为整数。（如果键不是整数）
散列后的整数模除(mod)表的大小求得表的索引。

⭐碰撞（冲突）：

多个键占用同一位置的时候称为碰撞。

有两种方式解决碰撞：

开放式散列：碰撞发生时会有多个键值存储在同一位置，通常以链表形式。（即拉链法）
闭合式散列：发生碰撞时用算法探查(probe)空闲位置。（难以实现）（需要设定表的容量）（不用分配动态内存，游戏引擎推荐使用）

CRE：探查可以用(1, -1, 4, -4, 9, -9, ….)类推。

⭐散列函数：

$h = H(k)$

散列函数必须是deterministic的，即相同输入不会产生的输出完全相同。良好的散列应该能把所有有效键平均分散至整个散列表从而把碰撞机会降至最低。散列函数的运算时间也需要够快。

如果键本身为整数，则$H(k) = k$。
如果键为32位浮点数，则散列函数可以仅仅把其位模式(bit pattern)诠释为32位整数。
如果键为字符串，则要使用字符串散列函数，把字符串中所有字符的ASCII码或者UTF码合并为单个32位整数。
好用的字符串散列算法有LOOKUP3、CRC32、MD5等。（MD5运算成本很高但是能产生非常好的结果）

⭐闭合散列表使用的探查算法：

线性探查(linear probing)：如果位置i被占用，则去查找$(i ± 1)$、$(i ± 2)$、$(i ± 3)$位置。

二次探查(quadratic probing)：如果位置i被占用，则去查找$(i ± 1^2)$、$(i ± 2^2)$、$(i ± 3^2)$等位置。

质数大小的散列表结合二次探查，效果非常好。