C_C++.md

## C/C++ 八股文

### 基础语法-01-20

> <a id="name1">完整例子以及解读</a>参考：https://interviewguide.cn/notes/03-hunting_job/02-interview/01-01-01-basic.html

#### 1、在main执行之前和之后执行的代码可能是什么？

**main函数执行之前**，主要就是初始化系统相关资源：

+ 设置栈指针
+ 初始化静态`static`变量和`global`全局变量，即`.data`段的内容
+ 将未初始化部分的全局变量赋初值：数值型`short`，`int`，`long`等为`0`，`bool`为`FALSE`，指针为`NULL`等等，即`.bss`段的内容     
+ 全局对象初始化，在`main`之前调用构造函数，这是可能会执行前的一些代码
+ 将main函数的参数`argc`，`argv`等传递给`main`函数，然后才真正运行`main`函数
+ `__attribute__((constructor))`

**main函数执行之后**：  

+ 全局对象的析构函数会在main函数之后执行； 
+ 可以用 **`atexit`** 注册一个函数，它会在main 之后执行;
+ `__attribute__((destructor))`



#### 2、结构体内存对齐问题？

- 结构体内成员按照声明顺序存储，第一个成员地址和整个结构体地址相同
- 未特殊说明时，按结构体中size最大的成员对齐（若有double成员，按8字节对齐）

