常用数据结构
- 数组
- 栈
- 队列
- 链表
- 树
- 图，最短路径的查询，
- 哈希表,把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。
C++中数据组织方式
- 数组，内置的数据类型，存放类型相同的对象的容器，数组的大小确定不变，不能随意向数组中增加元素
- 存放在栈中，其内存的分配和释放完全由系统自动完成
- vector 封装数组，连续内存，vector的大小可以变化，可以向数组中增加元素
- 支持随机访问即[]或vector.at()
- 存放在堆中，由STL库中程序负责内存的分配和释放，使用方便。
- 执行效率，数组>vector向量。主要原因是vector的扩容过程要消耗大量的时间
- list 封装了双向链表
- 内部插入、删除方便;不支持随机访问([]),单个元素内存相对占用内存大
- deque 双向队列，多个连续内存，功能上合并了vector和list。
- 支持随机访问，内部插入删除方便；占用内存大
- 注：vector，高效的随即存取，而不在乎插入和删除的效率
list，大量的插入和删除，而不关心随即存取
deque，随即存取，而且关心两端数据的插入和删除
- stack 基于deque实现，封装栈
- queue 基于deque实现，封装了队列
- map 红黑树实现，提供key-value的存储和查找功能
- set 平衡二叉树实现，时间复杂度O(lgN);类似于集合，里面的元素不会重复，而且呈现为有序性
- multiset 平衡二叉树实现，允许有重复元素
- hash_set 底层用hash table实现，时间复杂度取决于哈希函数和哈希负载情况;里面的元素不会重复。
- hash_map,基于hash table实现，提供key-value的存储和查找功能
