函数默认参数
int func(int a = 100, char c = 'h');
参数列表显式初始化后，调用的时候可以按照顺序选择不传递参数，此时函数会采用默认值。
Output parameter
除了tuple和pair，另一种返回多个值的方法是：传入参数时使用引用，这样就可以直接在函数里改变变量值，而不用返回。
文件流
参照CS106L stringstream操作，很相似。
collections
Vector：灵活的数组
grid：灵活的二维数组
允许创建collection的collection
linkedlist：链表，插入比vector更快，但占用内存多，且查询访问慢
stack：栈
queue：队列
Recursion
解决此类问题的时候，尽量避免arm's length recursion，同时先判断base case，再解决递归。
Avoid arm's length：只关注本节点的东西
搞清楚此类问题是permutation（排列）还是sublist（子列），两者所需递归次数不同。
C++ STL sequence vector工作方式
根据初始化，动态申请一个内存区域（C++数组）。
有两个表示容量的变量：size和capacity，size代表当前存储的数据数量，capacity代表当前动态数组能存储的最大数量。
当进行push操作时，若size已经达到capacity上限，则进行扩容：申请一片新的内存，将原来数据复制到新内存，再进行push操作。
Priority queue
根据权重，出队列的第一个是最优先的元素。
Implement methods
sorted/unsorted array
sorted/unsorted linkedlist
heap
树结构，root为最优先元素。
使用顺序容器存储，root下标为1，父节点下标为n/2，子节点下标为n2和n2 + 1。
父节点永远比子节点优先。
当插入新元素时，先将新元素放在最后，再将其与父节点比较，根据优先级进行交换（递归过程）。
当出队列时，将最后的元素放到root节点上，再与子节点比较，根据优先级进行交换（递归，与weight最小的子节点进行交换）。
操作复杂度为O(logN)。
Heap是一种特殊的二叉树，因为除了最后一层，其他层级都是满的。
BST：binary search tree
set和map的底层原理。
root节点的左子节点总比root小，右子节点总比root大。
remove
没有子节点的，直接移除。
只有左节点或者只有右节点的，移除自身后，将子节点放到自身位置。
既有左节点又有右节点的，移除自身后，将左子树的最大值或者右子树的最小值放到自身位置，并且易知左子树的最大值或者右子树的最小值是前两种情况之一。
如果需要平衡，详见红黑树。
BST和快速排序的相像之处
Trie
用于字符串存储检索。 节点结构为{bool flag; Node* nexts[26];} 二十六个子节点分别代表二十六个字母。
Huffman Coding
一种编码方式，相对于ASCII码能够节省空间（对出现频次高的字符分配较短的码）。 各字符编码长度的不统一，要求编码必须是prefix free coding，huffman coding就是寻找最佳的prefix free coding的一种方法。
算法
构建一个存储树的pqueue。
将原始文本的每个互不相同的字符作为单独的树节点添加到pqueue里去，权重为frequency。
当pqueue内元素大于等于两个时：
取前两个元素，将它们结合形成新树，父节点的0和1指针分别指向这两个元素，新树的权重为两个子树权重之和，再把新树重新入队列。
DFS
使用递归结构搜索。
BFS
借助Queue，逐层进行搜索。
dijkstra
借助PQueue，进行最短路计算。
算法
初始化：将起点入队。起点cost为0，其他点cost为无穷大。
当队列不为空：
出队列，标记该点，对于该元素的（未被标记的）邻接点：
计算从当前点到该邻接点的costTemp。
将costTemp与该邻接点的cost比较，并将cost替换为较小的cost，修改该邻接点的previousVertex。
最后：若要输出路径，则可从终点通过previousVertex一路追踪。
相关：贪心，DP，记忆化，子问题。
A*
通过更改PQueue的排序依据，在dijkstra基础上实现启发式搜索，只需将上述的cost，更改为cost + H，H为启发式函数，用来进行搜索优先级引导。
MST
Spanning tree
图连通，且无环。 例如，解决城市供应链问题（disaster planning）。
寻找MST（所有边权重和最小）算法
如何判断两个点是否连通？
无需每次都进行搜索，使用cluster方法。
一开始每一个点都在一个cluster里，当添加新边时，合并两个端点所在的cluster。
判断连通时，也只需判断一个端点的cluster是否包含另一个端点。使用set实现。
How to implement a graph?
edge list：使用一个容器存储边，每一个元素就是一条边，添加方便，但查询需要O（E）复杂度。
adjacency list：对于每一个顶点，维护一个邻接点列表，查询方便，添加新顶点需要更新其所有邻接点的列表。
adjacency matrix：邻接矩阵，查询特定边最方便，但在有些情况下会存在空间浪费，并且添加新顶点也更复杂。
Hashing
底层存储结构是一个数组，将要存储的数据本身经过变换，变换成一个hash code，作为存在数组里的下标，变换函数叫做hash function。 基本上所有操作都是O(1)复杂度。
解决collision
probing：若当前下标被占用，则顺延至下一个最近的未被占用的下标。
separate chaining：若一个下标有collision，就创建一个链表，存储所有对应此下标的元素。
当一个下标链表下的元素越来越多时，时间复杂度会增大，此时考虑扩容，也考虑将链表转换为树。
扩容
需要将所有元素都重新hash一遍。
Robin Hood Hashing
对probing hashing方法的补充。
实现
每个元素在插入的时候都记录其真实下标与原下标的距离，记为哈希代价。
插入元素时，若找到空位置，则插入，若位置已被占用，则比较哈希代价，若当前元素哈希代价较大，则占据此位置，原先的元素按照此规则重新插入到表内；若当前元素代价小于等于原元素，则顺延检查下一个元素，直到遇到空位置或者代价小于要插入元素的元素。
删除元素时，直接删除要插入的元素，并查看后一个元素，若后一个元素代价不为零，则移到前一个位置，同时代价减一，如此顺延，直到后一个元素的代价为零或者后一个元素是空位置。
查找元素时，从原位置开始找起，结束条件为：
找到元素。
当前位置元素的代价小于这个位置到原点的距离。
找到空位置。
数组大小有限时，若查找的位置超过capacity，则取模。
Inheritance
使用private关键字继承：有些时候子类并不完全支持父类的操作，或者父类的操作对子类不合实际，但子类又想继承父类的部分代码，就需要用private关键字继承，使得client端不能调用来自父类的函数。