- C++11 以后引入两个关键字 [alignas](https://zh.cppreference.com/w/cpp/language/alignas) 与 [alignof](https://zh.cppreference.com/w/cpp/language/alignof)。其中`alignof`可以计算出类型的对齐方式，`alignas`可以指定结构体的对齐方式

- `alignas`在某些情况下是不能使用的，若`alignas`小于自然对齐的最小单位，则被忽略，具体例子[参考原文](#name1)

- 如果想使用单字节对齐的方式，使用`alignas`是无效的。应该使用`#pragma pack(push,1)`或者使用`__attribute__((packed))`




#### 3、指针和引用的区别 :fire:

- 指针是一个变量，存储的是一个地址，引用跟原来的变量实质上是同一个东西，是原变量的别名

- 指针可以有多级，引用只有一级

- 指针可以为空，引用不能为`NULL`且在定义时必须初始化

- 指针在初始化后可以改变指向，而引用在初始化之后不可再改变

  > 因为引用的本质就是**指针常量**，int &ref = a; 实际为 int * const ref = &a;

- `sizeof`指针得到的是本指针的大小，`sizeof`引用得到的是引用所指向变量的大小

- 当把指针作为参数进行传递时，也是将实参的一个拷贝传递给形参，两者指向的地址相同，但不是同一个变量，**在函数中改变这个变量的指向不影响实参，而引用却可以**

  ```cpp
  void fun(int *p) { 
   *p = 4;	// 这个没有改变形参 p 的值，但是可以改变 p 指向地址的值
  }
  void func(int &p) { p = 5; }	// 引用本质是指针常量
  ```
  
- **引用本质是一个指针，同样会占8字节内存**；指针是具体变量，需要占用存储空间（具体情况还要具体分析）

- 引用在声明时必须初始化为另一变量，一旦出现必须为`typename refname &varname`形式；指针声明和定义可以分开，可以先只声明指针变量而不初始化，等用到时再指向具体变量。

- 引用一旦初始化之后就不可以再改变（变量可以被引用为多次，但引用只能作为一个变量引用）；指针变量可以重新指向别的变量。

- 不存在指向空值的引用，必须有具体实体；但是存在指向空值的指针

> 参考代码：[点击寻找](#name1)
>
> 在编译器看来: 自动解引用并且转换为指针
>
> ```cpp
> int a = 10, &b = a;
> b = 20;
> // 👆🏻等价于👇🏻
> int a = 10, * const b = &a;
> *b = 20;
> ```



#### 4、在传递函数参数时，什么时候该使用指针，什么时候该使用引用呢？

<details>
    <summary>查看答案</summary>
    <li>需要返回函数内局部变量的内存的时候用指针。使用指针传参需要开辟内存，用完要记得释放指针，不然会内存泄漏。而返回局部变量的引用是没有意义的
    <li>对栈空间大小比较敏感（比如递归）的时候使用引用。使用引用传递不需要创建临时变量，开销要更小</li>
    <li>类对象作为参数传递的时候使用引用，这是C++类对象传递的标准方式</li>
</details>



#### 5、堆和栈的区别

- 申请方式不同：栈由系统自动分配，堆是自己申请和释放的。

- 申请大小限制不同

  - 栈顶和栈底是之前预设好的，栈是向栈底扩展，大小固定，可以通过`ulimit -a`查看，由`ulimit -s`修改

  - 堆向高地址扩展，是不连续的内存区域，大小可以灵活调整
- 申请效率不同

  - 栈由系统分配，速度快，不会有碎片，栈（先进后出）

  - 堆由程序员分配，速度慢，且会有碎片，二叉树（堆排序）


> 栈空间默认是 4M, 堆区一般是 1G~4G 

<img src="https://img-blog.csdnimg.cn/20200328120626151.png" alt="heap and stack" style="zoom:90%;" align="left"/>



|                  | 堆                                                           | 栈                                                           |
| :--------------- | :----------------------------------------------------------- | ------------------------------------------------------------ |
| **管理方式**     | 堆中资源由程序员控制（容易产生memory leak）                  | 栈资源由编译器自动管理，无需手工控制                         |
| **内存管理机制** | 系统有一个**记录空闲内存地址的链表**，当系统收到程序申请时，遍历该链表，寻找第一个空间大于申请空间的堆结点，删除空闲结点链表中的该结点，并将该结点空间分配给程序（大多数系统会在这块内存空间首地址记录本次分配的大小，这样delete才能正确释放本内存空间，另外系统会将多余的部分重新放入空闲链表中） | 只要栈的剩余空间大于所申请空间，系统为程序提供内存，否则报异常提示栈溢出。（这一块理解一下**链表和队列**的区别，不连续空间和连续空间的区别，应该就比较好理解这两种机制的区别了） |
| **空间大小**     | 堆是不连续的内存区域（因为系统是用链表来存储空闲内存地址，自然不是连续的），堆大小受限于计算机系统中有效的虚拟内存（32bit  系统理论上是4G），所以堆的空间比较灵活，比较大 | 栈是一块连续的内存区域，大小是操作系统预定好的，Windows下栈大小是2M（也有是1M，在编译时确定，VC中可设置） |
| **碎片问题**     | 对于堆，频繁的new/delete会造成大量碎片，使程序效率降低       | 对于栈，它是有点类似于数据结构上的一个先进后出的栈，进出一一对应，不会产生碎片。（看到这里我突然明白了为什么面试官在问我堆和栈的区别之前先问了我栈和队列的区别） |
| **生长方向**     | 堆向上，向高地址方向增长                                     | 栈向下，向低地址方向增长                                     |
| **分配方式**     | **堆都是动态分配**（没有静态分配的堆）                       | **栈有静态分配和动态分配**，静态分配由编译器完成（如局部变量分配），动态分配由`alloca`函数分配，但栈的动态分配的资源由编译器进行释放，无需程序员实现 |
| **分配效率**     | 堆由C/C++函数库提供，机制很复杂。所以堆的效率比栈低很多      | 栈是其系统提供的数据结构，计算机在底层对栈提供支持，分配专门寄存器存放栈地址，栈操作有专门指令 |

> **形象的比喻**
>
> - 栈就像我们去饭馆里吃饭，只管点菜（发出申请）、付钱、和吃（使用），吃饱了就走，不必理会切菜、洗菜等准备工作和洗碗、刷锅等扫尾工作，他的好处是快捷，但是自由度小
>
> - 堆就象是自己动手做喜欢吃的菜肴，比较麻烦，但是比较符合自己的口味，而且自由度大



#### 6、堆快还是栈快？

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


#### 7、区别以下指针类型？

- 指针数组强调数组，里面元素都是指针；数组指针强调指针，指针指向**整个数组**首地址。[参考](http://c.biancheng.net/view/335.html)

```cpp
// 指针数组，强调数组概念，是一个数组变量，数组大小为5，数组内每个元素都是指向int类型的指针变量
// [] 优先级大于 *，所以 p 和 [] 先结合，表现为数组
int *p[5];	

// 数组指针，强调是指针，只有一个变量，是指针类型，不过指向的是一个int类型的数组，这个数组大小是5
int arr[5]={1，2，3，4，5};
int (*p1)[5] = &arr;
// int (*p2)[5] = arr; // error，等号两侧类型不匹配

// 函数声明，函数名是p，参数是int类型的，返回值是int *类型的
int *p(int);

// 函数指针，强调是指针，该指针指向的函数具有int类型参数，并且返回值是int类型的
int (*p)(int)
```

**另外参考：施磊《指向类成员的指针》**



#### 8、new/delete 与 malloc/free 的异同

**相同点**：都可用于内存的动态申请和释放

**不同点**：

- 前者是 C++ 运算符，后者是 C/C++ 语言标准库函数

- new 自动计算要分配的空间大小，malloc 需要手工计算

- new 是类型安全的，malloc 不是。例如：

  ```cpp
  int *p = new float[2]; //编译错误
  int *p = (int*)malloc(2 * sizeof(double));//编译无错误
  ```

*  new 调用名为 **operator new** 的标准库函数分配足够空间并调用相关对象的构造函数，delete 对指针所指对象运行适当的析构函数；然后通过调用名为 **operator delete** 的标准库函数释放该对象所用内存。后者均没有相关调用
*  后者需要库文件支持，前者不用
*  new 是封装了malloc，直接 free 不会报错，但是这只是释放内存，而不会析构对象 



#### 9、new和delete是如何实现的？

- new 的实现过程是：首先调用名为 **operator new** 的标准库函数，分配足够大的原始为类型化的内存，以保存指定类型的一个对象；接下来运行该类型的一个构造函数，用指定初始化构造对象；最后返回指向新分配并构造后的的对象的指针
- delete的实现过程：对指针指向的对象运行适当的析构函数；然后通过调用名为 **operator delete** 的标准库函数释放该对象所用内存



#### 10、malloc和new的区别？

- malloc 和 free 是**标准库函数**，支持[覆盖](https://blog.csdn.net/cpongo3/article/details/93996121)；new 和 delete 是**运算符**，支持重载

- malloc 仅仅分配内存空间，free 仅仅回收空间，不具备调用构造函数和析构函数功能，用 malloc 分配空间存储类的对象存在风险；new 和 delete 除了分配回收功能外，还会调用构造函数和析构函数

- malloc 和 free 返回的是 void 类型指针（必须进行类型转换），new 和 delete 返回的是具体类型指针



#### 11、既然有了malloc/free，C++中为什么还需要new/delete呢？直接用malloc/free不好吗？

- malloc/free 和 new/delete 都是用来申请内存和回收内存的
- 在对 **非基本数据类型的对象** 使用的时候，对象创建的时候还需要执行构造函数，销毁的时候要执行析构函数，即使用 new/delete
- malloc/free 是库函数，是已经编译的代码，所以不能把构造函数和析构函数的功能强加给 malloc/free，所以 new/delete 是必不可少的



#### 12、被free回收的内存是立即返还给操作系统吗？

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



#### 13、宏定义和函数有何区别？

- 宏在 **预处理阶段** 完成替换，之后被替换的文本参与编译，相当于直接插入了代码，运行时不存在函数调用，执行起来更快；函数调用在 **运行** 时需要跳转到具体调用函数
- 宏定义属于在结构中插入代码，没有返回值；函数调用具有返回值
- 宏定义参数没有类型，不进行类型检查；函数参数具有类型，需要检查类型
- 宏定义不要在最后加分号



#### 14、宏定义和typedef区别？

- 宏主要用于定义**常量及书写复杂的内容**；typedef 主要用于定义**类型别名**

- 宏替换发生在编译阶段之前，属于文本插入替换；typedef 是编译的一部分

- 宏不检查类型；typedef 会检查数据类型

- 宏不是语句，不要在最后加分号；typedef 是语句，要加分号标识结束

- 注意对指针的操作，`typedef char * p_char` 和 `#define p_char char *` 区别巨大

  ```cpp
  #include <iostream>
  using namespace std;
  
  typedef int* PINT;
  #define SINT int*
  
  int main()
  {
      int a = 10, b = 20, c = 30;
      const PINT p = &a;	// const 修饰的是 p，所以 p 是不能被赋值的
      *p = 100;			// 但是 *p 是可以变的
      // p = &c;  		// error
      cout << p << ' ' << *p << endl;
  
      const int* p1 = &b;	// 这里 const 修饰的是 *p1，和 int const *p1 等价
      // *p1 = 100;		// error
      p1 = &b;			// p1 本身是变量
      cout << p1 << ' ' << *p1 << endl;
      
      const SINT p2 = &a;	// 等价于 const int* p2，同上
      // *p2 = 100;		// error，*p2 是常量
      p2 = &c;
      cout << p2 << ' ' << *p2 << endl;
      return 0;
  }
  ```



#### 15、变量声明和定义区别？

- 声明仅仅是把变量的声明的位置及类型提供给编译器，并不分配内存空间；定义要在定义的地方为其分配**存储空间**

- 相同变量可以在多处声明（外部变量extern），但只能在一处定义



#### 16、strlen和sizeof区别？

- sizeof 是**运算符**，并不是函数，结果在 **编译时得到** 而非运行中获得；strlen是字符处理的**库函数**

- sizeof 参数可以是任何数据的类型或者数据（sizeof参数不退化）；strlen的参数只能是字符指针且结尾是`'\0'`的字符串

- 因为sizeof值在编译时确定，所以不能用来得到动态分配（运行时分配）存储空间的大小

~~~cpp
const char* str = "name";
cout << strlen(str) << ' ' << sizeof(str) << endl;  // 4 8(指针长度)

char s[] = {'n', 'a', 'm', 'e', '\0'};
cout << strlen(s) << ' ' << sizeof s << endl;       // 4 5

// 上面 sizeof（str）的值为8，是在64位的编译环境下的，指针的占用大小为8字节，
// 而在32位环境下，指针占用大小为4字节
// 一个指针占内存的大小跟编译环境有关，而与机器的位数无关
// 比如64位系统的GCC默认生成的是64位程序，但如果你指定-m32参数，那就会生成32位程序
~~~



#### 17、常量指针和指针常量区别？:fire:

- **指针常量**：指针本身是一个常量，必须初始化，一旦初始化完成，它的值（也就是存放在指针中的地址）就不能在改变了，即不能中途改变指向，如`int *const p`

- **常量指针**：指向常量的指针，也就是后面所指明的 int const 和 const int，都是一个常量，可以写作`int const *p`或`const int *p`

  

#### 18、a和&a有什么区别？

```cpp
int a[10];
// a是数组名，是数组首元素地址，+1表示地址值加上一个int类型的大小
// 如果a的值是0x00000001，加1操作后变为0x00000005，*(a+1) = a[1]

int (*p)[10] = &a;
// &a是数组的指针，其类型为int (*)[10]（就是前面提到的数组指针）
// 其加1时，系统会认为是数组首地址加上整个数组的偏移（10个int型变量），值为数组a尾元素后一个元素的地址
// *(int *)p == a[0]
```



#### 19、C++和Python区别

[点击查找连接](#name1)



#### 20、C++和C语言的区别

<details>
    <summary>查看答案</summary>
    <li>C++ 支持重载，C 语言不允许</li>
    <li>C++ 相对与 C 增加了一些关键字，如：bool、using、dynamic_cast、namespace等等</li>
    <li>C++ 新增了引用，引用型变量是其他变量的一个别名，我们可以认为他们只是名字不相同，其他都是相同的</li>
</details>

[点击查找连接](#name1)



### 基础语法-21-40

> <a id="name2">完整例子以及解读</a>参考：https://interviewguide.cn/notes/03-hunting_job/02-interview/01-01-02-basic.html

#### 21、C++与Java的区别

[点击以上连接查看](#name2)



#### 22、C++中struct和class的区别

**相同点**

- 两者都拥有成员函数、公有和私有部分
- 任何可以使用class完成的工作，同样可以使用struct完成

**不同点**

- 两者中如果不对成员不指定公私有，struct默认是公有的，class则默认是私有的

- class默认是private继承，而struct模式是public继承

**引申**：C++ 和 C 的 struct 区别

- C 中 struct 是用户**自定义数据类型**（UDT）；C++ 中 struct 是**抽象数据类型**（ADT），支持成员函数的定义，（C++中的struct能继承，能实现多态）
- C 中 struct 是没有权限的设置的，且 struct 中只能是一些变量的集合体，可以封装数据却不可以隐藏数据，而且成员**不可以是函数**；C++ 中 struct 增加了访问权限，且可以和类一样**有成员函数**，成员默认访问说明符为public（为了与C兼容）
- struct 作为类的一种特例是用来自定义数据结构的。一个结构标记声明后，在 C 中必须在结构标记前加上 struct，才能做结构类型名（除非使用`typedef struct class{}`）; C++ 中结构体标记（结构体名）可以**直接作为结构体类型名使用**，此外结构体 struct 在 C++ 中被当作类的一种特例



#### 23、define宏定义和const的区别

**编译阶段**

- define 在 **预处理** 阶段起作用，而 const 是在 **编译运行** 的时候起作用

**安全性**

- define 只做**替换**，不做类型检查和计算，也不求解，容易产生错误，一般最好加上一个大括号包含住全部的内容，要不然很容易出错
- const 常量有**数据类型**，编译器可以对其进行类型安全检查

**内存占用**

- define只是将宏名称进行替换，在内存中会产生多分相同的备份。const在程序运行中只有一份备份，且可以执行常量折叠，能将复杂的的表达式计算出结果放入常量表

- 宏替换发生在编译阶段之前，属于文本插入替换；const作用发生于编译过程中

- 宏定义的数据没有分配内存空间，只是插入替换掉；const 定义的变量只是值不能改变，但要分配内存空间。




#### 24、C++中const和static的作用 :fire:

**static**

- 不考虑类的情况
  - 隐藏：所有不加 static 的全局变量和函数具有全局可见性，可以在其他文件中使用，加了之后只能在该文件所在的编译模块中使用
  - **默认初始化为0**，包括未初始化的全局静态变量与局部静态变量，都存在全局未初始化区
  - 静态变量在函数内定义始终存在，且只**进行一次初始化**，具有记忆性，其作用范围与局部变量相同，函数退出后仍然存在，但不能使用
- 考虑类的情况
  - static 成员变量：只与类关联，**不与类的对象关联**。定义时要分配空间，不能在类声明中初始化，**必须在类定义体外部初始化**，初始化时不需要标示为static；可以被非 static 成员函数任意访问
  - static 成员函数：不具有`this`指针，无法访问类对象的非 static 成员变量和非 static 成员函数；**不能被声明为const、虚函数和volatile**；可以被非 static 成员函数任意访问

**const**

- 不考虑类的情况

  - const 常量在**定义时必须初始化**，之后无法更改

  - const 形参可以接收const和非const类型的实参，例如

    ```C++
    // i 可以是 int 型或者 const int 型
    void fun(const int& i) {}
    ```
  
- 考虑类的情况

  - const 成员变量：不能在类定义外部初始化，只能通过构造函数 **初始化列表** 进行初始化，并且必须有构造函数；不同类对其 const 数据成员的值可以不同，所以不能在类中声明时初始化
  
  - const 成员函数：实际修饰该成员函数隐含的 this 指针，**表明在该成员函数中不能对类的任何成员进行修改**
  
    > **const 对象**不可以调用非 const 成员函数；**非 const 对象都可以调用**；不可以改变非`mutable`数据的值
    >
    > mutable 关键字声明的变量可以在 const 成员函数中被修改
    
    ```cpp
    class Test
    {
        const int a;
        // const int a = 4; // 也可以直接这样写，但是不太灵活
    
    public:
        Test(int x): a(x) {	// a 只能通过初始化列表初始化
            // a = x; // error
            cout << "Construct...\n" << a << endl;
        }
        ~Test() {
            cout << "Destoryed..." << endl;
        };
    
        void foo_const() const {	// 所有对象都可以调用
            cout << "foo_const " << a << endl;
        }
        
        void foo() { // const 对象无法调用
            cout << "foo " << a << endl;
        }
    };
    
    int main(int argc, char const *argv[]) {
        const Test t(4);
        // 参考：https://blog.csdn.net/bit_zyx/article/details/124825804
        // t.foo(); // error, const Test* this 无法转成 Test *，权限放大了
        t.foo_const();	// correct
    
        Test t1(5);
        t1.foo();		// correct
        t1.foo_const();	// correct
        
        return 0;
    }
    ```
    
    > const成员只能调用const函数：https://blog.csdn.net/qq_40242197/article/details/118584131



#### 25、C++的顶层const和底层const

[点击寻找原文链接](#name2)



#### 26、数组名和指针（这里为指向数组首元素的指针）区别？

- 二者均可通过增减偏移量来访问数组中的元素

- 数组名不是真正意义上的指针，可以理解为常指针，所以数组名没有自增、自减等操作

- **当数组名当做形参传递给调用函数后，就失去了原有特性，退化成一般指针，多了自增、自减操作，但sizeof运算符不能再得到原数组的大小了**



#### 27、final和override关键字

- override 用在父类函数中指定了该函数是**继承于基类的**
- final 用于指定 **某个类不希望被继承** 或者 **某个虚函数不希望被重写**



#### 28、拷贝初始化和直接初始化

- 当用于类类型对象时，初始化的拷贝形式和直接形式有所不同：**直接初始化**直接调用与实参匹配的构造函数，**拷贝初始化**总是调用拷贝构造函数。拷贝初始化首先使用指定构造函数创建一个临时对象，然后用拷贝构造函数将那个临时对象拷贝到正在创建的对象。举例如下：

  ```cpp
  string str1("I am a string");//语句1 直接初始化
  string str2(str1);//语句2 直接初始化，str1是已经存在的对象，直接调用拷贝构造函数对str2进行初始化
  string str3 = "I am a string";//语句3 拷贝初始化，先为字符串”I am a string“创建临时对象，再把临时对象作为参数，使用拷贝构造函数构造str3
  string str4 = str1;//语句4 拷贝初始化，这里相当于隐式调用拷贝构造函数，而不是调用赋值运算符函数
  ```

- **为了提高效率，允许编译器跳过创建临时对象这一步，**直接调用构造函数构造要创建的对象，这样就完全等价于**直接初始化了**（语句1和语句3等价），但是需要辨别两种情况：
  - 当拷贝构造函数为private时：语句3和语句4在编译时会报错
  - 使用explicit修饰构造函数时：如果构造函数存在隐式转换，编译时会报错



#### 29、初始化和赋值的区别

- 对于简单类型来说，初始化和赋值没什么区别
- 对于 **类和复杂数据** 类型来说，这两者的区别就大了，举例如下：

```cpp
class A{
public:
    int num1;
    int num2;
public:
    A(int a=0, int b=0):num1(a),num2(b){};
    // 最好自己定义拷贝构造函数，否则使用编译自动生成的会出出现一些意外，自动生成的是直接赋值
    // 参考：https://blog.csdn.net/weixin_43700340/article/details/89308144
    A(const A& a) {	
        num1 = a.num1;
        num2 = a.num2;
    };
    //重载 = 号操作符函数
    A& operator=(const A& a){
        num1 = a.num1 + 1;
        num2 = a.num2 + 1;
        return *this;
    };
};
int main(){
    A a(1,1);
    A a1 = a; //拷贝初始化操作，调用拷贝构造函数
    A b;
    b = a;//赋值操作，对象a中，num1 = 1，num2 = 1；对象b中，num1 = 2，num2 = 2
    return 0;
}
```



#### 30、extern "C" 的用法

为了能够**正确的在 C++ 代码中调用C语言**的代码：在程序中加上extern "C"后，相当于告诉编译器这部分代码是C语言写的，因此要按照C语言进行编译，而不是C++；

哪些情况下使用extern "C"：

（1）C++ 代码中调用 C 语言代码；

（2）在 C++ 中的头文件中使用；

（3）在多个 人协同开发时，可能有人擅长 C 语言，而有人擅长 C++；

> 例子参考：[点击寻找原文链接](#name2)



#### 31、野指针和悬空指针

都是是指向无效内存区域(这里的无效指的是"不安全不可控")的指针，访问行为将会导致未定义行为。

- 野指针：没有被初始化过的指针
  - **原因以及解决**：指针变量未及时初始化 => 定义指针变量及时初始化，要么置空
- 悬空指针：指针最初指向的内存已经被释放了的一种指针，C++11 引入智能指针可以避免悬空指针的产生
  - **原因以及解决**：指针 free 或 delete 之后没有及时置空 => 释放操作后立即置空



#### 32、C和C++的类型安全

 **什么是类型安全？**

- 类型安全很大程度上可以等价于**内存安全**，类型安全的代码不会试图访问自己没被授权的内存区域

- “类型安全”常被用来形容编程语言，其根据在于该门编程语言是否提供保障类型安全的机制；有的时候也用“类型安全”形容某个程序，判别的标准在于该程序是否隐含类型错误

**（1）C 的类型安全**

C 只在局部上下文中表现出类型安全，比如试图从一种结构体的指针转换成另一种结构体的指针时，编译器将会报告错误，除非使用**显式类型转换**。然而，C 中相当多的操作是不安全的。以下是两个十分常见的例子：

- printf格式输出

  ```cpp
  #include <stdio.h>
  int main()
  {
      printf("int: %d\n", 10);		// int: 10
      printf("float: %f\n", 10);		// float: 0.000000 (明显错误的输出)
      // printf("string: %s\n", 10);	// segmentation fault
  }
  ```

- malloc 函数的返回值
  - malloc 是 C 中进行内存分配的函数，它的返回类型是 `void *` 即空类型指针，常常有这样的用法 `char* pStr=(char *)malloc(100 * sizeof(char))`，这里明显做了显式的类型转换
  - 类型匹配尚且没有问题，但是一旦出现`int * pInt=(int *)malloc(100 * sizeof(char))`就很可能带来一些问题，而这样的转换 C 并不会提示错误


**（2）C++的类型安全**

如果 C++ 使用得当，它将远比 C 更有类型安全性。相比于C语言，C++提供了一些新的机制保障类型安全：

- 操作符 new 返回的指针类型严格与对象匹配，而不是`void *`
- C 中很多以`void *`为参数的函数可以改写为 C++ 模板函数，而模板是支持类型检查的
- 引入 const 关键字代替 `#define constant`，它是有类型、有作用域的，而`#define constant`只是简单的文本替换
- 一些`#define`宏可被改写为`inline`函数，结合函数的重载，可在类型安全的前提下支持多种类型，当然改写为模板也能保证类型安全
- C++ 提供了**dynamic_cast**关键字，使得转换过程更加安全，因为`dynamic_cast`比`static_cast`涉及更多具体的类型检查

> 例子请参考：[点击寻找原文链接](#name2)例2：不同类型指针之间转换
>
> 上面两个例子之所以引起类型不安全的问题，是因为程序员使用不得当。第一个例子用到了空类型指针`void*`，第二个例子则是在两个类型指针之间进行强制转换。因此，想保证程序的类型安全性，应尽量避免使用空类型指针，尽量不对两种类型指针做强制转换。



#### 33、C++中的重载、重写（覆盖）和隐藏的区别 :fire:

**（1）重载（overload）**

重载是指在同一范围定义中的同名成员函数才存在重载关系。主要特点是**函数名相同，参数类型和数目有所不同**，不能出现参数个数和类型均相同，仅仅依靠返回值不同来区分的函数。**重载和函数成员是否是虚函数无关。**

- 注意 const 和 volatile 对形参的影响

```cpp
// 重载
void func(int* a) {}
void func(const int* a) {}

// 不叫重载
void func(int* a) {}
void func(int* const a) {}

// 不叫重载
void func(int a) {}
void func(const int a) {}
```

**（2）重写（覆盖）（override）**

重写指的是在派生类中覆盖基类中的同名函数，**重写就是重写函数体**，**要求基类函数必须是虚函数**且：

- 与基类的虚函数有相同的参数个数
- 与基类的虚函数有相同的参数类型
- 与基类的虚函数有相同的返回值类型

**重载与重写的区别：**

- 重写是**父类和子类**之间的垂直关系，重载是**不同函数**之间的水平关系
- 重写要求参数列表相同，重载则要求参数列表不同，返回值不要求
- 重写关系中，**调用方法**根据对象类型决定，重载根据调用时**实参表与形参表**的对应关系来选择函数体

**（3）隐藏（hide）**

隐藏指的是某些情况下，派生类中的函数屏蔽了基类中的同名函数，包括以下情况：

- **两个函数参数相同，但是基类函数不是虚函数。** 和重写的区别在于基类函数是否是虚函数。

- **两个函数参数不同，无论基类函数是不是虚函数，都会被隐藏。** 和重载的区别在于两个函数不在同一个类中。

> 例子参考：[点击寻找原文链接](#name2)



#### 34、C++有哪几种的构造函数

C++中的构造函数可以分为4类：

- 默认构造函数：完成对象的初始化工作
- 初始化构造函数（有参数）：完成对象的初始化工作
- 拷贝构造函数：复制本类的对象
- 转换构造函数：将其他类型的变量，隐式转换为本类对象
- 移动构造函数（move和右值引用）
- 委托构造函数

> 举个例子：[点击寻找原文链接](#name2)



#### 35、浅拷贝和深拷贝的区别

**浅拷贝**

浅拷贝只是拷贝一个指针，并**没有新开辟一个地址**，拷贝的指针和原来的指针指向同一块地址，**如果原来的指针所指向的资源释放了，那么再释放浅拷贝的指针的资源就会出现错误。**

**深拷贝**

深拷贝不仅拷贝值，还**开辟出一块新的空间**用来存放新的值，即使原先的对象被析构掉，释放内存了也不会影响到深拷贝得到的值。在自己实现拷贝赋值的时候，**如果有指针变量的话是需要自己实现深拷贝的。**

> :fire:例子参考：[点击寻找原文链接](#name2)
>
> 从执行结果可以看出，浅拷贝在对象的拷贝创建时存在风险，即被拷贝的对象析构释放资源之后，拷贝对象析构时会再次释放一个已经释放的资源，深拷贝的结果是两个对象之间没有任何关系，各自成员地址不同。



#### 36、内联函数和宏定义的区别

- 在使用时，宏只**在编译前**做简单**字符串替换**。而内联函数**在编译时**可以进行参数**类型检查**，且具有返回值
- 内联函数在编译时直接将函数代码嵌入到目标代码中，**省去函数调用的开销**来提高执行效率，并且进行参数类型检查，具有返回值，可以**实现重载**
- 宏定义时要注意书写（参数要括起来）否则容易出现歧义，内联函数不会产生歧义
- 内联函数有类型检测、语法判断等功能，而宏没有

**内联函数适用场景:**

- 使用宏定义的地方都可以使用 inline 函数
- 作为类成员接口函数来读写类的私有成员或者保护成员，会提高效率



#### 37、public, protected, private 访问和继承权限的区别？

**一、访问权限**

| 访问权限  | 外部               | 派生类             | 内部               |
| --------- | ------------------ | ------------------ | ------------------ |
| public    | :heavy_check_mark: | :heavy_check_mark: | :heavy_check_mark: |
| protected | :x:                | :heavy_check_mark: | :heavy_check_mark: |
| private   | :x:                | :x:                | :heavy_check_mark: |

public、protected、private 的访问权限范围关系：public > protected > private

- public的变量和函数在**类的内部外部**都可以访问
- protected的变量和函数只能在**类的内部和其派生类**中访问
- private修饰的元素只能在**类内**访问

**二、继承权限**

1. 派生类继承自基类的成员权限有四种状态：public、protected、private、不可见
2. 派生类对基类成员的访问权限取决于两点：① 继承方式；② 基类成员在基类中的访问权限
3. 派生类对基类成员的访问权限是取以上两点中的更小的访问范围（**除了 private 的继承方式遇到 private 成员是不可见外**）

派生类对基类成员的访问形象有如下两种：

- **内部访问**：由派生类中新增的成员函数对从基类继承来的成员的访问
- **外部访问**：在派生类外部，通过派生类的对象对从基类继承来的成员的访问

> 原文有误，基类的 private 成员在派生类都是不可见的



#### 38、如何用代码判断大小端存储

- 大端存储：数据的高字节存储在低地址中

- 小端存储：数据的高字节存储在高地址中

所以在**Socket编程**中，往往需要将**操作系统所用的小端存储**的IP地址转换为**大端存储**，这样才能进行网络传输

例如：32bit 的数字`0x12345678`，在大小端模式中的存储方式为：

```bash
# 内存地址：0x4000	0x4001	0x4002	0x4003
# 大端内容：0x12		0x34	0x56	0x78
# 小端内容：0x78		0x56	0x34	0x12
```

> 具体判断代码：[点击寻找原文链接](#name2)
>
> 1. 强制类型转换：int 转 char
> 2. 利用 union 重叠式存储



#### 39、volatile, mutabe, explicit 关键字的用法

**(1) volatile**

- volatile 关键字是一种类型修饰符，**用它声明的类型变量表示可以被某些编译器未知的因素更改**，比如：操作系统、硬件或者其它线程等。遇到这个关键字声明的变量，编译器对访问该变量的代码就不再进行优化，从而可以提供对特殊地址的稳定访问。
- 当要求使用 volatile 声明的变量的值的时候，**系统总是重新从它所在的内存读取数据**，即使它前面的指令刚刚从该处读取过数据。
- **volatile 定义变量的值是易变的，每次用到这个变量的值的时候都要去重新读取这个变量的值，而不是读寄存器内的备份。多线程中被几个任务共享的变量需要定义为volatile类型。**

**volatile 指针**

volatile 指针和 const 修饰词类似，const 有常量指针和指针常量的说法，volatile 也有相应的概念

修饰由指针指向的对象、数据是 const 或 volatile 的：

```C++
const char* cpch;
volatile char* vpch;
```

指针自身的值——一个代表地址的整数变量，是 const 或 volatile 的：

```C++
char* const pchc;
char* volatile pchv;
```

 注意：

- 可以把一个 非volatile int 赋给 volatile int，但是不能把 非volatile对象 赋给一个 volatile对象
- 除了基本类型外，对用户定义类型也可以用 volatile 类型进行修饰
- C++ 中一个有 volatile 标识符的类只能访问它接口的子集，一个由类的实现者控制的子集。用户只能用 const_cast 来获得对类型接口的完全访问。此外 volatile 向 const 一样会从类传递到它的成员

**多线程下的volatile**   

有些变量是用volatile关键字声明的。当两个线程都要用到某一个变量且该变量的值会被改变时，应该用volatile声明，**该关键字的作用是防止优化编译器把变量从内存装入CPU寄存器中。**如果变量被装入寄存器，那么两个线程有可能一个使用内存中的变量，一个使用寄存器中的变量，这会造成程序的错误执行。volatile的意思是让编译器每次操作该变量时一定要从内存中真正取出，而不是使用已经存在寄存器中的值。

**(2) mutable**

mutable 的中文意思是“可变的，易变的”，跟 constant（既C++中的const）是反义词。在C++中，mutable 也是为了突破 const 的限制而设置的。被mutable修饰的变量，将永远处于可变的状态，即使在一个const函数中。我们知道，如果类的成员函数不会改变对象的状态，那么这个成员函数一般会声明成const的。但是，有些时候，我们需要**在const函数里面修改一些跟类状态无关的数据成员，那么这个函数就应该被 mutable 来修饰，并且放在函数后后面关键字位置**。

> [C++中的mutable关键字 - 夜行过客 - 博客园 (cnblogs.com)](https://www.cnblogs.com/yongdaimi/p/9565996.html)

**(3) explicit**

explicit 关键字用来修饰类的构造函数，被修饰的构造函数的类，不能发生相应的隐式类型转换，只能以**显示的方式进行类型转换**，注意以下几点：

- explicit 关键字只能用于类内部的构造函数声明上

- [C++2.0 之前](https://blog.csdn.net/guoyunfei123/article/details/89003369) explicit 关键字作用于**单个参数**的构造函数，[C++2.0](https://blog.csdn.net/qq_15041569/article/details/110781180) explicit 可以作用于多个参数的构造函数使用

- 被 explicit 修饰的构造函数的类，不能发生相应的隐式类型转换



#### 40、什么情况下会调用拷贝构造函数

- 用类的一个实例化对象去初始化另一个对象的时候
- 函数的参数是类的对象时（非引用传递）
- 函数的返回值是函数体内局部对象的类的对象时 ,此时虽然发生 [Named Return Value (NRV) 优化](https://blog.csdn.net/zha_1525515/article/details/7170059)，但是由于返回方式是值传递，所以会在返回值的地方调用拷贝构造函数

:warning: 第三种情况在 Linux g++ 下则不会发生拷贝构造函数，不仅如此即使返回局部对象的引用，依然不会发生拷贝构造函数

总结就是：即使发生**NRV优化**的情况下:

- **Linux+ g++ 的环境**是不管值返回方式还是引用方式返回的方式**都不会**发生拷贝构造函数

- **Windows + VS2019**在值返回的情况下发生拷贝构造函数，**引用返回方式则不发生拷贝构造函数**

> 代码例子：[点击寻找原文链接](#name2)



### 基础语法-41-60

> <a id="name3">完整例子以及解读</a>参考：https://interviewguide.cn/notes/03-hunting_job/02-interview/01-01-03-basic.html

#### 41、C++中有几种类型的new

在C++中，new有三种典型的使用方法：plain new，nothrow new 和 placement new

**（1）plain new**

言下之意就是普通的new，就是我们常用的new，在C++中定义如下：

```C++
void* operator new(std::size_t) throw(std::bad_alloc);
void operator delete(void *) throw();
```

因此 **plain new** 在空间分配失败的情况下，抛出异常**std::bad_alloc**而不是返回NULL，因此通过判断返回值是否为NULL是徒劳的。例子参考 [点击查看原文链接](#name3)

**（2）nothrow new**

nothrow new 在空间分配失败的情况下是不抛出异常，**而是返回 NULL**，更多例子参考 [点击查看原文链接](#name3)，定义如下：

```C++
void * operator new(std::size_t,const std::nothrow_t&) throw();
void operator delete(void*) throw();
```

**（3）placement new**

这种 new 允许在一块已经分配成功的内存上重新构造对象或对象数组。placement new 不用担心内存分配失败，因为它根本不分配内存，它做的唯一一件事情就是调用对象的构造函数。定义如下：

```C++
void* operator new(size_t, void*);
void operator delete(void*, void*);
```

使用 placement new 需要注意两点：

- palcement new 的主要用途就是反复使用一块较大的动态分配的内存来构造不同类型的对象或者他们的数组

- placement new 构造起来的对象数组，要显式的调用他们的析构函数来销毁（析构函数并不释放对象的内存），千万不要使用delete，这是因为 placement new 构造起来的对象或数组大小并不一定等于原来分配的内存大小，使用 delete 会造成内存泄漏或者之后释放内存时出现运行时错误

举个例子：

```C++
#include <iostream>
#include <string>
using namespace std;
class ADT{
	int i;
	int j;
public:
	ADT(){
		i = 10;
		j = 100;
		cout << "ADT construct i=" << i << "j="<<j <<endl;
	}
	~ADT(){
		cout << "ADT destruct" << endl;
	}
};
int main()
{
	char *p = new(nothrow) char[sizeof ADT + 1];
	if (p == NULL) {
		cout << "alloc failed" << endl;
	}
	ADT *q = new(p) ADT;// placement new:不必担心失败，只要p所指对象的空间足够ADT创建即可
	// delete q;		// 错误!不能在此处调用delete q;
	q->ADT::~ADT();		// 显示调用析构函数
	delete[] p;
	return 0;
}
//输出结果：
//ADT construct i=10j=100
//ADT destruct
```



#### 42、C++的异常处理的方法

**（1）try、throw和catch关键字**

C++ 中的异常处理机制主要使用 **try、throw 和 catch** 三个关键字，程序的执行流程：

- 先执行 try 包裹的语句块，如果执行过程中没有异常发生，则不会进入任何 catch 包裹的语句块，如果发生异常，则使用 throw 抛出异常
- 再由 catch 进行捕获，throw 可以抛出各种数据类型的信息，代码中使用的是数字，也可以自定义异常 class。**catch根据throw抛出的数据类型进行精确捕获（不会出现类型转换），如果匹配不到就直接报错，可以使用catch(...)的方式捕获任何异常（不推荐）**

**（2）函数的异常声明列表**

有时候，程序员在定义函数的时候知道函数可能发生的异常，可以在函数声明和定义时，指出所能抛出异常的列表，写法如下：

```cpp
int fun() throw(int,double,A,B,C) {...};
```

这种写法表名函数可能会抛出 int, double 型或者 A、B、C 三种类型的异常，如果 throw 中为空，表明不会抛出任何异常，如果没有   throw 则可能抛出任何异常

**（3）C++标准异常类 exception**

C++ 标准库中有一些类代表异常，这些类都是从 exception 类派生而来的，如下图所示

<img src="https://axiu-image-bed.oss-cn-shanghai.aliyuncs.com/img/202205212342667.png" alt="img" style="zoom:80%;" align="left"/>



- bad_typeid：使用 typeid 运算符，如果其操作数是一个多态类的指针，而该指针的值为 NULL，则会拋出此异常
- bad_cast：在用 dynamic_cast 进行从多态基类对象（或引用）到派生类的引用的强制类型转换时，如果转换是不安全的，则会拋出此异常
- bad_alloc：在用 new 运算符进行动态内存分配时，如果没有足够的内存，则会引发此异常
- out_of_range：用 vector 或 string 的 at 成员函数根据下标访问元素时，如果下标越界，则会拋出此异常

>具体用法：[点击查看原文链接](#name3)



#### 43、static 的用法和作用？

1. **隐藏（static函数和变量）**：当同时编译多个文件时，所有未加 static 前缀的全局变量和函数都具有全局可见性。

2. **保持变量内容的持久（static变量中的记忆功能和全局生存期）**：存储在静态数据区的变量会在程序刚开始运行时就完成初始化，也是唯一的一次初始化。共有两种变量存储在静态存储区：全局变量 和 static变量，只不过和全局变量比起来，static 可以控制变量的可见范围，说到底static还是用来隐藏的。

3. **默认初始化为 0（static变量）**：其实全局变量也具备这一属性，因为全局变量也存储在静态数据区。在静态数据区，内存中所有的字节默认值都是0x00。

4. **类成员声明static**

   - 函数体内static变量的作用范围为该函数体，不同于auto变量，该变量的内存只被分配一次，因此其值在下次调用时仍维持上次的值

   - 在模块内的static全局变量可以被模块内所用函数访问，但不能被模块外其它函数访问

   - 在模块内的static函数只可被这一模块内的其它函数调用，这个函数的使用范围被限制在声明它的模块内

   - 在类中的**static成员变量**属于整个类所拥有，**对类的所有对象只有一份拷贝**

   - 在类中的**static成员函数**属于整个类所拥有，这个函数**不接收this指针**，因而只能访问类的static成员变量

   - static类对象必须要在类外进行初始化，static修饰的变量先于对象存在，所以static修饰的变量要在类外初始化

   - **static成员函数不能被virtual修饰**，static成员不属于任何对象或实例，所以加上virtual没有任何实际意义；静态成员函数没有this指针，虚函数的实现是为每一个对象分配一个vptr指针，而vptr是通过this指针调用的，所以不能为virtual

     > 虚函数的调用关系：`this->vptr->ctable->virtual function`



#### 44、指针和const的用法

> 参考 T17. [常量指针和指针常量]和 T25.[顶层和底层const]



#### 45、形参与实参的区别？

1)  **形参只有在函数内部有效**：形参变量只有在被调用时才分配内存单元，在调用结束时， 即刻释放所分配的内存单元。
2)  实参在进行函数调用时，它们都必须具有确定的值， 以便把这些值传送给形参。 因此应预先用赋值，输入等办法使实参获得确定值，会产生一个临时变量。
3)  实参和形参在数量上，类型上，顺序上应严格一致， 否则会发生“类型不匹配”的错误。
4)  函数调用中发生的数据传送是单向的。 即**只能把实参的值传送给形参**，而不能把形参的值反向地传送给实参。 因此在函数调用过程中，形参的值发生改变，而实参中的值不会变化。



#### 46、值传递、指针传递、引用传递的区别和效率

1)   值传递：有一个形参向函数所属的栈拷贝数据的过程，如果值传递的对象是类对象   或是大的结构体对象，将耗费一定的时间和空间。（传值）

2)  指针传递：同样有一个形参向函数所属的栈拷贝数据的过程，但拷贝的数据是一个固定为4字节的地址。（传值，传递的是地址值）

3)  引用传递：同样有上述的数据拷贝过程，但其是针对地址的，相当于为该数据所在的地址起了一个别名。（传地址）

4)  效率上讲，**指针传递和引用传递比值传递效率高**。一般主张使用引用传递，代码逻辑上更加紧凑、清晰。



#### 47、静态变量什么时候初始化

1)  初始化只有一次，但是可以多次赋值，在主程序之前，编译器已经为其分配好了内存。

2)  **静态局部变量和全局变量一样，数据都存放在全局区域**，所以在主程序之前，编译器已经为其分配好了内存，但在C和C++中静态局部变量的初始化节点又有点不太一样。**在C中，初始化发生在代码执行之前，编译阶段分配好内存之后，就会进行初始化**，所以我们看到**在C语言中无法使用变量对静态局部变量进行初始化**，在程序运行结束，变量所处的全局内存会被全部回收。

3)  **在C++中，初始化时在执行相关代码时才会进行初始化**，主要是由于C++引入对象后，要进行初始化必须执行相应构造函数和析构函数，在构造函数或析构函数中经常会需要进行某些程序中需要进行的特定操作，并非简单地分配内存。所以C++标准定为全局或静态对象是有首次用到时才会进行构造，并通过`atexit()`来管理。在程序结束，按照构造顺序反方向进行逐个析构。所以在C++中是可以使用变量对静态局部变量进行初始化的。



#### 48、const关键字作用

1. 阻止一个变量被改变，可以使用const关键字。在定义该const变量时，通常需要对它进行初始化，因为以后就没有机会再去改变它了；  

2. 对指针来说，可以指定指针本身为const，也可以指定指针所指的数据为const，或二者同时指定为const；  

3. 在一个函数声明中，const可以修饰形参，表明它是一个输入参数，在函数内部不能改变其值；  

4. 对于类的成员函数，若指定其为const类型，则表明其是一个常函数，不能修改类的成员变量，**类的常对象只能访问类的常成员函数**；  

5. 对于类的成员函数，有时候必须指定其返回值为const类型，以使得其**返回值不能作为“左值”**；

6. const成员函数可以访问非const对象的非const数据成员、const数据成员，也可以访问const对象内的所有数据成员；

7. 非const成员函数可以访问非const对象的非const数据成员、const数据成员，但不可以访问const对象的任意数据成员；

8. 一个没有明确声明为const的成员函数被看作是将要修改对象中数据成员的函数，而且编译器不允许它为一个const对象所调用。因此**const对象只能调用const成员函数**。

9. const类型变量可以通过类型转换符`const_cast`将const类型转换为非const类型；

10. const类型变量必须定义的时候进行初始化，该变量必须**在类的初始化列表中进行初始化**；

    

#### 49、什么是类的继承？

1) 类与类之间的关系
   - has-A：包含关系，用以描述一个类由多个部件类构成，实现has-A关系用类的成员属性表示，即一个类的成员属性是另一个已经定义好的类；
   - use-A：一个类使用另一个类，通过类之间的成员函数相互联系，定义友元或者通过传递参数的方式来实现；
   - is-A：继承关系，关系具有传递性；

2) 继承就是一个类继承了另一个类的属性和方法，这个新的类包含了上一个类的属性和方法，被称为**子类或者派生类**，被继承的类称为**父类或者基类**；

3) 继承的特点：子类拥有父类的所有属性和方法，子类可以拥有父类没有的属性和方法，子类对象可以当做父类对象使用；

4) 继承中的访问控制：public、protected、private

5) 继承中的构造和析构函数

6) 继承中的兼容性原则



#### 什么是内存池，如何实现

内存池（Memory Pool） 是一种**内存分配**方式。通常我们习惯直接使用 new、malloc 等申请内存，这样做的缺点在于：由于所申请内存块的大小不定，当频繁使用时会造成大量的内存碎片并进而降低性能。内存池则是在真正使用内存之前，先申请分配一定数量的、大小相等（一般情况下）的内存块留作备用。当有新的内存需求时，就从内存池中分出一部分内存块， 若内存块不够再继续申请新的内存。这样做的一个显著优点是尽量避免了内存碎片，使得内存分配效率得到提升。

这里简单描述一下《STL源码剖析》中的内存池实现机制：

allocate 包装 malloc，deallocate 包装 free

一般是一次20*2个的申请，先用一半，留着一半，为什么也没个说法，侯捷在 STL 那边书里说好像是C++委员会成员认为20是个比较好的数字，既不大也不小

1. 首先客户端会调用 malloc() 配置一定数量的区块（固定大小的内存块，通常为8的倍数），假设40个32bytes的区块，其中20个区块（一半）给程序实际使用，1个区块交出，另外19个处于维护状态。剩余一半留给内存池，即 20*32byte
2. 客户端之后有有内存需求，想申请 20\*64bytes 的空间，这时内存池只有 20*32bytes，就先将 10\*64bytes 个区块返回，1个区块交出，另外9个处于维护状态，此时内存池空空如也
3. 接下来如果客户端还有内存需求，就必须再调用 malloc() 配置空间，此时新申请的区块数量会增加一个随着配置次数越来越大的附加量，同样一半提供程序使用，另一半留给内存池。申请内存的时候用永远是先看内存池有无剩余，有的话就用上，然后挂在0-15号某一条链表上，要不然就重新申请。
4. 如果整个堆的空间都不够了，就会在原先已经分配区块中寻找能满足当前需求的区块数量，能满足就返回，不能满足就向客户端报bad_alloc 异常

allocator 就是用来分配内存的，最重要的两个函数是 allocate 和 deallocate，就是用来申请内存和回收内存的，外部（一般指容器）调用的时候只需要知道这些就够了。内部实现，目前的所有编译器都是直接调用的 ::operator new() 和 ::operator delete()，说白了就是和直接使用new运算符的效果是一样的，所以老师说它们都没做任何特殊处理。 



最开始GC2.9之前：

new 和 operator new 的区别：new 是个运算符，编辑器会调用 operator new(0)，operator new()里面有调用malloc的操作，那同样的 operator delete()里面有调用的free的操作



GC 2.9 的 alloc 的一个比较好的分配器的实现规则：

维护一条0-15号的一共16条链表，其中0表示8 bytes ，1表示 16 bytes,2表示 24bytes，以此内推 15 表示 16* 8 = 128bytes，如果在申请时并不是8的倍数，那就找刚好能满足内存大小的那个位置。比如想申请 12，那就是找16了，想申请 20 ，那就找 24 了

但是现在 GC4.9 及其之后也还有，变成_pool_alloc这个名字了，不再是默认的了，你需要自己去指定它可以自己指定，比如说vector\<string,__gnu_cxx::pool_alloc<string>> vec 这样来使用它，现在用的又回到以前那种对 malloc 和 free 的包装形式了



#### 50、从汇编层去解释一下引用

~~~cpp
// x的地址为ebp-4，b的地址为ebp-8，因为栈内的变量内存是从高往低进行分配的，所以b的地址比x的低
9:      int x = 1;
00401048  mov     dword ptr [ebp-4],1

10:     int &b = x;
// 将x的地址ebp-4放入eax寄存器
0040104F   lea     eax,[ebp-4]
// 将eax的值放入b的地址
00401052  mov     dword ptr [ebp-8],eax
~~~



#### 51、深拷贝与浅拷贝是怎么回事？

- 浅复制 ：只是拷贝了基本类型的数据，而引用类型数据，复制后也是会发生引用，我们把这种拷贝叫做“浅拷贝”或“浅复制”，换句话说，浅复制仅仅是指向被复制的内存地址，如果原地址中对象被改变了，那么浅复制出来的对象也会相应改变。

- 深复制 ：在计算机中开辟了一块新的内存地址用于存放复制的对象。



#### 52、new和malloc的区别？

- new/delete是C++关键字，需要编译器支持。malloc/free是库函数，需要头文件支持；
- 使用new操作符申请内存分配时**无须指定内存块的大小**，编译器会根据类型信息自行计算。而malloc则需要显式地指出所需内存的尺寸；
- new操作符内存分配成功时，返回的是对象类型的指针，类型严格与对象匹配，**无须进行类型转换**，故new是符合类型安全性的操作符。而malloc内存分配成功则是返回`void *`，需要通过强制类型转换将`void *`指针转换成我们需要的类型；
- new内存分配失败时，会抛出bac_alloc异常。malloc分配内存失败时返回NULL；
- new会先调用operator new函数，申请足够的内存（通常底层使用malloc实现）。然后调用类型的构造函数，初始化成员变量，最后返回自定义类型指针。delete先调用析构函数，然后调用operator delete函数释放内存（通常底层使用free实现）。malloc/free是库函数，只能动态的申请和释放内存，无法强制要求其做自定义类型对象构造和析构工作。



#### 53、delete p、delete [] p、allocator 都有什么作用？

- 动态数组管理new一个数组时，[]中必须是一个整数，但是不一定是常量整数，普通数组必须是一个常量整数；
- new动态数组返回的并不是数组类型，而是一个元素类型的指针；
- delete[]时，数组中的元素按逆序的顺序进行销毁；
- new在内存分配上面有一些局限性，new的机制是**将内存分配和对象构造组合在一起**，同样的，delete也是**将对象析构和内存释放组合在一起**的。allocator将这两部分分开进行，allocator申请一部分内存，不进行初始化对象，只有当需要的时候才进行初始化操作。

> new 和 delete 能混用吗？C++ 为什么区分单个元素和数组的内存分配和释放呢？

- 单个元素：new/delete，数组元素 new []/delete []
- 对于普通的编译器内置类型 new/delete[] new []/delete 是没有影响的
- 自定义的类类型，**有析构函数，为了调用正确的析构函数，那么开辟对象数组的时候，会多开辟4个字节**，记录对象的个数，因此 new/delete 和 new []/delete [] 不能混用



#### 54、new和delete的实现原理， delete是如何知道释放内存的大小的？

1. new 通过 operator new分配内存：
   - 对于简单类型，`new[]`计算好大小后调用operator new；
   - 对于复杂数据结构，`new[]`先调用operator new[]分配内存，然后在p的前四个字节写入数组大小n，然后调用n次构造函数，针对复杂类型，`new[]`会额外存储数组大小；

2. `delete`简单数据类型默认只是调用`free`函数
   - 复杂数据类型先调用析构函数再调用 operator delete；
   - 针对简单类型，`delete`和`delete[]`等同；
   - 假设指针p指向new []分配的内存。因为要4字节存储数组大小，实际分配的内存地址为`[p-4]`，系统记录的也是这个地址。`delete[]`实际释放的就是`p-4`指向的内存。而delete会直接释放p指向的内存，这个内存根本没有被系统记录，所以会崩溃。

3. 需要在 new [] 一个对象数组时，需要保存数组的维度，C++ 的做法是在分配数组空间时多分配了 4 个字节的大小，专门保存数组的大小，在 delete [] 时就可以取出这个保存的数，就知道了需要调用析构函数多少次了。



#### 55、malloc申请的存储空间能用delete释放吗？

不能，当然从理论上说使用malloc申请的内存是可以通过delete释放的。不过一般不这样写的。而且也不能保证每个C++的运行时都能正常：

- malloc/free主要为了兼容C，new和delete 完全可以取代malloc/free的

- malloc/free的操作对象都是必须明确大小的，而且不能用在动态类上

- new 和delete会自动进行类型检查和大小，malloc/free不能执行构造函数与析构函数，所以动态对象它是不行的



#### 56、malloc与free的实现原理？:fire:

1. 在标准C库中，提供了malloc/free函数分配释放内存，这两个函数底层是由brk、mmap、munmap这些系统调用实现的；

2. brk是将数据段(.data)的最高地址指针_edata往高地址推，mmap是在进程的虚拟地址空间中（堆和栈中间，称为文件映射区域的地方）找一块空闲的虚拟内存。这两种方式分配的都是虚拟内存，没有分配物理内存。在第一次访问已分配的虚拟地址空间的时候，发生缺页中断，操作系统负责分配物理内存，然后建立虚拟内存和物理内存之间的映射关系；

3. malloc小于128k的内存，使用brk分配内存，将_edata往高地址推；malloc大于128k的内存，使用mmap分配内存，在堆和栈之间找一块空闲内存分配；brk分配的内存需要等到高地址内存释放以后才能释放，而mmap分配的内存可以单独释放。当最高地址空间的空闲内存超过128K（可由M_TRIM_THRESHOLD选项调节）时，执行内存紧缩操作（trim）。在上一个步骤free的时候，发现最高地址空闲内存超过128K，于是内存紧缩；

4. malloc是从堆里面申请内存，也就是说函数返回的指针是指向堆里面的一块内存。操作系统中有一个记录空闲内存地址的链表。当操作系统收到程序的申请时，就会遍历该链表，然后就寻找第一个空间大于所申请空间的堆结点，然后就将该结点从空闲结点链表中删除，并将该结点的空间分配给程序。



#### 57、malloc、realloc、calloc的区别

1)   malloc函数

~~~cpp
void* malloc(unsigned int num_size);

int *p = malloc(20*sizeof(int));	// 申请20个int类型的空间；malloc申请的空间的值是随机初始化的
~~~

2)   calloc函数

~~~cpp
void* calloc(size_t n,size_t size);

int *p = calloc(20, sizeof(int));	// calloc申请的空间的值是初始化为0的
~~~

3)   realloc函数

~~~cpp
void realloc(void *p, size_t new_size);	// 给动态分配的空间分配额外的空间，用于扩充容量
~~~



#### 58、类成员初始化方式？构造函数的执行顺序 ？为什么用成员初始化列表会快一些？

**（1）初始化方式**

- 赋值初始化，通过在函数体内进行赋值初始化，在所有的数据成员被**分配内存空间后**才进行的；

- 列表初始化，在冒号后使用初始化列表进行初始化，分配内存空间后在进入函数体之前给数据成员赋值，就是说初始化这个数据成员此时函数体还未执行。 

> 前者是在构造函数当中做赋值的操作，而后者是做纯粹的初始化操作。C++的赋值操作是会产生临时对象的。临时对象的出现会降低程序的效率

**（2）派生类构造函数的执行顺序**

①  虚拟基类的构造函数（多个虚拟基类则按照继承的顺序执行构造函数）

②  基类的构造函数（多个普通基类也按照继承的顺序执行构造函数）

③  类类型的成员对象的构造函数（按照初始化顺序）

④  派生类自己的构造函数



#### 59、有哪些情况必须用到成员列表初始化？作用是什么？

1)  必须使用成员初始化的四种情况
    - 当初始化一个**引用成员**时；
    - 当初始化一个**常量成员**时；
    - 当调用一个基类的构造函数，而它拥有一组参数时；
    - 当调用一个成员类的构造函数，而它拥有一组参数时；

2)  成员初始化列表做了什么
    - 编译器会一一操作初始化列表，以适当的顺序在构造函数之内安插初始化操作，并且在任何显示用户代码之前；
    - list中的项目顺序是由类中的成员声明顺序决定的，不是由初始化列表的顺序决定的；



