C/C++ 各类问题总结、八股文整理_c++算法什么操作会大幅增加时间与内存

参考资料：c++后端开发 资料整理学习

一、基础

1、指针和引用的区别

• 指针是一个指向另一个变量的地址（新的变量），我们可以通过这个地址修改另一个变量；
  引用是一个别名，对引用的操作就是对变量本身的操作；
• 指针可以有多级；（级数）
  引用只有一级；
• 传参的时候，使用指针的话需要解引用才能对参数做修改；
  而使用引用可以直接对参数进行修改；
• 指针的大小一般是四个字节；
  引用的大小取决于被引用的对象（指的是使用sizeof运算符得到的结果，引用本质上还是使用指针，因此所占内存和指针是一样的）；
• 指针可以为空；
  引用不能为空。

---

---

2、在函数传递参数时，什么时候用指针，什么时候用引用？

• 需要返回函数内局部变量的地址的内存时使用指针；使用指针传参需要开辟内存，用完需释放指针，避免内存泄漏；
  而返回局部变量的引用的没有意义的。【C/C++ 返回函数内局部变量和局部变量的地址】
• 对栈空间大小敏感（如递归）的时候使用引用（使用引用不需要创建临时变量，开销更小）；
• 类对象作为参数传递时使用引用，这是C++类对象传递的标准方式。

---

---

3、堆和栈的区别

1、管理方式的不同： 栈由系统自动分配和释放，而堆是人为申请开辟和释放；

2、空间大小的不同： 栈获得的空间较小，一般最多为2M；而堆获得的空间较大，理论上有 2~3G；

3、申请效率的不同： 栈由系统自动分配，速度较快，而堆一般速度比较慢；

4、存储内容的不同： 栈在函数调用时，函数调用语句的下一条可执行语句的地址第一个进栈，然后函数的各个参数和局部变量进栈，其中静态变量是不入栈的。而堆一般是在头部用一个字节存放堆的大小，堆中的具体内容是人为安排;

5、底层结构的不同：栈向下生长，是连续的空间，后进先出，不产生内存碎片；而堆向上生长，是不连续的空间，会产生内存碎片。

---

---

4、堆快一些还是栈快一些？

• 栈快一些。
• 操作系统在底层会对栈提供支持，会分配专门的寄存器存放栈的地址，栈的入栈出栈操作也十分简单，并且有专门的指令执行，所以栈的效率比价快也比较高。
• 而堆的操作是由C/C++函数库提供的，在分配堆内存的时候，需要一定的算法寻找合适的内存大小，并且获取堆的内容需要两次访问，第一次访问指针，第二次根据指针保存的地址访问内存，因此堆比较慢。

---

---

5、new 和 delete 是如何实现的，以及new 和 malloc 的异同

实现：

• 在 new 一个对象的时候，首先会调用 malloc 为对象分配内存空间，然后调用对象的构造函数。
• delete 会调用对象的析构函数，然后调用 free 回收内存。

异同：

• malloc/free是C/C++的标准库函数，new/delete是 C++ 的运算符。他们都用于申请动态内存和释放内存。

• new 建立的是一个对象，返回指定类型的指针，并且可以自动计算所需要大小；
  malloc 分配的是一块内存区域，必须由我们计算要字节数，并且在返回后强行转换为实际类型的指针。。

• new 和 malloc 都会分配空间，但是 new 还会根据调用对象的构造函数进行初始化，malloc 需要给定空间大小（字节数），而 new 只需要对象名。

• 对于非内部数据对象（如类对象），只用malloc/free无法满足动态对象的要求。
  这是因为对象在创建的同时需要自动执行构造函数，消亡之前要自动执行析构函数，而由于malloc/free是库函数而不是运算符，不在编译器的控制权限之内，也就不能自动执行构造和析构函数。

• 对于内部数据类型，由于其没有构造函数和析构函数的要求，malloc/free 和 new/delete 的作用是等价的。

---

---

6、既然有了malloc/free，为什么还要new/delete？

• malloc/free是C/C++的标准库函数，new/delete是 C++ 的运算符。他们都用于申请动态内存和释放内存。
• new 建立的是一个对象，malloc 分配的是一块内存区域。
• 对于非内部数据对象（如类对象），只用malloc/free无法满足动态对象的要求。
  这是因为对象在创建的同时需要自动执行构造函数，消亡之前要自动执行析构函数，而由于malloc/free是库函数而不是运算符，不在编译器的控制权限之内，也就不能自动执行构造和析构函数。因此，在C++中需要一个能完成动态内存分配和初始化工作的运算符new，和一个能调用析构函数后释放内存的运算符delete。
• 对于内部数据类型，由于其没有构造函数和析构函数的要求，malloc/free 和 new/delete 的作用是等价的。

---

---

7、C和C++的区别

• C是面向过程，C++是面向对象。
  C++有封装、继承和多态的特性；封装隐藏了实现细节，使得代码模块化；继承通过子类继承父类的方法和属性，实现了代码重用；多态则是“一个接口，多个实现”，通过子类重写父类的虚函数，实现接口重用。
• C和C++内存管理的方法不一样，C使用malloc/free，C++除此之外还用new/delete。
• C++中有函数重载和引用等概念，C中没有。

---

---

8、delete 和 delete[] 的区别

• delete 只调用一次析构函数，而 delete[] 会调用每个成员的析构函数。
• 用 new 分配的内存用 delete 释放，用 new[] 分配的内存用 delete[] 释放。
• 调用 new[] 之后，释放内存使用 delete[]，没有指定需要析构对象的个数，，自己设计编译器的话怎么实现operator delete？
  就是申请内存时可以多分配几个字节用来存放对象个数，delete[] 的时候可以先调整指针位置来获取这个值。

---

---

9、C++、Java的联系与区别，包括语言特性、垃圾回收、应用场景等

• C++ 和Java都是面向对象的语言，C++是编译成可执行文件直接运行的，JAVA是编译之后在JAVA虚拟机上运行的，因此JAVA有良好的跨平台特性，但是执行效率没有C++ 高。
• C++的内存管理由程序员手动管理，JAVA的内存管理是由Java虚拟机完成的，它的垃圾回收使用的是标记-回收算法。
• C++有指针，Java没有指针，只有引用。
• JAVA和C++都有构造函数，但是C++有析构函数但是Java没有。

---

---

10、C++和Python区别

• python是一种脚本语言，是解释执行的，而C++是编译语言，是需要编译后在特定平台运行的。python可以很方便的跨平台，但是效率没有C++高。
• python使用缩进来区分不同的代码块，C++使用花括号来区分
• C++中需要事先定义变量的类型，而python不需要，python的基本数据类型只有数字，布尔值，字符串，列表，元组等等
• python的库函数比C++的多，调用起来很方便

---

---

11、struct 和 class 的区别

• struct 的成员的访问权限默认是 public，而class的成员默认是 private；

• struct 的继承默认是 public 继承，而class默认是private继承；

• class 可以作为模板，而 struct 不可以。（C++函数模板详解）

    template <class 类型参数1, class类型参数2, ...>	
    返回值类型  模板名(形参表)
    {
        函数体
    }
  1
  2
  3
  4
  5

• 总的来说，struct 更适合看成是一个数据结构的实现体，class 更适合看成是一个对象的实现体。

C和C++中的Struct区别:

C++ 中保留了C语言的 struct 关键字，并且加以扩充。
在C语言中，struct 只能包含成员变量，不能包含成员函数。
而在C++中，struct 类似于 class，既可以包含成员变量，又可以包含成员函数。

---

---

12、#define 和 const 的联系与区别

联系： 他们都用于定义常量。

区别：

• define 定义的变量没有类型，只是进行简单的文本替换，可能会有多个拷贝，占用的内存空间大；
• const 定义的常量是有类型的，存放在静态存储区，只有一个拷贝，占用的内存空间小。
• define 定义的常量是在预处理阶段进行替换，而 const 在编译阶段确定它的值。
• define 不会进行安全类型检查，而const会进行类型安全检查，安全性更高；
• const 可以定义函数而define不可以。

