C++大厂面试真题

2021-04-03 本文已影响0人拉普拉斯妖kk

C++标准库的map和set有什么区别，如何实现的？

map和set都是C++的关联容器，其底层实现都是红黑树。
map和set区别在于：
- map中的元素是key-value（键-值）对：关键字起到索引的作用，值则表示与索引相关联的数据；set是关键字的简单集合，set中的元素都只包含一个关键字。
- set的迭代器是const的，不允许修改元素的值；map允许修改value，但不允许修改key。
其原因是map和set是根据关键字排序来保证其有序性的，如果允许修改关键字的话，那么首先需要删除该键，然后调节树平衡，再插入修改后的键值，再重新调节树平衡。这样会破坏map和set的结构，导致迭代器失效。
- map支持下标操作，set不支持下标操作。

红黑树的特点：红黑树是二叉查找树，但在每个节点增加一个存储为表示节点的颜色，可以是红色或黑色，通过对任意一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长两倍。因此，它是一种弱平衡二叉树，相对于严格的平衡二叉（AVL）树来说，它的旋转次数少，所以对于查找、插入、删除较多的情况下，通常使用红黑树。
AVL是严格平衡的，频繁的插入和删除，会引起频繁的再平衡，导致效率降低；红黑树是弱平衡的，算是一种折中，插入最多旋转2次，删除最多旋转3次。所以红黑树在查找、插入、删除的复杂度都是O(logn)，且性能稳定，所以STL里面很多结构包括map底层都是使用的红黑树。

weak_ptr是为了配合shared_ptr而引入的一种智能指针，因为没有重载operator*和->，所以它不能像普通指针那样使用。
weak_ptr最大作用在于协助shared_ptr工作，像旁观者那样观测资源的使用情况。weak_ptr可以从一个shared_ptr或者另一个weak_ptr对象构造，获得资源的观测权。但weak_ptr没有共享资源，它的构造不会引起shared_ptr引用计数的增加。
使用weak_ptr的成员函数use_count()可以观测资源的引用计数，另一个成员函数expired()的功能等价于use_count()==0，表示被观测的资源已经不存在。weak_ptr也可以使用成员函数lock()从被观测的shared_ptr获得一个可用的shared_ptr对象，从而操作资源。但当expired()==true的时候，lock()函数将返回一个存储空指针的shared_ptr。
简单来说就是：
- 观测shared_ptr资源使用情况。
- 解除shared_ptr循环引用问题.

从右向左压栈的顺序是与C/C++支持可变参数有关的。C/C++要求在声明参数可变的函数时，需要有至少一个确定的参数。为什么呢？因为需要有一个参数为函数提供可变参数的类型（否则函数怎么知道如何解析后续的可变参数？比如，可变参数列表中有两个参数，一个int型，一个byte型，函数在解析可变参数表时，怎么知道这5字节的数据到底应该如何去解析）如果一个可变参数的参数类型事先确定的话，这个参数就没有存在的意义了。
如果参数入栈顺序是从左向右压栈，第一个参数（即描述可变参数表各变量类型的那个参数）将被放在栈底，由于可变参的函数第一步就需要解析可变参数表的各参数类型，即第一步就需要得到上述参数，因此，将它放在栈底是很不方便的。当然，从左向右压栈的话也可以实现可变参的功能，但是这样的话，该功能实现起来会复杂些。

（答案仅供参考）Duilib是DirectUI思想的一种实现。DirectUI通俗来说就是在窗口上指定一块区域（仅仅是一个区域，不是一个实体控件）通过各种消息模拟一个控件的功能。完全可以在一个对话框类的OnMouseMove、OnLButtonDown等函数中模拟一个按钮出来。但是模拟的控件一多就混乱了，为了统一管理，逻辑上更清晰类似于实体控件。把每种控件封装成类处理各种消息，并通过自定义的消息分发机制把消息分发到各个模拟控件里。这种模拟的方式绘制和消息处理效率相比于实体控件要低。
Duilib的图片绘制代码中也有影响性能的地方，所有的控件的图片绘制都是调用CControlUI的DrawImage函数，而此函数调用了CRenderEngine的DrawImageString函数。在绘制图片时，DrawImageString会解析图片字符串的属性，然后找到对片的HBITMAP资源，最后调用真正的绘图函数去绘制。问题就在于每绘制一个图片都会再次解析一次字符串，当界面比较复杂，而且图片字符串也比较复杂时，这个解析的过程就影响了程序效率。当然这可以通过缓存图片资源解析结果的方式来优化。

内存泄漏是指在程序中动态申请的内存或者资源在使用完后，没有释放。这样可能导致程序使用的内存不断增大，最终会因系统内存不足，而导致程序崩溃或其他错误。
在Windows下可以通过任务管理器查看内存使用情况，可以简单分析是否有内存泄漏。也有很多像VLD这样的内存泄漏检测工具。如果是使用VC库来写程序的话，在Debug版本中也可以使用VC的C运行库中提供的像_CrtCheckMemory、_CrtCheckMemory、_CrtMemCheckpoint、_CrtMemDifference、_CrtMemDumpAllObjectsSince等函数来检测和定位内存泄漏问题。

程序崩溃一般有3个原因：
- 操作了野指针
- 内存访问错误（包括格式化数据类型错误、索引越界等）
- 堆栈溢出
在Windows下我们一般会在编译程序时保留其pdb文件，设置崩溃时生成dump文件。因此，可以通过VS或者Windbg结合pdb文件来分析崩溃产生的dump。大部分时候，通过Windbg的“!analyze -v”命令我们就能定位到崩溃问题的代码行。如果崩溃的代码行不是实际引起问题的地方，我们也可以通过相关代码的上下文结合log以及崩溃前操作等现象来分析崩溃原因。最后，还可以通过dump查看崩溃时其他的堆栈或者线程信息，做进一步分析。