#### 60、C++中新增了string，它与C语言中的 char *有什么区别吗？它是如何实现的？

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



### 基础语法-61-80

> <a id="name4">完整例子以及解读</a>参考：https://interviewguide.cn/notes/03-hunting_job/02-interview/01-01-04-basic.html

#### 61、什么是内存泄露，如何检测与避免

**内存泄露**

一般我们常说的内存泄漏是指**堆内存的泄漏**。堆内存是指程序从堆中分配的，大小任意的(内存块的大小可以在程序运行期决定)内存块，使用完后必须显式释放的内存。应用程序般使用malloc,、realloc、 new等函数从堆中分配到块内存，使用完后，程序必须负责相应的调用free或delete释放该内存块，否则，这块内存就不能被再次使用，我们就说这块内存泄漏了

**避免内存泄露的几种方式**

- 计数法：使用new或者malloc时，让该数+1，delete或free时，该数-1，程序执行完打印这个计数，如果不为0则表示存在内存泄露
- 一定要将基类的析构函数声明为**虚函数**
- 对象数组的释放一定要用**delete []**
- 有new就有delete，有malloc就有free，保证它们一定成对出现

**检测工具**

- Linux下可以使用**Valgrind工具**
- Windows下可以使用**CRT库**



#### 62、对象复用的了解，零拷贝的了解

**对象复用**

对象复用其本质是一种设计模式：Flyweight享元模式。

通过将对象存储到“对象池”中实现对象的重复利用，这样可以避免多次创建重复对象的开销，节约系统资源。

**零拷贝**

零拷贝就是一种避免 CPU 将数据从一块存储拷贝到另外一块存储的技术。

零拷贝技术可以减少数据拷贝和共享总线操作的次数。

在 C++ 中，vector 的一个成员函数 **emplace_back()** 很好地体现了零拷贝技术，它跟`push_back()`函数一样可以将一个元素插入容器尾部，区别在于：**使用`push_back()`函数需要调用拷贝构造函数和转移构造函数，而使用`emplace_back()`插入的元素原地构造，不需要触发拷贝构造和转移构造**，效率更高。

> 例子参考：[点击查看原文链接](#name4)



#### 63、介绍面向对象的三大特性，并且举例说明

三大特性：继承、封装和多态

**（1）继承**

**让某种类型对象获得另一个类型对象的属性和方法。**

它可以使用现有类的所有功能，并在无需重新编写原来的类的情况下对这些功能进行扩展

> 具体继承方式参考：[点击查看原文链接](#name4)

**（2）封装**

数据和代码捆绑在一起，避免外界干扰和不确定性访问。

封装，也就是**把客观事物封装成抽象的类**，并且类可以把自己的数据和方法只让可信的类或者对象操作，对不可信的进行信息隐藏，例如：将公共的数据或方法使用public修饰，而不希望被访问的数据或方法采用private修饰。

**（3）多态**  

同一事物表现出不同事物的能力，即向不同对象发送同一消息，不同的对象在接收时会产生不同的行为**（重载实现编译时多态，虚函数实现运行时多态）**。

多态性是允许你将父对象设置成为和一个或更多的他的子对象相等的技术，赋值之后，父对象就可以根据当前赋值给它的子对象的特性以不同的方式运作。**简单一句话：允许将子类类型的指针赋值给父类类型的指针**

实现多态有二种方式：覆盖（override），重载（overload）。

- 覆盖：是指子类重新定义父类的虚函数的做法。
- 重载：是指允许存在多个同名函数，而这些函数的参数表不同（或许参数个数不同，或许参数类型不同，或许两者都不同）。



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

**成员初始化列表的概念**

在类的构造函数中，不在函数体内对成员变量赋值，而是在构造函数的花括号前面使用冒号和初始化列表赋值

**效率**

用初始化列表会快一些的原因是，对于类型，它**少了一次调用构造函数的过程**，而在函数体中赋值则会多一次调用。而对于内置数据类型则没有差别。

> 例子参考：[点击查看原文链接](#name4)



#### 65、C++的四种强制转换 `xx_cast` :fire:

这些类型转换是语言级别的，没法查看源码，做更加安全的转换，格式为 `reinterpret_cast<type-id> (expression)`

**(1) reinterpret_cast**

它可以用于类型之间进行强制转换，类似于 C 风格的强制类型转换

**(2) const_cast**

去掉常量属性的一个类型转换，type_id 必须是指针或者引用类型，用来修改类型的 const 或 volatile 属性

```cpp
const int a = 1;
int *p = const_cast<int*>(&a);
cout << *p << ' ' << a << endl;	// 1 1
*p = 2;
cout << *p << ' ' << a << endl;	// 2 1

// int b = const_cast<int>(a); // error
```

**(3) static_cast**

提供编译器认为的安全的类型转换，没有任何联系的类型之间的转换就会被编译器否定，**没有运行时类型检查来保证转换的安全性**。它主要有如下几种用法：

- 用于基本数据类型之间的转换，如把 int 转换成 char，把 int 转换成 enum。可以把空指针转换成目标类型的空指针，把任何类型的表达式转换成 void 类型

  ```cpp
  int a = 1;
  double b = static_cast<double>(a);
  // double *p = static_cast<double *>(a); // error
  ```

- 用于类层次结构中基类（父类）和派生类（子类）之间指针或引用引用的转换

  - 进行**上行转换**（把派生类的指针或引用转换成基类表示）是安全的

    > 其实这个就是多态的过程：父类指针指向子类对象，比如父类是动物，子类有狗和猫，子类重写了父类的 speak() 方法，那么父类指针再调用 speak() 函数时就是根据不同的子类对象会有不同的效果，这就是动态联编，这就是多态！！！:fire:

  - 进行**下行转换**（把基类指针或引用转换成派生类表示）时，由于没有动态类型检查，所以是不安全的

**(4) dynamic_cast**

主要用于继承结构中，可以支持 RTTI 类型识别的上下转换，**有类型检查**，基类向派生类转换比较安全，但是派生类向基类转换则不太安全，**只能用于多态之间的转换**

> dynamic_cast 运算符可以在执行期决定真正的类型，也就是说expression 必须是多态类型。如果下行转换是安全的（也就说，如果基类指针或者引用确实指向一个派生类对象）这个运算符会传回适当转型过的指针。**如果下行转换不安全，这个运算符会传回空指针**（也就是说，基类指针或者引用没有指向一个派生类对象）

dynamic_cast主要用于类层次间的上行转换和下行转换，还可以用于类之间的交叉转换

在类层次间进行上行转换时，dynamic_cast 和 static_cast 的效果是一样的

```cpp
class Base
{
public:
    virtual void func() = 0;
};

class Derive1: public Base
{
public:
    void func() { cout << "call Derive1::func()" << endl; }

};

class Derive2: public Base
{
public:
    void func() { cout << "call Derive2::func()" << endl; }
    
    void derive2func()
    {
        cout << "call Derive2::derive2func()" << endl;
    }
};

void showFunc(Base *p)
{
    /* *
     * @brief dynamic_cast 会检查 p 指针是否指向的是一个 Derive2 类型的对象？
     * p->vfptr->vftable RTTI 信息，如果是 Derive2，那么转换成功
     * 返回 Derive2 对象的地址给 pd2，否则返回 nullptr 
     * */
    // 这里如果使用 static_cast 是不安全的，它是编译时期的类型转换，dynamic_cast 是运行时期的类型转换 RTTI
    Derive2 *pd2 = dynamic_cast<Derive2 *>(p);

    if (pd2 != nullptr) {
        pd2->derive2func();
    } else {
        p->func();
    }
};

int main()
{
    Derive1 d1;
    Derive2 d2;
    showFunc(&d1); // call Derive1::func()
    showFunc(&d2); // call Derive2::derive2func()
    return 0;
}
```





#### 66、C++函数调用的压栈过程

从代码入手，解释这个过程：

```C++
#include <iostream>
using namespace std;

int f(int n) 
{
	cout << n << endl;
	return n;
}

void func(int param1, int param2)
{
	int var1 = param1;
	int var2 = param2;
	printf("var1=%d,var2=%d", f(var1), f(var2));//如果将printf换为cout进行输出，输出结果则刚好相反
}

int main(int argc, char* argv[])
{
	func(1, 2);
	return 0;
}
//输出结果
//2
//1
//var1=1,var2=2
```

当函数从入口函数main函数开始执行时，编译器会将我们操作系统的运行状态，mian函数中的变量、main的参数、main函数的返回地址进行依次压栈；

当main函数开始调用func()函数时，编译器此时会将main函数的运行状态进行压栈，再将func()定义变量、func()函数的参数从右到左、func()函数的返回地址依次压栈；

当func()调用f()的时候，编译器此时会将func()函数的运行状态进行压栈，再将f()定义变量、f()函数的参数从右到左、f()的返回地址依次压栈

从代码的输出结果可以看出，函数f(var1)、f(var2)依次入栈，而后**先执行f(var2)，再执行f(var1)**，最后打印整个字符串，将栈中的变量依次弹出，最后主函数返回。

> 参考：[函数调用时栈是如何变化的？](https://cloud.tencent.com/developer/article/1920687)



#### 67、coredump 错误很常见，一般怎样调试？

- coredump是程序由于异常或者bug在运行时异常退出或者终止，在一定的条件下生成的一个叫做core的文件，**core文件会记录程序在运行时的内存，寄存器状态，内存指针和函数堆栈信息等等**。对这个文件进行分析可以定位到程序异常的时候对应的堆栈调用信息。
- gdb 调试



#### 68、说说移动构造函数

1. 我们用对象a初始化对象b，后对象a我们就不在使用了，但是对象a的空间还在呀（在析构之前），既然拷贝构造函数，实际上就是把a对象的内容复制一份到b中，**那么为什么我们不能直接使用a的空间呢？这样就避免了新的空间的分配，大大降低了构造的成本**。这就是移动构造函数设计的初衷；

2. 拷贝构造函数中，对于指针，我们一定要采用**深层复制**，而移动构造函数中，对于指针，我们采用**浅层复制**。浅层复制之所以危险，是因为两个指针共同指向一片内存空间，若第一个指针将其释放，另一个指针的指向就不合法了。

   > 所以我们只要避免第一个指针释放空间就可以了。避免的方法就是将第一个指针（比如a->value）置为NULL，这样在调用析构函数的时候，由于有判断是否为NULL的语句，所以析构a的时候并不会回收a->value指向的空间；

3)  移动构造函数的参数和拷贝构造函数不同，**拷贝构造函数的参数是一个左值引用，但是移动构造函数的参数是一个右值引用**。意味着，移动构造函数的参数是一个右值或者将亡值的引用。也就是说，只用用一个右值，或者将亡值初始化另一个对象的时候，才会调用移动构造函数。而那个move语句，就是将一个左值变成一个将亡值。



#### 69、C++中将临时变量作为返回值时的处理过程

首先需要明白一件事情，临时变量，在函数调用过程中是被压到程序进程的栈中的，当函数退出时，临时变量出栈，即临时变量已经被销毁，临时变量占用的内存空间没有被清空，但是可以被分配给其他变量，所以有可能在函数退出时，该内存已经被修改了，对于临时变量来说已经是没有意义的值了

C语言里规定：16bit程序中，**返回值**保存在ax寄存器中，32bit程序中，返回值保持在eax寄存器中，如果是64bit返回值，edx寄存器保存高32bit，eax寄存器保存低32bit

由此可见，函数调用结束后，**返回值被临时存储到寄存器中，并没有放到堆或栈中，也就是说与内存没有关系了**。当退出函数的时候，临时变量可能被销毁，但是返回值却被放到寄存器中与临时变量的生命周期没有关系，如果我们需要返回值，一般使用赋值语句就可以



#### 70、如何获取结构成员相对于结构开头的字节偏移量

- 使用`<stddef.h>`头文件中的，`offsetof`宏
- 例子参考：[点击寻找原文链接](#name4)



#### 71、静态类型和动态类型，静态绑定和动态绑定的介绍 :thinking:

- 静态类型：对象在声明时采用的类型，在编译期既已确定；
- 动态类型：通常是指一个指针或引用目前所指对象的类型，是在运行期决定的；
- 静态绑定：绑定的是静态类型，所对应的函数或属性依赖于对象的静态类型，发生在编译期；
- 动态绑定：绑定的是动态类型，所对应的函数或属性依赖于对象的动态类型，发生在运行期；

从上面的定义也可以看出，**非虚函数一般都是静态绑定，而虚函数都是动态绑定（如此才可实现多态性）**。

> 例子参考：[点击寻找原文链接](#name4)

 **本文代码里都是针对指针的情况来分析的，但是对于引用的情况同样适用。**至此总结一下静态绑定和动态绑定的区别：

- 静态绑定发生在编译期，动态绑定发生在运行期；

- 对象的动态类型可以更改，但是静态类型无法更改；

- 要想实现动态，必须使用动态绑定；

- 在继承体系中只有虚函数使用的是动态绑定，其他的全部是静态绑定；



#### 72、引用是否能实现动态绑定，为什么可以实现？

可以。引用在创建的时候必须**初始化**，在访问虚函数时，编译器会根据其所绑定的对象类型决定要调用哪个函数。注意只能调用虚函数。**虚函数才具有动态绑定。**



#### 73、全局变量和局部变量有什么区别？

- 生命周期不同：全局变量随主程序创建和创建，随主程序销毁而销毁；局部变量在局部函数内部，甚至局部循环体等内部存在，退出就不存在；

- 使用方式不同：通过声明后全局变量在程序的各个部分都可以用到；局部变量分配在堆栈区，只能在局部使用。 

操作系统和编译器通过内存分配的位置可以区分两者，**全局变量分配在全局数据段并且在程序开始运行的时候被加载。局部变量则分配在堆栈里面 。**



#### 74、指针加减计算要注意什么？

指针加减本质是对其所指地址的移动，移动的步长跟指针的类型是有关系的，因此在涉及到指针加减运算需要十分小心，加多或者减多都会导致指针指向一块未知的内存地址，如果再进行操作就会很危险。

> 例子参考：[点击寻找原文链接](#name4)

遇到指针的计算，**需要明确的是指针每移动一位，它实际跨越的内存间隔是指针类型的长度，建议都转成10进制计算，计算结果除以类型长度取得结果**



#### 75、 怎样判断两个浮点数是否相等？

对两个浮点数判断大小和是否相等不能直接用`==`来判断，会出错！明明相等的两个数比较反而是不相等！**对于两个浮点数比较只能通过相减并与预先设定的精度比较，记得要取绝对值！**浮点数与0的比较也应该注意。与浮点数的表示方式有关。



#### 76、方法调用的原理（栈，汇编）

[参考原文链接](#name4)



#### 77、C++中的指针参数传递和引用参数传递有什么区别？底层原理你知道吗？

**1)** **指针参数**传递本质上是值传递，它所传递的是一个**地址值**。

值传递过程中，被调函数的形式参数作为被调函数的局部变量处理，会在栈中开辟内存空间以存放由主调函数传递进来的实参值，从而形成了实参的一个副本（替身）。

值传递的特点是，被调函数对形式参数的任何操作都是作为局部变量进行的，不会影响主调函数的实参变量的值（形参指针变了，实参指针不会变）。

**2)** 引用参数传递过程中，被调函数的形式参数也作为局部变量在栈中开辟了内存空间，但是这时存放的是**由主调函数放进来的实参变量的地址**。

被调函数对形参（本体）的任何操作都被处理成间接寻址，即通过栈中存放的地址访问主调函数中的实参变量（根据别名找到主调函数中的本体）。

因此，被调函数对形参的任何操作都会影响主调函数中的实参变量。

**3)** 引用传递和指针传递是不同的，虽然他们都是在被调函数栈空间上的一个局部变量，但是任何对于引用参数的处理都会通过一个间接寻址的方式操作到主调函数中的相关变量。

而对于指针传递的参数，如果改变被调函数中的指针地址，它将应用不到主调函数的相关变量。如果想通过指针参数传递来改变主调函数中的相关变量（地址），那就得使用指向指针的指针或者指针引用。

**4)** 从编译的角度来讲，程序在编译时分别将**指针和引用添加到符号表上，符号表中记录的是变量名及变量所对应地址**。

指针变量在符号表上对应的地址值为指针变量的地址值，而引用在符号表上对应的地址值为引用对象的地址值（与实参名字不同，地址相同）。

符号表生成之后就不会再改，因此指针可以改变其指向的对象（指针变量中的值可以改），而引用对象则不能修改。



#### 78、类如何实现只能静态分配和只能动态分配

1. **静态分配**：把new、delete运算符重载为private属性。**动态分配**：把构造、析构函数设为protected属性，再用子类来动态创建

2. 建立类的对象有两种方式：

   ①  静态建立，静态建立一个类对象，就是由编译器为对象在栈空间中分配内存；

   ②  动态建立，A *p = new A(); 动态建立一个类对象，就是使用new运算符为对象在堆空间中分配内存。这个过程分为两步，第一步执行operator new()函数，在堆中搜索一块内存并进行分配；第二步调用类构造函数构造对象；

3)  只有使用new运算符，对象才会被建立在堆上，因此只要限制new运算符就可以实现类对象只能建立在栈上，可以将new运算符设为私有。



#### 79、如果想将某个类用作基类，为什么该类必须定义而非声明？

派生类中包含并且可以使用它从基类继承而来的成员，为了使用这些成员，派生类必须知道他们是什么。



#### 80、 继承机制中对象之间如何转换？指针和引用之间如何转换？

1)     **向上类型转换**：将**派生类**指针或引用转换为**基类**的指针或引用被称为向上类型转换，向上类型转换会自动进行，而且向上类型转换是**安全**的。

2)     **向下类型转换**：将基类指针或引用转换为**派生类**指针或引用被称为向下类型转换，向下类型转换不会自动进行，因为一个基类对应几个派生类，所以向下类型转换时不知道对应哪个派生类，所以在向下类型转换时必须加动态类型识别技术。RTTI技术，用**dynamic_cast**进行向下类型转换。



