面试之C++（篇二：STL）
目录
4.vector为什么要成倍扩容，而不按固定大小容量进行增长？
9.set/map、multiset/multimap、unordered_set/unordered_map的区别
1.STL六大组件
（1）容器（Container）
（2）适配器（Adapter）
（3）迭代器（Iterator）
（4）算法（Algorithm）
（5）分配器（Allocator，又称空间配置器）
（6）函数对象（Function Object，又称仿函数）
2.常见容器类及其底层实现
3.vector的扩容机制
（1）vector作为动态数组，在定义后可以根据插入的元素数量来进行扩容，vs中扩容倍数为1.5，gcc中为2。
（2）当vector分配的内存已满时，再插入数据将执行以下操作（以vs为例）：
- 根据当前的vector对象容量n，申请一块新的大小为1.5 * n 的内存空间；
- 将原先的数据拷贝到新的内存空间中；
- 释放原先的内存空间，并在新申请的内存空间插入新的元素。
4.vector为什么要成倍扩容，而不按固定大小容量进行增长？
成倍扩容的均摊时间复杂度为O(1)，按固定大小容量增长的均摊时间复杂度为O(n)，因此成倍扩容方法耗时更短。
具体的原理证明可以参考 https://blog.****.net/bryant_xw/article/details/89524910
5.vs中vector扩容倍数为什么是1.5倍？
（1）一般建议的vector扩容倍数为1到2之间，当扩容倍数大于2时，会导致内存空间的浪费。
（2）当扩容倍数为1.x（x较小，如1）时，可能会导致每次新数据的插入都要进行扩容，每次扩容带来的性能损耗是很大的。
（3）当扩容倍数为2时，每次扩容新申请的内存空间都会大于原先申请的内存空间之和，导致之前分配的内存空间无法再次使用，这对于数据的缓存是很不友好的。
（4）扩容倍数在1到2之间，太小或者太大都不好，因此折中选取了1.5。
具体的原理证明可以参考 https://blog.****.net/bryant_xw/article/details/89524910
6.vector数据插入的优化
（1）利用reserve函数预分配vector对象的内存空间，减少后续插入数据造成的扩容操作。
（2）利用emplace_back代替push_back进行元素的插入工作，push_back中要对临时变量要申请资源执行两次构造函数，而emplace_back利用移动构造，只执行了一次构造函数，提高了插入的效率。
7.forward_list和list的区别
forward_list为单向链表，每个结点只包含一个值和一个指向下一个结点的指针；list为双向链表，每个结点包含了一个值，一个指向下一结点的指针和一个指向前一结点的指针，此外list还是环形链表
8.deque的实现原理
（1）底层由一个中控器和多个缓冲区构成。
（2）中控器实际上是一个映射表，表上的每一项都指向一个连续的线性存储空间（数组）；缓冲区实际上就是一个数组，默认为512B；通过这两种结构使得deque的内存地址在逻辑空间上看上去是连续的。
（3）deque的迭代器具备四个指针，node表示映射表上结点的位置，cur表示当前的指针位置，first表示当前指针所在缓冲区的首地址，last表示当前指针所在缓冲区的尾地址，因此在首尾操作数据较为容易。
9.set/map、multiset/multimap、unordered_set/unordered_map的区别
（1）set/map：保证了元素的唯一性，且按一定顺序进行排序。
（2）multiset/multimap：允许元素重复，且按一定顺序进行排序。
（3）unordered_set/unordered_map：保证了元素的唯一性，乱序。
10.map与unordered_map的对比及应用场景
（1）在实现机制上，map是基于红黑树的，unordered_map是基于哈希表的。
（2）在数据存储上，map保证了插入数据的有序性，而unordered_map中存储的元素的无序的。
（3）由于map是基于红黑树的，每个结点都要保存值、左右子结点、父亲结点以及红/黑标记，占用大量的内存，但是只有插入的结点才会占用内存；而哈希表是要预先分配内存空间再进行数据的存储，更加耗费内存资源。
（4）当有顺序的需求时，选用map；当只有检索需求的话，选用unordered_map。
11.适配器及其底层实现
12.priority_queue与queue的区别
（1）在实现机制上，priority_queue是基于堆的，queue是基于deque的。
（2）在使用上，priority_queue根据allocator对元素进行了优先级排列（默认为大根堆），而queue模拟了一个现实生活中的队列，先进先出。
13.迭代器的作用，为什么引入迭代器？
迭代器的出现就是为了方便算法操作容器，通过迭代器访问容器在很大程度上隔离了容器的底层实现，使用时只需依赖迭代器提供的统一接口进行容器的访问。
（注：在使用容器的迭代器时，要考虑迭代器失效的问题，例如vector每次扩容都会导致原先的迭代器失效）
14.简述STL的内存分配机制（空间配置器的实现原理）
SGI STL设计了两层级的配置器，第一级配置器主要处理申请内存大于128B的情况，第二级配置器主要处理申请内存小于或等于128B的情况。
（1）第一级配置器_malloc_alloc_template调用allocate()中的malloc/realloc申请内存，调用deallocate()中的free释放内存；当申请内存空间不足时，则先释放内存再重新申请。
大于128B的内存申请过程如下：
- allocate中的malloc/realloc申请内存空间；
- 若申请成功则直接分配，失败则根据用户传递的_malloc_alloc_oom_handle指针，调用oom_malloc/oom_realloc释放指针指向的内存空间；
- 若该指针为空则抛出bad_alloc异常，不为空则释放指向的内存空间并重新申请内存。
（2）第二级配置器_default_alloc_template从已经预先申请好的内存空间（内存池）中分配内存，其中free_list是一个存储16个元素的内存映射数组，每个元素指向一个内存区块链表的首地址，free_list中索引 i 所对应的内存区块链表的地址总和为 ( i + 1 ) * 8，每个内存区块都是从内存池中获取的。
小于或等于128B的内存申请过程如下：
- 将要申请的内存大小向上提升为8的整数倍为 n（最大为128B）；
- 根据n计算在free_list对应的索引，获取内存区块链表的首地址；
- 接下来份多种情况讨论：
- 若n小于等于指向的空闲内存链表，分配相应的内存， 接着调用refill中的chunk_alloc从内存池中划取相应的内存区块进行链接，若内存池中没有足够的内存空间时，则转到4；
- 若n大于内存区块链表的大小，则调用chunk_alloc尝试从内存池中分配20块大小为 n 的区块，获取 n * 20 的内存大小；
- 若分配到了 n * a ( 1 ≤ a ≤ 20 ) 的内存，则将其中的一块返回给用户，剩余的区块链接到对应索引的空闲区块链表中；
- 若内存池空闲空间不足（小于 n ），则将先将内存池剩余内存链接到相应大小的空闲区块链表，然后申请新的内存池；
- 类似第一级配置器，通过malloc申请 (2 * n * 20) 的内存空间作为内存池。
空间配置器的内存分配过程挺复杂的，可以参考 https://www.cnblogs.com/geekpaul/p/4174751.html
以上内容均是个人理解总结，若有错误欢迎指出！