---

---

13、在c++中const的用法（定义、用途）

• const修饰类的成员变量目标是常量，不能被修改；
• const修饰类的成员函数，表示该函数不会修改类的数据成员，不会调用其他非const的成员函数。

---

---

14、C++中static的用法和意义

static的意思是静态的，用来修饰变量，函数和类成员。【作用：生命周期 和 作用域】（c++中static的用法详解）

• 变量：被static修饰的变量就是静态变量，它只在第一次被调用的时候初始化一次，被放在静态存储区，在程序运行过程中一直存在。局部静态变量的作用域在函数体内，全局静态变量的作用域在这个文件内。

• 函数：被static修饰过的函数就是静态函数，静态函数只能在本文件中使用，不能被其他文件调用，也不会和其他文件中的同名函数冲突。

• 类：
  在类中，被static修饰的成员变量是类静态成员，这个静态成员会被类的多个对象共用，也叫做类变量，而普通数据成员也叫做实例变量；静态成员变量定义时要分配空间，所以不能在类声明中定义，必须在类外进行一次初始化定义。
  –
  被static修饰的静态成员函数不能访问非静态成员，这是因为静态函数属于类而不是属于某个对象，静态函数中的 member可能都没有分配内存。静态成员函数没有隐含的 this 自变量，不能被 const 所修饰。所以，它就无法访问自己类的非静态成员；
  调用静态成员函数，可以用成员访问操作符(.)和(->)为一个类的对象或指向类对象的指针调用静态成员函数，也可以用类名::函数名调用。

在 C 和 C++ 的异同：
static修饰静态变量和静态函数是C和C++共有的，而static修饰类成员变量和成员函数则是C++独有。

全局静态变量：
定义：在全局变量之前加上关键字static，全局变量就被定义成为一个全局静态变量。
说明：
1）内存中的位置：静态存储区（静态存储区在整个程序运行期间都存在）
2）初始化：未经初始化的全局静态变量会被程序自动初始化为0（自动对象的值是任意的，除非它被显示初始化）
3）作用域：全局静态变量在声明它的文件之外是不可见的（实现文件隔离）。
全局静态变量的好处：
1）不会被其他文件所访问，修改；
2）其他文件中可以使用相同名字的变量，不会发生冲突。

局部静态变量：
定义：在局部变量之前加上关键字static，局部变量就被定义成为一个局部静态变量。
说明：
1）内存中的位置：静态存储区
2）初始化：未经初始化的局部静态变量会被程序自动初始化为0（自动对象的值是任意的，除非他被显示初始化）
3）作用域：作用域仍为局部作用域，当定义它的函数或者语句块结束的时候，作用域随之结束。
4）局部静态变量与全局变量同样只初始化一次，但是全局变量不属于函数本身，不再仅受函数的控制，给程序的维护带来不便。静态局部变量正好可以解决这个问题。静态局部变量保存在全局数据区，每次的值保持到下一次调用，直到下次赋新值。

注意：
当static用来修饰局部变量的时候，它就改变了局部变量的存储位置，从原来的栈中存放改为静态存储区。但是局部静态变量在离开作用域之后，并没有被销毁，而是仍然驻留在内存当中，直到程序结束，只不过我们不能再对它进行访问。
当static用来修饰全局变量的时候，它就改变了全局变量的作用域（在声明它的文件之外是不可见的），但是没有改变它的存放位置，还是在静态存储区中。

---

---

15、 计算以下几个类的大小

class A {};
int main(){
  cout<<sizeof(A)<<endl;	// 输出 1;
  A a;
  cout<<sizeof(a)<<endl;	// 输出 1;
  return 0;
}
1
2
3
4
5
6
7

空类的大小是1， 在C++中 空类会占 1 个字节，这是为了让对象的实例能够相互区别。

空类的实例大小就是类的大小，所以 sizeof(a) =1 字节；如果 a 是指针，则 sizeof(a) 就是指针的大小，即4字节。

具体来说，空类同样可以被实例化，并且每个实例在内存中都有独一无二的地址，因此，编译器会给空类隐含加上一个字节，这样空类实例化之后就会拥有独一无二的内存地址。

当该空白类作为基类时，该类的大小就优化为0了，子类的大小就是子类本身的大小。这就是所谓的空白基类最优化。

---

class A { virtual int Fun(){} };
int main(){
  cout<<sizeof(A)<<endl;// 输出 4(32位机器)/8(64位机器);
  A a;
  cout<<sizeof(a)<<endl;// 输出 4(32位机器)/8(64位机器);
  return 0;
}
1
2
3
4
5
6
7

因为有虚函数的类对象中都（最多）有一个 虚函数表指针 __vptr，其大小是 4(32位机器) / 8(64位机器) 字节。

---

class A { 
	static int a; 
	void fun();
};
int main(){
  cout<<sizeof(A)<<endl;	// 输出 1;
  A a;
  cout<<sizeof(a)<<endl;	// 输出 1;
  return 0;
}
1
2
3
4
5
6
7
8
9
10

普通函数也不占用类大小。

---

class A { int a; int b;};
int main(){
  cout<<sizeof(A)<<endl;// 输出 8;
  A a;
  cout<<sizeof(a)<<endl;// 输出 8;
  return 0;
}
 