### 基础语法-81-100

> <a id="name5">完整例子以及解读</a>参考：https://interviewguide.cn/notes/03-hunting_job/02-interview/01-01-05-basic.html



#### 81、知道C++中的组合吗？它与继承相比有什么优缺点吗？

**（1）继承**

继承是Is a 的关系，比如说Student继承Person,则说明Student is a Person。继承的优点是子类可以重写父类的方法来方便地实现对父类的扩展。

继承的缺点有以下几点：

① 父类的内部细节对子类是可见的。

② 子类从父类继承的方法在编译时就确定下来了，所以无法在运行期间改变从父类继承的方法的行为。

**（2）组合**

组合也就是设计类的时候把要组合的类的对象加入到该类中作为自己的成员变量。

组合的优点：

① 当前对象只能通过所包含的那个对象去调用其方法，所以所包含的对象的内部细节对当前对象是不可见的。

② 当前对象与包含的对象是一个低耦合关系，如果修改包含对象的类中代码不需要修改当前对象类的代码。

③ 当前对象可以在运行时动态的绑定所包含的对象。可以通过set方法给所包含对象赋值。

组合的缺点：① 容易产生过多的对象；② 为了能组合多个对象，必须仔细对接口进行定义。



#### 82、函数指针？:fire:

**1)  什么是函数指针?**

函数指针指向的是特殊的数据类型，**函数的类型是由其返回的数据类型和其参数列表共同决定的**，而函数的名称则不是其类型的一部分。

一个具体函数的名字，如果后面不跟调用符号(即括号)，则该名字就是该函数的指针(注意：大部分情况下，可以这么认为，但这种说法并不很严格)。

**2)  函数指针的声明方法**

`int (*pf)(const int&, const int&);`

上面的 pf 就是一个函数指针，指向所有返回类型为 int，并带有两个 const int& 参数的函数。注意 *pf 两边的括号是必须的，否则上面的定义就变成了：

`int *pf(const int&, const int&);`

而这声明了一个函数 pf，其返回类型为 int *， 带有两个 const int& 参数。

```cpp
using PF1 = int(*)(int, int); // 函数指针
PF1 f = sum; // 初始化方式 1
cout << f(1, 2) << endl;

PF1 f1 = &sum; // 初始化方式 2
cout << f1(1, 2) << endl;

using PF2 = int(int, int);    // 函数
PF2* f2 = sum;
cout << f2(1, 2) << endl;
```

**3)  为什么有函数指针**

函数与数据项相似，函数也有地址。我们希望在同一个函数中通过使用相同的形参在不同的时间使用产生不同的效果。

**4)  一个函数名就是一个指针，它指向函数的代码。**

一个函数地址是该函数的进入点，也就是调用函数的地址。**函数的调用可以通过函数名，也可以通过指向函数的指针来调用**。函数指针还允许将函数作为变元传递给其他函数；

**5)  两种方法赋值：**

指针名 = 函数名；  指针名 = &函数名

```cpp
int Func(int x);   // 声明一个函数
int (*p) (int x);  // 定义一个函数指针
p = Func;          // 将Func函数的首地址赋给指针变量p
p = &Func;
```



#### 83、说一说你理解的内存对齐以及原因

1. 分配内存的顺序是按照声明的顺序。

2. 每个变量相对于起始位置的偏移量必须是该变量类型大小的整数倍，不是整数倍空出内存，直到偏移量是整数倍为止。

3. 最后整个结构体的大小必须是里面变量类型**最大值的整数倍**。

添加了`#pragma pack(n)`后规则就变成了下面这样：

1. 偏移量要是n和当前变量大小中较小值的整数倍

2. 整体大小要是n和最大变量大小中较小值的整数倍

3. n值必须为1,2,4,8…，为其他值时就按照默认的分配规则



#### 84、结构体变量比较是否相等

1. 重载了 “==” 操作符

~~~cpp
struct foo {
    int a;
    int b;
    
    bool operator==(const foo& rhs) {
        return( a == rhs.a) && (b == rhs.b);
    }
};
~~~

2)   元素的话，一个个比；
3)   指针直接比较，如果保存的是同一个实例地址，则(p1==p2)为真；



#### 85、 函数调用过程栈的变化，返回值和参数变量哪个先入栈？

1. 调用者函数把被调函数所需要的参数按照与**被调函数的形参顺序相反的顺序压入栈中**；即: 从右向左依次把被调函数所需要的参数压入栈；
2. 调用者函数使用call指令调用被调函数，并把**call指令的下一条指令的地址当成返回地址**压入栈中(这个压栈操作隐含在call指令中)；
3. 在被调函数中，被调函数会先保存调用者函数的栈底地址(push ebp)，然后再保存调用者函数的栈顶地址，即：当前被调函数的栈底地址(mov ebp, esp)；
4. 在被调函数中，从ebp的位置处开始存放被调函数中的**局部变量和临时变量（static 变量不入栈）**，并且这些变量的地址按照定义时的顺序依次减小，即：这些变量的地址是按照栈的延伸方向排列的，先定义的变量先入栈，后定义的变量后入栈；



#### 86、define, const, typedef, inline的使用方法？他们之间有什么区别？

**（1）const与#define的区别**

1)  **const**定义的常量是变量**带类型**，而#define定义的只是个常数不带类型；

2)  define只在**预处理**阶段起作用，简单的文本替换，而const在**编译、链接过程**中起作用；

3)  define只是简单的字符串替换**没有类型检查**。而const是有数据类型的，是要进行判断的，可以避免一些低级错误；

4)  define预处理后，占用**代码段空间**，const占用**数据段空间**；

5)  const不能重定义，而define可以通过#undef取消某个符号的定义，进行**重定义**；

6)  define独特功能，比如可以用来**防止文件重复引用**。

**（2）#define和typedef的区别**

1)  执行时间不同：typedef在**编译阶段**有效，typedef有类型检查的功能；#define是宏定义，发生在**预处理阶段**，不进行类型检查；

2)  **功能差异**：typedef用来定义类型的别名，定义与平台无关的数据类型，与struct的结合使用等。#define不只是可以为类型取别名，还可以定义常量、变量、编译开关等；

3)  **作用域不同**：#define没有作用域的限制，只要是之前预定义过的宏，在以后的程序中都可以使用。而typedef有自己的作用域。

**（3）define与inline的区别**

1)  #define是**关键字**，inline是**函数**；

2)  宏定义在**预处理阶段**进行文本替换，inline函数在**编译阶段进行替换**；

3)  inline函数有**类型检查**，相比宏定义比较安全；



#### 87、你知道printf函数的实现原理是什么吗？

在C/C++中，对函数参数的扫描是**从后向前的**。

C/C++的函数参数是通过压入堆栈的方式来给函数传参数的（堆栈是一种先进后出的数据结构），最先压入的参数最后出来，在计算机的内存中，数据有2块，一块是堆，一块是栈（函数参数及局部变量在这里），而**栈是从内存的高地址向低地址生长的**，控制生长的就是堆栈指针了，最先压入的参数是在最上面，就是说在所有参数的最后面，最后压入的参数在最下面，结构上看起来是第一个，所以最后压入的参数总是能够被函数找到，因为它就在堆栈指针的上方。

printf的第一个被找到的参数就是那个**字符指针**，就是被双引号括起来的那一部分，函数通过判断字符串里控制参数的个数来**判断参数个数及数据类型**，通过这些就可算出数据需要的**堆栈指针的偏移量**了。



#### 88、为什么模板类一般都是放在一个h文件中 :thinking:

1. 模板定义很特殊。由`template<…>`处理的任何东西都意味着**编译器在当时不为它分配存储空间**，它一直处于等待状态直到被一个模板实例告知。在编译器和连接器的某一处，有一机制能去掉指定模板的多重定义。

   > 所以为了容易使用，几乎总是在头文件中放置全部的模板声明和定义。

2. 在分离式编译的环境下，编译器编译某一个.cpp文件时并不知道另一个.cpp文件的存在，也不会去查找（当遇到未决符号时它会寄希望于连接器）。这种模式在没有模板的情况下运行良好，但遇到模板时就傻眼了，因为模板仅在需要的时候才会实例化出来。

所以，当编译器只看到模板的声明时，它不能实例化该模板，只能创建一个具有外部连接的符号并期待连接器能够将符号的地址决议出来。

然而当实现该模板的.cpp文件中没有用到模板的实例时，编译器懒得去实例化，所以，整个工程的.obj中就找不到一行模板实例的二进制代码，于是连接器也黔驴技穷了。



#### 89、C++中类成员的访问权限和继承权限问题

[点击寻找原文链接](#name4)



#### 90、cout和printf有什么区别？

`cout <<`是一个函数，`cout <<`后可以跟不同的类型是因为`cout <<`已存在针对各种类型数据的重载，所以会自动识别数据的类型。输出过程会首先将输出字符放入缓冲区，然后输出到屏幕。

cout是有**缓冲输出**：

~~~cpp
cout << "abc " << endl;

// 和上面等价: flush立即强迫缓冲输出
cout << "abc\n "; cout << flush; 
~~~


 **printf是无缓冲输出。有输出时立即输出**

> [cout与printf区别](https://blog.csdn.net/QQ1449301756/article/details/47451887)



#### 91、你知道重载运算符吗？

1. 我们只能重载已有的运算符，而无权发明新的运算符；对于一个重载的运算符，其优先级和结合律与内置类型一致才可以；不能改变运算符操作数个数；

2. 两种重载方式：成员运算符和非成员运算符，**成员运算符比非成员运算符少一个参数**；下标运算符、箭头运算符必须是成员运算符；

3. 引入运算符重载，是为了实现类的多态性；

4. 当重载的运算符是成员函数时，this绑定到左侧运算符对象。成员运算符函数的参数数量比运算符对象的数量少一个；至少含有一个类类型的参数；

5. 从参数的个数推断到底定义的是哪种运算符，当运算符既是一元运算符又是二元运算符（+，-，*，&）；

6. 下标运算符必须是成员函数，下标运算符通常以所访问元素的引用作为返回值，同时最好定义下标运算符的常量版本和非常量版本；

7. **箭头运算符必须是类的成员，解引用通常也是类的成员**；重载的箭头运算符必须返回类的指针；



#### 92、当程序中有函数重载时，函数的匹配原则和顺序是什么？

1)  名字查找

2)  确定候选函数

3)  寻找最佳匹配



#### 93、定义和声明的区别

 **如果是指变量的声明和定义：**从编译原理上来说，声明是仅仅告诉编译器，有个某类型的变量会被使用，但是编译器并不会为它分配任何内存。**而定义就是分配了内存**。

**如果是指函数的声明和定义：**声明一般在头文件里，对编译器说：这里我有一个函数叫`function()`让编译器知道这个函数的存在。定义一般在源文件里，具体就是函数的实现过程写明函数体。



#### 94、全局变量和static变量的区别

1. 全局变量（外部变量）的说明之前再冠以static就构成了静态的全局变量。全局变量本身就是静态存储方式，静态全局变量当然也是静态存储方式。

   这两者在存储方式上并无不同。这两者的区别在于**非静态全局变量的作用域是整个源程序**，当一个源程序由多个原文件组成时，非静态的全局变量在各个源文件中都是有效的。

   而**静态全局变量则限制了其作用域**，即只在定义该变量的源文件内有效，在同一源程序的其它源文件中不能使用它。由于静态全局变量的作用域限于一个源文件内，只初始化一次，只能为该源文件内的函数公用，因此可以避免在其他源文件中引起错误。

2. static函数与普通函数有什么区别？

   static函数与普通的函数作用域不同。**只在当前源文件中使用的函数应该说明为内部函数（static）**，内部函数应该在当前源文件中说明和定义。

   对于可在当前源文件以外使用的函数应该在一个头文件中说明，要使用这些函数的源文件要包含这个头文件。static函数与普通函数最主要区别是**static函数在内存中只有一份，普通函数在每个被调用中维持一份拷贝**。



#### 95、静态成员与普通成员的区别是什么？

1)  **生命周期**：静态成员变量从类被加载开始到类被卸载，一直存在；普通成员变量只有在**类创建对象后**才开始存在，对象结束，它的生命期结束；

2)  **共享方式**：静态成员变量是全类共享；普通成员变量是**每个对象单独享用的**；

3)  **定义位置**：静态成员变量存储在**静态全局区**，而普通成员变量存储在**栈或堆**中；

4)  **初始化位置**：静态成员变量在**类外初始化**，而普通成员变量在类中初始化；

5)  **默认实参**：可以使用静态成员变量作为默认实参。



#### 96、说一下你理解的 ifdef, endif 代表着什么？

1. 一般情况下，源程序中所有的行都参加编译。但是有时希望对其中一部分内容只在满足一定条件才进行编译，也就是对一部分内容指定编译的条件，这就是**“条件编译”**。有时，希望当满足某条件时对一组语句进行编译，而当条件不满足时则编译另一组语句。 

2. 条件编译命令最常见的形式为： 

   ```bash
   #ifdef 标识符 
   程序段1 
   [#else 
   程序段2]
   #endif
   ```

   它的作用是：当标识符已经被定义过(一般是用`#define`命令定义)，则对`程序段1`进行编译，否则编译`程序段2`。其中`#else`部分也可以没有 


3)  在一个大的软件工程里面，可能会有多个文件同时包含一个头文件，当这些文件编译链接成一个可执行文件上时，就会出现大量“重定义”错误。在头文件中使用 #define、#ifndef、#ifdef、#endif 能**避免头文件重定义**。



#### 97、隐式转换，如何消除隐式转换？

1. C++的基本类型中并非完全的对立，部分数据类型之间是可以进行隐式转换的。**所谓隐式转换，是指不需要用户干预，编译器私下进行的类型转换行为**。很多时候用户可能都不知道进行了哪些转换

2. C++面向对象的多态特性，就是通过父类的类型实现对子类的封装。通过隐式转换，你可以直接将一个子类的对象使用父类的类型进行返回。在比如，数值和布尔类型的转换，整数和浮点数的转换等。某些方面来说，隐式转换给C++程序开发者带来了不小的便捷。C++是一门强类型语言，类型的检查是非常严格的。

3. 基本数据类型转换以取值范围的作为转换基础（保证精度不丢失）。隐式转换发生在从`小->大`的转换中。比如从`char->int`或 从`int->long`。自定义对象 子类对象可以隐式的转换为父类对象。

4. C++中提供了**explicit关键字**，在**构造函数声明**的时候加上explicit关键字，能够禁止隐式转换。

5. 如果构造函数只接受一个参数，则它实际上定义了转换为此类类型的隐式转换机制。可以通过将构造函数声明为explicit加以制止隐式类型转换，**关键字explicit只对一个实参的构造函数有效，需要多个实参的构造函数不能用于执行隐式转换，所以无需将这些构造函数指定为explicit**。



#### 98、C++如何处理多个异常的？

1. C++中的异常情况： 

   - **语法错误（编译错误）**：比如变量未定义、括号不匹配、关键字拼写错误等等编译器在编译时能发现的错误，这类错误可以及时被编译器发现，而且可以及时知道出错的位置及原因，方便改正。 
   - **运行时错误**：比如数组下标越界、系统内存不足等等。这类错误不易被程序员发现，它能通过编译且能进入运行，但运行时会出错，导致程序崩溃。为了有效处理程序运行时错误，C++中引入异常处理机制来解决此问题。

2. C++异常处理机制： 

   - 异常处理基本思想：执行一个函数的过程中发现异常，可以不用在本函数内立即进行处理， 而是抛出该异常，让函数的调用者直接或间接处理这个问题。 
   - C++异常处理机制由3个模块组成：try(检查)、throw(抛出)、catch(捕获) ，抛出异常的语句格式为：throw 表达式；如果try块中程序段发现了异常则抛出异常。 

   ```cpp
   try {
       // 能抛出异常的语句；（检查
   } catch(类型名[形参名]) { // 捕获特定类型的异常1
       // 处理1 
   } catch(类型名[形参名]) { // 捕获特定类型的异常2
       // 处理2
   } catch(...) { // 捕获所有类型的异常
   } 
   ```



#### 99、如何在不使用额外空间的情况下，交换两个数？

**(1) 算术**

```cpp
x = x + y
y = x - y
x = x - y
```

**(2) 异或**

```cpp
x = x^y
y = x^y
x = x^y
```



#### 100、你知道strcpy和memcpy的区别是什么吗？

1. 复制的内容不同。**strcpy只能复制字符串**，而memcpy可以复制任意内容，例如字符数组、整型、结构体、类等。
2. 复制的方法不同。**strcpy不需要指定长度，它遇到被复制字符的串结束符"\0"才结束，所以容易溢出**。memcpy则是根据其第3个参数决定复制的长度。
3. 用途不同。通常在复制字符串时用strcpy，而需要复制其他类型数据时则一般用memcpy



### 基础语法-101-120

> <a id="name6">完整例子以及解读</a>参考：https://interviewguide.cn/notes/03-hunting_job/02-interview/01-01-06-basic.html



#### 101、程序在执行int main(int argc, char *argv[])时的内存结构，你了解吗？

参数的含义是程序在命令行下运行的时候，需要**输入 argc 个参数**，每个参数是以 char 类型输入的，依次存在数组里面，数组是 argv[]，所有的参数**在指针 char * 指向的内存**中，数组的中元素的个数为 argc 个，第一个参数为程序的名称。



#### 102、volatile关键字的作用？

volatile 关键字是一种类型修饰符，**用它声明的类型变量表示可以被某些编译器未知的因素更改**，比如：操作系统、硬件或者其它线程等。遇到这个关键字声明的变量，编译器对访问该变量的代码就不再进行优化，从而可以提供对特殊地址的稳定访问。声明时语法：`int volatile vInt;` 当要求使用 volatile 声明的变量的值的时候，系统总是重新从它所在的内存读取数据，即使它前面的指令刚刚从该处读取过数据。而且读取的数据立刻被保存。

volatile用在如下的几个地方： 
 1) 中断服务程序中修改的供其它程序检测的变量需要加 volatile； 
 2) 多任务环境下各任务间共享的标志应该加 volatile； 
 3) 存储器映射的硬件寄存器通常也要加 volatile 说明，因为每次对它的读写都可能由不同意义；



#### 103、如果有一个空类，它会默认添加哪些函数？

~~~cpp
Empty(); // (1)缺省构造函数
Empty(const Empty& ); // (2)拷贝构造函数
~Empty(); // (3)析构函数
Empty& operator=( const Empty& ); // (4)赋值运算符
~~~



#### 104、C++中标准库是什么？

1)  C++ 标准库可以分为两部分：
    - **标准函数库**： 这个库是由通用的、独立的、不属于任何类的函数组成的。函数库继承自 C 语言
    - **面向对象类库**： 这个库是类及其相关函数的集合。

2)   输入/输出 I/O、字符串和字符处理、数学、时间、日期和本地化、动态分配、其他、宽字符函数

3)   标准的 C++ I/O 类、String 类、数值类、STL 容器类、STL 算法、STL 函数对象、STL 迭代器、STL 分配器、本地化库、异常处理类、杂项支持库



#### 105、你知道 const char* 与 string 之间的关系是什么吗？

1)  string 是c++标准库里面其中一个，封装了对字符串的操作，实际操作过程我们可以用 const char* 给 string 类初始化

2)  三者的转化关系如下所示： 

~~~cpp
// string 转 const char* 
string s = "abc"; 
const char* c_s = s.c_str(); 

// const char* 转 string，直接赋值即可 
const char* c_s = "abc"; 
string s(c_s); 

// string 转 char* 
string s = “abc”; 
const int len = s.length(); 
char* c = new char[len+1]; 
strcpy(c, s.c_str()); 

// char* 转 string 
char* c = “abc”; 
string s(c); 

// const char* 转char* 
const char* cpc = "abc"; 
char* pc = new char[strlen(cpc)+1]; 
strcpy(pc, cpc);

// char* 转 const char*，直接赋值即可 
char* pc = "abc";
const char* cpc = pc;
~~~



#### :dizzy: 为什么拷贝构造函数必须传引用不能传值？:fire:

1) 拷贝构造函数的作用就是用来复制对象的，在使用这个对象的实例来初始化这个对象的一个新的实例。
2) 参数传递过程到底发生了什么？
   将地址传递和值传递统一起来，归根结底还是传递的是"值"（地址也是值，只不过通过它可以找到另一个值）
   - 值传递：对于**内置数据类型**的传递时，直接赋值拷贝给形参(注意形参是函数内局部变量)；对于**类类型**的传递时，需要首先调用该类的拷贝构造函数来初始化形参(局部对象)；
   - 引用传递：无论对内置类型还是类类型，传递引用或指针最终都是传递的**地址值**！而地址总是指针类型(属于简单类型)，显然参数传递时，按简单类型的赋值拷贝，而不会有拷贝构造函数的调用(对于类类型)。

拷贝构造函数用来初始化一个非引用类类型对象，如果用传值的方式进行传参数，那么构造实参需要调用拷贝构造函数，**而拷贝构造函数需要传递实参，所以会一直递归**。

> 具体参考：https://blog.csdn.net/bit_zyx/article/details/124825804

**对于类类型作为参数，传值会调用拷贝构造函数，传引用不会！**

```cpp
class A{
    int val;
public:
    A(int x = 0):val(x){
        cout << "A(int x = 0)" << endl;
    }
    ~A(){
        cout << "~A()" << endl;
    }
    A(const A& a):val(a.val){	// 拷贝构造函数
        cout << "A(const A&)" << endl;
    }
    void show(){
        cout << val << endl;
    }
};

void show1(A a){
    a.show();
}

void show2(A &a){
    a.show();
}
// 主要观看输出，除了正常的构造析构之外 show1 会调用拷贝构造函数
int main(){
    A a = 10;
    show1(a);	// 会调用拷贝构造
    show2(a);	// 不会调用拷贝构造
}
```

> 参考：
>
> - [C++传参时值传递和引用传递的区别](https://blog.csdn.net/weixin_43973403/article/details/121162372)
> - [深入理解C++——引用传递](https://blog.csdn.net/qq_34719392/article/details/101787215)



#### 106、你什么情况用指针当参数，什么时候用引用，为什么？

1)  使用引用参数的主要原因有两个：
    - 程序员能修改调用函数中的数据对象
    - 通过传递引用可以不调用拷贝构造函数，提高效率 

2)  一般的原则：对于使用引用的值而不做修改的函数：
    - 如果**数据对象很小**，如内置数据类型或者小型结构，则按照值传递；                          
    - 如果数据对象是**数组**，则使用指针（唯一的选择），并且指针声明为指向**const的指针**；
    - 如果**数据对象是较大的结构**，则使用const指针或者引用，已提高程序的效率。这样可以节省结构所需的时间和空间；
    - 如果数据对象是**类对象**，则使用const引用（传递类对象参数的标准方式是按照引用传递）；

3)  对于修改函数中数据的函数：
    - 如果数据是内置数据类型，则使用指针
    - 如果数据对象是数组，指针和引用都可以，[原文链接](#name6)
    - 如果数据对象是结构，则使用引用或者指针
    - 如果数据是**类对象**，则使用**引用**



#### 107、你知道静态绑定和动态绑定吗？

1)  对象的静态类型：对象在**声明**时采用的类型。是在**编译期**确定的。

2)  对象的动态类型：目前所指对象的类型。是在**运行期**决定的。对象的动态类型可以更改，但是静态类型无法更改。

3)  静态绑定：绑定的是对象的静态类型，某特性（比如函数依赖于对象的静态类型，发生在编译期)

4)  动态绑定：绑定的是对象的动态类型，某特性（比如函数依赖于对象的动态类型，发生在运行期)



#### 108、如何设计一个计算仅单个子类的对象个数？

1. 为类设计一个**static静态变量** count 作为计数器；

2. 类定义结束后初始化count;

3. 在**构造函数**中对count进行+1;
4. 设计**拷贝构造函数**，在进行拷贝构造函数中进行count +1，操作；
5. 设计**赋值构造函数**，在进行赋值函数中对count+1操作；
6. 在**析构函数**中对count进行-1；



#### 109、怎么快速定位错误出现的地方

1. 如果是简单的错误，可以直接双击错误列表里的错误项或者生成输出的错误信息中带行号的地方就可以让编辑窗口定位到错误的位置上。

2. 对于复杂的模板错误，最好使用生成输出窗口。多数情况下出发错误的位置是最靠后的引用位置。如果这样确定不了错误，就需要先把自己写的代码里的引用位置找出来，然后逐个分析了。



#### 110、成员初始化列表会在什么时候用到？它的调用过程是什么？

1)  当初始化一个**引用成员变量**时；
2)  初始化一个**const成员变量**时；
3)  当调用一个基类的构造函数，而构造函数拥有一组参数时；
4)  当调用一个成员类的构造函数，而他拥有一组参数；

编译器会一一操作初始化列表，以适当顺序在构造函数之内安插初始化操作，并且在任何显示用户代码前。**list中的项目顺序是由类中的成员声明顺序决定的**，不是初始化列表中的排列顺序决定的。



#### 111、在进行函数参数以及返回值传递时，可以使用引用或者值传递，其中使用引用的好处有哪些？

- 在函数内部可以对此参数进行修改
- 提高函数调用和运行的效率（因为没有了传值和生成副本的时间和空间消耗）



