STL（Standard Template Library）
STL是C++标准模板库，是基于泛型编程的思想实现的，提供了容器、容器适配器、迭代器、空间适配器、函数对象和泛型算法。stl三类容器（顺序容器、关联容器、容器适配器）
顺序容器
vector
capacity：预设的容器大小(能装的元素数目)。
size：实际容器中的元素数目。
vector的底层是一个线性连续空间，是一个内存可以动态而被增长的数组，可以自行扩充容纳新元素，扩容策略是而被增长，它的二倍增长不是在原有空间上扩充，而是重新寻找空间，然后在新空间上对旧元素进行拷贝、再释放原空间。对vector的任何操作，一旦引起了空间的重新配置，那么指向原vector的所有迭代器就全部失效了，这是vector的push_back()可能带来的问题。
list
list是一个循环双向链表，底层并不保证结点空间的连续性，迭代器需要特殊处理。对list的insert操作不会导致迭代器失效，list不能使用stl泛型算法的sort和reserve，因为它们都需要具有随机访问迭代器，list 不具有。
deque
deque是一个双向开口的线性连续空间，它支持头尾的插入和删除、比vector更高效、提供随机访问，底层所维护的数据结构非常复杂，底层由一个动态的分段连续空间构成，即deque使有一段一段的丁连个连续空间构成，由中央map来维护整体连续的假象，map中存放的节点node指向一段连续空间，是deque的主体，称为缓冲区。deque 的缓冲区扩充策略是已存数据的缓冲区在 map 的中央区段，保证头部和尾部具有等量的插入能力。
容器适配器
stack
默认使用deque为底部容器。一种先进后出的数据结构，只有栈顶元素可以弹出，不允许有遍历行为。插入元素push()，删除元素pop()。
queue
默认使用deque为底部容器。一种先进先出的数据结构，有两个口，允许从尾端插入元素，从头部删除元素。
priority_queue
优先级队列，默认是大根堆，使用vector底部容器。在优先队列中，元素被赋予优先级，常用于构造堆。
关联容器
unordered_map
存储的机制是哈希表，内部的元素是无序的
unordered_set
存储的机制是哈希表，内部的元素是无序的
map
默认从小到大排序，有自动去重的功能。
存储键值对，底层是红黑树。会根据键值自动排序，不允许键值重复。
set
默认从小到大排序，有自动去重的功能。
存储值，底层是红黑树。会根据值自动排序，不允许值重复。
multimap
允许键值重复
multiset
允许键值重复
哈希表的原理，哈希函数，哈希冲突
原理：使用一个下标范围很大数组存储键值。当插入键值对时，并不是直接插入该数组中，而是通过对键进行Hash运算得到Hash值，然后和数组容量取模，得到在数组中的位置后再插入。
哈希冲突：影响哈希冲突的原因除了哈希函数还有数组本身的大小。如果数组非常大，则发生哈希冲突的可能性很低；若数组容量很小则，极端情况下为1，则一定发生哈希冲突。
哈希函数的分类：
- 直接定址法：直接使用key值本身或其线性函数作为hash地址，优点是简单、均匀、适合查找表的数据量小且连续的情况。
- 除留余数法：使用 key 模一个小于等于表长度的值作为 hash 地址，不仅可以对关键字取模，也可以对折叠法和平方取中法的结果取模。表厂最好为素数，可以减少 hash 冲突。
- 折叠法：把关键字分为相同的几部分，最后一部分的长度可以不同，然后将其叠加的和，舍去进位，作为 hash 地址。
- 平方取中法：取关键字平方后的中间几位作为 hash 地址。
- 随机数法：选择一个随机函数，取关键字的随机值作为 hash 地址。
解决哈希冲突的方法：
- 外部拉链法（常用）：使用链表对每一个hash地址维护一个桶节点，他们具有相同的key。
- 线性探测法：发生冲突后向后查找空闲的节点，查找到末尾后再从头开始查找。
- 二次探测法：发生冲突的地址为K，然后在K+12,K+22,K+32的节点位置查找。