C++面试题总结

Sat Sep 26, 2020

1.多态的实现

存在虚函数的类至少有一个(多继承会有多个)一维的虚函数表叫做虚表(virtual table)，属于类成员，虚表的元素值是虚函数的入口地址，在编译时就已经为其在数据端分配了空间。

编译器另外还为每个类的对象提供一个虚表指针(vptr)，指向虚表入口地址，属于对象成员。

在实例化派生类对象时，先实例化基类，将基类的虚表入口地址赋值给基类的虚表指针，当基类构造函数执行完时，再将派生类的虚表入口地址赋值给基类的虚表指针（派生类和基类此时共享一个虚表指针，并没有各自都生成一个），在执行父类的构造函数。

以上是C++多态的实现过程，可以得出结论：

1.有虚函数的类必存在一个虚表。
2.虚表的构建：基类的虚表构建，先填上虚析构函数的入口地址，之后所有虚函数的入口地址按在类中声明顺序填入虚表；派生类的虚表构建，先将基类的虚表内容复制到派生类虚表中，如果派生类覆盖了基类的虚函数，则虚表中对应的虚函数入口地址也会被覆盖，为了后面寻址的一致性。

虚函数表中有序放置了父类和子类中的所有虚函数，并且相同虚函数在类继承链中的每一个虚函数表中的偏移量都是一致的。所以确定的虚函数对应virtual table中一个固定位置n，n是一个在编译时期就确定的常量，所以，使用vptr加上对应的n，就可以得到对应的函数入口地址。

C++采用的这种绝对地址+偏移量的方法调用虚函数，查找速度快执行效率高，时间复杂度为O(1)

这里概括一下虚函数的寻址过程：

1、获取类型名和函数名
2、从符号表中获得当前虚函数的偏移量
3、利用偏移量得到虚函数的访问地址，并调用虚函数。vptrn

2.const关键字

常变量： const 类型说明符变量名

常引用： const 类型说明符 &引用名

常对象：类名 const 对象名

常成员函数：类名::fun(形参) const

常数组：类型说明符 const 数组名[大小]

常指针： const 类型说明符* 指针名，类型说明符* const 指针名

3.C++的空类

对于空类，编译器不会生成任何的成员函数，只会生成1个字节的占位符。

有时可能会以为编译器会为空类生成默认构造函数等，事实上是不会的。

编译器只会在需要的时候生成6个成员函数：一个缺省的构造函数、一个拷贝构造函数、一个析构函数、一个赋值运算符、一对取址运算符和一个this指针。

class Empty
{
};

等价于

class Empty
{
  public:
    Empty();                            //缺省构造函数
    Empty(const Empty &rhs);            //拷贝构造函数
    ~Empty();                           //析构函数 
    Empty& operator=(const Empty &rhs); //赋值运算符
    Empty* operator&();                 //取址运算符
    const Empty* operator&() const;     //取址运算符(const版本)
};

4.容器的优缺点

vector类似于C语言中的数组，它维护一段连续的内存空间，具有固定的起始地址。

list类似于C语言中的双向链表，它通过指针来进行数据的访问，因此维护的内存空间可以不连续，这也非常有利于数据的随机存取，因而它没有提供 [] 操作符重载。

deque类似于C语言中的双向队列，即两端都可以插入或者删除的队列。queue支持 [] 操作符，也就是支持随机存取，而且跟vector的效率相差无几。它支持两端的操作：push_back,push_front,pop_back,pop_front等，并且在两端操作上与list的效率也差不多。或者我们可以这么认为，deque是vector跟list的折中。

map类似于数据库中的１:１关系，它是一种关联容器，提供一对一(C++ primer中文版中将第一个译为键，每个键只能在map中出现一次，第二个被译为该键对应的值)的数据处理能力，这种特性了使得map类似于数据结构里的红黑二叉树。

multimap类似于数据库中的１:Ｎ关系，它是一种关联容器,提供一对多的数据处理能力。

set类似于数学里面的集合，不过set的集合中不包含重复的元素，这是和vector的第一个区别，第二个区别是set内部用平衡二叉树实现，便于元素查找，而vector是使用连续内存存储，便于随机存取。

multiset类似于数学里面的集合，集合中可以包含重复的元素。

1.如果需要高效的随机存取，不在乎插入和删除的效率，使用vector；

2、如果需要大量的插入和删除元素，不关心随机存取的效率，使用list；

3、如果需要随机存取，并且关心两端数据的插入和删除效率，使用deque；

4、如果打算存储数据字典，并且要求方便地根据key找到value，一对一的情况使用map，一对多的情况使用multimap；

5、如果打算查找一个元素是否存在于某集合中，唯一存在的情况使用set，不唯一存在的情况使用multiset。