#### 112、说一说strcpy、sprintf与memcpy这三个函数的不同之处

1)  操作对象不同
    - strcpy 的两个操作对象均为字符串 
    - sprintf 的操作源对象可以是多种数据类型，目的操作对象是字符串：`int sprintf(char *str, const char *format, ...)`
    - memcpy 的两个对象就是两个任意可操作的内存地址，并不限于何种数据类型

2)  执行效率不同：memcpy最高，strcpy次之，sprintf的效率最低

3)  实现功能不同
    - strcpy 主要实现字符串变量间的拷贝 
    - sprintf 主要实现**其他数据类型格式到字符串的转化** 
    - memcpy 主要是内存块间的拷贝



#### 113、将引用作为函数参数有哪些好处？

1)  传递引用给函数与传递指针的效果是一样的。**被调函数的形参就成为原来主调函数中的实参变量或对象的一个别名来使用**，所以在被调函数中对形参变量的操作就是对其相应的目标对象（在主调函数中）的操作。

2)  使用引用传递函数的参数，**在内存中并没有产生实参的副本**，它是直接对实参操作；而使用一般变量传递函数的参数，当发生函数调用时，需要给形参分配存储单元，形参变量是实参变量的副本；如果传递的是对象，还将调用拷贝构造函数。因此，当参数传递的数据较大时，用引用比用一般变量传递参数的效率和所占空间都好。

3)  使用指针作为函数的参数虽然也能达到与使用引用的效果，但是，在被调函数中同样要给形参分配存储单元，且需要重复使用“***指针变量名**”的形式进行运算，这很容易产生错误且程序的阅读性较差；另一方面，在主调函数的调用点处，必须用变量的地址作为实参。而引用更容易使用，更清晰。



#### 114、你知道数组和指针的区别吗？

1)  数组在内存中是连续存放的，开辟一块连续的内存空间；数组所占存储空间：`sizeof(数组名)`；数组大小：`sizeof(数组名)/sizeof(数组元素数据类型)`；

2)  用运算符sizeof 可以计算出数组的容量（字节数）。sizeof(p), p 为指针得到的是一个指针变量的字节数，而不是 p 所指的内存容量；

3)  编译器为了简化对数组的支持，实际上是利用指针实现了对数组的支持。具体来说，就是将表达式中的**数组元素引用转换为指针加偏移量的引用**；

4)  在向函数传递参数的时候，如果实参是一个数组，那用于接受的形参为对应的指针。也就是传递过去是数组的首地址而不是整个数组，能够提高效率；

5)  在使用下标的时候，两者的用法相同，都是原地址加上下标值，不过数组的原地址就是数组首元素的地址是**固定的**，指针的原地址就不是固定的。



#### 115、如何阻止一个类被实例化？有哪些方法？

1)  将类定义为**抽象基类**或者将构造函数声明为private；

2)  不允许类外部创建类对象，只能在类内部创建对象



#### 116、 如何禁止程序自动生成拷贝构造函数？ 

1)  为了阻止编译器默认生成拷贝构造函数和拷贝赋值函数，我们需要手动去**重写**这两个函数，某些情况下，为了避免调用拷贝构造函数和拷贝赋值函数，我们需要将他们设置成**private**，防止被调用；

2)  类的成员函数和friend函数还是可以调用private函数，如果这个private函数只声明不定义，则会产生一个连接错误；

3)  针对上述两种情况，我们可以定一个base类，在base类中将拷贝构造函数和拷贝赋值函数设置成private，那么派生类中编译器将不会自动生成这两个函数，且由于base类中该函数是私有的，因此派生类将阻止编译器执行相关的操作。



#### 117、你知道Debug和Release的区别是什么吗？

1)  调试版本，包含调试信息，所以容量比Release大很多，并且**不进行任何优化**（优化会使调试复杂化，因为源代码和生成的指令间关系会更复杂），便于程序员调试。Debug模式下生成两个文件，除了.exe或.dll文件外，还有一个.pdb文件，该文件记录了**代码中断点**等调试信息； 

2)  发布版本，不对源代码进行调试，**编译时对应用程序的速度进行优化**，使得程序在代码大小和运行速度上都是最优的。（调试信息可在单独的PDB文件中生成）。Release模式下生成一个文件.exe或.dll文件。

3)  实际上，Debug 和 Release 并没有本质的界限，他们只是一组编译选项的集合，编译器只是按照预定的选项行动。事实上，我们甚至可以修改这些选项，从而得到优化过的调试版本或是带跟踪语句的发布版本。



#### 118、main函数的返回值有什么值得考究之处吗？

程序运行过程入口点main函数，**main函数返回值类型必须是int**，这样返回值才能传递给程序激活者（如操作系统）表示程序正常退出。

`main(int args, char **argv)`参数的传递。参数的处理，一般会调用`getopt()`函数处理。



#### 119、模板会写吗？写一个比较大小的模板函数

~~~cpp
template<typename type1,typename type2>//函数模板 
type1 Max(type1 a,type2 b) { 
    return a > b ? a : b; 
} 

std::cout << "Max = " << Max(5.5,'a') << std::endl;
~~~

其实该模板有个比较隐晦的bug，那就是a、b只有在能进行转型的时候才能进行比较，否则 a > b 这一步是会报错的。这时候往往需要对于`operate>()`进行重载。

**`template<typename T>` 与`template<class T>` 基本类似，最好使用前者**

参考：

- [C++ 模板中 class T 和 typename T 的区别_Anadem](https://blog.csdn.net/Aloneingchild/article/details/105607306)

- [C++模板之typename和class关键字的区别 - CTHON](https://www.cnblogs.com/cthon/p/9201649.html)

- https://blog.csdn.net/gatieme/article/details/50946005
- https://stackoverflow.com/questions/2023977/difference-of-keywords-typename-and-class-in-templates





#### 120、strcpy函数和strncpy函数的区别？哪个函数更安全？

1. 函数原型

   ```cpp
   char *strcpy(char *dest, const char *src)
   char *strncpy(char *dest, const char *src, size_t n)
   ```

- strcpy函数: 如果参数 dest 所指的内存空间不够大，可能会造成缓冲溢出(buffer Overflow)的错误情况，在编写程序时请特别留意，或者用strncpy()来取代。 
- strncpy函数：用来复制源字符串的前n个字符，src 和 dest 所指的内存区域不能重叠，且 dest 必须有足够的空间放置n个字符。 
  - 如果目标长>指定长>源长，则将源长全部拷贝到目标长，自动加上’\0’ 
  -  如果指定长<源长，则将源长中按指定长度拷贝到目标字符串，不包括’\0’ 
  -  如果指定长>目标长，运行时错误 ；



### 基础语法-121-134

> <a id="name7">完整例子以及解读</a>参考：https://interviewguide.cn/notes/03-hunting_job/02-interview/01-01-07-basic.html



#### 121、static_cast比C语言中的转换强在哪里？

1)  更加安全；

2)  更直接明显，能够一眼看出是什么类型转换为什么类型，容易找出程序中的错误；可清楚地辨别代码中每个**显式的强制转**；可读性更好，能体现程序员的意图



#### 122、成员函数里 memset(this, 0, sizeof(*this)) 会发生什么？

有时候类里面定义了很多 int, char, struct 等C语言里的那些类型的变量，我习惯在构造函数中将它们初始化为0，但是一句句的写太麻烦，所以直接就memset(this, 0, sizeof *this)；将整个对象的内存全部置为0。对于这种情形可以很好的工作，但是下面几种情形是不可以这么使用的：

1)  类含有虚函数表：这么做会破坏虚函数表，后续对虚函数的调用都将出现异常；

2)  类中含有C++类型的对象：例如，类中定义了一个list的对象，由于在构造函数体的代码执行之前就对list对象完成了初始化，假设list在它的构造函数里分配了内存，那么我们这么一做就破坏了list对象的内存。



#### 123、你知道回调函数吗？它的作用？:fire:

1)  当发生某种事件时，系统或其他函数将会自动调用你定义的一段函数；
2)  回调函数就相当于一个**中断处理函数**，由系统在符合你设定的条件时自动调用。为此你需要做三件事：① 声明；② 定义；③ 设置触发条件，就是在你的函数中把你的回调函数名称转化为地址作为一个参数，以便于系统调用；
3)  回调函数就是一个通过**函数指针**调用的函数。如果你把函数的指针（地址）作为参数传递给另一个函数，当这个指针被用为调用它所指向的函数时，我们就说这是回调函数；

