STL容器
[TOC]
1. std::vector的底层存储机制
vector是一个动态数组，里面有一个指针指向一片连续的内存空间，当空间不够装下数据时，会自动申请另一片更大的空间。（通常是当前容量的50%或者100%），然后把原来的数据拷贝过去，接着释放原来的那片空间；当释放或者删除里面的数据时，其存储空间不释放，仅仅是清空了里面的数据。
2. std::vector的自增长机制
同一
3. std::list的底层存储机制
以节点为单位存放数据，节点的地址在内存中不一定连续，每次插入或者删除一个元素，就配置或者删除一个元素空间。
4. 什么时候用vector，什么时候用list
vector可以随机存储元素（可以通过公式直接计算出元素地址，而不需要挨个查找），但在非尾部插入或者删除数据时，效率很低，适合对象简单，对象数量变化不大，随机访问频繁的数据。
list不是随机存储，适用于对象大，对象数量变化频繁，插入和删除频繁的数据操作
5. list自带的排序函数的排序原理
6. vector和list的插入删除有啥区别
vector的插入和删除，需要对现有数据进行复制移动，如果vector存储的对象很大或者构造函数很复杂，则开销较大，若是简单的小数据，则效率比list高。
list插入和删除，都需要对现有数据进行遍历，在首部插入的效率比较高。
7. std::deque的底层机制
deque动态地以分段连续空间组合而成，随时可以增加一段新的连续空间并链接起来。不提供空间保留功能。
注意：除非必要，我们尽可能选择使用vector而非deque，因为deque的迭代器比vector迭代器复杂很多。对deque排序，为了提高效率，可先将deque复制到一个vector上排序，然后再复制回deque。
deque采用一块map（不是STL的map容器）作为主控，其为一小块连续空间，其中每个元素都是指针，指向另一段较大的连续空间（缓冲区）。
deque的迭代器包含4个内容：
1）cur：迭代器当前所指元素
2）first：此迭代器所指的缓冲区的头。
3）last：缓冲区尾。
4）node：指向管控中心。
8.std::map底层机制
map以红黑树为底层机制。这是一个平衡二叉搜索树，自动排序的效果好。
通过map的迭代器不能修改其键值，只能修改其实值。所以map的迭代器既不是const也不是mutable。
9. hashtable如何避免地址冲突
- 线性探测：先用hash function计算某个元素的插入位置，则继续向下寻找，直到找到一个可用位置。其删除采用惰性删除：只标记删除记号，实际删除操作等到表格重新整理时再进行
- 二次探测：
10. hash_map和map的区别
构造函数：hash_map需要hash_function和等于函数，而map需要比较函数
存储结构：hash_map以hashtable为底层，而map以RB-TREE为底层
hash_map查找速度比map快，而且速度基本与数据量无关，属于常数级别。而map的查找速度时logn级别。
如果考虑效率，尤其是元素达到一定数量级的时候，用hash_map
考虑内存，或者元素数量较小的时候，用map
11. hashtable，hash_set，hash_map的区别
hash_set以hashtable为底层，不具有排序功能，能快速查找。其键值就是实际的值。（set以红黑树为底层，有排序功能。）
hash_map以hashtable为底层，没有自动排序功能，能快速查找，每一个元素同时拥有一个键值和实值。（map以红黑树为底层，有排序功能。）
12. 红黑树性质
1）每个结点是红色或者黑色。
2）根结点为黑色。
3）叶结点为黑色的NULL结点。
4）如果结点为红，其子节点必须为黑。
5）任一结点到NULL的任何路径，所含黑结点数必须相同。
13. map和set的3个问题
1）为何map和set的插入删除效率比其他序列容器高
因为不需要内存拷贝和内存移动
2）为何map和set每次insert之后，以前保存的iterator不会失效
因为插入操作只是节点指针变换，节点内存没有改变。而iterator就像指向节点的指针，内存没变，指向内存的指针也不会变
3）当数据元素增多时，例如10000到20000，map的set查找速度如何变化
红黑书使用二分查找法，时间复杂度为logn，所以从10000增大到20000，查找次数从log10000=14变为log20000=15,多了一次而已
14. vector中begin和end函数返回啥
begin返回的是第一个元素的迭代器，end返回的时最后一个元素后面位置的迭代器
15. vector的插入操作可能会导致迭代器失效
插入操作可能导致vector动态增加大小，此时并不是在原空间后增加新的空间，而是以原大小的两倍配置一片空间并将原内容拷贝过来，释放原来的空间。由于操作改变了空间，所以迭代器失效
16. vector，list，map，deque，用了erase(it)后迭代器的变化
vector和deque是序列式容器，其内存分别是连续空间和分段连续空间，删除迭代器it后，其后面的迭代器都失效了，此时it及其后面的迭代器会自动加1，使it指向被删除元素的下一个元素。
list删除迭代器it时，其后面的迭代器都不会失效，将前面和后面连接起来即可。
map也是只能使当前删除的迭代器失效，其后面的迭代器依然有效。
17. hashtable和hashmap的区别
hashtable以hashmap为底层。有几点不同
1）hashtable是Dictionary的子类，而hashmap是map接口的一个实现类
2）hashtable中的方法是同步的，而hashmap的方法不同步