各种数据结构及其底层实现

• vector：底层数据结构为数组，支持快速随机访问。
  • 扩容规则为：当新建一个 vector 时，会首先分配一块连续的内存空间，当向其中增加元素是，如果初始分配空间已满，就会引起 vector 扩容。首先重新申请一个 2 倍大的内存空间；然后将原空间的内容拷贝过来；最后将原空间内容进行释放，将内存交还给操作系统。
  • 在插入位置和删除位置之后的多有迭代器和指针引用都会失效，同理，扩容之后的所有迭代器指针和引用也都会失效。
• list：双向链表，支持快速增删。
• deque：底层为一个中央控制器和多个缓冲区，支持收尾快速增删，也支持随机访问。deque是一个双端队列（double-ended queue），看起来像是 list 和vector的结合品。
• stack：底层一般用 list 或deque实现，封闭头部即可，不用 vector 的原因是容量大小有限制，扩容耗时。
• queue：单向队列，为先入先出原则。
• proority_queue：根据堆的处理规则来调整元素之间的位置，优先级队列相当于一个有权值的单向队列 queue，在这个队列中，所有元素是按照优先级排列的。
  根据堆的特性，优先级队列实现了 取出最大最小元素 时间复杂度为 , 对于 插入和删除，其最坏情况为。
• set：红黑树，有序，不重复。
• multiset：红黑树，有序，可重复。
• map：红黑树，有序，不重复，可以实现 的查找，插入和删除。
• multimap：红黑树，有序，可重复，可以实现 的查找，插入和删除。
• unordered_set：hash 表，无序，不重复。
• unordered_multiset：hash 表，无序，不重复。
• unordered_map：hash 表，无序，不重复，查找 时间复杂度理论上达到了。
• unordered_multimap：hash 表，无序，不重复，查找 时间复杂度理论上达到了。