> 回调函数和普通函数是有区别的，回调可以降低耦合度，具体参考：[C 语言回调函数详解 | 菜鸟教程 (runoob.com)](https://www.runoob.com/w3cnote/c-callback-function.html)



#### 124、什么是一致性哈希？

**一致性哈希**

一致性哈希是一种哈希算法，就是**在移除或者增加一个结点时，能够尽可能小的改变已存在key的映射关系**

尽可能少的改变已有的映射关系，一般是沿着顺时针进行操作，回答之前可以先想想，真实情况如何处理

一致性哈希将整个哈希值空间组**织成一个虚拟的圆环**，假设哈希函数的值空间为0~2^32-1，整个哈希空间环如下左图所示

![](https://cdn.jsdelivr.net/gh/forthespada/mediaImage1@1.6.4.2/202102//1566573802731.png)

一致性hash的基本思想就是使用相同的hash算法将数据和结点都映射到图中的环形哈希空间中，上右图显示了4个数据object1-object4在环上的分布图

**结点和数据映射**

假如有一批服务器，可以根据IP或者主机名作为关键字进行哈希，根据结果映射到哈希环中，3台服务器分别是nodeA-nodeC

现在有一批的数据object1-object4需要存在服务器上，则可以使用相同的哈希算法对数据进行哈希，其结果必然也在环上，可以沿着顺时针方向寻找，找到一个结点（服务器）则将数据存在这个结点上，这样数据和结点就产生了一对一的关联，如下图所示：

![](https://cdn.jsdelivr.net/gh/forthespada/mediaImage1@1.6.4.2/202102/1566573868429.png)

**移除结点**

如果一台服务器出现问题，如上图中的nodeB，则受影响的是其逆时针方向至下一个结点之间的数据，只需将这些数据映射到它顺时针方向的第一个结点上即可，下左图

![](https://cdn.jsdelivr.net/gh/forthespada/mediaImage1@1.6.4.2/202102/1566573901641.png)

**添加结点**

如果新增一台服务器nodeD，受影响的是其逆时针方向至下一个结点之间的数据，将这些数据映射到nodeD上即可，见上右图

**虚拟结点**

假设仅有2台服务器：nodeA和nodeC，nodeA映射了1条数据，nodeC映射了3条，这样数据分布是不平衡的。引入虚拟结点，假设结点复制个数为2，则nodeA变成：nodeA1和nodeA2，nodeC变成：nodeC1和nodeC2，映射情况变成如下：

![](https://cdn.jsdelivr.net/gh/forthespada/mediaImage1@1.6.4.2/202102/1566573927297.png)

这样数据分布就均衡多了，平衡性有了很大的提高

> 一致性哈希与一般哈希不同点在于：一致性哈希对 2^32 取模，是一个固定的值，并且**将「存储节点」和「数据」都映射到一个首尾相连的哈希环上**，一般哈希只对存储节点映射



#### 125、C++从代码到可执行程序经历了什么？

##### （1）预编译

主要处理源代码文件中的以“#”开头的预编译指令。处理规则见下：

1. 删除所有的#define，展开所有的宏定义
2. 处理所有的条件预编译指令，如 “#if”、“#endif”、“#ifdef”、“#elif” 和 “#else”
3. 处理“#include”预编译指令，将文件内容替换到它的位置，这个过程是递归进行的，文件中包含其他文件
4. 删除所有的注释，“//”和“/**/”
5. 保留所有的 #pragma 编译器指令，编译器需要用到他们，如：#pragma once 是为了防止有文件被重复引用
6. 添加行号和文件标识，便于编译时编译器产生调试用的行号信息，和编译时产生编译错误或警告是能够显示行号。

##### （2）编译

把预编译之后生成的 `xxx.i` 或 `xxx.ii` 文件，进行一系列词法分析、语法分析、语义分析及优化后，生成相应的**汇编代码**文件。

1. 词法分析：利用类似于“有限状态机”的算法，将源代码程序输入到扫描机中，将其中的字符序列分割成一系列的记号
2. 语法分析：语法分析器对由扫描器产生的记号，进行语法分析，产生语法树。由语法分析器输出的语法树是一种以表达式为节点的树
3. 语义分析：语法分析器只是完成了对表达式语法层面的分析，语义分析器则对表达式是否有意义进行判断，其分析的语义是静态语义——在编译期能分期的语义，相对应的动态语义是在运行期才能确定的语义
4. 优化：源代码级别的一个优化过程
5. 目标代码生成：由代码生成器将中间代码转换成目标机器代码，生成一系列的代码序列——汇编语言表示
6. 目标代码优化：目标代码优化器对上述的目标机器代码进行优化：寻找合适的寻址方式、使用位移来替代乘法运算、删除多余的指令等

##### （3）汇编

将汇编代码转变成机器可以执行的指令(**机器码**文件)。 汇编器的汇编过程相对于编译器来说更简单，没有复杂的语法，也没有语义，更不需要做指令优化，只是根据汇编指令和机器指令的对照表一一翻译过
来，汇编过程有汇编器 as 完成。经汇编之后，产生**目标文件**(与可执行文件格式几乎一样)`xxx.o`(Windows下)、`xxx.obj`(Linux下)。

##### （4）链接

将不同的源文件产生的目标文件进行链接，从而形成一个**可以执行的程序**。链接分为静态链接和动态链接：

##### 静态链接

函数和数据被编译进一个二进制文件。在使用静态库的情况下，在编译链接可执行文件时，链接器从库中复制这些函数和数据并把它们和应用程序的其它模块组合起来创建最终的可执行文件。

- 空间浪费：因为每个可执行程序中对所有需要的目标文件都要有一份副本，所以如果多个程序对同一个目标文件都有依赖，会出现同一个目标文件都在内存存在多个副本；

- 更新困难：每当库函数的代码修改了，这个时候就需要重新进行编译链接形成可执行程序。

- 运行速度快：但是静态链接的优点就是，在可执行程序中已经具备了所有执行程序所需要的任何东西，在执行的时候运行速度快。

##### 动态链接

动态链接的基本思想是把程序按照模块拆分成各个相对独立部分，在程序运行时才将它们链接在一起形成一个完整的程序，而不是像静态链接一样把所有程序模块都链接成一个单独的可执行文件。

- 共享库：就是即使需要每个程序都依赖同一个库，但是该库不会像静态链接那样在内存中存在多分，副本，而是这多个程序在执行时共享同一份副本；

- 更新方便：更新时只需要替换原来的目标文件，而无需将所有的程序再重新链接一遍。当程序下一次运行时，新版本的目标文件会被自动加载到内存并且链接起来，程序就完成了升级的目标。

- 性能损耗：因为把链接推迟到了程序运行时，所以每次执行程序都需要进行链接，所以性能会有一定损失。



#### 126、为什么友元函数必须在类内部声明？

> [点击查看原文链接](#name7)，但是感觉友元不声明在类内部那还叫友元吗



#### 127、友元函数和友元类的基本情况

> [点击查看原文链接](#name7)



#### 128、用C语言实现C++的继承

~~~cpp
#include <iostream>
using namespace std;

// C++中的继承与多态
struct A
{
    virtual void fun()  // C++中的多态:通过虚函数实现
    {
    	cout<<"A:fun()"<<endl;
	}
	int a;
};

struct B: public A     // C++中的继承:B类公有继承A类
{
	virtual void fun()  //C++中的多态:通过虚函数实现（子类的关键字virtual可加可不加）
	{
        cout<<"B:fun()"<<endl;
	}
	int b;
};

// C语言模拟C++的继承与多态

typedef void (*FUN)();   //定义一个函数指针来实现对成员函数的继承

struct _A    // 父类
{
    FUN _fun;  //由于C语言中结构体不能包含函数，故只能用函数指针在外面实现
    int _a;
};

struct _B     // 子类
{
    _A _a_;   // 在子类中定义一个基类的对象即可实现对父类的继承
    int _b;

};

void _fA()    // 父类的同名函数
{
    printf("_A:_fun()\n");
}

void _fB()    // 子类的同名函数
{
	printf("_B:_fun()\n");
}

int main()
{
    // 测试C++中的继承与多态
    A a;  //定义一个父类对象a
    B b;  //定义一个子类对象b

    A* p1 = &a;  //定义一个父类指针指向父类的对象
    p1->fun();  //调用父类的同名函数
    p1 = &b;   //让父类指针指向子类的对象
    p1->fun();  //调用子类的同名函数
    
	// C语言模拟继承与多态的测试
    _A _a;  //定义一个父类对象_a
    _B _b;  //定义一个子类对象_b
    _a._fun = _fA;    //父类的对象调用父类的同名函数
    _b._a_._fun = _fB;  //子类的对象调用子类的同名函数
    _A* p2 = &_a;  //定义一个父类指针指向父类的对象
    p2->_fun();   //调用父类的同名函
    p2 = (_A*)&_b; //让父类指针指向子类的对象,由于类型不匹配所以要进行强转
    p2->_fun();   //调用子类的同名函数
    
    return 0;
}
~~~



#### 129、动态编译与静态编译

1)  静态编译，编译器在编译可执行文件时，把需要用到的对应动态链接库中的部分提取出来，连接到可执行文件中去，使可执行文件在运行时不需要依赖于动态链接库；

2)  动态编译的可执行文件需要附带一个动态链接库，在执行时，需要调用其对应动态链接库的命令。所以其优点一方面是**缩小了执行文件本身的体积**，另一方面是**加快了编译速度**，节省了系统资源。缺点是哪怕是很简单的程序，只用到了链接库的一两条命令，也需要附带一个相对庞大的链接库；二是如果其他计算机上没有安装对应的运行库，则用动态编译的可执行文件就不能运行。



#### 130、hello.c 程序的编译过程


以下是一个 hello.c 程序：

```c
#include <stdio.h>
int main()
{
    printf("hello, world\n");
    return 0;
}
```

在 Unix 系统上，由编译器把源文件转换为目标文件。

```bash
gcc -o hello hello.c
```

这个过程大致如下：

![](https://cdn.jsdelivr.net/gh/forthespada/mediaImage1@1.6.4.2/202102/微信截图_20210201114531.png)

- 预处理阶段：处理以 # 开头的预处理命令；
- 编译阶段：翻译成汇编文件；
- 汇编阶段：将汇编文件翻译成可重定位目标文件；
- 链接阶段：将可重定位目标文件和 printf.o 等单独预编译好的目标文件进行合并，得到最终的可执行目标文件。

##### 静态链接

静态链接器以一组可重定位目标文件为输入，生成一个完全链接的可执行目标文件作为输出。链接器主要完成以下两个任务：

- 符号解析：每个符号对应于一个函数、一个全局变量或一个静态变量，符号解析的目的是将每个符号引用与一个符号定义关联起来。
- 重定位：链接器通过把每个符号定义与一个内存位置关联起来，然后修改所有对这些符号的引用，使得它们指向这个内存位置。

![](https://cdn.jsdelivr.net/gh/forthespada/mediaImage1@1.6.4.2/202102/微信截图_20210201114618.png)

##### 目标文件

- 可执行目标文件：可以直接在内存中执行；
- 可重定位目标文件：可与其它可重定位目标文件在链接阶段合并，创建一个可执行目标文件；
- 共享目标文件：这是一种特殊的可重定位目标文件，可以在运行时被动态加载进内存并链接；

##### 动态链接

静态库有以下两个问题：

- 当静态库更新时那么整个程序都要重新进行链接；
- 对于 printf 这种标准函数库，如果每个程序都要有代码，这会极大浪费资源。

共享库是为了解决静态库的这两个问题而设计的，在 Linux 系统中通常用 .so 后缀来表示，Windows 系统上它们被称为 DLL。它具有以下特点：

- 在给定的文件系统中一个库只有一个文件，所有引用该库的可执行目标文件都共享这个文件，它不会被复制到引用它的可执行文件中；
- 在内存中，一个共享库的 .text 节（已编译程序的机器代码）的一个副本可以被不同的正在运行的进程共享。

![](https://cdn.jsdelivr.net/gh/forthespada/mediaImage1@1.6.4.2/202102/微信截图_20210201115700.png)

**源代码 --> 预处理 --> 编译 --> 优化 --> 汇编 --> 链接 --> 可执行文件**

1)   预处理

读取c源程序，对其中的伪指令（以#开头的指令）和特殊符号进行处理。包括宏定义替换、条件编译指令、头文件包含指令、特殊符号。 预编译程序所完成的基本上是对源程序的“替代”工作。经过此种替代，生成一个没有宏定义、没有条件编译指令、没有特殊符号的输出文件。.i预处理后的c文件，.ii预处理后的C++文件。

2)   编译阶段

编译程序所要作得工作就是通过词法分析和语法分析，在确认所有的指令都符合语法规则之后，将其翻译成等价的中间代码表示或汇编代码。.s文件

3)   汇编过程

汇编过程实际上指把汇编语言代码翻译成目标机器指令的过程。对于被翻译系统处理的每一个C语言源程序，都将最终经过这一处理而得到相应的目标文件。目标文件中所存放的也就是与源程序等效的目标的机器语言代码。.o目标文件

4)   链接阶段

链接程序的主要工作就是将有关的目标文件彼此相连接，也即将在一个文件中引用的符号同该符号在另外一个文件中的定义连接起来，使得所有的这些目标文件成为一个能够诶操作系统装入执行的统一整体。



#### 131、介绍一下几种典型的锁

**读写锁**

- 多个读者可以同时进行读
- 写者必须互斥（只允许一个写者写，也不能读者写者同时进行）
- 写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）

**互斥锁**

一次只能一个线程拥有互斥锁，其他线程只有等待

互斥锁是在抢锁失败的情况下主动放弃CPU进入睡眠状态直到锁的状态改变时再唤醒，而操作系统负责线程调度，为了实现锁的状态发生改变时唤醒阻塞的线程或者进程，需要**把锁交给操作系统管理**，所以互斥锁在加锁操作时涉及上下文的切换。互斥锁实际的效率还是可以让人接受的，加锁的时间大概100ns左右，而实际上互斥锁的一种可能的实现是先自旋一段时间，当自旋的时间超过阀值之后再将线程投入睡眠中，因此在并发运算中使用互斥锁（每次占用锁的时间很短）的效果可能不亚于使用自旋锁

**条件变量**

互斥锁一个明显的缺点是他只有两种状态：锁定和非锁定。而条件变量通过允许线程阻塞和等待另一个线程发送信号的方法弥补了互斥锁的不足，他常和互斥锁一起使用，以免出现竞态条件。当条件不满足时，线程往往解开相应的互斥锁并阻塞线程然后等待条件发生变化。一旦其他的某个线程改变了条件变量，他将通知相应的条件变量唤醒一个或多个正被此条件变量阻塞的线程。总的来说**互斥锁是线程间互斥的机制，条件变量则是同步机制**。

**自旋锁**

如果进线程无法取得锁，进线程不会立刻放弃CPU时间片，而是一直循环尝试获取锁，直到获取为止。如果别的线程长时期占有锁那么自旋就是在浪费CPU做无用功，但是**自旋锁一般应用于加锁时间很短的场景**，这个时候效率比较高。



#### 132、delete和delete[]区别？

- delete只会调用一次析构函数。
- delete[]会调用数组中每个元素的析构函数。



#### 133、为什么不能把所有的函数写成内联函数?

内联函数以代码复杂为代价，它以**省去函数调用的开销**来提高执行效率。所以一方面如果内联函数体内代码执行时间相比函数调用开销较大，则没有太大的意义；另一方面每一处内联函数的调用都要复制代码，消耗更多的内存空间，因此以下情况不宜使用内联函数：

- 函数体内的代码比较长，将导致内存消耗代价
- 函数体内有循环，函数执行时间要比函数调用开销大



#### 134、为什么C++没有垃圾回收机制？这点跟Java不太一样。

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



### 内存管理-01-15

> <a id="new1">完整例子以及解读</a>参考：https://interviewguide.cn/notes/03-hunting_job/02-interview/01-02-01-memory.html



#### 1、类的对象存储空间？

- 非静态成员的数据类型大小之和
- 编译器加入的额外成员变量（如指向虚函数表的指针）
- 为了边缘对齐优化加入的padding

空类(无非静态数据成员)的对象的size为1，当作为基类时，size为 0



#### 2、简要说明C++的内存分区

**栈**：在执行函数时，函数内局部变量的存储单元都可以在栈上创建，函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中，效率很高，但是分配的内存容量有限

**堆**：就是那些由 `new`分配的内存块，他们的释放编译器不去管，由我们的应用程序去控制，一般一个`new`就要对应一个 `delete`。如果程序员没有释放掉，那么在程序结束后，操作系统会自动回收

**自由存储区**：如果说堆是操作系统维护的一块内存，那么自由存储区就是C++中通过new和delete动态分配和释放对象的抽象概念。需要注意的是，自由存储区和堆比较像，但不等价。

**全局/静态存储区**：全局变量和静态变量被分配到同一块内存中，在以前的C语言中，全局变量和静态变量又分为初始化的和未初始化的，在C++里面没有这个区分了，它们共同占用同一块内存区，在该区定义的变量若没有初始化，则会被自动初始化，例如int型变量自动初始为0

**常量存储区**：这是一块比较特殊的存储区，这里面存放的是常量，不允许修改

**代码区**：存放函数体的二进制代码



#### 3、什么是内存池，如何实现？

内存池（Memory Pool） 是一种**内存分配**方式。通常我们习惯直接使用 new、malloc 等申请内存，这样做的缺点在于：由于所申请内存块的大小不定，当频繁使用时会造成大量的**内存碎片**并进而降低性能。内存池则是在真正使用内存之前，先申请分配一定数量的、大小相等(一般情况下)的内存块留作备用。当有新的内存需求时，就从内存池中分出一部分内存块， 若内存块不够再继续申请新的内存。这样做的一个显著优点是尽量避免了内存碎片，使得内存分配效率得到提升。

> 具体参考：[原文链接](#new1)



#### 4、可以说一下你了解的C++得内存管理吗？

5个常见分区：栈、堆、全局/静态存储区、常量存储区、代码区



#### 5、C++中类的数据成员和成员函数内存分布情况

- 一个类对象的地址就是类所包含的这一片内存空间的**首地址**，这个首地址也就对应具体**某一个成员变量的地址**
- 成员函数不占用对象的内存。这是因为所有的函数都是存放在**代码区**的，不管是全局函数，还是成员函数
- **静态成员函数与一般成员函数的唯一区别就是没有this指针**，因此不能访问非静态数据成员
- 静态函数存放在**代码区**，静态变量/全局变量存放在**全局数据区**



#### 6、关于this指针你知道什么？

- this指针是类的指针，指向对象的首地址
- this指针只能在成员函数中使用，在全局函数、静态成员函数中都不能用this
- this指针只有在成员函数中才有定义，且存储位置会因编译器不同有不同存储位置

**用处**：非静态成员函数访问非静态成员变量时默认会调用this指针

**使用**：当形参与成员变量名相同赋值时用于区分需要使用 `this->n = n`

**特点**：非静态成员函数在编译时实际会将 `T* const this` 作为第一个参数，即 `int func(T* const this, int p);`



#### 7、几个this指针的易混问题

- this在成员函数的**开始执行前构造**，在成员的**执行结束后清除**
- this指针会因编译器不同而有不同的放置位置。可能是栈，也可能是寄存器，甚至全局变量
- this是通过函数参数的**首参**来传递的
- 普通的类函数（成员函数/静态函数）都不会创建一个函数表来保存函数指针。只有虚函数才会被放到函数表中

> 具体查看：[原文链接](#new1)



#### 8、内存泄漏的后果？如何监测？解决方法？

**后果：**大量的内存泄漏会导致程序的失败

**解决：**智能指针



#### 9、在成员函数中调用delete this会出现什么问题？对象还可以使用吗？

当调用delete this时，**类对象的内存空间被释放**。在delete this之后进行的其他任何函数调用，只要不涉及到this指针的内容，都能够正常运行。一旦涉及到this指针，如操作数据成员，调用虚函数等，就会出现不可预期的问题。



#### 10、delete this 之后为啥会出现不可预期的问题？

delete this释放了类对象的内存空间，但是内存空间却并不是马上被回收到系统中，可能是缓冲或者其他什么原因，导致这段内存空间暂时并没有被系统收回。此时这段内存是可以访问的，你可以加上100，加上200，但是其中的值却是不确定的。当你获取数据成员，可能得到的是一串很长的未初始化的随机数；访问虚函数表，指针无效的可能性非常高，造成系统崩溃。



#### 11、 如果在类的析构函数中调用delete this，会发生什么？

会导致堆栈溢出。原因很简单，delete的本质是“为将被释放的内存调用一个或多个析构函数，然后，释放内存”。显然，delete this会去调用本对象的析构函数，而析构函数中又调用delete this，形成无限递归，造成堆栈溢出，系统崩溃。



#### 12、你知道空类的大小是多少吗？

1. C++**空类的大小不为0**，不同编译器设置不一样，vs设置为1；
2. C++标准指出，不允许一个对象（当然包括类对象）的大小为0，不同的对象不能具有相同的地址；
3. 带有虚函数的C++类大小不为1，因为每一个对象会有一个**vptr**指向虚函数表，具体大小根据指针大小确定；
4. C++中要求**类的每个实例都必须有独一无二的地址**,那么编译器自动为空类分配一个字节大小，这样便保证了每个实例均有独一无二的内存地址。



#### 13、请说一下以下几种情况下，下面几个类的大小各是多少？

- 空类的大小是1， 在C++中空类会占一个字节，这是为了让对象的实例能够相互区别
- 有虚函数的类对象中都有一个**虚函数表指针 __vptr**，其大小是4字节（32位）/8字节（64位）
- 静态成员存放在静态存储区，不占用类的大小, 普通函数也不占用类大小

> 具体查看：[原文链接](#new1) :fire:



#### 14、this指针调用成员变量时，堆栈会发生什么变化？

当建立了类的多个对象时，在调用类的成员函数时，你并不知道具体是哪个对象在调用，此时你可以通过查看this指针来查看具体是哪个对象在调用。**this指针首先入栈，然后成员函数的参数从右向左进行入栈，最后函数返回地址入栈**。



#### 15、类对象的大小受哪些因素影响？

> 和 T1 类似

1. 类的非静态成员变量大小，静态成员不占据类的空间，成员函数也不占据类的空间大小；
2. 内存对齐另外分配的空间大小，类内的数据也是需要进行内存对齐操作的；
3. 虚函数的话，会在类对象插入vptr指针，加上指针大小；
4. 当该类是某类的派生类，那么派生类继承的基类部分的数据成员也会存在在派生类中的空间中，也会对派生类进行扩展。



### C++11—01-10

> <a id="new2">完整例子以及解读</a>参考：https://interviewguide.cn/notes/03-hunting_job/02-interview/01-03-01-C++11.html

#### 1、C++ 11有哪些新特性？[参考](https://cloud.tencent.com/developer/article/old/1745592)

- nullptr替代 NULL
- 引入了 auto 和 decltype 这两个关键字实现了类型推导
- 基于范围的 for 循环：`for(auto& i : res){}`
- 类和结构体的中初始化列表
- Lambda 表达式（匿名函数）
- std::forward_list（单向链表）
- 右值引用和move语义



#### 2、auto, decltype, decltype(auto) 的用法

**（1）auto**

C++11新标准引入了auto类型说明符，用它就能让编译器替我们去分析表达式所属的类型。和原来那些只对应某种特定的类型说明符(例如 int)不同，**auto 让编译器通过初始值来进行类型推演。从而获得定义变量的类型，所以说 auto 定义的变量必须有初始值。**

**（2）decltype**

有的时候我们还会遇到这种情况，**我们希望从表达式中推断出要定义变量的类型，但却不想用表达式的值去初始化变量**。还有可能是函数的返回类型为某表达式的值类型。在这些时候auto显得就无力了，所以C++11又引入了第二种类型说明符decltype，**它的作用是选择并返回操作数的数据类型。在此过程中，编译器只是分析表达式并得到它的类型，却不进行实际的计算表达式的值。**

```cpp
int func() {return 0};

//普通类型
decltype(func()) sum = 5; // sum的类型是函数func()的返回值的类型int, 但是这时不会实际调用函数func()
int a = 0;
decltype(a) b = 4; // a的类型是int, 所以b的类型也是int

//不论是顶层const还是底层const, decltype都会保留   
const int c = 3;
decltype(c) d = c; // d的类型和c是一样的, 都是顶层const
int e = 4;
const int* f = &e; // f是底层const
decltype(f) g = f; // g也是底层const

//引用与指针类型
//1. 如果表达式是引用类型, 那么decltype的类型也是引用
const int i = 3, &j = i;
decltype(j) k = 5; // k的类型是 const int&

//2. 如果表达式是引用类型, 但是想要得到这个引用所指向的类型, 需要修改表达式:
int i = 3, &r = i;
decltype(r + 0) t = 5; // 此时是int类型

//3. 对指针的解引用操作返回的是引用类型
int i = 3, j = 6, *p = &i;
decltype(*p) c = j; // c是int&类型, c和j绑定在一起

//4. 如果一个表达式的类型不是引用, 但是我们需要推断出引用, 那么可以加上一对括号, 就变成了引用类型了
int i = 3;
decltype((i)) j = i; // 此时j的类型是int&类型, j和i绑定在了一起
```

**（3）decltype(auto)**

decltype(auto) 是 C++14 新增的类型指示符，可以用来声明变量以及指示函数返回类型。在使用时，会将“=”号右边的表达式替换掉auto，再根据decltype的语法规则来确定类型。

```cpp
int e = 4;
const int* f = &e;		// f是底层const
decltype(auto) j = f;	// j的类型是const int*，并且指向的是e
```



#### 3、C++中NULL和nullptr区别

NULL 来自 C语言，一般由宏定义实现，而 nullptr 则是C++11的新增关键字

```cpp
#ifdef __cplusplus
#define NULL 0
#else
#define NULL ((void *)0)
#endif
```

nullptr 可以明确区分整型和指针类型，能够根据环境自动转换成相应的指针类型，但不会被转换为任何整型



#### 4、智能指针的原理、常用的智能指针及实现 :fire:

**原理**

智能指针是**一个类**，用来存储指向动态分配对象的指针，负责**自动释放动态分配的对象**，防止堆内存泄漏。动态分配的资源，交给一个类对象去管理，当类对象声明周期结束时，自动调用析构函数释放资源

**常用的智能指针**

**(1) shared_ptr**

实现原理：采用**引用计数器**的方法，允许多个智能指针指向同一个对象，每当多一个指针指向该对象时，指向该对象的所有智能指针内部的引用计数加1，每当减少一个智能指针指向对象时，引用计数会减1，当计数为0的时候会自动的释放动态分配的资源。

- 智能指针将一个计数器与类指向的对象相关联，引用计数器跟踪共有多少个类对象共享同一指针
- 每次创建类的**新对象**时，初始化指针并将引用计数置为1
- 当对象作为另一对象的副本而创建时，**拷贝构造函数**拷贝指针并增加与之相应的引用计数
- 对一个对象进行**赋值**时，赋值操作符减少左操作数所指对象的引用计数（如果引用计数为减至0，则删除对象），并增加右操作数所指对象的引用计数
- 调用**析构函数**时，构造函数减少引用计数（如果引用计数减至0，则删除基础对象）

> 例子参考：[原文链接](#new2)

**(2) unique_ptr**

unique_ptr 采用的是**独享所有权语义**，一个非空的 unique_ptr 总是拥有它所指向的资源。转移一个 unique_ptr 将会把所有权全部从源指针转移给目标指针，源指针被置空；所以 unique_ptr **不支持普通的拷贝和赋值操作**，不能用在 STL 标准容器中；局部变量的返回值除外（因为编译器知道要返回的对象将要被销毁）；如果你拷贝一个 unique_ptr，那么拷贝结束后，这两个 unique_ptr 都会指向相同的资源，造成在结束时对同一内存指针多次释放而导致程序崩溃

**(3) weak_ptr**

weak_ptr：弱引用。 引用计数有一个问题就是互相引用形成环（**环形引用**），这样两个指针指向的内存都无法释放。需要使用weak_ptr打破环形引用。weak_ptr是一个弱引用，它是为了配合shared_ptr而引入的一种智能指针，**它指向一个由shared_ptr管理的对象而不影响所指对象的生命周期，也就是说，它只引用，不计数**。如果一块内存被shared_ptr和weak_ptr同时引用，当所有shared_ptr析构了之后，不管还有没有weak_ptr引用该内存，内存也会被释放。所以weak_ptr不保证它指向的内存一定是有效的，在使用之前使用函数lock()检查weak_ptr是否为空指针

**(4) auto_ptr**

主要是为了**解决“有异常抛出时发生内存泄漏”的问题**。因为发生异常而无法正常释放内存。auto_ptr 有**拷贝语义**，拷贝后源对象变得无效，这可能引发很严重的问题；而 unique_ptr 则无拷贝语义，但提供了移动语义，这样的错误不再可能发生，因为很明显必须使用 std::move() 进行转移。auto_ptr 不支持拷贝和赋值操作，不能用在STL标准容器中。STL容器中的元素经常要支持拷贝、赋值操作，在这过程中 auto_ptr 会传递所有权，所以不能在 STL 中使用。



#### 5、说一说你了解的关于lambda函数的全部知识

- lambda表达式可以编写内嵌的**匿名函数**，用以替换独立函数或者函数对象
- 每当你定义一个lambda表达式后，编译器会自动生成一个匿名类（这个类当然**重载了()运算符**），我们称为闭包类型（closure type）



#### 6、智能指针的作用

- 方便管理堆内存
- shared_ptr内部的引用计数是线程安全的，但是对象的读取需要加锁
- 智能指针是个模板类，可以指定类型，传入指针通过构造函数初始化。也可以使用make_shared函数初始化
- unique_ptr“唯一”拥有其所指对象，同一时刻只能有一个unique_ptr指向给定对象（通过禁止拷贝语义、只有移动语义来实现）
-  weak_ptr 只可以从一个 shared_ptr 或另一个 weak_ptr 对象构造, 它的构造和析构不会引起引用记数的增加或减少



#### 7、说说你了解的auto_ptr作用

- 解决“有异常抛出时发生内存泄漏”的问题
- **auto_ptr的构造函数是explicit**，阻止了一般指针隐式转换为 auto_ptr的构造，所以不能直接将一般类型的指针赋值给auto_ptr类型的对象，必须用auto_ptr的构造函数创建对象
- 由于auto_ptr对象析构时会删除它所拥有的指针，所以使用时**避免多个auto_ptr对象管理同一个指针**
- auto_ptr内部实现，析构函数中删除对象用的是delete而不是delete[]，所以**auto_ptr不能管理数组**



#### 8、智能指针的循环引用

> [原文链接](#new2)



#### 9、手写实现智能指针类需要实现哪些函数？

实现一个模板类，具体有构造函数、拷贝构造函数、赋值构造函数、析构函数、移动函数，可以参考 T4



#### 10、智能指针出现循环引用怎么解决？

弱指针用于专门解决shared_ptr循环引用的问题，weak_ptr不会修改引用计数，即其存在与否并不影响对象的引用计数器。循环引用就是：两个对象互相使用一个shared_ptr成员变量指向对方。弱引用并不对对象的内存进行管理，在功能上类似于普通指针，然而一个比较大的区别是，弱引用能检测到所管理的对象是否已经被释放，从而避免访问非法内存。



### STL 模板库-01-20

> <a id="new3">完整例子以及解读</a>参考：https://interviewguide.cn/notes/03-hunting_job/02-interview/01-04-01-STL.html



#### 1、什么是STL？

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

- 算法包括排序，复制等常用算法，以及不同容器特定的算法
- 容器就是数据的存放形式，包括序列式容器和关联式容器，序列式容器就是list，vector等，关联式容器就是set，map等
- 迭代器就是在不暴露容器内部结构的情况下对容器的遍历



#### 2、解释一下什么是trivial destructor？

- 用户没有自定义析构函数，而由系统生成的析构函数就是 trivial destructor，它是“无关痛痒”的析构函数
- 用户自定义了析构函数，则称之为“non-trivial destructor”，这种析构函数**如果申请了新的空间一定要显式的释放，否则会造成内存泄露**



#### 3、使用智能指针管理内存资源，RAII是怎么回事？

- RAII全称是“Resource Acquisition is Initialization”，直译过来是“资源获取即初始化”，也就是说在构造函数中申请分配资源，在析构函数中释放资源
- 智能指针（std::shared_ptr 和 std::unique_ptr）即**RAII最具代表的实现**，使用智能指针，可以实现自动的内存管理，再也不需要担心忘记 delete 造成的内存泄漏



#### 4、迭代器：++it, it++ 哪个好，为什么？

1)  **前置返回一个引用**，后置返回一个对象

~~~cpp
// ++i 实现代码为：
int& operator++() {
    *this += 1;
    return *this;
}
~~~

2)  前置不会产生临时对象，**后置必须产生临时对象**，临时对象会导致效率降低

~~~cpp
// i++ 实现代码为：                 
int operator++(int) {
    int temp = *this;
    ++ (*this);
    return temp;
}
~~~

 

#### 5、说一下C++左值引用和右值引用

C++11正是通过引入右值引用来优化性能，具体来说是**通过移动语义来避免无谓拷贝**的问题，通过move语义来将临时生成的左值中的资源无代价的转移到另外一个对象中去，通过完美转发来解决不能按照参数实际类型来转发的问题（同时，完美转发获得的一个好处是可以实现移动语义）。 

1. 在C++11中所有的值必属于左值、右值两者之一，右值又可以细分为**纯右值、将亡值**。在C++11中**可以取地址的、有名字的就是左值**，反之，不能取地址的、没有名字的就是右值（将亡值或纯右值）。

   举个例子，int a = b+c, a 就是左值，其有变量名为a，通过&a可以获取该变量的地址；表达式b+c、函数int func()的返回值是右值，在其被赋值给某一变量前，我们不能通过变量名找到它，＆(b+c)这样的操作则不会通过编译。

2. C++11对C++98中的右值进行了扩充。在C++11中右值又分为纯右值 (prvalue，Pure Rvalue) 和将亡值 (xvalue，eXpiring Value)。其中纯右值的概念等同于我们在C++98标准中右值的概念，指的是临时变量和不跟对象关联的字面量值；

   将亡值则是C++11新增的跟右值引用相关的表达式，这样表达式通常是将要被移动的对象（移为他用），比如返回右值引用**T&&的函数返回值**、**std::move的返回值**，或者转换为T&&的类型转换函数的返回值。将亡值可以理解为通过“盗取”其他变量内存空间的方式获取到的值。在确保其他变量不再被使用、或即将被销毁时，通过“盗取”的方式可以避免内存空间的释放和分配，能够延长变量值的生命期。

3. 左值引用就是对一个左值进行引用的类型，右值引用就是对一个右值进行引用的类型。事实上，由于右值通常不具有名字，我们也只能通过引用的方式找到它的存在。右值引用和左值引用都是属于引用类型。

   无论是声明一个左值引用还是右值引用，都必须立即进行初始化。而其原因可以理解为是**引用类型本身自己并不拥有所绑定对象的内存，只是该对象的一个别名**。左值引用是具名变量值的别名，而右值引用则是不具名（匿名）变量的别名。左值引用通常也不能绑定到右值，但**常量左值引用**是个“万能”的引用类型。它可以接受非常量左值、常量左值、右值对其进行初始化。不过常量左值所引用的右值在它的“余生”中只能是只读的。相对地，**非常量左值只能接受非常量左值对其进行初始化**。

4. 右值值引用通常不能绑定到任何的左值，要想绑定一个左值到右值引用，通常需要**std::move()将左值强制转换为右值**。

**左值和右值**

左值：**表示的是可以获取地址的表达式**，它能出现在赋值语句的左边，对该表达式进行赋值。但是修饰符const的出现使得可以声明如下的标识符，它可以取得地址，但是没办法对其进行赋值

```C++
const int& a = 10;
```

右值：**表示无法获取地址的对象，有常量值、函数返回值、lambda表达式等**。无法获取地址，但不表示其不可改变，当定义了右值的右值引用时就可以更改右值。

**左值引用和右值引用**

左值引用：传统的C++中引用被称为左值引用

右值引用：C++11中增加了右值引用，右值引用关联到右值时，右值被存储到特定位置，右值引用指向该特定位置，也就是说，**右值虽然无法获取地址，但是右值引用是可以获取地址的**，该地址表示临时对象的存储位置

**这里主要说一下右值引用的特点：**

- 特点1：通过右值引用的声明，右值又“重获新生”，其生命周期与右值引用类型变量的生命周期一样长，只要该变量还活着，该右值临时量将会一直存活下去
- 特点2：右值引用独立于左值和右值。意思是右值引用类型的变量可能是左值也可能是右值
- 特点3：**T&& t在发生自动类型推断**的时候，它是左值还是右值取决于它的初始化

举个例子：

```C++
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void fun(T&& t)
{
    cout << t << endl;
}

int getInt()
{
    return 5;
}

int main() {
    int a = 10;
    int& b = a;  //b是左值引用
    int& c = 10;  //错误，c是左值不能使用右值初始化
    int&& d = 10;  //正确，右值引用用右值初始化
    int&& e = a;  //错误，e是右值引用不能使用左值初始化
    const int& f = a; //正确，左值常引用相当于是万能型，可以用左值或者右值初始化
    const int& g = 10;//正确，左值常引用相当于是万能型，可以用左值或者右值初始化
    const int&& h = 10; //正确，右值常引用
    const int& aa = h;//正确
    int& i = getInt();  //错误，i是左值引用不能使用临时变量（右值）初始化
    int&& j = getInt();  //正确，函数返回值是右值
    fun(10); //此时fun函数的参数t是右值
    fun(a); //此时fun函数的参数t是左值
    return 0;
}
```



#### 6、STL中hashtable的实现？

STL中的hashtable使用的是**开链法**解决hash冲突问题，如下图所示。

![](https://cdn.jsdelivr.net/gh/forthespada/mediaImage1@1.6.4.2/202102/1566639786045.png)

hashtable中的bucket所维护的list既不是list也不是slist，而是其自己定义的由hashtable_node数据结构组成的linked-list，而bucket聚合体本身使用vector进行存储。hashtable的迭代器只提供前进操作，不提供后退操作

在hashtable设计bucket的数量上，其内置了28个**质数**[53, 97, 193,...,429496729]，在创建hashtable时，会根据存入的元素个数选择大于等于元素个数的质数作为hashtable的容量（vector的长度），其中每个bucket所维护的linked-list长度也等于hashtable的容量。如果插入hashtable的元素个数超过了bucket的容量，就要进行重建table操作，即找出下一个质数，创建新的buckets vector，重新计算元素在新hashtable的位置。



#### 7、:dizzy:简单说一下STL中的traits技法

traits技法利用“内嵌型别“的编程技巧与**编译器的template参数推导功能**，增强C++未能提供的关于型别认证方面的能力。常用的有iterator_traits和type_traits。

**iterator_traits**

被称为**特性萃取机**，能够方面的让外界获取以下5中型别：

- value_type：迭代器所指对象的型别
- difference_type：两个迭代器之间的距离
- pointer：迭代器所指向的型别
- reference：迭代器所引用的型别
- iterator_category：三两句说不清楚，建议看书

**type_traits**

关注的是型别的**特性**，例如这个型别是否具备non-trivial defalt ctor（默认构造函数）、non-trivial copy ctor（拷贝构造函数）、non-trivial assignment operator（赋值运算符） 和non-trivial dtor（析构函数），如果答案是否定的，可以采取直接操作内存的方式提高效率，一般来说，type_traits支持以下5中类型的判断：

```c++
__type_traits<T>::has_trivial_default_constructor
__type_traits<T>::has_trivial_copy_constructor
__type_traits<T>::has_trivial_assignment_operator
__type_traits<T>::has_trivial_destructor
__type_traits<T>::is_POD_type
```

由于编译器只针对class object形式的参数进行参数推到，因此上式的返回结果不应该是个bool值，实际上使用的是一种空的结构体：

```C++
struct __true_type{};
struct __false_type{};
```

这两个结构体没有任何成员，不会带来其他的负担，又能满足需求，可谓一举两得

当然，如果我们自行定义了一个Shape类型，也可以针对这个Shape设计type_traits的特化版本

```C++
template<> struct __type_traits<Shape>{
	typedef __true_type has_trivial_default_constructor;
	typedef __false_type has_trivial_copy_constructor;
	typedef __false_type has_trivial_assignment_operator;
	typedef __false_type has_trivial_destructor;
	typedef __false_type is_POD_type;
};
```



#### 8、:dizzy:STL的两级空间配置器

1、首先明白为什么需要二级空间配置器？

我们知道动态开辟内存时，要在堆上申请，但若是我们需要

频繁的在堆开辟释放内存，则就会**在堆上造成很多外部碎片**，浪费了内存空间；

每次都要进行调用**malloc、free**函数等操作，使空间就会增加一些附加信息，降低了空间利用率；

随着外部碎片增多，内存分配器在找不到合适内存情况下需要合并空闲块，浪费了时间，大大降低了效率。

于是就设置了二级空间配置器，**当开辟内存<=128bytes时，即视为开辟小块内存，则调用二级空间配置器。**



关于STL中一级空间配置器和二级空间配置器的选择上，一般默认**选择的为二级空间配置器**。 如果大于128字节再转去一级配置器器。

##### 一级配置器

 **一级空间配置器**中重要的函数就是allocate、deallocate、reallocate 。 一级空间配置器是以malloc()，free()，realloc()等C函数执行实际的内存配置 。大致过程是：

1、直接allocate分配内存，其实就是malloc来分配内存，成功则直接返回，失败就调用处理函数

2、如果用户自定义了内存分配失败的处理函数就调用，没有的话就返回异常

3、如果自定义了处理函数就进行处理，完事再继续分配试试

![](https://cdn.jsdelivr.net/gh/forthespada/mediaImage2@2.6/202104/c++-189-1.png)

##### 二级配置器

![](https://cdn.jsdelivr.net/gh/forthespada/mediaImage2@2.6/202104/C++-189-2.png)

1、维护16条链表，分别是0-15号链表，最小8字节，以8字节逐渐递增，最大128字节，你传入一个字节参数，表示你需要多大的内存，会自动帮你校对到第几号链表（如需要13bytes空间，我们会给它分配16bytes大小），在找到第n个链表后查看链表是否为空，如果不为空直接从对应的free_list中拔出，将已经拨出的指针向后移动一位。

2、对应的free_list为空，先看其内存池是不是空时，如果内存池不为空：
（1）先检验它剩余空间是否够20个节点大小（即所需内存大小(提升后) * 20），若足够则直接从内存池中拿出20个节点大小空间，将其中一个分配给用户使用，另外19个当作自由链表中的区块挂在相应的free_list下，这样下次再有相同大小的内存需求时，可直接拨出。
（2）如果不够20个节点大小，则看它是否能满足1个节点大小，如果够的话则直接拿出一个分配给用户，然后从剩余的空间中分配尽可能多的节点挂在相应的free_list中。
（3）如果连一个节点内存都不能满足的话，则将内存池中剩余的空间挂在相应的free_list中（找到相应的free_list），然后再给内存池申请内存，转到3。
3、内存池为空，申请内存
此时二级空间配置器会使用malloc()从heap上申请内存，（一次所申请的内存大小为2 * 所需节点内存大小（提升后）* 20 + 一段额外空间），申请40块，一半拿来用，一半放内存池中。
4、malloc没有成功
在第三种情况下，如果malloc()失败了，说明heap上没有足够空间分配给我们了，这时，二级空间配置器会从比所需节点空间大的free_list中一一搜索，从比它所需节点空间大的free_list中拔除一个节点来使用。如果这也没找到，说明比其大的free_list中都没有自由区块了，那就要调用一级适配器了。



释放时调用deallocate()函数，若释放的n>128，则调用一级空间配置器，否则就直接将内存块挂上自由链表的合适位置。

STL二级空间配置器虽然解决了外部碎片与提高了效率，但它同时增加了一些缺点：

1.因为自由链表的管理问题，它会把我们需求的内存块自动提升为8的倍数，这时若你需要1个字节，它会给你8个字节，即浪费了7个字节，所以它又引入了内部碎片的问题，若相似情况出现很多次，就会造成很多内部碎片；

2.二级空间配置器是在堆上申请大块的狭义内存池，然后用自由链表管理，供现在使用，在程序执行过程中，它将申请的内存一块一块都挂在自由链表上，即不会还给操作系统，并且它的实现中所有成员全是静态的，所以它申请的所有内存只有在进程结束才会释放内存，还给操作系统，由此带来的问题有：1.即我不断的开辟小块内存，最后整个堆上的空间都被挂在自由链表上，若我想开辟大块内存就会失败；2.若自由链表上挂很多内存块没有被使用，当前进程又占着内存不释放，这时别的进程在堆上申请不到空间，也不可以使用当前进程的空闲内存，由此就会引发多种问题。



##### 一级分配器

GC4.9之后就没有第一级了，只有第二级

##### 二级分配器

——default_alloc_template 剖析

有个自动调整的函数：你传入一个字节参数，表示你需要多大的内存，会自动帮你校对到第几号链表（0-15号链表，最小8字节 最大128字节）



allocate函数：如果要分配的内存大于128字节，就转用第一级分配器，否则也就是小于128字节。那么首先判断落在第几号链表，定位到了，先判断链表是不是空，如果是空就需要充值，（调节到8的倍数，默认一次申请20个区块，当然了也要判断20个是不是能够申请到，如果只申请到一个那就直接返回好了，不止一个的话，把第2到第n个挨个挂到当前链表上，第一个返回回去给容器用,n是不大于20的，当然了如果不在1-20之间，那就是内存碎片了，那就先把碎片挂到某一条链表上，然后再重新malloc了，malloc  2*20个块）去内存池去拿或者重新分配。不为空的话



#### 9、vector与list的区别与应用？怎么找某vector或者list的倒数第二个元素 :fire:

**vector数据结构**

- vector和数组类似，拥有一段连续的内存空间，并且起始地址不变。因此能高效的进行随机存取，时间复杂度为O(1)；但因为内存空间是连续的，所以在进行插入和删除操作时，会造成内存块的拷贝，时间复杂度为O(n)。另外，当数组中内存空间不够时，会重新申请一块内存空间并进行内存拷贝。

- 连续存储结构：vector是可以实现**动态增长**的对象数组，支持对数组高效率的访问和在数组尾端的删除和插入操作，在中间和头部删除和插入相对不易，需要挪动大量的数据。它与数组最大的区别就是vector不需程序员自己去考虑容量问题，库里面本身已经实现了容量的动态增长，而数组需要程序员手动写入扩容函数进形扩容。

**list数据结构**

- list是由双向链表实现的，因此内存空间是不连续的。只能通过指针访问数据，所以list的随机存取非常没有效率，时间复杂度为o(n)；但由于链表的特点，能高效地进行插入和删除。

- 非连续存储结构：list是一个双链表结构，支持对链表的双向遍历。每个节点包括三个信息：元素本身，指向前一个元素的节点（prev）和指向下一个元素的节点（next）。因此list可以高效率的对数据元素任意位置进行访问和插入删除等操作。由于涉及对额外指针的维护，所以开销比较大。

**两者区别**

vector的随机访问效率高，但在插入和删除时（不包括尾部）需要挪动数据，不易操作。list的访问要遍历整个链表，它的随机访问效率低。但对数据的插入和删除操作等都比较方便，改变指针的指向即可。**vector中的迭代器在使用后就失效了，而list的迭代器在使用之后还可以继续使用。** 

**访问倒数第二个元素**

- vector：直接下标访问

- link：反向迭代器来遍历



#### 10、STL 中vector删除其中的元素，迭代器如何变化？为什么是两倍扩容？释放空间？

size() 函数返回的是已用空间大小，capacity() 返回的是总空间大小，capacity()-size() 则是剩余的可用空间大小。当 size() 和 capacity() 相等，说明 vector 目前的空间已被用完，如果再添加新元素，则会引起 vector 空间的动态增长。

由于动态增长会引起重新分配内存空间、拷贝原空间、释放原空间，这些过程会降低程序效率。因此可以使用`reserve(n)`预先分配一块较大的指定大小的内存空间，这样当指定大小的内存空间未使用完时，是不会重新分配内存空间的，这样便提升了效率。只有当`n>capacity()`时，调用`reserve(n)`才会改变 vector容量。`resize()`成员函数只改变元素的数目，不改变 vector 的容量。

- 空的 vector 对象，size() 和 capacity() 都为 0
- 当空间大小不足时，新分配的空间大小为原空间大小的2倍
- 使用 reserve() 预先分配一块内存后，在空间未满的情况下，不会引起重新分配，从而提升了效率
- 当 reserve() 分配的空间比原空间小时，是不会引起重新分配的
- resize()函数只改变容器的元素数目，未改变容器大小
- 用`reserve(size_type)`只是扩大capacity值，这些内存空间可能还是“野”的，如果此时使用`[]`来访问，则可能会越界。而`resize(size_type new_size)`会真正使容器具有new_size个对象

不同的编译器，vector有不同的扩容大小。在 VS 下是1.5倍，在 GCC 下是2倍；空间和时间的权衡。简单来说， 空间分配的多，平摊时间复杂度低，但浪费空间也多

使用k=2增长因子的问题在于，每次扩展的新尺寸必然刚好大于之前分配的总和，也就是说，之前分配的内存空间不可能被使用。这样对内存不友好。最好把增长因子设为(1, 2)

对比可以发现采用成倍方式扩容，可以保证常数的时间复杂度，而增加指定大小的容量只能达到O(n)的时间复杂度，因此，使用成倍的方式扩容。

 

#### 11、vector如何释放空间？

由于vector的内存占用空间只增不减，比如你首先分配了10,000个字节，然后erase掉后面9,999个，留下一个有效元素，但是内存占用仍为10,000个。所有内存空间是在vector析构时候才能被系统回收。empty()用来检测容器是否为空的，clear()可以清空所有元素。但是**即使clear()，vector所占用的内存空间依然如故，无法保证内存的回收**。

如果需要空间动态缩小，可以考虑使用deque。如果vector，可以用swap()来帮助你释放内存。

~~~cpp
vector<int>(vec).swap(vec);	// 将 vec 中多余内存清除
vector<int>().swap(vec);	// 清空 vec 的全部内存
~~~



#### 12、容器内部删除一个元素

**顺序容器**（序列式容器，比如vector、deque）

erase迭代器不仅使所指向被删除的迭代器失效，而且使被删元素之后的所有迭代器失效(list除外)，所以不能使用erase(it++)的方式，但是erase的返回值是下一个有效迭代器；

it = c.erase(it);

**关联容器**（关联式容器，比如map、set、multimap、multiset等）

erase迭代器只是被删除元素的迭代器失效，但是返回值是void，所以要采用erase(it++)的方式删除迭代器；

c.erase(it++)



#### 13、STL迭代器如何实现

1. 迭代器是一种抽象的设计理念，通过迭代器可以在不了解容器内部原理的情况下遍历容器，除此之外，STL中迭代器一个最重要的作用就是作为容器与STL算法的粘合剂。
2. 迭代器的作用就是提供一个遍历容器内部所有元素的接口，因此迭代器内部必须保存一个与容器相关联的指针，然后重载各种运算操作来遍历，其中最重要的是`*`运算符与`->`运算符，以及`++`、`--`等可能需要重载的运算符重载。这和C++中的智能指针很像，**智能指针也是将一个指针封装，然后通过引用计数或是其他方法完成自动释放内存的功能。**
3. 最常用的迭代器的相应型别有五种：value type、difference type、pointer、reference、iterator catagoly;



#### 14、map, set是怎么实现的，红黑树是怎么能够同时实现这两种容器？ 为什么使用红黑树？

1)  他们的底层都是以红黑树的结构实现，因此插入删除等操作都在O(logn)时间内完成，因此可以完成高效的插入删除；

2)  在这里我们定义了一个模版参数，如果它是key那么它就是set，如果它是map，那么它就是map；底层是红黑树，实现map的红黑树的节点数据类型是key+value，而实现set的节点数据类型是value

3)  因为map和set要求是**自动排序**的，红黑树能够实现这一功能，而且时间复杂度比较低。

> 红黑树参考：[30张图带你彻底理解红黑树 - 简书 (jianshu.com)](https://www.jianshu.com/p/e136ec79235c)



#### 15、如何在共享内存上使用STL标准库？

1. 想像一下把STL容器，例如map, vector, list等等，放入共享内存中，IPC一旦有了这些强大的通用数据结构做辅助，无疑进程间通信的能力一下子强大了很多。

   我们没必要再为共享内存设计其他额外的数据结构，另外STL的高度可扩展性将为IPC所驱使。STL容器被良好的封装，默认情况下有它们自己的内存管理方案。

   当一个元素被插入到一个STL列表(list)中时，列表容器自动为其分配内存，保存数据。考虑到要将STL容器放到共享内存中，而容器却自己在**堆**上分配内存。

   一个最笨拙的办法是在堆上构造STL容器，然后把容器复制到共享内存，并且确保所有容器的内部分配的内存指向共享内存中的相应区域，这基本是个不可能完成的任务。

2. 假设进程A在共享内存中放入了数个容器，进程B如何找到这些容器呢？

   一个方法就是进程A**把容器放在共享内存中的确定地址上**（fixed offsets），则进程B可以从该已知地址上获取容器。另外一个改进点的办法是，进程A先在共享内存某块确定地址上放置一个map容器，然后进程A再创建其他容器，然后给其取个名字和地址一并保存到这个map容器里。进程B知道如何获取保存了地址映射的map容器，然后同样再根据名字取得其他容器的地址。



#### 16、map插入方式有哪几种？

~~~cpp
// 用insert函数插入pair数据，
mapStudent.insert(pair<int, string>(1, "student_one")); 

// 用insert函数插入value_type数据
mapStudent.insert(map<int, string>::value_type(1, "student_one"));

// 在insert函数中使用make_pair()函数
mapStudent.insert(make_pair(1, "student_one")); 

// 用数组方式插入数据
mapStudent[1] = "student_one"; 
~~~



#### 17、STL中 unordered_map 和 map 的区别，hash_map 如何解决冲突以及扩容

1)  unordered_map和map类似，都是存储的key-value的值，可以通过key快速索引到value。不同的是unordered_map不会根据key的大小进行**排序**
2)  存储时是根据key的hash值判断元素是否相同，即unordered_map内部元素是无序的，而map中的元素是按照二叉搜索树存储，进行中序遍历会得到有序遍历
3)  所以使用时map的key需要定义`operator<`。而unordered_map需要定义**hash_value函数**并且重载`operator==`。但是很多系统内置的数据类型都自带这些，那么如果是自定义类型，那么就需要自己重载`operator<`或者hash_value函数
4)  unordered_map (hash_map) 的底层实现是 hash_table，而hash_table 使用的**开链法**进行冲突避免
5)  **什么时候扩容**：当向容器添加元素的时候，会判断当前容器的元素个数，如果大于等于阈值——即当前数组的长度乘以加载因子的值的时候，就要自动扩容啦
6)  **扩容(resize)** 就是重新计算容量，向 hash_map 对象里不停的添加元素，而 hash_map 对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素



#### 18、vector越界访问下标，map越界访问下标？vector删除元素时会不会释放空间？

1)  通过下标访问vector中的元素时会做边界检查，但该处的实现方式要看具体IDE，不同IDE的实现方式不一样，确保不可访问越界地址。
2)  map的下标运算符`[]`的作用是：将key作为下标去执行查找，并返回相应的值；如果不存在这个key，就将一个具有该key和value的默认值（一般来说整数为“0“，字符和字符串为”空“）插入这个map。
3)  vector 删除元素不能改变容量大小：
    - erase成员函数，它删除了 `itVect` 迭代器指向的元素，并且返回要被删除的 `itVect`之后的迭代器，迭代器相当于一个智能指针；
    - clear成员函数，只能清空内容，不能改变容量大小；如果要想在删除内容的同时释放内存，那么你可以选择deque容器。



