51 vector中的size和capacity的区别
- size表示当前vector中有多少个元素（finish - start）;
- capacity函数则表示它已经分配的内存中可以容纳多少元素（end_of_storage - start）;
52 vector中erase方法与algorithn中的remove方法区别
- vector中erase方法真正删除了元素，迭代器不能访问了
- remove只是简单地将元素移到了容器的最后面，迭代器还是可以访问到。因为algorithm通过迭代器进行操 作，不知道容器的内部结构，所以无法进行真正的删除。
53 vector迭代器失效的情况
- 当插入一个元素到vector中，由于引起了内存重新分配，所以指向原内存的迭代器全部失效。
- 当删除容器中一个元素后,该迭代器所指向的元素已经被删除，那么也造成迭代器失效。erase方法会返回下 一个有效的迭代器，所以当我们要删除某个元素时，需要it=vec.erase(it);。
54 正确释放vector的内存(clear(), swap(), shrink_to_fit())
- vec.clear()：清空内容，但是不释放内存。
- vector().swap(vec)：清空内容，且释放内存，想得到一个全新的vector。
- vec.shrink_to_fit()：请求容器降低其capacity和size匹配。
- vec.clear();vec.shrink_to_fit();：清空内容，且释放内存。
55 list的底层原理
- ist的底层是一个双向链表，使用链表存储数据，并不会将它们存储到一整块连续的内存空间中。恰恰相反， 各元素占用的存储空间（又称为节点）是独立的、分散的，它们之间的线性关系通过指针来维持,每次插入或 删除一个元素，就配置或释放一个元素空间。
- list不支持随机存取，如果需要大量的插入和删除，而不关心随即存取
56 什么情况下用vector，什么情况下用list，什么情况下用deque
- vector可以随机存储元素（即可以通过公式直接计算出元素地址，而不需要挨个查找），但在非尾部插入删 除数据时，效率很低，适合对象简单，对象数量变化不大，随机访问频繁。除非必要，我们尽可能选择使用 vector而非deque，因为deque的迭代器比vector迭代器复杂很多。
- list不支持随机存储，适用于对象大，对象数量变化频繁，插入和删除频繁，比如写多读少的场景。
- 需要从首尾两端进行插入或删除操作的时候需要选择deque。
57 priority_queue的底层原理
- priority_queue：优先队列，其底层是用堆来实现的。在优先队列中，队首元素一定是当前队列中优先级最 高的那一个
58 map 、set、multiset、multimap的底层原理
m a p 、 s e t 、 m u l t i s e t 、 m u l t i m a p 的 底 层 实 现 都 是 红 黑 树 ， e p o l l 模 型 的 底 层 数 据 结 构 也 是 红 黑 树 ， l i n u x 系 统 中 C F S 进 程 调 度 算 法 ， 也 用 到 红 黑 树 。
红 黑 树 的 特 性 ：
- 每个结点或是红色或是黑色；
- 根结点是黑色；
- 每个叶结点是黑的；
- 如果一个结点是红的，则它的两个儿子均是黑色；
- 每个结点到其子孙结点的所有路径上包含相同数目的黑色结点
59 为何map和set的插入删除效率比其他序列容器高
- 因为不需要内存拷贝和内存移动
60 为何map和set每次Insert之后，以前保存的iterator不会失效？
- 因为插入操作只是结点指针换来换去，结点内存没有改变。而iterator就像指向结点的指针，内存没变，指 向内存的指针也不会变。
61 当数据元素增多时（从10000到20000），map的set的查找速度会怎样
变化？
- RB-TREE用二分查找法，时间复杂度为logn，所以从10000增到20000时，查找次数从log10000=14次到 log20000=15次，多了1次而已
62 map 、set、multiset、multimap的特点
- set和multiset会根据特定的排序准则自动将元素排序，set中元素不允许重复，multiset可以重复。
- map和multimap将key和value组成的pair作为元素，根据key的排序准则自动将元素排序（因为红黑树也是 二叉搜索树，所以map默认是按key排序的），map中元素的key不允许重复，multimap可以重复。
- map和set的增删改查速度为都是logn，是比较高效的
63 为何map和set的插入删除效率比其他序列容器高，而且每次insert之后，
以前保存的iterator不会失效？
- 存储的是结点，不需要内存拷贝和内存移动。
- 插入操作只是结点指针换来换去，结点内存没有改变。而iterator就像指向结点的指针，内存没变，指向内 存的指针也不会变。
64 为何map和set不能像vector一样有个reserve函数来预分配数据?
- 在map和set内部存储的已经不是元素本身了，而是包含元素的结点。也就是说map内部使用的Alloc并不是 map<Key, Data, Compare, Alloc>声明的时候从参数中传入的Alloc。
65 set的底层实现实现为什么不用哈希表而使用红黑树？
- set中元素是经过排序的，红黑树也是有序的，哈希是无序的
- 如果只是单纯的查找元素的话，那么肯定要选哈希表了，因为哈希表在的最好查找时间复杂度为O(1)，并且 如果用到set中那么查找时间复杂度的一直是O（1），因为set中是不允许有元素重复的。而红黑树的查找时 间复杂度为O(lgn)