大家好，我是阿秀。
这是《逆袭进大厂》系列的第四期，本期是 C++ 重头戏，也就是标准模板库 STL 的内容，本期是 24098 个字。
按照阿秀自己经历过的三十多场校招面试来看，校招 C++ 岗区分度比较高的两个知识点就是虚函数和STL知识。
说人话就是虚函数和STL部分答得好一点，面试评级就好一点，最后拿到好offer的希望就大一些。
你懂我意思叭？四字概括就是"钱多，速来"！
还有就是很多人催我发一个PDF版本，这个我还在整理，实在不是我不发。因为还有操作系统、计算机网络、MySQL、Redis等篇章还没整理出来，等这个《逆袭进大厂》系列完结后会放出来的。
如果还没看过前三期的小伙伴们可以去温习一下前面几篇文章，下一期是操作系统的八股文。
《逆袭进大厂》全系列
老规矩，一起来看一下本期目录好了，看看你们会多少。
话不多说，开车了。
187、STL中hashtable的实现？
STL中的hashtable使用的是开链法解决hash冲突问题，如下图所示。
hashtable中的bucket所维护的list既不是list也不是slist，而是其自己定义的由hashtable_node数据结构组成的linked-list，而bucket聚合体本身使用vector进行存储。hashtable的迭代器只提供前进操作，不提供后退操作
在hashtable设计bucket的数量上，其内置了28个质数[53, 97, 193,…,429496729]，在创建hashtable时，会根据存入的元素个数选择大于等于元素个数的质数作为hashtable的容量（vector的长度），其中每个bucket所维护的linked-list长度也等于hashtable的容量。
如果插入hashtable的元素个数超过了bucket的容量，就要进行重建table操作，即找出下一个质数，创建新的buckets vector，重新计算元素在新hashtable的位置。
《STL源码解析》侯捷
188、简单说一下STL中的traits技法
traits技法利用“内嵌型别“的编程技巧与编译器的template参数推导功能，增强C++未能提供的关于型别认证方面的能力。常用的有iterator_traits和type_traits。
iterator_traits
被称为特性萃取机，能够方面的让外界获取以下5中型别：
- value_type：迭代器所指对象的型别
- difference_type：两个迭代器之间的距离
- pointer：迭代器所指向的型别
- reference：迭代器所引用的型别
- iterator_category：三两句说不清楚，建议看书
type_traits
关注的是型别的特性，例如这个型别是否具备non-trivial defalt ctor（默认构造函数）、non-trivial copy ctor（拷贝构造函数）、non-trivial assignment operator（赋值运算符） 和non-trivial dtor（析构函数），如果答案是否定的，可以采取直接操作内存的方式提高效率，一般来说，type_traits支持以下5中类型的判断：
__type_traits<T>::has_trivial_default_constructor __type_traits<T>::has_trivial_copy_constructor __type_traits<T>::has_trivial_assignment_operator __type_traits<T>::has_trivial_destructor __type_traits<T>::is_POD_type
由于编译器只针对class object形式的参数进行参数推到，因此上式的返回结果不应该是个bool值，实际上使用的是一种空的结构体：
struct __true_type{}; struct __false_type{};
这两个结构体没有任何成员，不会带来其他的负担，又能满足需求，可谓一举两得
当然，如果我们自行定义了一个Shape类型，也可以针对这个Shape设计type_traits的特化版本
template<> struct __type_traits<Shape>{ typedef __true_type has_trivial_default_constructor; typedef __false_type has_trivial_copy_constructor; typedef __false_type has_trivial_assignment_operator; typedef __false_type has_trivial_destructor; typedef __false_type is_POD_type; };
《STL源码解析》侯捷 P103-P110
189、STL的两级空间配置器
1、首先明白为什么需要二级空间配置器？
我们知道动态开辟内存时，要在堆上申请，但若是我们需要
频繁的在堆开辟释放内存，则就会在堆上造成很多外部碎片，浪费了内存空间；
每次都要进行调用malloc、free函数等操作，使空间就会增加一些附加信息，降低了空间利用率；
随着外部碎片增多，内存分配器在找不到合适内存情况下需要合并空闲块，浪费了时间，大大降低了效率。
于是就设置了二级空间配置器，当开辟内存<=128bytes时，即视为开辟小块内存，则调用二级空间配置器。
关于STL中一级空间配置器和二级空间配置器的选择上，一般默认选择的为二级空间配置器。如果大于128字节再转去一级配置器器。
一级配置器
一级空间配置器中重要的函数就是allocate、deallocate、reallocate 。一级空间配置器是以malloc()，free()，realloc()等C函数执行实际的内存配置 。大致过程是：
1、直接allocate分配内存，其实就是malloc来分配内存，成功则直接返回，失败就调用处理函数
2、如果用户自定义了内存分配失败的处理函数就调用，没有的话就返回异常
3、如果自定义了处理函数就进行处理，完事再继续分配试试
二级配置器
1、维护16条链表，分别是0-15号链表，最小8字节，以8字节逐渐递增，最大128字节，你传入一个字节参数，表示你需要多大的内存，会自动帮你校对到第几号链表（如需要13bytes空间，我们会给它分配16bytes大小），在找到第你个链表后查看链表是否为空，如果不为空直接从对应的free_list中拔出，将已经拨出的指针向后移动一位。
2、对应的free_list为空，先看其内存池是不是空时，如果内存池不为空：
（1）先检验它剩余空间是否够20个节点大小（即所需内存大小(提升后) * 20），若足够则直接从内存池中拿出20个节点大小空间，将其中一个分配给用户使用，另外19个当作自由链表中的区块挂在相应的free_list下，这样下次再有相同大小的内存需求时，可直接拨出。
（2）如果不够20个节点大小，则看它是否能满足1个节点大小，如果够的话则直接拿出一个分配给用户，然后从剩余的空间中分配尽可能多的节点挂在相应的free_list中。
（3）如果连一个节点内存都不能满足的话，则将内存池中剩余的空间挂在相应的free_list中（找到相应的free_list），然后再给内存池申请内存，转到3。
3、内存池为空，申请内存
此时二级空间配置器会使用malloc()从heap上申请内存，（一次所申请的内存大小为2 * 所需节点内存大小（提升后）* 20 + 一段额外空间），申请40块，一半拿来用，一半放内存池中。
4、malloc没有成功
在第三种情况下，如果malloc()失败了，说明heap上没有足够空间分配给我们了，这时，二级空间配置器会从比所需节点空间大的free_list中一一搜索，从比它所需节点空间大的free_list中拔除一个节点来使用。如果这也没找到，说明比其大的free_list中都没有自由区块了，那就要调用一级适配器了。
释放时调用deallocate()函数，若释放的n>128，则调用一级空间配置器，否则就直接将内存块挂上自由链表的合适位置。
STL二级空间配置器虽然解决了外部碎片与提高了效率，但它同时增加了一些缺点：
1.因为自由链表的管理问题，它会把我们需求的内存块自动提升为8的倍数，这时若你需要1个字节，它会给你8个字节，即浪费了7个字节，所以它又引入了内部碎片的问题，若相似情况出现很多次，就会造成很多内部碎片；
2.二级空间配置器是在堆上申请大块的狭义内存池，然后用自由链表管理，供现在使用，在程序执行过程中，它将申请的内存一块一块都挂在自由链表上，即不会还给操作系统，并且它的实现中所有成员全是静态的，所以它申请的所有内存只有在进程结束才会释放内存，还给操作系统，由此带来的问题有：1.即我不断的开辟小块内存，最后整个堆上的空间都被挂在自由链表上，若我想开辟大块内存就会失败；2.若自由链表上挂很多内存块没有被使用，当前进程又占着内存不释放，这时别的进程在堆上申请不到空间，也不可以使用当前进程的空闲内存，由此就会引发多种问题。
一级分配器
GC4.9之后就没有第一级了，只有第二级
二级分配器：
——default_alloc_template 剖析
有个自动调整的函数：你传入一个字节参数，表示你需要多大的内存，会自动帮你校对到第几号链表（0-15号链表，最小8字节 最大128字节）
allocate函数：如果要分配的内存大于128字节，就转用第一级分配器，否则也就是小于128字节。那么首先判断落在第几号链表，定位到了，先判断链表是不是空，如果是空就需要充值，（调节到8的倍数，默认一次申请20个区块，当然了也要判断20个是不是能够申请到，如果只申请到一个那就直接返回好了，不止一个的话，把第2到第n个挨个挂到当前链表上，第一个返回回去给容器用,n是不大于20的，当然了如果不在1-20之间，那就是内存碎片了，那就先把碎片挂到某一条链表上，然后再重新malloc了，malloc 2*20个块）去内存池去拿或者重新分配。不为空的话
190、 vector与list的区别与应用？怎么找某vector或者list的倒数第二个元素
1) vector数据结构
vector和数组类似，拥有一段连续的内存空间，并且起始地址不变。因此能高效的进行随机存取，时间复杂度为o(1);但因为内存空间是连续的，所以在进行插入和删除操作时，会造成内存块的拷贝，时间复杂度为o(n)。另外，当数组中内存空间不够时，会重新申请一块内存空间并进行内存拷贝。连续存储结构：vector是可以实现动态增长的对象数组，支持对数组高效率的访问和在数组尾端的删除和插入操作，在中间和头部删除和插入相对不易，需要挪动大量的数据。它与数组最大的区别就是vector不需程序员自己去考虑容量问题，库里面本身已经实现了容量的动态增长，而数组需要程序员手动写入扩容函数进形扩容。
2) list数据结构
list是由双向链表实现的，因此内存空间是不连续的。只能通过指针访问数据，所以list的随机存取非常没有效率，时间复杂度为o(n);但由于链表的特点，能高效地进行插入和删除。非连续存储结构：list是一个双链表结构，支持对链表的双向遍历。每个节点包括三个信息：元素本身，指向前一个元素的节点（prev）和指向下一个元素的节点（next）。因此list可以高效率的对数据元素任意位置进行访问和插入删除等操作。由于涉及对额外指针的维护，所以开销比较大。
区别：
vector的随机访问效率高，但在插入和删除时（不包括尾部）需要挪动数据，不易操作。list的访问要遍历整个链表，它的随机访问效率低。但对数据的插入和删除操作等都比较方便，改变指针的指向即可。list是单向的，vector是双向的。vector中的迭代器在使用后就失效了，而list的迭代器在使用之后还可以继续使用。
3)
int mySize = vec.size();vec.at(mySize -2);
list不提供随机访问，所以不能用下标直接访问到某个位置的元素，要访问list里的元素只能遍历，不过你要是只需要访问list的最后N个元素的话，可以用反向迭代器来遍历：
191、STL 中vector删除其中的元素，迭代器如何变化？为什么是两倍扩容？释放空间？
size()函数返回的是已用空间大小，capacity()返回的是总空间大小，capacity()-size()则是剩余的可用空间大小。当size()和capacity()相等，说明vector目前的空间已被用完，如果再添加新元素，则会引起vector空间的动态增长。
由于动态增长会引起重新分配内存空间、拷贝原空间、释放原空间，这些过程会降低程序效率。因此，可以使用reserve(n)预先分配一块较大的指定大小的内存空间，这样当指定大小的内存空间未使用完时，是不会重新分配内存空间的，这样便提升了效率。只有当n>capacity()时，调用reserve(n)才会改变vector容量。
resize()成员函数只改变元素的数目，不改变vector的容量。
1、空的vector对象，size()和capacity()都为0
2、当空间大小不足时，新分配的空间大小为原空间大小的2倍。
3、使用reserve()预先分配一块内存后，在空间未满的情况下，不会引起重新分配，从而提升了效率。
4、当reserve()分配的空间比原空间小时，是不会引起重新分配的。
5、resize()函数只改变容器的元素数目，未改变容器大小。
6、用reserve(size_type)只是扩大capacity值，这些内存空间可能还是“野”的，如果此时使用“[ ]”来访问，则可能会越界。而resize(size_type new_size)会真正使容器具有new_size个对象。
不同的编译器，vector有不同的扩容大小。在vs下是1.5倍，在GCC下是2倍；
空间和时间的权衡。简单来说， 空间分配的多，平摊时间复杂度低，但浪费空间也多。
使用k=2增长因子的问题在于，每次扩展的新尺寸必然刚好大于之前分配的总和，也就是说，之前分配的内存空间不可能被使用。这样对内存不友好。最好把增长因子设为(1,2)
对比可以发现采用采用成倍方式扩容，可以保证常数的时间复杂度，而增加指定大小的容量只能达到O(n)的时间复杂度，因此，使用成倍的方式扩容。
如何释放空间：
由于vector的内存占用空间只增不减，比如你首先分配了10,000个字节，然后erase掉后面9,999个，留下一个有效元素，但是内存占用仍为10,000个。所有内存空间是在vector析构时候才能被系统回收。empty()用来检测容器是否为空的，clear()可以清空所有元素。
但是即使clear()，vector所占用的内存空间依然如故，无法保证内存的回收。
如果需要空间动态缩小，可以考虑使用deque。如果vector，可以用swap()来帮助你释放内存。
vector(Vec).swap(Vec); 将Vec的内存空洞清除； vector().swap(Vec); 清空Vec的内存；
192、容器内部删除一个元素
1) 顺序容器
erase迭代器不仅使所指向被删除的迭代器失效，而且使被删元素之后的所有迭代器失效(list除外)，所以不能使用erase(it++)的方式，但是erase的返回值是下一个有效迭代器；
it = c.erase(it)
2) 关联容器
erase迭代器只是被删除元素的迭代器失效，但是返回值是void，所以要采用erase(it++)的方式删除迭代器；
c.erase(it++)
193、STL迭代器如何实现
1、 迭代器是一种抽象的设计理念，通过迭代器可以在不了解容器内部原理的情况下遍历容器，除此之外，STL中迭代器一个最重要的作用就是作为容器与STL算法的粘合剂。
2、 迭代器的作用就是提供一个遍历容器内部所有元素的接口，因此迭代器内部必须保存一个与容器相关联的指针，然后重载各种运算操作来遍历，其中最重要的是*运算符与->运算符，以及++、--等可能需要重载的运算符重载。这和C++中的智能指针很像，智能指针也是将一个指针封装，然后通过引用计数或是其他方法完成自动释放内存的功能。
3、最常用的迭代器的相应型别有五种：value type、difference type、pointer、reference、iterator catagoly;
194、map、set是怎么实现的，红黑树是怎么能够同时实现这两种容器？为什么使用红黑树？
1) 他们的底层都是以红黑树的结构实现，因此插入删除等操作都在O(logn时间内完成，因此可以完成高效的插入删除；
2) 在这里我们定义了一个模版参数，如果它是key那么它就是set，如果它是map，那么它就是map；底层是红黑树，实现map的红黑树的节点数据类型是key+value，而实现set的节点数据类型是value
3) 因为map和set要求是自动排序的，红黑树能够实现这一功能，而且时间复杂度比较低。
195、如何在共享内存上使用stl标准库？
1) 想像一下把STL容器，例如map, vector, list等等，放入共享内存中，IPC一旦有了这些强大的通用数据结构做辅助，无疑进程间通信的能力一下子强大了很多。
我们没必要再为共享内存设计其他额外的数据结构，另外，STL的高度可扩展性将为IPC所驱使。STL容器被良好的封装，默认情况下有它们自己的内存管理方案。
当一个元素被插入到一个STL列表(list)中时，列表容器自动为其分配内存，保存数据。考虑到要将STL容器放到共享内存中，而容器却自己在堆上分配内存。
一个最笨拙的办法是在堆上构造STL容器，然后把容器复制到共享内存，并且确保所有容器的内部分配的内存指向共享内存中的相应区域，这基本是个不可能完成的任务。
2) 假设进程A在共享内存中放入了数个容器，进程B如何找到这些容器呢？
一个方法就是进程A把容器放在共享内存中的确定地址上（fixed offsets），则进程B可以从该已知地址上获取容器。另外一个改进点的办法是，进程A先在共享内存某块确定地址上放置一个map容器，然后进程A再创建其他容器，然后给其取个名字和地址一并保存到这个map容器里。
进程B知道如何获取该保存了地址映射的map容器，然后同样再根据名字取得其他容器的地址。
196、map插入方式有几种？
1) 用insert函数插入pair数据， mapStudent.insert(pair<int, string>(1, "student_one")); 2) 用insert函数插入value_type数据 mapStudent.insert(map<int, string>::value_type (1, "student_one")); 3) 在insert函数中使用make_pair()函数 mapStudent.insert(make_pair(1, "student_one")); 4) 用数组方式插入数据 mapStudent[1] = "student_one";
197、STL中unordered_map(hash_map)和map的区别，hash_map如何解决冲突以及扩容
1) unordered_map和map类似，都是存储的key-value的值，可以通过key快速索引到value。不同的是unordered_map不会根据key的大小进行排序，
2) 存储时是根据key的hash值判断元素是否相同，即unordered_map内部元素是无序的，而map中的元素是按照二叉搜索树存储，进行中序遍历会得到有序遍历。
3) 所以使用时map的key需要定义operator<。而unordered_map需要定义hash_value函数并且重载operator==。但是很多系统内置的数据类型都自带这些，
4) 那么如果是自定义类型，那么就需要自己重载operator<或者hash_value()了。
5) 如果需要内部元素自动排序，使用map，不需要排序使用unordered_map
6) unordered_map的底层实现是hash_table;
7) hash_map底层使用的是hash_table，而hash_table使用的开链法进行冲突避免，所有hash_map采用开链法进行冲突解决。
8) 什么时候扩容：当向容器添加元素的时候，会判断当前容器的元素个数，如果大于等于阈值---即当前数组的长度乘以加载因子的值的时候，就要自动扩容啦。
9) 扩容(resize)就是重新计算容量，向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。
198、vector越界访问下标，map越界访问下标？vector删除元素时会不会释放空间？
1) 通过下标访问vector中的元素时不会做边界检查，即便下标越界。
也就是说，下标与first迭代器相加的结果超过了finish迭代器的位置，程序也不会报错，而是返回这个地址中存储的值。
如果想在访问vector中的元素时首先进行边界检查，可以使用vector中的at函数。通过使用at函数不但可以通过下标访问vector中的元素，而且在at函数内部会对下标进行边界检查。
2) map的下标运算符[]的作用是：将key作为下标去执行查找，并返回相应的值；如果不存在这个key，就将一个具有该key和value的某人值插入这个map。
3) erase()函数，只能删除内容，不能改变容量大小;
erase成员函数，它删除了itVect迭代器指向的元素，并且返回要被删除的itVect之后的迭代器，迭代器相当于一个智能指针;clear()函数，只能清空内容，不能改变容量大小;如果要想在删除内容的同时释放内存，那么你可以选择deque容器。
199、map中[]与find的区别？
1) map的下标运算符[]的作用是：将关键码作为下标去执行查找，并返回对应的值；如果不存在这个关键码，就将一个具有该关键码和值类型的默认值的项插入这个map。
2) map的find函数：用关键码执行查找，找到了返回该位置的迭代器；如果不存在这个关键码，就返回尾迭代器。
200、 STL中list与queue之间的区别
1) list不再能够像vector一样以普通指针作为迭代器，因为其节点不保证在存储空间中连续存在；
2) list插入操作和结合才做都不会造成原有的list迭代器失效;
3) list不仅是一个双向链表，而且还是一个环状双向链表，所以它只需要一个指针；
4) list不像vector那样有可能在空间不足时做重新配置、数据移动的操作，所以插入前的所有迭代器在插入操作之后都仍然有效；
5) deque是一种双向开口的连续线性空间，所谓双向开口，意思是可以在头尾两端分别做元素的插入和删除操作；可以在头尾两端分别做元素的插入和删除操作；
6) deque和vector最大的差异，一在于deque允许常数时间内对起头端进行元素的插入或移除操作，二在于deque没有所谓容量概念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来，deque没有所谓的空间保留功能。
201、STL中的allocator,deallocator
1) 第一级配置器直接使用malloc()、free()和relloc()，第二级配置器视情况采用不同的策略：当配置区块超过128bytes时，视之为足够大，便调用第一级配置器；当配置器区块小于128bytes时，为了降低额外负担，使用复杂的内存池整理方式，而不再用一级配置器；
2) 第二级配置器主动将任何小额区块的内存需求量上调至8的倍数，并维护16个free-list，各自管理大小为8~128bytes的小额区块；
3) 空间配置函数allocate()，首先判断区块大小，大于128就直接调用第一级配置器，小于128时就检查对应的free-list。如果free-list之内有可用区块，就直接拿来用，如果没有可用区块，就将区块大小调整至8的倍数，然后调用refill()，为free-list重新分配空间；
4) 空间释放函数deallocate()，该函数首先判断区块大小，大于128bytes时，直接调用一级配置器，小于128bytes就找到对应的free-list然后释放内存。
202、STL中hash_map扩容发生什么？
1) hash table表格内的元素称为桶（bucket),而由桶所链接的元素称为节点（node),其中存入桶元素的容器为stl本身很重要的一种序列式容器——vector容器。之所以选择vector为存放桶元素的基础容器，主要是因为vector容器本身具有动态扩容能力，无需人工干预。
2) 向前操作：首先尝试从目前所指的节点出发，前进一个位置（节点），由于节点被安置于list内，所以利用节点的next指针即可轻易完成前进操作，如果目前正巧是list的尾端，就跳至下一个bucket身上，那正是指向下一个list的头部节点。
203、常见容器性质总结？
1.vector 底层数据结构为数组 ，支持快速随机访问
2.list 底层数据结构为双向链表，支持快速增删
3.deque 底层数据结构为一个中央控制器和多个缓冲区，详细见STL源码剖析P146，支持首尾（中间不能）快速增删，也支持随机访问
deque是一个双端队列(double-ended queue)，也是在堆中保存内容的.它的保存形式如下:
[堆1] --> [堆2] -->[堆3] --> …
每个堆保存好几个元素,然后堆和堆之间有指针指向,看起来像是list和vector的结合品.
4.stack 底层一般用list或deque实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时
5.queue 底层一般用list或deque实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时（stack和queue其实是适配器,而不叫容器，因为是对容器的再封装）
6.priority_queue 的底层数据结构一般为vector为底层容器，堆heap为处理规则来管理底层容器实现
7.set 底层数据结构为红黑树，有序，不重复
8.multiset 底层数据结构为红黑树，有序，可重复
9.map 底层数据结构为红黑树，有序，不重复
10.multimap 底层数据结构为红黑树，有序，可重复
11.unordered_set 底层数据结构为hash表，无序，不重复
12.unordered_multiset 底层数据结构为hash表，无序，可重复
13.unordered_map 底层数据结构为hash表，无序，不重复
14.unordered_multimap 底层数据结构为hash表，无序，可重复
204、vector的增加删除都是怎么做的？为什么是1.5或者是2倍？
1) 新增元素：vector通过一个连续的数组存放元素，如果集合已满，在新增数据的时候，就要分配一块更大的内存，将原来的数据复制过来，释放之前的内存，在插入新增的元素；
2) 对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就都失效了 ；
3) 初始时刻vector的capacity为0，塞入第一个元素后capacity增加为1；
4) 不同的编译器实现的扩容方式不一样，VS2015中以1.5倍扩容，GCC以2倍扩容。
对比可以发现采用采用成倍方式扩容，可以保证常数的时间复杂度，而增加指定大小的容量只能达到O(n)的时间复杂度，因此，使用成倍的方式扩容。
1) 考虑可能产生的堆空间浪费，成倍增长倍数不能太大，使用较为广泛的扩容方式有两种，以2二倍的方式扩容，或者以1.5倍的方式扩容。
2) 以2倍的方式扩容，导致下一次申请的内存必然大于之前分配内存的总和，导致之前分配的内存不能再被使用，所以最好倍增长因子设置为(1,2)之间：
3) 向量容器vector的成员函数pop_back()可以删除最后一个元素.
4) 而函数erase()可以删除由一个iterator指出的元素，也可以删除一个指定范围的元素。
5) 还可以采用通用算法remove()来删除vector容器中的元素.
6) 不同的是：采用remove一般情况下不会改变容器的大小，而pop_back()与erase()等成员函数会改变容器的大小。