#### 19、map中 [] 与 find 的区别？

1) map的下标运算符[]的作用是：将关键码作为下标去执行查找，并返回对应的值；**如果不存在这个关键码，就将一个具有该关键码和值类型的默认值的项插入这个map**。

2) map的find函数：用关键码执行查找，找到了返回该位置的迭代器；如果不存在这个关键码，就返回尾迭代器。



#### 20、 STL中 list 与 queue 之间的区别

1) list不再能够像vector一样以普通指针作为迭代器，因为其**节点不保证在存储空间中连续存在**；

2) list插入操作和结合才做都不会造成原有的list迭代器失效;

3) list不仅是一个双向链表，而且还是一个环状双向链表，所以它只需要一个指针；

4) list不像vector那样有可能在空间不足时做重新配置、数据移动的操作，所以插入前的所有迭代器在插入操作之后都仍然有效；

5) deque是一种**双向开口的连续线性空间**，所谓双向开口，意思是可以在头尾两端分别做元素的插入和删除操作；可以在头尾两端分别做元素的插入和删除操作；

6) deque和vector最大的差异，一在于deque允许常数时间内对起头端进行元素的插入或移除操作，二在于deque没有所谓容量概念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来，deque没有所谓的空间保留功能。



### STL 模板库-21-40

> <a id="new4">完整例子以及解读</a>参考：https://interviewguide.cn/notes/03-hunting_job/02-interview/01-04-02-STL.html



#### 21、:dizzy:STL中的 allocator, deallocator

1) 第一级配置器直接使用malloc()、free()和relloc()，第二级配置器视情况采用不同的策略：当配置区块超过128bytes时，视之为足够大，便调用第一级配置器；当配置器区块小于128bytes时，为了降低额外负担，使用复杂的内存池整理方式，而不再用一级配置器；

2) 第二级配置器主动将任何小额区块的内存需求量上调至8的倍数，并维护16个free-list，各自管理大小为8~128bytes的小额区块；

3) 空间配置函数allocate()，首先判断区块大小，大于128就直接调用第一级配置器，小于128时就检查对应的free-list。如果free-list之内有可用区块，就直接拿来用，如果没有可用区块，就将区块大小调整至8的倍数，然后调用refill()，为free-list重新分配空间；

4) 空间释放函数deallocate()，该函数首先判断区块大小，大于128bytes时，直接调用一级配置器，小于128bytes就找到对应的free-list然后释放内存。



#### 22、STL中hash_map扩容发生什么？ 

1)   hash table表格内的元素称为桶（bucket)，而由桶所链接的元素称为节点（node)，其中存入桶元素的容器为 STL 本身很重要的一种序列式容器—**vector容器**。之所以选择vector为存放桶元素的基础容器，主要是因为vector容器本身具有动态扩容能力，无需人工干预。

2)   向前操作：首先尝试从目前所指的节点出发，前进一个位置（节点），由于节点被安置于list内，所以利用节点的next指针即可轻易完成前进操作，如果目前正巧是list的尾端，就跳至下一个bucket身上，那正是指向下一个list的头部节点。



#### 23、常见容器性质总结？

1. vector：底层数据结构为**数组** ，支持快速随机访问

2. list：底层数据结构为**双向链表**，支持快速增删

3. deque：底层数据结构为**一个中央控制器和多个缓冲区**，详细见STL源码剖析P146，支持首尾（中间不能）快速增删，也支持随机访问，deque是一个双端队列(double-ended queue)，也是在堆中保存内容的。它的保存形式：`[堆1] --> [堆2] -->[堆3] --> ...` 每个堆保存好几个元素,然后堆和堆之间有指针指向，看起来像是list和vector的结合品。

4. stack：底层一般用 list 或 deque 实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时

5. queue：底层一般用 list 或 deque 实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时

   > stack和queue其实是适配器，而不叫容器，因为是对容器的再封装）

6. priority_queue：底层数据结构一般为 vector 为底层容器，堆 heap 为处理规则来管理底层容器实现

7. set：底层数据结构为**红黑树**，有序，不重复

8. multiset：底层数据结构为**红黑树**，有序，可重复 

9. map：底层数据结构为**红黑树**，有序，不重复

10. multimap：底层数据结构为**红黑树**，有序，可重复

11. unordered_set：底层数据结构为**hash表**，无序，不重复

12. unordered_multiset 底层数据结构为**hash表**，无序，可重复 

13. unordered_map   底层数据结构为**hash表**，无序，不重复

14. unordered_multimap 底层数据结构为**hash表**，无序，可重复 

 

#### 24、vector的增加删除都是怎么做的？为什么是1.5或者是2倍？

1)  新增元素：vector通过一个连续的数组存放元素，如果集合已满，在新增数据的时候，就要分配一块更大的内存，将原来的数据复制过来，释放之前的内存，在插入新增的元素；

2)  对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就都失效了 ；

3)  初始时刻vector的capacity为0，塞入第一个元素后capacity增加为1；

4)  不同的编译器实现的扩容方式不一样，VS2015中以1.5倍扩容，GCC以2倍扩容。

对比可以发现采用采用成倍方式扩容，可以保证**常数的时间复杂度**，而增加指定大小的容量只能达到O(n)的时间复杂度，因此使用成倍的方式扩容。

1. 考虑可能产生的堆空间浪费，成倍增长倍数不能太大，使用较为广泛的扩容方式有两种，以2二倍的方式扩容，或者以1.5倍的方式扩容

2. 以2倍的方式扩容，导致下一次申请的内存必然大于之前分配内存的总和，导致之前分配的内存不能再被使用，所以最好倍增长因子设置为(1,2)之间： 

3. 向量容器 vector 的成员函数 **pop_back()** 可以删除最后一个元素；而函数 **erase()** 可以删除由一个 iterator 指出的元素，也可以删除一个指定范围的元素；还可以采用通用算法 **remove()** 来删除vector容器中的元素

   不同的是：采用 remove 一般情况下不会改变容器的大小，而 pop_back() 与erase() 等成员函数会改变容器的大小



#### 25、说一下STL每种容器对应的迭代器

| 容器                                   | 迭代器         |
| -------------------------------------- | -------------- |
| vector、deque                          | 随机访问迭代器 |
| stack、queue、priority_queue           | 无             |
| list、(multi)set/map                   | 双向迭代器     |
| unordered_(multi)set/map、forward_list | 前向迭代器     |



#### 26、:dizzy:STL中迭代器失效的情况有哪些？

> 具体参看：[原文链接](#new4)



#### 27、:dizzy:STL中vector的实现

vector是一种序列式容器，其数据安排以及操作方式与array非常类似，两者的唯一差别就是对于空间运用的灵活性，众所周知，array占用的是静态空间，一旦配置了就不可以改变大小，如果遇到空间不足的情况还要自行创建更大的空间，并手动将数据拷贝到新的空间中，再把原来的空间释放。vector则使用灵活的动态空间配置，维护一块**连续的线性空间**，在空间不足时，可以自动扩展空间容纳新元素，做到按需供给。其在扩充空间的过程中仍然需要经历：**重新配置空间，移动数据，释放原空间**等操作。这里需要说明一下动态扩容的规则：以原大小的两倍配置另外一块较大的空间（或者旧长度+新增元素的个数），源码：

```C++
const size_type len  = old_size + max(old_size, n);
```

 Vector扩容倍数与平台有关，在Win +  VS 下是 1.5倍，在 Linux + GCC 下是 2 倍 ，测试代码：

```C++
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    //在Linux + GCC下
	vector<int> res(2,0);
	cout << res.capacity() <<endl; //2
	res.push_back(1);
	cout << res.capacity() <<endl;//4
	res.push_back(2);
	res.push_back(3);
    cout << res.capacity() <<endl;//8
	return 0;
    
    
    //在 win 10 + VS2019下
    vector<int> res(2,0);
	cout << res.capacity() <<endl; //2
	res.push_back(1);
	cout << res.capacity() <<endl;//3
	res.push_back(2);
	res.push_back(3);
    cout << res.capacity() <<endl;//6
     
}
```

运行上述代码，一开始配置了一块长度为2的空间，接下来插入一个数据，长度变为原来的两倍，为4，此时已占用的长度为3，再继续两个数据，此时长度变为8，可以清晰的看到空间的变化过程

需要注意的是，频繁对vector调用push_back()对性能是有影响的，这是因为每插入一个元素，如果空间够用的话还能直接插入，若空间不够用，则需要重新配置空间，移动数据，释放原空间等操作，对程序性能会造成一定的影响



#### 28、:dizzy:STL中slist的实现

list是双向链表，而slist（single linked list）是单向链表，它们的主要区别在于：前者的迭代器是双向的Bidirectional iterator，后者的迭代器属于单向的Forward iterator。虽然slist的很多功能不如list灵活，但是其所耗用的空间更小，操作更快。

根据STL的习惯，插入操作会将新元素插入到指定位置之前，而非之后，然而slist是不能回头的，只能往后走，因此在slist的其他位置插入或者移除元素是十分不明智的，但是在slist开头却是可取的，slist特别提供了insert_after()和erase_after供灵活应用。考虑到效率问题，slist只提供push_front()操作，元素插入到slist后，存储的次序和输入的次序是相反的

slist的单向迭代器如下图所示：

![](https://cdn.jsdelivr.net/gh/forthespada/mediaImage1@1.6.4.2/202102/1566227016872.png)

slist默认采用alloc空间配置器配置节点的空间，其数据结构主要代码如下

```C++
template <class T, class Allco = alloc>
class slist
{
	...
private:
    ...
    static list_node* create_node(const value_type& x){}//配置空间、构造元素
    static void destroy_node(list_node* node){}//析构函数、释放空间
private:
    list_node_base head; //头部
public:
    iterator begin(){}
    iterator end(){}
    size_type size(){}
    bool empty(){}
    void swap(slist& L){}//交换两个slist，只需要换head即可
    reference front(){} //取头部元素
    void push_front(const value& x){}//头部插入元素
    void pop_front(){}//从头部取走元素
    ...
}
```

举个例子：

```C++
#include <forward_list>
#include <algorithm>
#include <iostream>
using namespace std;

int main()
{
	forward_list<int> fl;
	fl.push_front(1);
	fl.push_front(3);
	fl.push_front(2);
	fl.push_front(6);
	fl.push_front(5);

	forward_list<int>::iterator ite1 = fl.begin();
	forward_list<int>::iterator ite2 = fl.end();
	for(;ite1 != ite2; ++ite1)
	{
		cout << *ite1 <<" "; // 5 6 2 3 1
	}
	cout << endl;

	ite1 = find(fl.begin(), fl.end(), 2); //寻找2的位置

	if (ite1 != ite2)
		fl.insert_after(ite1, 99);
	for (auto it : fl)
	{
		cout << it << " ";  //5 6 2 99 3 1
	}
	cout << endl;

	ite1 = find(fl.begin(), fl.end(), 6); //寻找6的位置
	if (ite1 != ite2)
		fl.erase_after(ite1);
	for (auto it : fl)
	{
		cout << it << " ";  //5 6 99 3 1
	}
	cout << endl;	
	return 0;
}
```

需要注意的是C++标准委员会没有采用slist的名称，forward_list在C++ 11中出现，它与slist的区别是没有size()方法。



#### 29、:dizzy:STL中list的实现

相比于vector的连续线型空间，list显得复杂许多，但是它的好处在于插入或删除都只作用于一个元素空间，因此list对空间的运用是十分精准的，对任何位置元素的插入和删除都是常数时间。list不能保证节点在存储空间中连续存储，也拥有迭代器，迭代器的“++”、“--”操作对于的是指针的操作，list提供的迭代器类型是双向迭代器：Bidirectional iterators。

list节点的结构见如下源码：

```C++
template <class T>
struct __list_node{
    typedef void* void_pointer;
    void_pointer prev;
    void_pointer next;
    T data;
}
```

从源码可看出list显然是一个双向链表。list与vector的另一个区别是，在插入和接合操作之后，都不会造成原迭代器失效，而vector可能因为空间重新配置导致迭代器失效。

此外list也是一个环形链表，因此只要一个指针便能完整表现整个链表。list中node节点指针始终指向尾端的一个空白节点，因此是一种“前闭后开”的区间结构

list的空间管理默认采用alloc作为空间配置器，为了方便的以节点大小为配置单位，还定义一个list_node_allocator函数可一次性配置多个节点空间

由于list的双向特性，其支持在头部（front)和尾部（back)两个方向进行push和pop操作，当然还支持erase，splice，sort，merge，reverse，sort等操作，这里不再详细阐述。



#### 30、:dizzy:STL中的deque的实现

