C++开发工程师面试基本知识（汇总）

C++开发工程师面试基本知识（汇总）

文章目录

• 1.C++中指针和引用的区别
• 2.静态联编和动态联编（静态多态和动态多态）
• 3.虚函数和多态
• 4.抽象类（abstract class）
• 5.标准模板库（Standard Template Library，STL）
• 6.STL容器map和unordered_map

1.C++中指针和引用的区别

指针：指针是一个变量，只不过这个变量存储的是一个地址，指向内存的一个存储单元
引用：引用是变量的别名

2.静态联编和动态联编（静态多态和动态多态）

静态联编：在程序链接阶段就可以确定的调用。
动态联编：在程序执行时才能确定的调用。

3.虚函数和多态

C++中多态机制主要是靠虚函数实现的，关键字virtual

形成多态必须具备三个条件：
1、必须存在继承关系；
2、继承关系必须有同名虚函数（其中虚函数是在基类中使用关键字Virtual声明的函数，在派生类中重新定义基类中定义的虚函数时，会告诉编译器不要静态链接到该函数）；
3、存在基类类型的指针或者引用，通过该指针或引用调用虚函数；

虚函数（Virtual Function）是通过一张虚函数表（Virtual Table）来实现的。

在这个表中，主是要一个类的虚函数的地址表，这张表解决了继承、覆盖的问题，保证其容真实反应实际的函数。这样，在有虚函数的类的实例中这个表被分配在了 这个实例的内存中，所以，当我们用父类的指针来操作一个子类的时候，这张虚函数表就显得由为重要了，它就像一个地图一样，指明了实际所应该调用的函数。（虚函数表实质上是个指针数组，它中的指针指向实际调用的函数的地址）

4.抽象类（abstract class）

含有纯虚函数的类叫抽象父类。纯虚函数是通过在声明中使用 “= 0” 来指定的，如下所示：

? 抽象类是不能定义对象的，它只能作为接口使用

纯虚函数在基类中是没有定义的，必须在子类中加以实现，很像java中的接口函数

? 抽象类只能作为基类来使用，其纯虚函数的实现由派生类给出

如果派生类中没有重新定义纯虚函数，而只是继承基类的纯虚函数，则这个派生类仍然还是一个抽象类。如果派生类中给出了基类纯虚函数的实现，则该派生类就不再是抽象类了，它是一个可以建立对象的具体的类。

5.标准模板库（Standard Template Library，STL）

C++支持三种不同的编程方式：面向过程，面向对象和泛型编程。

C++的强大之处，一定程度上在于STL提供了大量的 实用的 高效的 代码。

STL以泛型思维为基础，提供了6大组件：容器(containers)、算法(algorithms)、迭代器(iterators)、仿函数(functors)、适配器(adapters)、分配器(allocators)。

vector、list、deque、set、map等都是容器中的结构，定义这些结构后，就可以用来存放数据。从实现的角度来看，容器就是一种class template。

6.STL容器map和unordered_map

当我们提到效率的时候，map和unordered_map之间存在着很大的区别。如果我们想要顺利地使用这些，必须了解这些结构实现的的内在机制。

map是靠红黑树（Red Black Tree）实现的。

红黑树是非严格平衡二叉搜索树，具有自动排序的功能（AVL是严格平衡二叉搜索树）。因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素。因此，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉搜索树（又名二叉查找树、二叉排序树，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值）存储的，使用中序遍历可将键值按照从小到大遍历出来。

unordered_map是靠哈希表（Hash table）实现的。

unordered_map内部实现了一个哈希表（也叫散列表），通过把关键码值映射到Hash表中一个位置来访问记录，查找的时间复杂度可达到O(1)，其在海量数据处理中有着广泛应用。因此，其元素的排列顺序是无序的。

map和unordered_map的查找元素时间和插入元素操作时间对比。

查找元素时间：
map： 该类型的搜索时间复杂度为log(n)
unordered_map ： 搜索时间复杂度。O(1)为平均时间，最坏情况下的时间复杂度为O（n）;

插入元素的时间：
map : 该操作的时间 复杂度为log(n)+再平衡时间
unordered_map : 该操作的时间复杂度与搜索的时间复杂度一样。

注：内容不断扩充中