线性数据结构
- 数组/向量 vector
优点内存局部性好
下标直接访问 - 链表（基本操作）list
查找、插入、删除 带有哑结点的链表 - 栈 stack
深度优先算法 - 队列 queue
控制流程图算法 广度优先算法
集合和字典(set和map) 基于基本的线性结构
- 7大功能
查找、插入、删除 最小元 最大元 上一元素 下一元素 - 底层实现
可以使用无序数组、有序数组
使用二叉查找树来实现 保持平衡(红黑树) h=O(logn)
treap 树堆
堆结构（priority_queue）
- 优先级队列 下沉操作 上浮操作
散列(unordered_set) 优点快速查找
- 散列函数的设计
- 装填因子的选择 a = total/m格
- 底层实现 使用结链法
- 性能分析 最长链、平均链长
- 可用于字符串子串匹配 rabin-karp算法