class A { static int a; int b; };
int main(){
  cout<<sizeof(A)<<endl;// 输出 4;
  A a;
  cout<<sizeof(a)<<endl;// 输出 4;
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

静态成员存放在静态存储区，不占用类的大小。

---

---

16、 定义和声明的区别

• 声明是告诉编译器变量的类型和名字，不分配空间；
• 定义就是对这个变量和函数进行内存分配和初始化。需要分配空间，同一个变量可以被声明多次，但是只能被定义一次。

---

---

17、typedef 和 define 的区别

• #define是预处理命令，在预处理阶段是执行简单的替换，不做正确性的检查；
• typedef是在编译阶段处理的，它是在自己的作用域内给已经存在的类型一个别名。

---

---

18、被 free 回收的内存时立即返还给操作系统吗？为什么？

不是的，被 free 回收的内存会首先被 ptmalloc 使用双链表保存起来，当用户下一次申请内存的时候，会尝试从这些内存中寻找合适的返回。这样就避免了频繁的系统调用，占用过多的系统资源。同时 ptmalloc 也会尝试对小块内存进行合并，避免过多的内存碎片。

---

---

19、引用作为函数参数以及返回值的好处

对比值传递，引用传参的好处：
1）在函数内部可以对此参数进行直接修改
2）在内存中不产生被返回值的副本，提高函数调用和运行的效率（因为没有了传值和生成副本的时间和空间消耗）

但是有以下的限制：
1）不能返回局部变量的引用。因为函数返回以后局部变量就会被销毁；
2）不能返回函数内部 new 分配的内存的引用。虽然不存在局部变量的被动销毁问题，可对于这种情况（返回函数内部 new 分配内存的引用），又面临其它尴尬局面。例如，被函数返回的引用只是作为一个临时变量出现，而没有被赋予一个实际的变量，那么这个引用所指向的空间（由 new 分配）就无法释放，造成内存泄漏。
3）可以返回类成员的引用，但是最好是const。因为如果其他对象可以获得该属性的非常量的引用，那么对该属性的单纯赋值就会破坏业务规则的完整性。

---

---

20、友元函数和友元类

参考：友元(友元函数、友元类和友元成员函数) C++

• 友元(frend)机制允许一个类将对其非公有成员的访问权授予指定的函数或者类；提供了不同类的成员函数之间、类的成员函数和一般函数之间进行数据共享的机制。

• 友元函数是指某些虽然不是类成员函数却能够访问类的所有成员的函数。类授予它的友元特别的访问权，这样该友元函数就能访问到类中的所有成员。

• 友元类的所有成员函数都是另一个类的友元函数，都可以访问另一个类中的隐藏信息（包括私有成员和保护成员）。当希望一个类可以存取另一个类的私有成员时，可以将该类声明为另一类的友元类。
  (1) 友元关系不能被继承。
  (2) 友元关系是单向的，不具有交换性。若类B是类A的友元，类A不一定是类B的友元，要看在类中是否有相应的声明。
  (3) 友元关系不具有传递性。若类B是类A的友元，类C是B的友元，类C不一定是类A的友元，同样要看类中是否有相应的申明。

• 通过友元，一个不同函数或者另一个类中的成员函数可以访问类中的私有成员和保护成员。
  友元的正确使用能提高程序的运行效率，但同时也破坏了类的封装性和数据的隐藏性，导致程序可维护性变差。

---

---

21、volatile 关键字的作用

C++中volatile关键字的使用详解

volatile 关键字是一种类型修饰符，用它声明的类型变量表示可以被某些编译器未知的因素更改，比如：操作系统，硬件或者其他线程等。

遇到这个关键字声明的变量， 编译器对访问该变量的代码就不再进行优化（编译器的优化是让该变量存放到CPU寄存器而不是内存），系统总是从它所在的内存读取数据并立刻保存，从而可以提供对特殊地址的稳定访问。

volatile int i=10;
int a = i;
...
// 其他代码，并未明确告诉编译器，对 i 进行过操作
int b = i;
1
2
3
4
5

volatile 指出 i 是随时可能发生变化的，每次使用它的时候必须从 i 的地址中读取，因而编译器生成的汇编代码会重新从 i 的地址读取数据放在 b 中。

而优化做法是，由于编译器发现两次从 i 读数据的代码之间的代码没有对 i 进行过操作，它会自动把上次读的数据放在 b 中，而不是重新从 i 地址内存里面读。这样一来，如果 i 是一个寄存器变量、端口数据或者多线程共享变量就容易出错，所以说 volatile 可以保证对特殊地址的稳定访问。

---

---

22、STL中的 sort() 算法是用什么实现的，stable_sort()呢？

• STL中的 sort 是用快速排序和插入排序结合的方式实现的，stable_sort() 是归并排序。

---

---

23、vector 在什么情况下会迭代器失效？

• 当 vector 在插入的时候，如果原来的空间不够，会将申请新的内存并将原来的元素移动到新的内存，此时指向原内存地址的所有迭代器就失效了，first 和 end 迭代器都失效
• 当 vector 在插入的时候，被插入元素以及它后面的所有元素迭代器都失效
• 当 vector 在删除的时候，被删除元素以及它后面的所有元素迭代器都失效。

---

---

24、为什么C++没有实现垃圾回收？

• 首先，实现一个垃圾回收器会带来额外的空间和时间开销。你需要开辟一定的空间保存指针的引用计数和对他们进行标记 mark。然后需要单独开辟一个线程在空闲的时候进行 free 操作。
• 垃圾回收会使得C++不适合进行很多底层的操作。

---

---

25、有一个类A，里面有个类B类型的b，还有一个B类型的*b，什么情况下要用到前者，什么情况下用后者？

• 一个具体的类和一个类的指针，主要差别就是占据的内存大小和读写速度。
  类占据的内存大，但是读写速度快。类指针内存小，但是读写需要解引用。
• 所以可知，以搜索为主的场景中，应当使用类；以插入删除为主的场景中，应当使用类指针。

---

---

26、从代码到可执行文件的过程

1. 预编译（预处理）： （.cpp -> .i）

（1） 将所有的 #define 删除，并且展开所有的宏定义
（2） 处理所有的条件预编译指令，如 #if、#ifdef
（3） 处理#include预编译指令，将被包含的文件插入到该预编译指令的位置。
（4） 过滤所有的注释，如 //、/* */
（5） 添加行号和文件名标识。

2. 编译：（.s）

（1） 词法分析：将源代码的字符序列分割成一系列的记号。
（2） 语法分析：对记号进行语法分析，产生语法树。
（3） 语义分析：判断表达式是否有意义。
（4） 代码优化：公关子表达式的提取、循环优化、删除无用代码等。
（5） 目标代码生成：生成汇编代码。
（6） 目标代码优化：冗余指令删除、控制流优化、代数优化、机器特有指令的使用。

3. 汇编：(.o) 将汇编代码转变成机器 可执行的指令（二进制）。

4. 链接： 将不同的源文件产生的目标文件进行链接，从而形成一个可执行的程序。

---

---

27、头文件 “ ” 与 < > 有什么区别？

区别：

（1）尖括号< >的头文件是系统文件，双引号" "的头文件是自定义文件。

（2）编译器预处理阶段查找头文件的路径不一样。

查找路径：

使用尖括号< >的头文件的查找路径：编译器设置的头文件路径–>系统变量。

使用双引号" "的头文件的查找路径：当前头文件目录–>编译器设置的头文件路径–>系统变量。

---

---

28、宏#define

#define命令是一个宏命令，它用来将一个标识符定义为一个字符串，该标识符被称为宏名，被定义的字符串称为替换文本。

该命令有两种格式：一种是不带参数的宏定义，另一种是带参数的宏定义。

1、不带参数的宏定义的声明格式如下所示：

#define  宏名  字符串
例：#define  PI  3.1415
1
2

2、带参数的宏定义的声明格式如下所示：

#define  宏名（参数列表）  宏
例：#define  MAX(x,y)  ((x)>(y)?(x):(y))
1
2

宏是在预编译阶段被展开的。在预编译阶段是不会进行语法检查、语义分析的，宏被暴力替换，因此对于带参数的有些运算宏定义应注意括号的使用。

不带参数的宏命令我们可以用常量const来替代，比如const int PI = 3.1415，可以起到同样的效果，而且还比宏安全，因为这条语句会在编译阶段进行语法检查。

---

而带参数的宏命令有点类似函数的功能，在C++中可以使用内联函数或模板来替代，内联函数比宏命令安全，因为内联函数的替换发生在编译阶段，同样会进行语法检查、语义分析等。

---

---

29、inline 关键字 和 内联函数

• 普通的内联函数：

在函数名前加上 inline 关键字即定义了内联函数。
适合需要频繁调用且代码量小的函数，能够减少函数调用时指令的跳转次数。

内联函数的替换发生在编译阶段，同样会进行语法检查、语义分析等，该函数的代码会被插入到调用代码流中（空间换时间，概念上类似于展开 #define 宏）。

能够改善性能，因为优化器能够顺序集成被调用代码，即将被调用代码直接优化进调用代码中。

函数设定为内联，这只是个请求，而编译器可以忽略它。
有些函数即使声明为内联的也不一定会被编译器内联，比如虚函数和递归函数就不会被正常内联。（让编译器能够区别对待很长的函数和短的函数，另外如果选择了正确的编译选项，还能使编译器生成易于调试的代码。）

缺点：
（1）如果函数的代码较长，使用内联将消耗过多内存；
（2）如果函数体内有循环，那么执行函数代码时间比调用开销大，因此不要在内联函数内使用循环语句和开关语句；

• 类的成员函数：

（1）隐式声明的内联成员函数：类内声明并定义的函数都是内联成员函数（不管是否有inline修饰符）；
（2）显式声明的内联成员函数：函数用 inline 修饰符在类内声明，并在同一文件内在类外用 inline 修饰符定义函数体；
（3）普通成员函数：在类内声明，类外定义，不使用 inline 修饰符。

---

---

30、extern “C” 的作用

extern “C” 链接规范的主要作用就是为了能够正确实现C++代码调用其他C语言代码。
加上 extern “C” 后，会指示编译器这部分的代码按C语言，而不是C++的方式进行编译。

链接规范的用法有两种：

1. 单个声明的链接规范，比如：extern "C" void foo();
2. 一组声明的链接规范，比如：

extern "C"
{
　　void foo();
　　int bar();
}
1
2
3
4
5

需要链接规范的原因：函数重载

由于C++支持函数重载，因此编译器编译函数的过程中会将 参数类型+函数名 加到编译后的代码中；而C语言并不支持函数重载，因此编译C语言代码的函数时不会带上函数的参数类型，一般只包括函数名。

为什么不建议把#include 指令放置在 extern “C” { … } 里面？

1. extern “C” { } 的嵌套
2. 可能会无意中改变一个函数声明的链接规范

---

正确的做法是在对应的C头文件中单独加入extern “C”

---

---

31、C++ 虚函数（多态）和虚函数表

virtual 声明的函数为虚函数，与 C++ 多态相关。

虚函数是在编译时，并不能确定的类函数，而是在运行时确定的。

核心点：通过基类对象（指向子类的父类指针）访问派生类实现的（同名）函数。基类指针可以按照基类的方式来做事，也可以按照派生类的方式来做事，它有多种形态，或者说有多种表现方式，我们将这种现象称为多态。

1. 只需将基类中的成员函数声明为虚函数即可，派生类重写的 virtual 函数自动成为虚函数，并告诉编译器不要静态链接到该函数；

2. 基类中的析构函数必须为虚函数，否则delete的时候，只会调用基类析构函数，不会调用子类析构函数，造成子类对象释放不完全，内存泄漏；（声明了虚析构函数会先调用子类析构函数，再调用基类析构函数）

3. 虚函数的使用将导致类对象占用更大的内存空间（虚函数表指针）。虚函数表（virtual function table）包含了虚函数的地址，由所有虚函数对象共享。当派生类重新定义虚函数时，则将该函数的地址添加到虚函数表中。无论一个类对象中定义了多少个虚函数，虚函数指针只有一个。相应地，每个对象在内存中的大小要比没有虚函数时大4个字节（32位主机，不包括虚析构函数）。

4. 如果一个类含有虚表，则该类的所有对象都会含有一个虚表指针，并且该虚表指针指向同一个虚表。虚表的内容是依据类中的虚函数声明次序一一填入函数指针。

5. 派生类会继承基类的虚表（以及所有其他可以继承的成员），当我们在派生类中重写虚函数时，虚表就受了影响；表中的元素所指的函数地址将不再是基类的函数地址，而是派生类的函数地址。

6. 重写函数的特征标（包括参数的数目、类型和顺序）以及返回值必须与基类函数一致，否则将覆盖基类函数；

7. 重写不同于重载。（重载的函数具有不同的参数列表）

---

---

32、纯虚函数

一个类的成员函数被声明为纯虚函数，以便在派生类中重新定义该函数更好地适用于对象，则意味着该类是ABC(Abstract Base Class，抽象基类)，即只能被继承，而不能用来声明对象。纯虚函数通常需要在类声明的后面加上关键词 “=0” 。 如 virtual int area() = 0;

---

---

33、内存泄漏

申请了一块内存空间，使用完毕后没有释放掉。

• 导致内存泄漏：

（1）new 和 malloc 申请资源使用后，没有用 delete 和 free 释放；

（2）子类继承父类时，父类析构函数不是虚函数;

（3）比如文件句柄、socket、自定义资源类没有使用对应的资源释放函数;

（4）shared_ptr共享指针成环，造成循环引用计数，资源得不到释放。

• 定位内存泄漏：

（1）查看内存的使用情况 win 任务管理器 linux ps -aux

（2）分析代码、分析代码的工具检查malloc的调用情况

（3）封装malloc、free，记录申请、释放的信息到日志中

• 解决内存泄漏：

（1）良好的编码习惯，使用了内存分配的函数，一旦使用完毕，要记得使用其相应的函数释放掉；

（2）将分配的内存的指针以链表的形式自行管理，使用完毕之后从链表中删除，程序结束时可检查该链表；

（3）使用智能指针；

（4）将基类的析构函数设为虚函数；

（5）一些常见的工具插件可以帮助检测内存泄露，如ccmalloc、Dmalloc、Leaky、Valgrind等等。

---

---

34、内存碎片

内存碎片分为：内部碎片 和 外部碎片。

• 内部碎片： 是由于采用固定大小的内存分区，当一个进程不能完全使用分给它的固定内存区域时就产生了内部碎片，通常内部碎片难以完全避免；

• 外部碎片： 是由于某些未分配的连续内存区域太小，以至于不能满足任意进程的内存分配请求，从而不能被进程利用的内存区域。再比如堆内存的频繁申请释放，也容易产生外部碎片。

解决方法：段页式管理、内存池。

---

---

35、mutable 关键字

const 修饰变量表示改变量内容不可修改，在类中，const还可以修饰成员函数，修饰成员函数后就不可以更改成员变量了。

mutalbe 的意思是“可变”，和C++中的 const 相反，在C++中，mutable 也是为了突破 const 的限制而设置的。被 mutable 修饰的变量，将永远处于可变的状态，即使在一个 const 函数中。

所以 mutable 一个常见的作用就是 在 const 函数里面来修改被 mutable 修饰的成员变量。

---

---

36、C++的调用惯例

函数的调用过程：
1）从栈空间分配存储空间
2）从实参的存储空间复制值到形参栈空间
3）进行运算

形参在函数未调用之前都是没有分配存储空间的，在函数调用结束之后，形参弹出栈空间，清除形参空间。

数组作为参数的函数调用方式是地址传递，形参和实参都指向相同的内存空间，调用完成后，形参指针被销毁，但是所指向的内存空间依然存在，不能也不会被销毁。

当函数有多个返回值的时候，不能用普通的 return 的方式实现，需要通过传回地址的形式进行，即地址/指针传递。

37、变量不赋初值的情况，其值是多少？

• 对于存放在静态存储区的变量（全局变量、静态局部变量、静态全局变量），在初始化未赋初值（即未显式初始化）时，编译器会将其自动初始化为0（若是字符类数据则初始化为‘\0’）；
• 对于存放在栈空间的局部自动变量，在初始化未赋初值时，那么在第一次赋值之前，其值都是不确定的垃圾值。
• 对于局部数组变量，在进行部分显式初始化后，其余为定义的部分将自动初始化为0。

int a;
char ch;
int f[5];
int main()
{
    static int b; 
    int c;
    int d[5];
    int e[5] = {1};
    printf("字符型全局变量    --未赋初值  %c\n\n", ch); // 全局变量
    printf("整型全局变量      --未赋初值  %d\n\n", a);  // 全局变量
    printf("静态整型局部变量  --未赋初值  %d\n\n", b);  // 静态局部变量
    printf("整型局部变量      --未赋初值  %d\n\n", c);  // 局部变量
    printf("整型局部数组变量  --未赋初值  %d -- %d\n\n", d[0], d[2]);
    printf("整型局部数组变量  --部分赋值  %d -- %d\n\n", e[0], e[2]);       
    printf("整型全局数组变量  --未赋初值  %d -- %d\n\n", f[0], f[2]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

字符型全局变量    --未赋初值

整型全局变量      --未赋初值  0

静态整型局部变量   --未赋初值  0

整型局部变量      --未赋初值  4194432

整型局部数组变量   --未赋初值  6422400 -- 4201152

整型局部数组变量   --部分赋值  1 -- 0

整型全局数组变量   --未赋初值  0 -- 0
1
2
3
4
5
6
7
8
9
10
11
12
13

38、&和&&的区别

• &
  1）按位运算符；
  2）逻辑运算符：& 左右两端条件式有一个为假就会不成立，但是两端都会运行，不具有短路功能；
• &&
  逻辑运算符：短路运算符，因为只要左端条件式为假直接不成立，不会去判断右端条件式。

| 和 || 也类似，|| 具有短路功能，当左端条件为真时，结果成立，不再运行右端语句的判断。

39、运算符重载相关

C++的运算符包括：算术运算符、关系运算符、逻辑运算符、位运算符、赋值运算符、杂项运算符

只能作为成员函数重载的运算符有：=、()、[]、->、new、delete；

不能重载的运算符： . 、.*、::、sizeof 、?:
前2个不能被重载是保证能正常访问成员，域运算和sizeof不能被重载是因为运算对象是类而不是对象

40、动态绑定（多态）只有在指针和引用时才有效，其他情况下无效

#include <iostream>

using namespace std;
class A {
  public:
    virtual void print() {
        cout << "A::print()"
             << "\n";
    }
};

class B : public A {
  public:
    virtual void print() {
        cout << "B::print()"
             << "\n";
    }
};

class C : public A {
  public:
    virtual void print() {
        cout << "C::print()"
             << "\n";
    }
};

void print(A a) { a.print(); }

int main() {
    A a, *aa, *ab, *ac;
    B b;
    C c;
    aa = &a;
    ab = &b;
    ac = &c;
    a.print();
    b.print();
    c.print();
    aa->print();
    ab->print();
    ac->print();
    print(a);
    print(b);
    print(c);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

A::print() B::print() C::print() A::print() B::print() C::print() A::print() A::print() A::print()

虚函数会具有动态绑定功能，会按照实际类型调用相关的函数。
1、 a.print(); b.print(); c.print();
分别输出A::print() B::print() C::print(),
2、aa->print(); ab->print(); ac->print();
由于是虚函数，所以输出实际对象类型对应的print，因此输出A::print() B::print() C::print(),
3、void print(A a){ a.print();}函数声明的形参为A类型的，相当于强制类型转换，因此调用print(A a)函数的输出都是A::print()

41、 explicit 关键字的作用

在C++中，我们有时可以将构造函数用作自动类型转换函数。但这种自动特性并非总是合乎要求的，有时会导致意外的类型转换，因此，C++新增了关键字 explicit，用于关闭这种自动特性。即被explicit关键字能够防止被修饰的类构造函数进行自动地隐式类型转换（= 赋值 或 不同类型的值传递），只能显式地进行类型转换。

C++中的 explicit 关键字只能用于修饰只有一个参数或只有一个未提供默认值的类构造函数，它的作用是表明该构造函数是显式的，而非隐式的；

class Demo{`在这里插入代码片`
public:
    Demo(){};				//没有参数，无法进行隐式类型转换
    Demo(int a){};			//有唯一参数，可以进行隐式类型转换
    Demo(int a,int b){};	//多个参数且无默认值，无法进行隐式类型转换
    Demo(int a=0,int b=0,int c,int d=0){};	//只有一个参数无默认值，可以进行隐式类型转换
};

void fun(Demo demo){
	cout << "fun" << endl;
}

int main(){
	Demo d = 10;		// 自动类型转换
	fun(10);			// 自动类型转换
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

跟它相对应的另一个关键字是 implicit，即为隐式的，类构造函数默认情况下即声明为 implicit。

#include <iostream>
using namespace std;

class Demo{
public:
    Demo(){};					
    explicit Demo(int a){};		
    Demo(int a,int b){};		
    explicit Demo(const Demo& d){};
};
int main()
{
    Demo d1(10);	// 可以
    Demo d2 = 10;	// 报错！
    Demo d3 = d1;	// 报错！
    Demo d4(d1);	// 可以
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

42、哪些函数不能被声明为虚函数？

1. 普通函数（非成员函数，不能被覆盖）
2. 友元函数（C++不支持友元函数继承）
3. 内联函数（编译期间展开，虚函数是在运行期间绑定）
4. 构造函数（没有对象不能使用虚函数，先有构造函数后有虚函数，虚函数是对对象的动作）
5. 静态成员函数（只有一份大家共享）

虚函数的使用原则：可以把 public 或 protected 的部分成员函数声明为虚函数；
即普通的（非静态）成员函数或析构函数可以被声明为虚函数，
虚函数不能声明为静态的、全局的、友元的。

43、C++ << 对字符数组的重载

<< 运算符默认对输出字符数组和字符指针进行重载，均输输出字符串直到遇到结束符 ‘\0’ (但不输出该结束字符)为止

1. 输出由字符数组保存的字符串：char arr[]=“12345”; cout<<arr; 输出结果为：12345
2. 输出由字符指针指向的字符串：char* p = “12345”（或 p = arr;）;cout << p;输出结果为：12345

44、一个数的二进制 0 和 1的个数

x = x | (x + 1); 反转二进制中的最后一个 0

int fun(unsigned int x){	// 数 x 二进制 0 的个数
     int n = 0;
     while(x + 1){			// 每循环一次 0 的数量减一 ，直到溢出
         n++; 
         x = x | (x + 1);	// 反转最后一个 0
     }
     return n;
}
1
2
3
4
5
6
7
8

x = x & (x - 1); 反转二进制中的最后一个 1

int fun(unsigned int x){	// 数 x 二进制 1 的个数
     int n = 0;
     while(x){				// 每循环一次 1 的数量减一 ，直到为 0
         n++; 
         x = x & (x - 1);	// 反转最后一个 1
     }
     return n;
}
1
2
3
4
5
6
7
8

45、C++多态中虚函数表的存放位置？

参考一
参考二
参考三
参考四

46、C++中对象new出来和直接声明的区别

• 首先，最直观的，new出来的对象需要使用指针接收，而直接声明的不用。例如 A* a=new A() 与A a（）。
• new出来的对象是直接使用堆空间，而局部声明一个对象是放在栈中。
• new出来的对象类似于申请空间，因此需要delete销毁，而直接声明的对象则在使用完直接销毁。
• new出来的对象的生命周期是具有全局性，譬如在一个函数块里new一个对象，可以将该对象的指针返回回去，该对象依旧存在。而声明的对象的生命周期只存在于声明了该对象的函数块中，如果返回该声明的对象，将会返回一个已经被销毁的对象。
• new对象指针用途广泛，比如作为函数返回值、函数参数等。

#include <iostream>
using namespace std;
 
class A {
public:
	A(int x1=0,int y1=0):x(x1),y(y1){}
	~A()
	{
		cout << "distory A" << endl;
	}
	void printA() {
		cout << "OK" << endl;
	}
private:
	int x, y;
};
A define() {
	A a;
	return a;
    //这里能return 是因为使用了拷贝构造函数
    //如果拷贝构造函数delete后，只能new再返回
}
A* nobject() {
	A* a = new A();
	return a;
}
int main() {
	A a1 = define();
	a1.printA();
	A* a2 = nobject();
	a2->printA();
	delete a2;
	int waitNum
	cin >> waitNum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

47、if-else 和 switch 哪个效率更高

1、switch 以空间换时间，当分支较多时，switch的效率更高。因为switch是随机访问的，就是确定了选择值之后直接跳转到那个特定的分支，但是 if-else 是遍历所以得可能值，直到找到符合条件的分支。

2、由汇编代码可知道，switch-case占用较多的代码空间，因为它要生成跳表，特别是当 case 常量分布范围很大但实际有效值又比较少的情况，switch…case 的空间利用率将变得很低，此时优化的方法是不会生成跳表，而是像 if-else 一样逐一判断。

3、switch…case 只能处理 case 为常量的情况，对非常量的情况是无能为力的。例如 if (a > 1 && a < 100)，是无法使用 switch-case 来处理的。所以，switch 只能是在常量选择分支时比 if-else 效率高，但是if-else能应用于更多的场合，更加灵活。

---

---

---

二、C++ STL

1、C++的STL介绍

C++ STL 从广义来讲包括了三类：算法，容器和迭代器。

• 算法包括排序，复制等常用算法，以及不同容器特定的算法。
• 容器就是数据的存放形式，包括序列式容器和关联式容器（排序容器、哈希容器），序列式容器就是list，vector等，关联式容器就是set，map等。
• 迭代器就是在不暴露容器内部结构的情况下对容器的遍历。
• 适配器：stack<T> 和 queue<T> 本质上也属于序列容器，只不过它们都是在 deque 容器的基础上改头换面而成，通常更习惯称它们为容器适配器。

---

---

2、 STL源码中的hash表的实现

• STL中的 hash 表就是 unordered_map。使用的是哈希进行实现（注意与map的区别）。
  它记录的键是元素的哈希值，通过对比元素的哈希值来确定元素的值。
  unordered_map 的底层实现是 hashtable，采用开链法（也就是用桶）来解决哈希冲突，默认的桶大小是10.
• 哈希表HashMap的底层实现和扩容

---

---

3、解决哈希冲突的方式

C++ 数据结构与算法（五）（哈希表）

1. 开放地址方法：
   当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。
   （1）线性探测
   按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上往后加一个单位，直至不发生哈希冲突。　
   （2）再平方探测
   按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上先加1的平方个单位，若仍然存在则减1的平方个单位。随之是2的平方，3的平方等等。直至不发生哈希冲突。
   （3）伪随机探测
   按顺序决定值时，如果某数据已经存在，通过随机函数随机生成一个数，在原来值的基础上加上随机数，直至不发生哈希冲突。
2. 链式地址法（HashMap的哈希冲突解决方法）
   对于相同的值，使用链表进行连接。使用数组存储每一个链表。
   优点：
   （1）拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
   （2）由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
   （3）开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
   （4）在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。
   缺点：
   指针占用较大空间时，会造成空间浪费，若空间用于增大散列表规模进而提高开放地址法的效率。
3. 再哈希法：当发生哈希冲突时使用另一个哈希函数计算地址值，直到冲突不再发生。这种方法不易产生聚集，但是增加计算时间，同时需要准备许多哈希函数。
4. 建立公共溢出区：采用一个溢出表存储产生冲突的关键字。如果公共溢出区还产生冲突，再采用处理冲突方法处理。

---

---

4、STL中unordered_map和map的区别

• unordered_map 是使用哈希实现的，占用内存比较多，查询速度比较快，是常数时间复杂度。它内部是无序的，需要实现==操作符。
• map 底层是采用红黑树实现的，插入删除查询时间复杂度都是O(log(n))，它的内部是有序的，因此需要实现比较操作符(<)。

---

---

5、STL中vector的实现

• STL中的vector是封装了动态数组的顺序容器，用于维护一段连续的动态控件，内部有三个成员函数，用来储存起始位置，已使用位置，以及最后位置。
• 不过与动态数组不同的是，vector可以根据需要自动扩大容器的大小。具体策略是每次容量不够用时重新申请一块大小为原来容量两倍的内存，将原容器的元素拷贝至新容器，并释放原空间，返回新空间的指针。

---

---

6、vector使用的注意点及其原因，频繁对vector调用push_back()对性能的影响和原因

如果需要频繁插入，最好先指定vector的大小。频繁调用push_back()会使得程序花费很多时间在vector扩容上，这个过程是十分耗时和耗内存的，因为扩容涉及到申请新空间、拷贝、释放原空间等过程。这种情况可以考虑使用 list。

---

---

7、C++中vector和list的区别

• vector和数组类似，拥有一段连续的内存空间。vector申请的是一段连续的内存，当插入新的元素内存不够时，通常以2倍重新申请更大的一块内存，将原来的元素拷贝过去，释放旧空间。因为内存空间是连续的，所以在进行插入和删除操作时，会造成内存块的拷贝，时间复杂度为o(n)。
• list是由双向链表实现的，因此内存空间是不连续的。只能通过指针访问数据，所以list的随机存取非常没有效率，时间复杂度为o(n)；但由于链表的特点，能高效地进行插入和删除。
• vector拥有一段连续的内存空间，能很好的支持随机存取，因此vector::iterator支持“+”，“+=”，“<”等操作符。
  （随机存取或称直接访问指当存储器中的消息被读取或写入时，所需要的时间与这段信息所在的位置无关。反之则称循序访问，其所需要的时间与信息位置就会有关系。）
• list的内存空间可以是不连续，它不支持随机访问，因此list::iterator则不支持“+”、“+=”、“<”等
• vector::iterator和list::iterator都重载了“++”运算符。
• 总之，如果需要高效的随机存取，而不在乎插入和删除的效率，使用vector；
  如果需要大量的插入和删除，而不关心随机存取，则应使用list。

---

---

8、string 的底层实现

• string继承自basic_string,其实是对char进行了封装，封装的 string 包含了char数组，容量，长度等等属性。
• string可以进行动态扩展，在每次扩展的时候另外申请一块原空间大小两倍的空间（2*n），然后将原字符串拷贝过去，并加上新增的内容。

---

---

9、set，map和vector的插入复杂度

• map, set, multimap, multiset 上述四种容器采用红黑树实现（有序），红黑树是平衡二叉树的一种；
• unordered_set,unordered_map 采用哈希表实现（无序）；
• vector 和数组类似；
• list 即是链表。

---

---

10、set、map特性与区别

• set是一种关联式容器，特性如下：
  （1）set低层以红黑树为底层容器
  （2）所得元素的只有key没有value，value就是key
  （3）不允许键key重复
  （4）所有元素都会被自动排序
  （5）不能通过迭代器来改变set的值，因为set的值就是键
• map是一种关联式容器，特性如下：
  （1）map以红黑树作为底层容器
  （2）所有元素都是 pair<键key, 值value> 存在
  （3）不允许键key重复
  （4）所有元素是通过键进行自动排序的
  （5）map的键是不能修改的，但是其键对应的值是可以修改的

---

---

11、map、set为什么要用红黑树实现

红黑树是一种二叉查找树，但在每个节点上增加一个存储为用于表示节点的颜色，可以是红或者黑。通过对任何一条从根到叶子节点的路径上各个节点的着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因此，红黑树是一种弱平衡树，但又相对与要求严格的AVL树来说，他的旋转次数较少，所以对于搜索，插入，删除操作比较多的情况下，通常使用红黑树。

---

---

12、STL里迭代器什么情况下失效，具体说几种情况

STL 迭代器失效的几种情况总结
C++容器类插入和删除时迭代器的失效情况总结

• 序列式(数组式) 容器
  • vector 迭代器失效
    （1）erase() 和 insert() 会使当前位置到容器末尾元素的迭代器全部失效 ；这是因为vetor,deque使用了连续分配的内存，删除一个元素导致后面所有的元素会向前移动一个位置，此时 iter 已经指向的是未知内存；解决方法是利用 erase方法可以返回下一个有效的 iterator。
    （2）扩容时，所有迭代器都会失效。
  • deque 迭代器失效
    （1）插入到除首尾位置之外的任何位置都会导致迭代器、指针和引用都会失效，但是如果在首尾位置添加元素，迭代器会失效，但是指针和引用不会失效；
    （2）如果在首尾之外的任何位置删除元素，那么指向被删除元素外其他元素的迭代器全部失效；
    （3）在其首部或尾部删除元素则只会使指向被删除元素的迭代器失效。

---

• 节点式容器：
  • 关联式容器(如map, set,multimap,multiset)
    （1）删除当前的iterator，仅仅会使当前的iterator失效，只要在erase 时，递增当前 iterator erase(iter++)或者 利用 erase 返回的有效迭代器 iter = cont.erase(iter);进行操作即可；
    （2）插入不会使得任何迭代器失效。
    这是因为map之类的容器，使用了红黑树来实现，插入、删除一个结点不会对其他结点造成影响。
  • 链表式容器(如list)
    （1）删除当前的iterator，仅仅会使当前的iterator失效，只要在erase 时，递增当前 iterator erase(iter++)或者 利用 erase 返回的有效迭代器 iter = cont.erase(iter);进行操作即可；
    （2）插入不会使得任何迭代器失效。
    这是因为list之类的容器，使用了链表来实现，插入、删除一个结点不会对其他结点造成影响。

---

• 哈希容器（unordered_map, unordered_multimap, unordered_multiset, unordered_set）：
  （1）删除当前的iterator，仅仅会使当前的iterator失效，只要在erase 时，递增当前 iterator erase(iter++)或者 利用 erase 返回的有效迭代器 iter = cont.erase(iter);进行操作即可；
  （2）插入不会使得任何迭代器失效。
  这是因为这些容器使用了哈希表来实现，插入、删除一个结点不会对其他结点造成影响。

---

---

13、vector用swap来缩减空间（释放内存）

容器 v1 只有两个元素size，却有着很大的容量 capacity，会造成存储浪费（vector析构时会释放内存空间）。
所以我们 vector<int>(v1).swap(v1);
（1）用 v1 初始化一个临时对象，临时对象会根据 v1 的元素个数进行初始化；
（2）交换临时对象 和 v1；
（3）临时对象交换后销毁，v1原来的空间也销毁了；v1就指向现在的空间，明显占用空间减少（capacity = size）。

vector<int>().swap(v1); 则可以清空容器并释放内存。

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> v1;
    for(int i=0;i<10000;i++)
    v1.push_back(1);
    cout<<"size:"<<v1.size()<<endl;
    cout<<"capacity:"<<v1.capacity()<<endl;

    vector<int>(v1).swap(v1);
    //vector<int>(v1)代表用v1初始化一个临时对象；
    //.swap(v1)代表将之前的临时对象和v1交换
    cout<<"size:"<<v1.size()<<endl;
    cout<<"capacity:"<<v1.capacity()<<endl;

	vector<int>().swap(v1);		//清空容器并释放内存
	cout<<s1.capacity()<<endl;	//输出当前容器内的内存

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

size:10000
capacity:16384
size:10000
capacity:10000
1
2
3
4

扩展：C++ STL容器类型的内存释放

14、容器适配器 stack、queue、priority_queue

容器适配器就是将不适用的序列式容器（包括 vector、deque 和 list）变得适用。

容器适配器的底层实现就是通过封装某个序列式容器，并重新组合该容器中包含的成员函数，使其满足某些特定场景的需要。

容器适配器本质上还是容器，只不过此容器模板类的实现，利用了大量其它基础容器模板类中已经写好的成员函数。当然，如果必要的话，容器适配器中也可以自创新的成员函数。

需要注意的是，STL 中的容器适配器，其内部使用的基础容器并不是固定的，用户可以在满足特定条件的多个基础容器中自由选择。

三、C++特性

1、C++的重载和重写

• 重载（overload）是指函数名相同，参数列表不同的函数实现方法。它们的返回值可以不同，但返回值不可以作为区分不同重载函数的标志。
• 重写（override）是指函数名相同，参数列表相同，只有方法体不相同的实现方法。一般用于子类继承父类时对父类方法的重写。子类的同名方法屏蔽了父类方法的现象称为隐藏。

2、面向对象的三大特性

• 封装：隐藏了类的实现细节和成员数据，实现了代码模块化，比如类的 private 和 public；
• 继承：使子类可以服用父类的成员和方法，实现了代码重用；
• 多态：“一个接口，多个实现”，通过父类调用子类的成员，实现了接口重用，如父类的指针指向子类的对象。

3、多态的实现

C++多态包括编译时多态和运行时多态，
编译时多态体现在函数重载和模板上，
运行时多态体现在虚函数上。

虚函数：在基类的函数前加上 virtual 关键字，在派生类中重写该函数，运行时将会根据（指针）对象的实际类型来调用响应的函数。如果对象类型是派生类，就调用派生类的函数；如果对象类型时基类，就调用基类的函数。

4、 函数重载时怎么解决重名冲突

对于C++，同名函数会根据参数类型和数量的不同，编译成不用的函数名，这样在链接阶段就可以正确的区分，从而实现重载。

由于C++支持函数重载，因此编译器编译函数的过程中会将 参数类型+函数名 加到编译后的代码中；
而C语言并不支持函数重载，因此编译C语言代码的函数时不会带上函数的参数类型，一般只包括函数名。

5、C++虚函数、虚函数表、虚函数指针

• C++的虚函数（virtual 关键字）是实现多态的机制。
  核心点：通过基类对象（指向子类的父类指针）访问派生类实现的（同名）函数。

• 虚函数表是每个类中存放虚函数地址的指针数组，类的实例在调用虚函数时会在虚函数表中寻找函数地址进行调用；

• 虚表指针放在类的开头，通过对虚表指针的解引用找到虚表；

• 对象的虚表指针用来指向自己所属类的虚表，虚表中的指针会指向其继承的最近的一个类的虚函数；

• 虚函数的条目，及虚函数指针的赋值（或虚表的构造）发生在编译阶段；

• 虚表是属于类的，一个类只需要一个虚表即可，同一个类的所有对象都使用同一个虚表；

• 为了指定对象的虚表，对象内部包含一个虚表的指针，来指向自己所使用的虚表。为了让每个包含虚表的类的对象都拥有一个虚表指针，编译器在类中添加了一个指针 *__vptr，用来指向虚表。这样，当类的对象在创建时便拥有了这个指针，且这个指针的值会自动被设置为指向类的虚表。

• 一个继承类的基类如果包含虚函数，那么这个继承类也拥有自己的虚表；
  如果子类覆盖重写了父类的函数，则子类的虚函数表会指向子类实现的函数地址，否则指向基类的函数地址；

• 如果多重继承和多继承的话，子类的虚函数表长什么样子？
  多重继承的情况下越是祖先的父类的虚函数更靠前，多继承的情况下越是靠近子类名称的类的虚函数在虚函数表中更靠前。

6、编译器处理虚函数

如果类中有虚函数，就将虚函数的地址记录在类的虚函数表中。

派生类在继承基类的时候，如果有重写基类的虚函数，就将虚函数表中响应的函数指针设置为派生类的函数地址，否则为基类的函数地址；

为每个类的实例添加一个虚表指针（vptr），虚表指针指向类的虚函数表。实例在调用虚函数的时候，通过这个虚函数表指针找到类中的虚函数表，找到相应的函数进行调用。

7、基类的析构函数一般写成虚函数的原因

• 首先析构函数可以为虚函数，当析构一个指向子类的父类指针时，编译器可以根据虚函数表寻找到子类的析构函数进行调用，从而正确释放子类对象的资源。

• 如果析构函数不被声明成虚函数，则编译器实施静态绑定，在删除指向子类的父类指针时，只会调用父类的析构函数而不调用子类析构函数，这样就会造成子类对象析构不完全造成内存泄漏。

8、构造函数为什么一般不定义为虚函数

• 因为创建一个对象时需要确定对象的类型，而虚函数是在运行时确定其类型的。而在构造一个对象时，由于对象还未创建成功，编译器无法知道对象的实际类型，是类本身还是类的派生类等等；

• 虚函数的调用需要虚函数表指针，而该指针存放在对象的内存空间中；若构造函数声明为虚函数，那么由于对象还未创建，还没有内存空间，更没有虚函数表地址用来调用虚函数即构造函数了。

9、构造函数或者析构函数中调用虚函数会怎样

• 在构造函数中调用虚函数，由于当前对象还没有构造完成，此时调用的虚函数指向的是基类的函数实现方式。

• 在析构函数中调用虚函数，此时调用的是子类的函数实现方式。

10、纯虚函数

• 纯虚函数是只有声明没有实现的虚函数，是对子类的约束，是接口继承；
  以便在派生类中重新定义该函数，更好地适用于对象。

• 纯虚函数通常需要在类声明的后面加上关键词 “=0” 。 如 virtual int area() = 0;

• 包含纯虚函数的类是抽象类，它不能被实例化（声明对象），只有实现了这个纯虚函数的子类才能生成对象；

• 使用场景：当这个类本身产生一个实例没有意义的情况下，把这个类的函数实现为纯虚函数，比如动物可以派生出老虎兔子，但是实例化一个动物对象就没有意义。并且可以规定派生的子类必须重写某些函数的情况下可以写成纯虚函数。

11、静态绑定和动态绑定

• 静态绑定也就是将该对象相关的属性或函数绑定为它的静态类型，也就是声明时的类型，在编译的时候就确定。在调用的时候编译器会寻找它声明的类型进行访问。

• 动态绑定就是将该对象相关的属性或函数绑定为它的动态类型，具体的属性或函数在运行期确定（类型可以变化，多态性），通常通过虚函数 virtual 实现动态绑定。

12、深拷贝和浅拷贝

基本类型：即值类型，变量对应的内存区域存储的是值；
引用类型：即地址类型，变量对应的内存区域存储的是指针，而真正的数据在指针地址对应的内存区域里。

对于基本类型，如 int a = 10; int b = a; 拷贝就是赋值，在栈空间申请 b 的位置，然后将 a 的值赋值给 b，两者互相独立。

对于引用类型才有深拷贝的浅拷贝的区别：

• 浅拷贝：拷贝出来的目标对象的指针和源对象的指针指向的内存空间是同一块空间；
  浅拷贝只是一种简单的拷贝，让几个对象公用一个内存，然而当内存销毁的时候，指向这个内存空间的所有指针需要重新定义，不然会造成野指针错误。
• 深拷贝是新开辟一块空间，拷贝所有的属性，并拷贝属性指向的动态分配的内存（原对象的资源）。
  当对象和它所引用的对象一起拷贝时即发生深拷贝。
  深拷贝可以避免重复的释放和写冲突，例如使用浅拷贝的对象进行释放后，对原对象的释放会导致内存泄漏或程序崩溃。

在C+ +面向对象程序设计中，通过构造函数对对象进行初始化，它可以为对象在计算机内存中开辟内存空间，也可以为对象的数据成员提供初始值。拷贝构造函数的功能是用一个已有的对象来初始化一个被创建的同类的对象，是一种特殊的构造函数，具有一般构造函数的所有特性，其形参是本类对象的引用 &。用户可以根据自己实际问题的需要定义特定的拷贝构造函数，以实现同类对象之间数据成员的传递。CExample(const CExample& C){ }

一般情况下，只需使用系统提供的浅拷贝构造函数即可，但是，如果对象的数据成员包括指向堆空间的指针，就不能使用这种拷贝方式，否则会导致指针悬挂问题，因为两个对象都拥有同一个资源，对象析构时，该资源将经历两次资源返还，此时必须自定义深拷贝构造函数 或 重载赋值运算符 =，为创建的对象分配堆空间，否则会出现动态分配的指针变量悬空的情况。

13、对象复用，零拷贝

• 对象复用指的是设计模式，对象可以采用不同的设计模式达到复用的目的，最常见的就是集成和组合模式。
• 零拷贝指的是在进行操作时，避免CPU从一处存储拷贝到另一处存储中。在Linux中，我们可以减少数据在内核空间和用户空间的来回拷贝实现，比如通过调用 mmap() 代替 read() 调用。

用程序调用mmap()，磁盘上的数据会通过DMA被拷贝的内核缓冲区，接着操作系统会把这段内核缓冲区与应用程序共享，这样就不需要把内核缓冲区的内容往用户空间拷贝。应用程序再调用 write()，操作系统直接将内核缓冲区的内容拷贝到 socket 缓冲区中，这一切都发生在内核态，最后，socket 缓冲区再把数据发到网卡去。

14、C++的所有构造函数

• 默认构造函数是当类没有实现自己的构造函数时，编译器默认提供的一个无参缺省构造函数，不会处理静态数据成员；
• 重载构造函数也成为一般构造函数，一个类可以有多个重载构造函数，但是需要参数类型或者个数不同；
  可以在重载构造函数中自定义类的初始化方式；
• 拷贝构造函数是一种特殊的构造函数，形参是本类对象的引用 &，它在创建对象时，是使用同一类中之前创建的对象来初始化新创建的对象（对象复制）。

#include <iostream>
using namespace std;

class A{
public:
	int a;
	A(){
		cout << "默认构造函数" << endl;
	}

	A(int a) : a(a){
		cout << "(带参数)重载构造函数" << endl;
	}

	A(A& b){
		a = b.a;
		cout << "拷贝构造函数" << endl;
	}
};

int main()
{
	A a;
	A aa(1);
	A aaa(aa);
 	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

声明了重载构造函数或拷贝构造函数后，如果不声明默认构造函数，那么这个类将不具有默认构造函数。

15、什么时候调用拷贝构造函数

• 对象以值传递的方式传入函数参数，会拷贝创建一个临时的对象变量，函数结束后会析构掉这个对象；
• 对象以值传递的方式从函数返回，函数执行结束时，将调用拷贝构造函数对无名临时对象初始化；
• 对象需要通过另一个同类型对象进行初始化。

16、结构体内存对齐方式和为什么要进行内存对齐？

因为结构体的成员可以有不同的数据类型，所占大小也不一样；同时，由于CPU读取数据时按块读取的,内存对齐可以使得CPU一次就可以将所需的数据读进来，能够减少访存指令周期，提高CPU存储速度。

对齐规则：
（1）结构体变量的首地址能够被其最宽基本成员类型大小所整除；
（2）结构体每个成员相对于结构体首地址的偏移量都是成员大小的整数倍，如有需要编译器会在成员之间加上填充字节（internal adding）；
（3）结构体的总大小为结构体最宽基本成员类型大小的整数倍，如有需要编译器会在最末一个成员之后加上填充字节（trailing padding）。

17、C++ 智能指针

18、模板的用法与使用场景、实现原理

用 template <typename T, ....> 关键字进行声明，接下来就可以进行模板函数和模板类的
的编写。

编译器会对函数模板进行两次编译：
第一次编译在声明的地方对模板代码本身进行编译，这次编译会进行语法检查，但不会生成具体的代码；
第二次编译是对代码参数替换后再进行编译，生成具体的函数代码。

19、成员初始化列表的概念，为什么用成员初始化列表会快一些？

成员初始化列表就是在类或者结构体的构造函数中，在参数列表后以冒号:开头，逗号,进行分隔的一系列初始化字段。

class A{
	int id;
	string name;
	const int price;
	A(int& inputID, string& inputName, int p) : id(inputID), name(inputName), price(p) {} 	// 成员初始化列表
};
1
2
3
4
5
6

初始化类的成员有两种方式，一是使用初始化列表，二是在构造函数体内进行赋值操作。

使用初始化列表主要是基于性能问题，对于内置类型，如 int, float 等，使用初始化类表和在构造函数体内初始化差别不是很大，但是对于类类型来说，最好使用初始化列表，为什么呢？

• 因为使用成员初始化列表进行初始化的话，会直接使用传入参数的拷贝构造函数进行初始化，省去了一次执行默认构造函数的过程；

• 而通过在构造函数体内进行赋值的话，会调用一次默认构造函数，然后再进行赋值操作进行初始化。

使用初始化列表少了一次调用默认构造函数的过程，这对于数据密集型的类来说，是非常高效的。

此外，成员是按照他们在类中出现的顺序（类结构体中声明的顺序）进行初始化的，而不是按照他们在初始化列表出现的顺序初始化的。

另外，有三种情况跟必须使用成员初始化列表进行初始化：

1. 常量成员的初始化，因为常量成员只能初始化不能赋值；
2. 引用类型，引用必须在定义的时候初始化，并且不能重新赋值；
3. 没有默认构造函数的对象，因为使用初始化列表可以不必调用默认构造函数来初始化，而是直接调用拷贝构造函数初始化。

四、调试程序