vector是单向开口（尾部）的连续线性空间，deque则是一种双向开口的连续线性空间，虽然vector也可以在头尾进行元素操作，但是其头部操作的效率十分低下（主要是涉及到整体的移动）

![](https://cdn.jsdelivr.net/gh/forthespada/mediaImage1@1.6.4.2/202102/1565876257552.png)

deque和vector的最大差异一个是deque运行在常数时间内对头端进行元素操作，二是deque没有容量的概念，它是动态地以分段连续空间组合而成，可以随时增加一段新的空间并链接起来

deque虽然也提供随机访问的迭代器，但是其迭代器并不是普通的指针，其复杂程度比vector高很多，因此除非必要，否则一般使用vector而非deque。如果需要对deque排序，可以先将deque中的元素复制到vector中，利用sort对vector排序，再将结果复制回deque

deque由一段一段的定量连续空间组成，一旦需要增加新的空间，只要配置一段定量连续空间拼接在头部或尾部即可，因此deque的最大任务是如何维护这个整体的连续性

deque的数据结构如下：

```C++
class deque
{
    ...
protected:
    typedef pointer* map_pointer;//指向map指针的指针
    map_pointer map;//指向map
    size_type map_size;//map的大小
public:
    ...
    iterator begin();
    itertator end();
    ...
}
```

![](https://cdn.jsdelivr.net/gh/forthespada/mediaImage1@1.6.4.2/202102/1565876324016.png)

deque内部有一个指针指向map，map是一小块连续空间，其中的每个元素称为一个节点，node，每个node都是一个指针，指向另一段较大的连续空间，称为缓冲区，这里就是deque中实际存放数据的区域，默认大小512bytes。整体结构如上图所示。

deque的迭代器数据结构如下：

```C++
struct __deque_iterator
{
    ...
    T* cur;//迭代器所指缓冲区当前的元素
    T* first;//迭代器所指缓冲区第一个元素
    T* last;//迭代器所指缓冲区最后一个元素
    map_pointer node;//指向map中的node
    ...
}
```

从deque的迭代器数据结构可以看出，为了保持与容器联结，迭代器主要包含上述4个元素

![](https://cdn.jsdelivr.net/gh/forthespada/mediaImage1@1.6.4.2/202102/1565877658970.png)

deque迭代器的“++”、“--”操作是远比vector迭代器繁琐，其主要工作在于缓冲区边界，如何从当前缓冲区跳到另一个缓冲区，当然deque内部在插入元素时，如果map中node数量全部使用完，且node指向的缓冲区也没有多余的空间，这时会配置新的map（2倍于当前+2的数量）来容纳更多的node，也就是可以指向更多的缓冲区。在deque删除元素时，也提供了元素的析构和空闲缓冲区空间的释放等机制。



#### 31、:dizzy:STL中stack和queue的实现

**stack**

stack（栈）是一种先进后出（First In Last Out）的数据结构，只有一个入口和出口，那就是栈顶，除了获取栈顶元素外，没有其他方法可以获取到内部的其他元素，其结构图如下：

![](https://cdn.jsdelivr.net/gh/forthespada/mediaImage1@1.6.4.2/202102/1565957994483.png)

stack这种单向开口的数据结构很容易由**双向开口的deque和list**形成，只需要根据stack的性质对应移除某些接口即可实现，stack的源码如下：

```C++
template <class T, class Sequence = deque<T> >
class stack
{
	...
protected:
    Sequence c;
public:
    bool empty(){return c.empty();}
    size_type size() const{return c.size();}
    reference top() const {return c.back();}
    const_reference top() const{return c.back();}
    void push(const value_type& x){c.push_back(x);}
    void pop(){c.pop_back();}
};
```

从stack的数据结构可以看出，其所有操作都是围绕Sequence完成，而Sequence默认是deque数据结构。stack这种“修改某种接口，形成另一种风貌”的行为，成为adapter(配接器)。常将其归类为container adapter而非container

stack除了默认使用deque作为其底层容器之外，也可以使用双向开口的list，只需要在初始化stack时，将list作为第二个参数即可。由于stack只能操作顶端的元素，因此其内部元素无法被访问，也不提供迭代器。

**queue**

queue（队列）是一种先进先出（First In First Out）的数据结构，只有一个入口和一个出口，分别位于最底端和最顶端，出口元素外，没有其他方法可以获取到内部的其他元素，其结构图如下：

![](https://cdn.jsdelivr.net/gh/forthespada/mediaImage1@1.6.4.2/202102/1565958318457.png)

类似的，queue这种“先进先出”的数据结构很容易由双向开口的deque和list形成，只需要根据queue的性质对应移除某些接口即可实现，queue的源码如下：

```C++
template <class T, class Sequence = deque<T> >
class queue
{
	...
protected:
    Sequence c;
public:
    bool empty(){return c.empty();}
    size_type size() const{return c.size();}
    reference front() const {return c.front();}
    const_reference front() const{return c.front();}
    void push(const value_type& x){c.push_back(x);}
    void pop(){c.pop_front();}
};
```

从queue的数据结构可以看出，其所有操作都也都是是围绕Sequence完成，Sequence默认也是deque数据结构。queue也是一类container adapter。

同样，queue也可以使用list作为底层容器，不具有遍历功能，没有迭代器。



#### 32、:dizzy:STL中的heap的实现

heap（堆）并不是STL的容器组件，是priority queue（优先队列）的底层实现机制，因为binary max heap（大根堆）总是最大值位于堆的根部，优先级最高。

binary heap本质是一种complete binary tree（完全二叉树），整棵binary tree除了最底层的叶节点之外，都是填满的，但是叶节点从左到右不会出现空隙，如下图所示就是一颗完全二叉树

![](https://cdn.jsdelivr.net/gh/forthespada/mediaImage1@1.6.4.2/202102/1566039990260.png)

完全二叉树内没有任何节点漏洞，是非常紧凑的，这样的一个好处是可以使用array来存储所有的节点，因为当其中某个节点位于$i$处，其左节点必定位于$2i$处，右节点位于$2i+1$处，父节点位于$i/2$（向下取整）处。这种以array表示tree的方式称为隐式表述法。

因此我们可以使用一个array和一组heap算法来实现max heap（每个节点的值大于等于其子节点的值）和min heap（每个节点的值小于等于其子节点的值）。由于array不能动态的改变空间大小，用vector代替array是一个不错的选择。

那heap算法有哪些？常见有的插入、弹出、排序和构造算法，下面一一进行描述。

**push_heap插入算法**

由于完全二叉树的性质，新插入的元素一定是位于树的最底层作为叶子节点，并填补由左至右的第一个空格。事实上，在刚执行插入操作时，新元素位于底层vector的end()处，之后是一个称为percolate up（上溯）的过程，举个例子如下图：

![](https://cdn.jsdelivr.net/gh/forthespada/mediaImage1@1.6.4.2/202102/1566040870063.png)

新元素50在插入堆中后，先放在vector的end()存着，之后执行上溯过程，调整其根结点的位置，以便满足max heap的性质，如果了解大根堆的话，这个原理跟大根堆的调整过程是一样的。

**pop_heap算法**

heap的pop操作实际弹出的是根节点吗，但在heap内部执行pop_heap时，只是将其移动到vector的最后位置，然后再为这个被挤走的元素找到一个合适的安放位置，使整颗树满足完全二叉树的条件。这个被挤掉的元素首先会与根结点的两个子节点比较，并与较大的子节点更换位置，如此一直往下，直到这个被挤掉的元素大于左右两个子节点，或者下放到叶节点为止，这个过程称为percolate down（下溯）。举个例子：

![](https://cdn.jsdelivr.net/gh/forthespada/mediaImage1@1.6.4.2/202102//1566041421056.png)

根节点68被pop之后，移到了vector的最底部，将24挤出，24被迫从根节点开始与其子节点进行比较，直到找到合适的位置安身，需要注意的是pop之后元素并没有被移走，如果要将其移走，可以使用pop_back()。

**sort算法**

一言以蔽之，因为pop_heap可以将当前heap中的最大值置于底层容器vector的末尾，heap范围减1，那么不断的执行pop_heap直到树为空，即可得到一个递增序列。

**make_heap算法**

将一段数据转化为heap，一个一个数据插入，调用上面说的两种percolate算法即可。

代码实测：

```C++
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	vector<int> v = { 0,1,2,3,4,5,6 };
	make_heap(v.begin(), v.end()); //以vector为底层容器
	for (auto i : v)
	{
		cout << i << " "; // 6 4 5 3 1 0 2
	}
	cout << endl;
	v.push_back(7);
	push_heap(v.begin(), v.end());
	for (auto i : v)
	{
		cout << i << " "; // 7 6 5 4 1 0 2 3
	}
	cout << endl;
	pop_heap(v.begin(), v.end());
	cout << v.back() << endl; // 7 
	v.pop_back();
	for (auto i : v)
	{
		cout << i << " "; // 6 4 5 3 1 0 2
	}
	cout << endl;
	sort_heap(v.begin(), v.end());
	for (auto i : v)
	{
		cout << i << " "; // 0 1 2 3 4 5 6
	}
	return 0;
}
```



#### 33、:dizzy:STL中的priority_queue的实现

priority_queue，优先队列，是一个拥有权值观念的queue，它跟queue一样是顶部入口，底部出口，在插入元素时，元素并非按照插入次序排列，它会自动根据权值（通常是元素的实值）排列，权值最高，排在最前面，如下图所示。

![](https://cdn.jsdelivr.net/gh/forthespada/mediaImage1@1.6.4.2/202102/1566126001158.png)

默认情况下，priority_queue使用一个max-heap完成，底层容器使用的是一般为vector为底层容器，堆heap为处理规则来管理底层容器实现 。priority_queue的这种实现机制导致其不被归为容器，而是一种容器配接器。关键的源码如下：

```C++
template <class T, class Squence = vector<T>, 
class Compare = less<typename Sequence::value_tyoe> >
class priority_queue{
	...
protected:
    Sequence c; // 底层容器
    Compare comp; // 元素大小比较标准
public:
    bool empty() const {return c.empty();}
    size_type size() const {return c.size();}
    const_reference top() const {return c.front()}
    void push(const value_type& x)
    {
        c.push_heap(x);
        push_heap(c.begin(), c.end(),comp);
    }
    void pop()
    {
        pop_heap(c.begin(), c.end(),comp);
        c.pop_back();
    }
};
```

priority_queue的所有元素，进出都有一定的规则，只有queue顶端的元素（权值最高者），才有机会被外界取用，它没有遍历功能，也不提供迭代器

举个例子：

```C++
#include <queue>
#include <iostream>
using namespace std;

int main()
{
	int ia[9] = {0,4,1,2,3,6,5,8,7 };
	priority_queue<int> pq(ia, ia + 9);
	cout << pq.size() <<endl;  // 9
	for(int i = 0; i < pq.size(); i++)
	{
		cout << pq.top() << " "; // 8 8 8 8 8 8 8 8 8
	}
	cout << endl;
	while (!pq.empty())
	{
		cout << pq.top() << ' ';// 8 7 6 5 4 3 2 1 0
		pq.pop();
	}
	return 0;
}
```



#### 34、:dizzy:STL中set的实现？

STL中的容器可分为序列式容器（sequence）和关联式容器（associative），set属于关联式容器。

set的特性是，所有元素都会根据元素的值自动被排序（默认升序），set元素的键值就是实值，实值就是键值，set不允许有两个相同的键值

set不允许迭代器修改元素的值，其迭代器是一种constance iterators

标准的STL set以RB-tree（红黑树）作为底层机制，几乎所有的set操作行为都是转调用RB-tree的操作行为，这里补充一下红黑树的特性：

- 每个节点不是红色就是黑色
- 根结点为黑色
- 如果节点为红色，其子节点必为黑
- 任一节点至（NULL）树尾端的任何路径，所含的黑节点数量必相同

关于红黑树的具体操作过程，比较复杂读者可以翻阅《算法导论》详细了解。

举个例子：

```C++
#include <set>
#include <iostream>
using namespace std;


int main()
{
	int i;
	int ia[5] = { 1,2,3,4,5 };
	set<int> s(ia, ia + 5);
	cout << s.size() << endl; // 5
	cout << s.count(3) << endl; // 1
	cout << s.count(10) << endl; // 0

	s.insert(3); //再插入一个3
	cout << s.size() << endl; // 5
	cout << s.count(3) << endl; // 1

	s.erase(1);
	cout << s.size() << endl; // 4

	set<int>::iterator b = s.begin();
	set<int>::iterator e = s.end();
	for (; b != e; ++b)
		cout << *b << " "; // 2 3 4 5
	cout << endl;

	b = find(s.begin(), s.end(), 5);
	if (b != s.end())
		cout << "5 found" << endl; // 5 found

	b = s.find(2);
	if (b != s.end())
		cout << "2 found" << endl; // 2 found

	b = s.find(1);
	if (b == s.end())
		cout << "1 not found" << endl; // 1 not found
	return 0;
}
```

关联式容器尽量使用其自身提供的find()函数查找指定的元素，效率更高，因为STL提供的find()函数是一种顺序搜索算法。 



#### 35、:dizzy:STL中map的实现

map的特性是所有元素会根据键值进行自动排序。map中所有的元素都是pair，拥有键值(key)和实值(value)两个部分，并且不允许元素有相同的key

一旦map的key确定了，那么是无法修改的，但是可以修改这个key对应的value，因此map的迭代器既不是constant iterator，也不是mutable iterator

标准STL map的底层机制是RB-tree（红黑树），另一种以hash table为底层机制实现的称为hash_map。map的架构如下图所示

![](https://cdn.jsdelivr.net/gh/forthespada/mediaImage1@1.6.4.2/202102/1566380621064.png)

map的在构造时缺省采用递增排序key，也使用alloc配置器配置空间大小，需要注意的是在插入元素时，调用的是红黑树中的insert_unique()方法，而非insert_euqal()（multimap使用）

举个例子：

```C++
#include <map>
#include <iostream>
#include <string>
using namespace std;

int main()
{
	map<string, int> maps;
    //插入若干元素
	maps["jack"] = 1;
	maps["jane"] = 2;
	maps["july"] = 3;
	//以pair形式插入
	pair<string, int> p("david", 4);
	maps.insert(p);
	//迭代输出元素
	map<string, int>::iterator iter = maps.begin();
	for (; iter != maps.end(); ++iter)
	{
		cout << iter->first << " ";
		cout << iter->second << "--"; //david 4--jack 1--jane 2--july 3--
	}
	cout << endl;
	//使用subscipt操作取实值
	int num = maps["july"];
	cout << num << endl; // 3
	//查找某key
	iter = maps.find("jane");
	if(iter != maps.end())
		cout << iter->second << endl; // 2
    //修改实值
	iter->second = 100;
	int num2 = maps["jane"]; // 100
	cout << num2 << endl;
	
	return 0;
}
```

需要注意的是subscript（下标）操作既可以作为左值运用（修改内容）也可以作为右值运用（获取实值）。例如：

```C++
maps["abc"] = 1; //左值运用
int num = masp["abd"]; //右值运用
```

无论如何，subscript操作符都会先根据键值找出实值，源码如下：

```C++
...
T& operator[](const key_type& k)
{
	return (*((insert(value_type(k, T()))).first)).second;
}
...
```

代码运行过程是：首先根据键值和实值做出一个元素，这个元素的实值未知，因此产生一个与实值型别相同的临时对象替代：

```C++
value_type(k, T());
```

再将这个对象插入到map中，并返回一个pair：

```C++
pair<iterator,bool> insert(value_type(k, T()));
```

pair第一个元素是迭代器，指向当前插入的新元素，如果插入成功返回true，此时对应左值运用，根据键值插入实值。插入失败（重复插入）返回false，此时返回的是已经存在的元素，则可以取到它的实值

```C++
(insert(value_type(k, T()))).first; //迭代器
*((insert(value_type(k, T()))).first); //解引用
(*((insert(value_type(k, T()))).first)).second; //取出实值
```

由于这个实值是以引用方式传递，因此作为左值或者右值都可以



#### 36、set和map的区别，multimap和multiset的区别

set只提供一种数据类型的接口，但是会将这一个元素分配到key和value上，而且它的 compare_function 用的是 `identity()` 函数，这个函数是输入什么输出什么，这样就实现了set机制，**set的key和value其实是一样的了**。其实他保存的是两份元素，而不是只保存一份元素

map则提供两种数据类型的接口，分别放在key和value的位置上，他的比较function采用的是红黑树的 compare_function，保存的确实是两份元素。

> set 和 map 的insert都是采用红黑树的 insert_unique() 独一无二的插入

multimap 和 map 的唯一区别就是：`multimap`调用的是红黑树的`insert_equal()`，可以重复插入而`map`调用的则是独一无二的插入`insert_unique()`，multiset 和 set也一样，底层实现都是一样的，只是在插入的时候调用的方法不一样。

**红黑树概念** [参考](https://www.jianshu.com/p/e136ec79235c)

面试时候现场写红黑树代码的概率几乎为0，但是红黑树一些基本概念还是需要掌握的。

1. 它是二叉排序树（继承二叉排序树特显）：
   - 若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值。 
   - 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值。 
   - 左、右子树也分别为二叉排序树。 

2. 它满足如下几点要求： 
   - 树中所有节点非红即黑
   - **根节点必为黑节点**
   - **红节点的子节点必为黑（黑节点子节点可为黑）**
   - **从根到NULL的任何路径上黑结点数相同**

3. 查找时间一定可以控制在O(logn)



#### 37、STL中unordered_map和map的区别和应用场景

map支持键值的自动排序，底层机制是**红黑树**，红黑树的查询和维护时间复杂度均为 $O(\log n)$，但是空间占用比较大，因为每个节点要保持父节点、孩子节点及颜色的信息

unordered_map是C++ 11新添加的容器，底层机制是**哈希表**，通过hash函数计算元素位置，其查询时间复杂度为O(1)，维护时间与bucket桶所维护的list长度有关，但是建立hash表耗时较大

从两者的底层机制和特点可以看出：map适用于有序数据的应用场景，unordered_map适用于高效查询的应用场景



#### 38、hashtable 中解决冲突有哪些方法？

**记住前三个：**

- **线性探测**：使用hash函数计算出的位置如果已经有元素占用了，则向后依次寻找，找到表尾则回到表头，直到找到一个空位

- **开链**：每个表格维护一个list，如果hash函数计算出的格子相同，则按顺序存在这个list中

- **再散列**：发生冲突时使用另一种hash函数再计算一个地址，直到不冲突

- **二次探测**：使用hash函数计算出的位置如果已经有元素占用了，按照$1^2$、$2^2$、$3^2$...的步长依次寻找，如果步长是随机数序列，则称之为伪随机探测

- **公共溢出区**：一旦hash函数计算的结果相同，就放入公共溢出区



### 其余问题-01-20

> <a id="new5">完整例子以及解读</a>参考：https://interviewguide.cn/notes/03-hunting_job/02-interview/01-04-02-STL.html

#### 1、C++的多态如何实现

- 编译时多态：运算符重载、函数重载
- 运行时多态：继承，覆盖并且向上转型（派生类指针指向基类对象，子类方法覆盖父类方法）



#### 2、为什么析构函数一般写成虚函数

由于类的多态性，**基类指针可以指向派生类的对象**，如果删除该基类的指针，就会调用该指针指向的派生类析构函数，而派生类的析构函数又自动调用基类的析构函数，这样整个派生类的对象完全被释放。

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

所以将析构函数声明为虚函数是十分必要的。**在实现多态时，当用基类操作派生类，在析构时防止只析构基类而不析构派生类的状况发生，要将基类的析构函数声明为虚函数。**



#### 3、构造函数能否声明为虚函数或者纯虚函数，析构函数呢？

虚函数对应一个 vtable (虚函数表)，类中存储一个 vptr 指向这个 vtable。如果构造函数是虚函数，就需要通过 vtable 调用，可是对象没有初始化就没有 vptr，无法找到 vtable，所以构造函数不能是虚函数



#### 4、基类的虚函数表存放在内存的什么区，虚表指针vptr的初始化时间

由于虚表指针vptr跟虚函数密不可分，对于有虚函数或者继承于拥有虚函数的基类，对该类进行实例化时，**在构造函数执行时会对虚表指针进行初始化**，并且存在对象内存布局的最前面

- 虚函数表位于只读数据段（.rodata），也就是 C++内存模型中的**常量区**
- 虚函数则位于代码段（.text），也就是 C++内存模型中的**代码区**



#### 5、:dizzy:模板函数和模板类的特例化



#### 6、构造函数，析构函数，虚函数可否声明为内联函数

将构造函数和析构函数声明为inline是没有什么意义的，即编译器并不真正对声明为inline的构造和析构函数进行内联操作，因为编译器会在构造和析构函数中添加额外的操作（申请/释放内存，构造/析构对象等），致使构造函数/析构函数并不像看上去的那么精简

> [原文链接](#new5)



#### 7、C++模板是什么，你知道底层怎么实现的？

模板的实参推演：不用实例化直接推导参数类型，例如`compare(10, 20)` ，其中 compare 是函数模板

模板在调用点处被编译器替换成对应类型的模板函数

模板的特例化是用户提供的实例化模板函数

函数模板、模板特例化、非模板函数可以共存，编译器会怎么简单怎么来



#### 8、构造函数为什么不能为虚函数？析构函数为什么要虚函数？

参考 T3



#### 9、析构函数的作用，如何起作用？



#### 10、构造函数和析构函数可以调用虚函数吗，为什么



#### 11、构造函数、析构函数的执行顺序？构造函数和拷贝构造的内部都干了啥？

- 构造：从基类到父类
- 析构：从父类到基类



#### 12、虚析构函数的作用，父类的析构函数是否要设置为虚函数？



#### 13、构造函数析构函数可否抛出异常



#### 14、构造函数一般不定义为虚函数的原因

参考 T3



#### 15、类什么时候会析构？



#### 16、构造函数或者析构函数中可以调用虚函数吗？

参考 T10



#### 17、:dizzy:构造函数的几种关键字



#### 18、构造函数、拷贝构造函数和赋值操作符的区别 :fire:

```cpp
class A
{
public:
    A() { 
        cout << "我是构造函数" << endl; 
    }
    
    A(const A& a) {
        cout << "我是拷贝构造函数" << endl;
    }

    A(const A&& a) {
        cout << "我是移动构造函数" << endl;
    }

    A& operator = (A& a) {
        cout << "我是赋值操作符" << endl;
        return *this;
    }

    ~A() {};
};
```



#### 19、拷贝构造函数和赋值运算符重载的区别



#### 20、什么是虚拟继承 :fire:

虚继承就是子类中只有一份**间接父类**的数据，用于解决多继承中父类为非虚基类时出现的数据冗余的问题，也就是菱形继承的问题。

- 父类数据并不存在虚继承的子类中，子类通过**虚基表指针 vbptr**，指向虚基表，表中有**偏移量**，这个偏移量就是表的地址到父类数据地址的距离
- 虚继承只有在**多继承**时才有效，并且只有**一个**间接父类才可以

<img src="https://img-blog.csdnimg.cn/5868ad5ce2734b258366a0756b0d13b0.png" style="zoom:40%;" />

> 参考：[虚继承详解](https://blog.csdn.net/weixin_61857742/article/details/127344922)



### 其余问题-21-36

> <a id="new6">完整例子以及解读</a>参考：https://interviewguide.cn/notes/03-hunting_job/02-interview/01-04-02-STL.html



#### 21、什么情况会自动生成默认构造函数？



#### 22、抽象基类为什么不能创建对象？



#### 23、模板类和模板函数的区别是什么？

模板类中构造函数和析构函数名可以不用加类型参数列表，其他出现模板的地方都要加上类型参数列表



#### 24、多继承的优缺点，作为一个开发者怎么看待多继承



#### 25、模板和实现可不可以不写在一个文件里面？为什么？

不可以，模板调用之前一定要看到模板定义的地方，这样的话模板才能够被正常的实例化，产生能够被编译器编译的代码，所以模板代码都是放在头文件中的，然后在源文件中直接 include 包含即可



#### 26、:dizzy:将字符串“hello world”从开始到打印到屏幕上的全过程?

- 用户执行 hello 可执行文件
- OS 创建一个新进程，将 hello 执行文件映射到该进程结构
- OS 设置好 cpu 上下文之后，进程执行该程序
- 如果发生缺页中断，OS 分配一页物理内存，将代码从磁盘读入内存然后执行
- hello 程序中通过系统 cout 或者 printf 在显示器上显示输出字符串

#### 27、为什么拷贝构造函数必须传引用不能传值？



#### 28、静态函数能定义为虚函数吗？常函数呢？说说你的理解



#### 29、虚函数的代价是什么？



#### 30、说一说你了解到的移动构造函数？



#### 31、什么情况下会合成构造函数？都说一说，你知道的都说一下



#### 32、那什么时候需要合成拷贝构造函数呢？



#### 33、构造函数的执行顺序是什么？



#### 34、一个类中的全部构造函数的扩展过程是什么？



#### 35、哪些函数不能是虚函数？



#### 36、什么是纯虚函数，与虚函数的区别

- 虚函数是为了实现动态编联产生的，目的是通过基类类型的指针指向不同对象时，自动调用相应的、和基类同名的函数（使用同一种调用形式，既能调用派生类又能调用基类的同名函数）。虚函数需要在基类中加上virtual修饰符修饰，因为virtual会被隐式继承，所以子类中相同函数都是虚函数。当一个成员函数被声明为虚函数之后，其派生类中同名函数自动成为虚函数，在派生类中重新定义此函数时要求函数名、返回值类型、参数个数和类型全部与基类函数相同。
- 纯虚函数只是相当于一个接口名，但含有纯虚函数的类**不能够实例化**



> 以上所有摘自：https://github.com/forthespada/InterviewGuide