史上最全的C++/游戏开发面试问题总结（二）——虚函数，内存，STL
The following article is from 游戏开发那些事 Author Jerish
笔者毕业两年，最近通过猎头拿到了腾讯游戏以及网易游戏的两个客户端研发offer（UE4/C++）。在面试前夕，笔者对C++进行了较为全面的复习和总结，乐观
这个系列的文章预计有《C++基础》、《内存、STL、虚函数相关》、《数据结构与算法》、《操作系统与网络》四篇（当前是第二篇），每篇都是以问答的形式分享并给出了参考资料的链接地址。大部分问题回答的比较简洁，需要大家去仔细阅读参考资料的具体内容，当然也可以直接问我~文中涉及到很多书籍与资料，后续我会把相关的电子书分享给大家。
虚函数机制相关
问：virtual function的优缺点（提问概率：★★★★）
优点：实现多态
缺点：MFC中的消息机制以及Qt中都没有采用C++中的虚函数机制，原因大概如下~
1.在子类很少覆盖基类函数实现的时候内存开销太大，每个类需要产生一张虚表，每生成一个对象的时候，需要在对象里存放一个vptr。
2.基类指针指向派生类对象的情况下，无法内联优化
3.在执行效率上肯定多了一些开销，需要寻找函数地址4.虚表的存在可能破坏一些封装安全，可以通过vptr绕过private的限制
参考书籍与资料：《C++ Primer》《The Design and Evolution of C++》（C++语言的设计与演化）
问：多继承的优缺点（提问概率：★★★）
好处：简单来讲就是为了实现多个基类特有的功能
缺点：菱形继承；二义性
参考书籍与资料：《C++ Primer》《The Design and Evolution of C++》（C++语言的设计与演化）
问：为什么要用virtual destructor?为什么没有virtual constructor?（提问概率：★★★★）
第一点，构造函数执行前，对象的内存信息都没有，vptr也没有初始化，如何找到虚函数表，实现虚调用。其次，需要理解虚函数的意义，他是为了实现多态，让子类去覆盖父类的操作，但是前提是你需要知道当前的类型是什么，而C++里面构造函数可以说决定了他的类型。另外，构造函数与析构函数的执行不同，他是从父类开始一步一步的构造成一个子类(即使父类没有构造函数也可能会被编译器合成一个)，所以你不能跳过父类的构造函数，子类的很多成员可能需要在父类的基础上去初始化。
不过，从设计的角度来考虑的话，虚构造的思想还是有意义的，和我们设计模式中的工厂模式有点类似。我们希望不受语言的限制，在声明的时候直接自动的调用子类的构造函数，参考Delphi语言。
参考书籍与资料：构造函数不能是虚函数? https://www.zhihu.com/question/35632207/answer/63936329
问：类的内存布局是什么样的？考虑有虚函数、多继承、虚继承几种情况。（提问概率：★★★★★）
简单总结一下就是类只有成员变量占用内存（静态成员不占类内部内存，函数不占内存）。如果有虚函数，每个类对象都会有一个虚函数指针Vptr（占用一个指针大小的内存），vptr指向一个虚函数表，表里面记录了各项标记virtual的函数，子类如果覆盖父类虚函数，对应虚表位置的虚函数会被子类的替换（虚表在运行时其位置与大小就被决定了，一个类只有一个虚表）
https://www.cnblogs.com/demian/p/6538301.html，侵删
单继承GrandChild->Child-> Parent
多继承Derive->Base1Derive->Base2; Derive->Base1
多继承菱形继承D->Base1 D->Base2;Base1->B; Base2->B
多继承菱形虚继承D->Base1 D->Base2;Base1->B; Base2->B
参考书籍与资料：《The Design and Evolution of C++》（C++语言的设计与演化）《Inside the C++ Object Model》（深度探索C++对象模型）
虚继承及继承的内存布局
https://www.cnblogs.com/demian/p/6538301.html
问：dynamic_cast是怎么实现的（提问概率：★★★★）
dynamiccast属于RTTI,运行时类型识别的一个内容，他是c++realise1.0的主要扩充功能之一。主要内容是typeid与typeinfo的实现,基本思路就是在有虚函数的类的虚表的头部位置存放RTTI的相关信息。在VC里面可以看到是一个叫做RTTI Complete Object Locator的结构体里面存放相关的信息。在强转的时候，会读取里面对应的类的信息进而判断是否能转换成功
参考书籍与资料：《The Design and Evolution of C++》（C++语言的设计与演化）
c _rtti机制深度剖析 http://www.docin.com/p-1097232112.html
Classes, Methodsand RTTI
http://www.openrce.org/articles/full_view/23
Visual C++ RTTI Inspection
https://blog.quarkslab.com/visual-c-rtti-inspection.html
C++内存管理相关
问：C++内存模型是什么？如何理解自由存储区与堆的区别？（提问概率：★★★★）
在C++中，内存区分为5个区，分别是堆、栈、自由存储区、全局/静态存储区、常量存储区。malloc在堆上分配的内存，使用free释放内存，而new所申请的内存则是在自由存储区上，使用delete来释放，不过这只是表象。进一步来讲，基本上所有的C++编译器默认使用堆来实现自由存储，即缺省的全局运算符new和delete也会按照malloc和free的方式来被实现，这时藉由new运算符分配的对象，说它在堆上也对，说它在自由存储区上也正确。
所以，new所申请的内存区域在C++中称为自由存储区，如果是通过malloc实现的，那么他也是在堆上的。
参考书籍与资料：《The Design and Evolution of C++》（C++语言的设计与演化）
https://www.cnblogs.com/QG-whz/p/5060894.html
问：memory alignmentand padding, 内存对齐的原理与意义（提问概率：★★★★）
结构体以及类成员对齐，意义就是减少cpu读取的次数，提高效率。比如一个int变量长度为4个字节，cpu一次读4个字节，当然是一次读取比较好。但是如果前面有一个char，地址为0-1。那么这个int的地址就为1-4。导致cpu，分两次读取int值。
具体的对齐规则，要说的非常准确可能比较麻烦，简单来讲就是，每个变量看后面的变量，如果后面的变量大，就和后面的大小对齐并补充字节。最后一个变量，按照成员内最大的对齐值，对齐并补充字节。
参考书籍与资料：
对内存对齐的深一步理解
https://www.cnblogs.com/coding-my-life/p/5374562.html
５分钟搞定内存字节对齐
https://blog.csdn.net/hairetz/article/details/4084088
内存对齐与内存分配原则
https://blog.csdn.net/tingyun_say/article/details/51443803
问：std::shared_ptr的实现，reference count在哪里定义（提问概率：★★★）
shared_ptr作为一种智能指针，本质上一个模板类，表现上与指针相同，是因为重载了&以及*这两个运算符（当然还有=等运算符）。由于其本身的计数机制，防止资源泄露上面很有意义。
Shareptr在实现上有两个核心的成员，一个是指向资源对象的指针变量，另一个是指向引用计数的指针变量。第一个参数不言而喻，第二个参数为什么也是指针？因为多个shared_ptr对象指向同一资源时，其中一个shared_ptr对象析构了count = count -1,是不会影响到其他shared_ptr对象的，所以使用指针可以达到多个shared_ptr对象指向同一资源的能够共享count目的。另外，原生的shared_ptr的读写在多线程当中是不安全的，因为读写不具有原子性，所以多线程使用shared_ptr一定要加锁。循环引用会造成内存泄露。
参考书籍与资料：
std::shared_ptr
https://en.cppreference.com/w/cpp/memory/shared_ptr
为什么多线程读写 shared_ptr 要加锁？
https://blog.csdn.net/solstice/article/details/8547547
问：new expression,operator new和malloc的联系（提问概率：★★★★）
malloc：是从C语言移植过来的语义，表示申请一定大小的内存并返回void*指针，在堆上申请内存，申请失败会返回Null
new：C++里的关键字，针对对象而言，申请一块内存的然后并在内存上构造对应的对象，最后返回该对象的指针。深入：new是从自由存储区分配的内存，自由存储区可能不在堆上，在静态存储区（全局变量做的对象池）。申请失败会抛出异常。可以通过new[]对数组进行内存申请与构造
Operator new：C++里面与Malloc类似的语义，只申请内存而不构造对象
New操作的第一步就是调用OperatorNew来执行内存的申请。深入：operator new可以基于malloc实现，一般也都是这么做的，可以被重载
参考书籍与资料： 《C++ Primer》《The Design and Evolution of C++》（C++语言的设计与演化）
http://blog.csdn.net/wudaijun/article/details/9273339
http://blog.jobbole.com/102002/#article-comment
问：placement new的意义（提问概率：★★★）
placement new作用不太像new，或者说只是一个不完整的new，因为他不分配内存，只是在给定地址上调用构造函数，在c++里面，placement new实际上就是operator new的一种重载方式之一。
一个普通的new可以拆分成两步，第一步，申请内存返回指针，执行一个非placement的operator new(可能通过malloc实现)。第二步，在指定位置上构造对象(这个操作一般是编译器帮我们做了，但是并不是执行placement new，虽然功能上差不多，这里面有细微的差别)。c++单独提供给我们一个placement new 来做第二步操作，因为有的时候我们可能想使用自己的内存申请方式(比如malloc)，但是你发现除了placement new以外你好像没有其他办法在指定位置上调用构造函数。
另外，想要使用placement new，底层系统并不告诉你这个地址上是否已经有对象了，如果你在已经构造的对象上面执行，那么前一个对象就会被销毁，理论上析构函数也不会执行。总之，要避免这种情况。
参考书籍与资料：《Inside the C++ Object Model》（深度探索C++对象模型）
What uses are there for “placement new”?
https://stackoverflow.com/questions/222557/what-uses-are-there-for-placement-new
Placement new operator in C++
https://www.geeksforgeeks.org/placement-new-operator-cpp/
问:allocator的实现与使用意义（提问概率：★★★）
c++11新标准里面加入，他本身是一个类模板，功能上其实就是把new拆开，把内存申请和对象构造分成两个步骤，是不是很熟悉？这不就是operator new和placement new么？实际上allocator就是利用operator new来实现的。
为什么要这么做？举个例子，假如我要new一个长度为100的string数组，那我在申请内存的同时还要构造100个string对象，而实际上我整个程序从开始到结束可能只用了10个string。那为了减小构造的开销，这里就将内存申请与对象构造分开，也就有了allocator。当然，我们也可以使用operator new来做这个操作，只不过allocator帮我们做了一些简单的封装，类型检查等。另外，说到allocator就不得不提一下stl里面的空间配置器alloc，他除了上面简单的封装外还还考虑到了以下三个方面：1.多线程内存分配(内存池互斥访问)2.内存分配失败的异常处理3.实现一个轻量级内存池来解决小块内存导致的内存碎片问题
第一种情况，基本的实现就是在构造时加锁，析构时解锁。
内存分配失败的话，给用户提供一个函数去定义异常时的处理逻辑。
针对内存碎片问题，sgi stl里面的allocator里面设计了一个双层配置器，当申请内存超过128byte，就认为足够大，直接调用malloc分配。反之，调用第二级配置器使用内存池来处理，内存池实现思路就是先申请一块比较大的内存，分成n块，每次有小的内存申请时就给他一块。
参考书籍与资料：《STL源码剖析》
https://en.cppreference.com/w/cpp/memory/allocator
https://zh.wikipedia.org/wiki/%E5%88%86%E9%85%8D%E5%99%A8_(C%2B%2B)
问：RAII是什么？有什么意义？应用场景？（提问概率：★★★★）
RAII 是 resource acquisition is initialization 的缩写，意为“资源获取即初始化”。其核心是把资源和对象的生命周期绑定，对象创建获取资源，对象销毁释放资源。常见的例子就是智能指针，通过声明一个包含资源对象指针的类，在这个类执行析构的时候释放指针指向的对象。
参考书籍与资料：
RAII https://zh.wikipedia.org/wiki/RAII
RAII cppreference.com
https://zh.cppreference.com/w/cpp/language/raii
问：内存泄露是什么意思？如何检测与避免内存泄漏？（提问概率：★★★★）
指由于疏忽或错误造成程序未能释放已经不再使用的内存的情况。内存泄漏并非指内存在物理上的消失，而是应用程序分配某段内存后，由于设计错误，导致在释放该段内存之前就失去了对该段内存的控制，从而造成了内存的浪费
检测:windows可以使用crtdumpmemoryleaks替换free为freedebug还可以使用crtmemcheckpoint结合difference比较。
避免:智能指针，如ue垃圾回收机制。
参考书籍与资料：C/C++内存泄漏及检测
https://www.cnblogs.com/skynet/archive/2011/02/20/1959162.html
问：成员函数调用delete this会发生什么？之后再进行读写会怎么样？（提问概率：★★★★）
在类的成员函数中能不能调用delete this？答案是肯定的，能调用，而且很多老一点的库都有这种代码。假设这个成员函数名字叫release，而delete this就在这个release方法中被调用，那么这个对象在调用release方法后，还能进行其他操作，如调用该对象的其他方法么？答案仍然是肯定的，调用release之后还能调用其他的方法，但是有个前提：被调用的方法不涉及这个对象的数据成员和虚函数。
如果这时候调用普通的成员函数应该没有问题，因为这些成员函数与普通函数区别不大也在代码段，也需要走函数栈的逻辑。
如果调用虚函数，那就需要获取类内存的虚函数指针，这就涉及到堆内存的操作了，因为这时候虚函数指针也会被设置成未初始化的值，会有问题。
如果操作非指针成员变量，可能读和写都没有问题。
如果操作指针成员变量，指针可能设置成未初始化的值，很可能指向不合法的地方，强制赋值可能会导致崩溃
简单来说就是不要再去操作他的内存数据，否则很有可能崩溃，因为释放后，这个内存不确定系统如何处理。
另外，delete this会去调用本对象的析构函数，而析构函数中又调用delete this，形成无限递归，造成堆栈溢出，系统崩溃。
参考书籍与资料：what will happen if you do “deletethis;” in a member function?
https://stackoverflow.com/questions/7039597/what-will-happen-if-you-do-delete-this-in-a-member-function
在类的成员函数中调用delete this
http://blog.sina.com.cn/s/blog_4b4cf2af0100ywgv.html
STL相关
问：vector的实现与增长（提问概率：★★★★★）
vector是stl提供的动态数组，想了解他就要从他的特性开始分析。首先，他是一个模板类，意味着可以存放各种类型的元素，同时他也是一个数组，存储是连续的。 里面保存了三个指针，分别指向头、数据尾、数组尾。
内存分配:常规的数组必须在定义的时候就分配好固定的大小，而vector可以动态的改变，也就说明他可以动态的申请与释放内存。我们要知道，频繁的申请与释放内存对程序的效率影响是非常大的，因为如果当前地址空间不够用的话，就需要重新找一块更大的空间来装数据，再把数据全部都拷贝过去。所以vector为了达到比较好的效果，在添加元素的时候会多申请一定大小的内存，从而减少内存分配的次数。capacity()返回的就是包括缓冲区在内的空间大小，而size()返回的就是当前实际使用的空间大小。如果想主动的提前分配内存，可以使用reserve(n)，会强制重新分配一次内存，超出实际使用的部分就会成为缓存区。如果想直接构造出长度为n的动态数组可以使用resize(n)，实际分配的空间肯定要比n大，不过如果n比当前size小的话，大于size的数据都会被清空，如果比capacity还大的话就会重新执行一次内存分配。
关于内存释放，如果只是简单的调用 clear()全部清空数据,erase()清空部分数据都只是单纯的清空里面的数据并不会释放掉。默认只会在调用vector的析构函数的时候才会真正释放空间，所以如果想强制释放那就新建一个空的vector，然后对这个vector使用swap讲内存交换，那么原来的vector就会释放，新的vector呢？
另外，由于涉及到模板，也就会涉及到迭代器，凡是重新申请过内存，插入删除数据的，迭代器都会失效，理解上也很容易就是指针可能指向的不是你原来的那个位置了。
参考书籍与资料：《STL源码解析》（SGI的STL），VC STL里面的源码（打开VS自己看，读起来比较吃力）
问：map的实现 unordered_map的原理；如果从空的table开始一直增加元素，会出现什么情况？（提问概率：★★★★★）
map分为有序map和无序map（unordered_map），实现的基本数据结构分别是红黑树与哈希表。(set同理)里面每一个元素是一个pair< const key_type,mapped_type >类型，注意key是const的，不可以修改。对于一个数据结构，常见的操作无非是查找，插入，删除。红黑树作为一种二叉搜索树，具有log(n)的查找效率，不过前提是数据具有足够的随机性。！！！
hashmap理想上则是具有常数平均时间的效率，或者说一次或几次就可以查到，当然如果数据量过大，散列表空间就不能和数据量保持1：1，这时候就要靠hash函数来处理数据，将数据尽可能的分散在不同的桶bucket里面。
sgi stl的hash使用的是开链操作来避免hash表空间过大又想保持一定效率的问题，开链就是在一个位置用链表来存储所有冲突项。其实hashmap里面常说的桶bucket就是vector数组的一个元素，每个桶里面的数据是以链表(开链)的形式存储，进一步来说这些操作与定义都是通过一个基本的数据结构hashtable来实现的，所有的无序关联容器都是。hashtable里面的hash函数就是常说的取模函数，根据存储数据key值(注意，是对key而不是value)对桶的长度取余数来存放。默认提供的hash函数无法处理常见内置类型以外的数据，如各种自定义类，其实string本身也算是特殊类型，但是语言内部可以转为const char*处理，他经过函数处理也会得到一个size类型（一般对字符串的哈希函数比较特别，参考各种字符串Hash函数比较）。
什么时候需要rehash？当你的桶里面的平均数量（Map大小/桶的数量）大于max(这个可以自己设置)，就需要rehash。也可以主动调用rehash(n),保证桶的数量大于n，注意n是桶的数量。改变桶的数量就相当于改变Vector的长度，如果超过vector的capacity就会调用Vector的扩容机制（但是实际上他每次hash的时候都会直接调用vector的reserve进行扩容）。
什么时候执行reserve（Java里好像是resize）？注意reserve与vector的reserve不一样，他的目的并不是扩容，而是希望当前哈希表里面可以容纳n个元素。如果n>桶的数量*负载因子的时候就会触发rehash，否则不会触发。rehash有可能进一步触发vector的扩容。参考下面的英文注释。
Request acapacity change Sets the number of buckets in the container
(bucket_count) to the most appropriate to contain at least n elements.
If n is greater than the current bucket_count multiplied by the
max_load_factor, the container’s bucket_count is increased and a
rehash is forced. If n is lower than that, the function may have no
effect.
不过我发现 VC的STL里面的处理方式好像不太一样，他是自动先检测是否满足当前负载因子>最大负载因子，满足就会先触发重新设置桶的数量，如果桶的数量小于512就直接乘以8，否则如果小于Vector容量的一半的话就乘以2。这个过程我们看到他直接设置桶的数量并没有调用rehash函数，如果是主动调用rehash的话是直接翻倍的。而且不论是手动还是自动调整桶的数量，他都会触发Vector的扩容函数。
//手动调用：重新分配桶的数量
void rehash(size_type _Buckets)
{ // rebuild table with at least _Bucketsbuckets
size_type _Maxsize = _Vec.max_size() / 4;
size_type _Newsize = _Min_buckets;
for (; _Newsize < _Buckets && _Newsize <_Maxsize; )
_Newsize *= 2; // doubleuntil big enough
if (_Newsize< _Buckets)
_Xout_of_range("invalid hash bucket count");
while (!(size() / max_load_factor() < _Newsize)
&& _Newsize < _Maxsize)
_Newsize *= 2; // doubleuntil load factor okay
_Init(_Newsize);
_Reinsert();
}
//自动检查：设置桶的数量
void _Check_size()
{ // grow table as needed
if(max_load_factor() < load_factor())
{ // rehash to bigger table
size_type _Newsize = bucket_count();
if (_Newsize <512)
_Newsize *= 8; //multiply by 8
elseif (_Newsize <_Vec.max_size() / 2)
_Newsize *= 2; //multiply safely by 2
_Init(_Newsize);
_Reinsert();
}
}
//重新分配桶的数量，同时进行扩容
void _Init(size_type _Buckets = _Min_buckets)
{ // initialize hash table with _Bucketsbuckets, leave list alone
_Vec.reserve(2 * _Buckets); // avoidcurdling _Vec if exception occurs
_Vec.assign(2 * _Buckets, _Unchecked_end());
_Mask = _Buckets - 1;
//赋值_Maxidx，重新设置桶的数量
_Maxidx = _Buckets;
}
参考书籍与资料：《STL源码解析》（SGI的STL），VC STL里面的源码（打开VS查看）
std::map::erase http://www.cplusplus.com/reference/map/map/erase/
问：stl里deque是如何实现的？（提问概率：★★★）
其实deque由一段一段内存构成的，他是分段连续,而不是内存连续。当走向段的尾端时候自动跳到下一段。map记录着一系列的固定长度的数组的地址，这个map仅仅保存的是数组的地址,真正的数据在数组中存放着。deque先从map中央间的位置(因为双向队列，前后都可以插入元素，前面需要留出一定的空间)找到一个数组地址，向该数组中放入数据，数组不够时继续在map中找空闲的数组来存数据。当map也不够时重新分配内存当作新的map,把原来map中的内容copy的新map中。所以使用deque的复杂度要大于vector，尽量使用vector。（图片来自网络，侵删）
参考书籍与资料：《STL源码解析》（SGI的STL），VC STL里面的源码（打开VS查看）
问：stl里heap与priority_queue？（提问概率：★★）
heap是基于vector来实现的，不过他不属于容器组件，因为他的主要是为优先级队列priority_queue的实现提供基础结构。所谓的优先级队列，其实就是队首元素一定是当前队列中优先级最高的那一个，只能通过 top() 函数来访问队首元素。我们知道最大堆与最小堆拥有这种特性，所以很适合用来实现priority_queue，当然其他数据结构也可以实现，不过从实现复杂度与计算复杂度等方面heap最为合适。
参考书籍与资料：《STL源码解析》（SGI的STL），VC STL里面的源码（打开VS查看）
std::priority_queue https://en.cppreference.com/w/cpp/container/priority_queue
问：stl里面各个容器的基础数据结构是？（提问概率：★★★★）
图截自STL源码分析一书，常问的是优先级队列，hashmap，map底层的数据结构是什么。答案分别是Vector，hashtable以及RB—tree（红黑树），具体细节大家可以仔细看一下关于容器的这两章内容。
参考书籍与资料：“STL源码”，《STL源码剖析》