起始

C/C++ language

Keywords 🔑

const

const 限定符用处是：对被修饰对象进行限定，在初始化后对象在后续过程中不能进行修改操作，分为修饰变量、修饰指针、修饰引用、修饰函数

区别于宏

宏定义 #define const 常量
宏定义，相当于字符替换 常量声明
预处理器处理 编译器处理
无类型安全检查 有类型安全检查
不分配内存 要分配内存
存储在代码段 存储在数据段
可通过 #undef 取消 不可取消

const 引用

指的是对常量对象进行引用，但是注意const引用是将对const 修饰的某类型对象限定为不可修改

1
2
3
4
5
const int a = 5;
const int& aRef = a;
int& b = aRef; 
// Error: cannot bind non-const lvalue reference of type 'int&' to an rvalue of type 'const int'
// 因为如果成了，那我们可以根据b修改a的值了，而a本身不可修改

const 指针

从以下代码看出const修饰的影响，有一个名词叫做顶层const和底层const，前者表示指针本身是常量（不可更改），后者表示指针所指对象是常量（对象不可更改），通常意义上来讲顶层const的限制弱于底层 const。所以在进行拷贝操作时，顶层const基本上不受影响，而底层const的限制性更大，当进行拷贝考入考出时，左右对象必须是相同的底层const资格（因为执行对象拷贝时有限制，常量的底层const不能赋值给非常量的底层const）

代码示例1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int a = 5;   // 顶层const
int b = 9;

const int* c = &a; // 底层const
int* const d = &b; // 顶层const
const int* const e = &a; // 前一个为底层const 后一个为顶层const

c = &b; // OK
*c = 6; // Error

d = &a; // Error
*d = 10; // OK

e = &b; // Error
*e = 7; // Error

const int e = 5;
d = &e; // Error

底层const和顶层const

  • 顶层const：指的是const修饰的变量本身是一个常量，无法修改，指的是指针，就是 * 号的右边
  • 底层const：指的是const修饰的变量所指向的对象是一个常量，指的是所指变量，就是 * 号的左边

const函数

修饰成员函数，说明该成员函数内不能修改成员变量

小结

这部分讲的大概很复杂很绕，其实不要去记什么常量引用，常量啥的，只需要记住const修饰对象将会导致一个不可更改的对象即可。对待这个东西我个人的处理看待方式就是，先搞清楚目标对象是什么样的const，然后再做处理，也许和指针引用搭配的时候是有点绕。在确定对象是在当前过程中readonly的，那么我们就应该对其const修饰，对于非内部数据的输入参数，应该将单纯的值类型A a更改为const A& a，避免了拷贝，同时避免了对其修改，提高了效率

static

对修饰对象更改其存储区域和生命周期，使得变量存储在静态区，在运行前分配了空间。由于直接存储在静态区，在多人开发项目时，为了防止与他人命名空间里的函数重名，通过static修饰能做到这一点。

修饰变量：变量所在对象只保存一个该变量，而且能够直接访问

修饰成员函数：不需要生成对象实例就可以访问该函数

static 变量存储于全局数据区

static 函数仍然存储与代码区

作用：

隐藏、保证变量内容持久、默认初始化为0

什么时候初始化：

C中，初始化发生在代码执行之前，编译阶段分配好内存之后，就会进行初始化

C++中，初始化时在执行相关代码时才会进行初始化

this

隐式访问：在类的非静态成员函数中，this指针是隐式可用的，它指向调用成员函数的对象实例

类型：在类T的成员函数内，this的类型是T* const。这意味着this是一个指向T类型的常量指针，你不能改变this指针的指向，即不能让this指向另一个对象，但可以修改这个对象的成员（除非成员是const）底层const

const成员函数：在const成员函数中，this指针的类型是const T* const，这意味着你既不能改变this指针的指向，也不能通过this指针修改对象的成员

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class MyClass {
public:
    int value;

    // 成员函数修改对象成员
    void setValue(int value) {
        // 使用this指针明确指定成员变量
        this->value = value;
    }   
     // const成员函数，不修改任何成员变量
    void printValue() const {
        // 输出成员变量value的值
        std::cout << "Value: " << value << std::endl;
        // this->value = 5; // 错误：这会尝试修改成员变量，但在const成员函数中是不允许的
    }
};

int main() {
    MyClass obj;
    obj.setValue(10); // 调用成员函数设置value  此时是 T* const起作用
    bj.printValue(); // 调用const成员函数		此时是 const T* const起作用
    return 0;
}

delete this？

delete this 是合法的，但是要非常小心使用。delete this 语句用于在对象的成员函数中释放该对象的内存，但这种操作需要确保在调用该语句之后，不再访问已释放的内存，否则会导致未定义的行为或程序崩溃

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>

class MyClass {
public:
    void destroy() {
        std::cout << "Destroying object..." << std::endl;
        delete this;
    }

    void doSomething() {
        std::cout << "Doing something..." << std::endl;
        // 使用成员函数中的 delete this
        destroy();
        // 试图访问已释放的内存，这是不安全的
        // std::cout << "After deletion..." << std::endl;
    }

    ~MyClass() {
        std::cout << "Destructor called." << std::endl;
    }
};

int main() {
    MyClass* obj = new MyClass();
    obj->doSomething(); // 调用 delete this
    // 尝试访问已释放的内存
    // obj->doSomething();
    return 0;
}

\\Doing something...
\\Destroying object...
\\Destructor called...

Q:如果在类的析构函数中调用delete this，会发生什么

A:无限递归导致stackoverflow

inline

内联函数是C++中的一种函数声明方式，它告诉（建议）编译器在调用函数时将函数的代码插入到调用处，而不是像普通函数那样通过跳转执行。这样做可以减少函数调用的开销，提高程序的执行效率

1
2
3
4
5
6
inline int add(int a, int b) {
    return a + b;
}

int c = add(3,4);
//add()函数被声明为内联函数。当调用add()函数时，编译器会尝试将函数的代码直接插入到调用处，而不是生成一个函数调用的指令

特性：

编译器不一定会遵循inline关键字，它可能会根据具体情况决定是否将函数内联。通常情况下，编译器会将短小的函数内联，而对于较大的函数，编译器可能会忽略inline关键字

内联机制主要用于提高小型函数的执行效率，对于复杂的构造函数和析构函数，使用内联需要谨慎考虑

优点：

  1. 内联函数同宏函数一样将在被调用处进行代码展开，省去了参数压栈、栈帧开辟与回收，结果返回等，从而提高程序运行速度。
  2. 内联函数相比宏函数来说，在代码展开时，会做安全检查或自动类型转换（同普通函数），而宏定义则不会。
  3. 在类中声明同时定义的成员函数，自动转化为内联函数，因此内联函数可以访问类的成员变量，宏定义则不能。

**缺点：**包括可能导致代码体积增加，因为函数的代码会被复制到每个调用处，以及可能增加编译时间

Q:关于其他函数是否可以内联

构造函数和析构函数内联：

将构造函数和析构函数声明为inline是没有什么意义的，即编译器并不真正对声明为inline的构造和析构函数进行内联操作，因为编译器会在构造和析构函数中添加额外的操作（申请/释放内存，构造/析构对象等），致使构造函数/析构函数并不像看上去的那么精简。

原因：只是建议，但是构造函数和析构函数本身会被编译器添加很多复杂代码额外操作，所以不精简，所以不会内联。

虚函数内联：

分情况讨论：当是指向派生类的指针（多态性）调用声明为inline的虚函数时，不会内联展开；当是对象本身调用虚函数时，会内联展开

虚函数是为了实现运行时多态性而设计的，它允许在派生类中重写基类中的同名函数，而在运行时动态地确定应该调用哪个版本的函数，内联函数允许在调用处直接展开函数的代码，以减少函数调用的开销。但是，对于虚函数来说，编译器需要在运行时确定实际调用的函数版本，这与内联函数的特性相矛盾。因此，虚函数通常不会被声明为内联函数。虚函数的实现通常涉及虚函数表（vtable）和虚函数指针（vptr），而内联函数的展开是在编译期间完成的，这两者的机制不兼容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>  
using namespace std;
class Base
{
public:
   inline virtual void who()
   {
   	cout << "I am Base\n";
   }
   virtual ~Base() {}
};
class Derived : public Base
{
public:
   inline void who()  // 不写inline时隐式内联
   {
   	cout << "I am Derived\n";
   }
};

int main()
{
   // 此处的虚函数 who()，是通过类（Base）的具体对象（b）来调用的，
   // 编译期间就能确定了，所以它可以是内联的，但最终是否内联取决于编译器。 
   Base b;
   b.who();

   // 此处的虚函数是通过指针调用的，呈现多态性，需要在运行时期间才能确定，
   // 所以不能为内联。  
   Base *ptr = new Derived();
   ptr->who();
}

sizeof

本节主要强调数据对齐的问题

起始位置的偏移量必须是该变量类型大小的整数倍

  • 为什么要使用数据对齐技术

    • 硬件优化：许多硬件平台对特定类型的数据访问有最优的内存对齐要求。正确对齐的数据可以直接从内存读取，而未对齐的数据可能需要多次访问才能完成读取，这样会降低性能。

    • 平台要求：某些平台可能不允许未对齐的内存访问，尝试这样做可能导致硬件异常。

  • 对齐方式

    • 自然对齐：数据的对齐边界通常是其类型大小的最小倍数。例如，int类型（假设为4字节）的数据应该在4字节对齐的地址处开始。
    • 指定对齐：C++11引入了alignas关键字，允许程序员指定变量或类型的对齐要求

  • 其它

    • 虚函数本身、成员函数（包括静态与非静态）和静态数据成员都是不占用类对象的存储空间

    • 对于包含虚函数的类，不管有多少个虚函数，只有一个虚指针,vptr的大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class A {
private:

public:
	virtual void Say() {
		cout<<"A::Say()"<<endl;
	}
};
// 仅含vptr没有数据成员所以sizeof(A)只有一个指针的大小, 64位机器上这个结果是 8 字节

class A {
private:
	char a;
public:
	virtual void Say() {
		cout<<"A::Say()"<<endl;
	}
};
// 16字节， char a被对齐了

一个指针占内存的大小跟编译环境有关，而与机器的位数无关

volatile

编译器会对代码进行各种优化，包括对变量的读写操作进行优化，如将变量的值缓存到寄存器中，以提高程序的执行效率，告诉编译器不要对这些变量的读写操作进行优化

extern “c”

  • 被 extern 限定的函数或变量是 extern 类型的
  • 被 extern "C" 修饰的变量和函数是按照 C 语言方式编译和链接的

struct in C++ & C

C：

struct只能作为单纯用作数据的复合类型，结构体和函数名同名不冲突

C++:

可以定义函数、访问修饰符，若结构体的名字与函数名相同，使用结构体，只能使用带struct定义

struct vs class in c++

二者几乎相同，最本质的一个区别就是默认的访问控制

默认的继承访问权限。struct 是 public 的，class 是 private 的。

struct 作为数据结构的实现体，它默认的数据访问控制是 public 的，而 class 作为对象的实现体，它默认的成员变量访问控制是 private 的

union

联合（union）是一种节省空间的特殊的类，一个 union 可以有多个数据成员，但是在任意时刻只有一个数据成员可以有值，当某个成员被赋值后其他成员变为未定义状态。

  • 默认访问控制符为 public
  • 可以含有构造函数、析构函数
  • 不能含有引用类型的成员
  • 不能继承自其他类，不能作为基类
  • 不能含有虚函数

union vs struct vs classs

union struct class
定义多个成员，使用一个 定义多个成员，使用多个 定义多个成员，使用多个
默认public访问 默认public访问 默认private访问
不可以继承 可以继承 可以继承

explict

  • explicit 修饰构造函数时，可以防止隐式转换和复制初始化
  • explicit 修饰转换函数时，可以防止隐式转换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class MyClass {
public:
    MyClass(int x) {
        // constructor code
        std::cout << "MyClass copy constructor" << endl;
    }
};

void func(MyClass obj) {
    // function code
}

int main() {
    func(10); // 编译通过，隐式类型转换为 MyClass 对象
}

class MyClass {
public:
    explicit MyClass(int x) {
        // constructor code
    }
};

void func(MyClass obj) {
    // function code
}

int main() {
    func(10); // 编译错误，禁止隐式类型转换
}

enum枚举类

传统枚举有问题：

  • 会隐式转换为int
  • 用来表征枚举变量的实际类型不能明确指定，从而无法支持枚举类型的前向声明。
  • 作用域不受限,会容易引起命名冲突

C++11使用枚举类解决以上问题

  • 新的enum的作用域不在是全局的
  • 不能隐式转换成其他类型
  • 以指定用特定的类型来存储enum

auto

类型推断关键字，但是推断结果有时会和初始类型小有区别，auto一般会忽略顶层const而保存底层const

1
2
3
4
5
const int i = 10, &r = i;
   auto b = r; // b int not const int
   const auto c = r; // c const int
   auto d = &i; // d const int*
   const auto e = &i; // e const int*

decltype

decltype：类型推断，应用于想从目标推断定义目标的类型，选择并返回操作数的数据类型。但是注意decltype(目标)和decltype((目标))的区别

1
2
3
4
5
6
7
8
9
int i = 0;
decltype(i) j = 1;
std::cout << typeid(i).name() << std::endl;
decltype((i)) k = i;
std::cout << typeid(k).name() << std::endl;

std::cout << &i << std::endl;
std::cout << &j << std::endl;	// j is an int, so the address of j is different from i
std::cout << &k << std::endl;	// k is a reference to i, so the address of k is the same as i

类型转换关键字

static_cast是最常用的类型转换形式，用于基本数据类型之间的转换，如整型和浮点型、指针类型之间的转换（只要它们是相关的类型），以及类层次结构中向上（子类指针或引用转换为基类指针或引用）的转换。

dynamic_cast专门用于处理类的层次结构中的向下转换（基类指针或引用转换为派生类指针或引用），并在运行时检查类型的安全性。它要求至少有一个基类声明为虚拟的（即至少有一个虚函数）。

原理：所有多态类型的虚表中都需要包含一个特殊的虚表项，该虚表项中存放了虚基表中记录了虚基类与派生类的偏移地址。dynamic_cast 会直接将这个偏移量添加到基类子对象指针上，然后便得到了派生对象的指针

const_cast用于修改类型的const或volatile属性，比如将一个const指针转换为非const指针，允许修改所指向的数据。它不能改变非const对象的const性质，也不能改变对象的类型。

1
2
3
4
5
6
7
8
int i = 10;
float f = static_cast<float>(i); // 整型转换为浮点型

Base* b = new Derived;
Derived* d = dynamic_cast<Derived*>(b); // 基类指针转换为派生类指针

const int* ci = new int(10);
int* i = const_cast<int*>(ci); // 移除const属性

reinterpret_cast可以将指针或引用转换为任何类型的指针或引用

宏 vs typedef vs typename vs inline

宏：

  • #define定义的宏在预处理阶段就被替换，它不受C++作用域规则的限制。
  • 定义的宏没有类型信息，是文本替换,占用代码段空间

typedef:

  • typedef是在编译时处理的，它提供了一种方便的方式来简化复杂类型的声明。
  • typedef给类型起了一个新的名字，但并不创建新的类型。它遵循C++的作用域规则

typename:

  • typename可以用来声明模板参数是一个类型，也用于指明依赖于模板参数的名称是类型。
  • 在模板定义中，typename用来消除歧义，告诉编译器某个特定的标识符应该被视为类型。

inline:

  • inline在编译时处理，建议编译器把该函数放置与每个调用该函数的地方
  • 遵循C++的作用域规则

NULL vs nullptr

  • NULL：NULL通常被定义为整数0，或者是一个宏定义，如#define NULL 0或#define NULL ((void*)0)。它的实际类型可能因编译器而异。
  • nullptr：nullptr是C++11引入的一个新的关键字，它表示一个指向任何类型的空指针。nullptr的类型是std::nullptr_t，可以隐式转换为任何指针类型。

new/delete

  • new的实现过程是：首先调用名为operator new的标准库函数，计算内存大小；接下来运行该类型的一个构造函数，初始化构造对象；最后返回指向构造后的对象的指针
  • delete的实现过程：对指针指向的对象运行适当的析构函数；然后通过调用名为operator delete的标准库函数释放该对象所用内存

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

内存分配

malloc、calloc、relloc - free

  1. malloc：
    • 函数原型：void* malloc(size_t size);
    • 功能：在堆上分配指定字节数的内存空间，并返回指向分配内存的指针。它不会初始化分配的内存，因此内存中的值是未定义的。
    • 使用：通常用于动态分配单个对象或一段连续的内存块。
  2. calloc：
    • 函数原型：void* calloc(size_t num, size_t size);
    • 功能：在堆上分配指定数量和大小的连续内存块，并将内存初始化为零。
    • 使用：通常用于动态分配数组或结构体等需要初始化为零的内存。
  3. realloc：
    • 函数原型：void* realloc(void* ptr, size_t size);
    • 功能：重新分配之前通过 malloc、calloc 或 realloc 分配的内存块的大小。如果旧的内存块大小足够容纳新的大小，则不会分配新的内存，而是扩展或缩小原有内存块。
    • 使用：常用于调整动态分配内存的大小，例如在动态数组扩展或缩小时使用。

new - delete

  1. new / new[]：完成两件事，先底层调用 malloc 分配了内存，然后调用构造函数（创建对象）。
  2. delete/delete[]：也完成两件事，先调用析构函数（清理资源），然后底层调用 free 释放空间。
  3. new 在申请内存时会自动计算所需字节数，而 malloc 则需我们自己输入申请内存空间的字节数。

STL相关

STL容器一览
容器 底层数据结构 时间复杂度 有无序 可不可重复 其他
array 数组 随机读改 O(1) 无序 可重复 支持随机访问
vector 数组 随机读改、尾部插入、尾部删除 O(1) 头部插入、头部删除 O(n) 无序 可重复 支持随机访问
deque 双端队列 头尾插入、头尾删除 O(1) 无序 可重复 一个中央控制器 + 多个缓冲区，支持首尾快速增删，支持随机访问
forward_list 单向链表 插入、删除 O(1) 无序 可重复 不支持随机访问
list 双向链表 插入、删除 O(1) 无序 可重复 不支持随机访问
stack deque / list 顶部插入、顶部删除 O(1) 无序 可重复 deque 或 list 封闭头端开口，不用 vector 的原因应该是容量大小有限制，扩容耗时
queue deque / list 尾部插入、头部删除 O(1) 无序 可重复 deque 或 list 封闭头端开口，不用 vector 的原因应该是容量大小有限制，扩容耗时
priority_queue vector + max-heap 插入、删除 O(log2n) 有序 可重复 vector容器+heap处理规则
set 红黑树 插入、删除、查找 O(log2n) 有序 不可重复
multiset 红黑树 插入、删除、查找 O(log2n) 有序 可重复
map 红黑树 插入、删除、查找 O(log2n) 有序 不可重复
multimap 红黑树 插入、删除、查找 O(log2n) 有序 可重复
unordered_set 哈希表 插入、删除、查找 O(1) 最差 O(n) 无序 不可重复
unordered_multiset 哈希表 插入、删除、查找 O(1) 最差 O(n) 无序 可重复
unordered_map 哈希表 插入、删除、查找 O(1) 最差 O(n) 无序 不可重复
unordered_multimap 哈希表 插入、删除、查找 O(1) 最差 O(n) 无序 可重复

STL算法复杂度一览

算法 底层算法 时间复杂度 可不可重复
find 顺序查找 O(n) 可重复
sort 内省排序 O(n*log2n) 可重复

为什么用内省排序：

因为快排在面对小数组（比如大小为10的数组）且基本有序的情况下，它的表现还没插入排序要好。因为数组的基本有序，使得插入排序不用很多次的执行元素的移动，并且可以避免递归。 在SGI STL中的函数sort使用的排序算法其实就是内省式的排序算法

快排的递归层次过深的时候，很可能会退化成O(n^2)。内省式排序使用k来控制快排的递归深度，当快排的递归深度到达k的时候选择使用heap排序。

STL迭代器一览

容器 迭代器
vector、deque 随机访问迭代器
stack、queue、priority_queue 无
list、(multi)set/map 双向迭代器
unordered_(multi)set/map、forward_list 前向迭代器

STL关系一览

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
STL:
---序列式容器: string,vector,array,deque,list,forward_list
---容器适配器: stack,queue,priority_queue
---关联式容器: 
------红黑树结构：map,set,multimap,multiset
------哈希结构：unordered_map,unordered_set,unordered_multimap,unordered_multiset

vector:可变大小数组
deque:双端队列
list:双向链表
array:固定大小数组
string:类似于vector但是专门保存字符
forward_list:前向链表

map:关联数组：key-value pair 有序
set：只保存关键字的容器：key is value 有序
mutilmap：关键字可重复出现
mutilset：关键字可重复出现

unordered_map:hash函数组织map 无序
unordered_set:hash函数组织set 无序
unordered_mutilmap:hash函数组织map 无序 关键字可重复出现
unordered_mutilset:hash函数组织set 无序 关键字可重复出现
空间配置器
	|
	v
	*容器<-------------------+
         |			|
         v			|
      *迭代器  ----> *算法--->仿函数
         ^          /		^
          \        /		|
           \      v		|
            适配器<--------------+

STL高频问题[重点]

什么是STL

STL是C++整个联邦的一个重要组成部分(泛型库)，它包含…6个部分，…

其中容器分为序列容器、关联容器、容器适配器（栈、队列）

重要容器：string/vector/list+map/set/unordered_map/unordered_set

STL六大组件

容器：数据结构，容器通过迭代器暴露其元素，使得算法可以操作这些元素

迭代器：访问容器的泛型指针，让用户通过特定的接口访问容器的数据，不需要了解容器内部的底层数据结构

算法：数据操作方式

函数对象（仿函数）：函数对象是重载了函数调用操作符（()）的类实例。STL中的函数对象可以用作算法的某些操作，如定义比较行为（less，greater等），定义算法作用与容器的行为。

sort(a.begin(), a.end(),less<int>());

适配器：可以修改或扩展迭代器、容器和仿函数的行为，使其能够以新的方式被算法使用或操作。(stack\queue)

空间配置器：在更底层被容器使用来管理内存分配的，但它通常对于 STL 的使用者是透明的，除非需要自定义内存管理行为，内存池。【可以作为说是STL优化策略】【堆中申请内存】

内存池是一种用于管理和分配内存的技术，它通过预先申请一块固定大小的内存空间，并将其划分为多个小块，提供给程序按需分配和释放

Q:why memory pool?

**A:**如果将内存申请交给每个STL容器自己去申请管理，一是不安全容易内存泄漏二是频繁申请小块内存导致内存碎片，影响程序运行效率

Q:内存池实现机制

A: allocate 包装 malloc，deallocate包装free

Q:空间配置器是一级和二级的，为什么要二级空间配置器(1大1小)

**A:**一级空间配置器对于大块内存非常有效，直接与内存管理机制交互减少额外开销，但是频繁分配和释放小块内存的场景，将会导致性能下降和内存碎片,所以引入二级空间配置器，底层原理是链表构成的内存.

STL各大容器

vector

动态增长数组，底层是类似于一个array，但是比array灵活，内部数据连续存储，是一种可以动态增长的序列容器，元素在内存连续存放，随机存取时间复杂度O(1)，尾端操作最佳性能，头部操作O(n)

  • 底层原理

    类似于数组array，唯一差别是vector更加灵活，他的start和end迭代器分别指向所申请连续空间的首尾

  • 增加元素时若超过自身最大容量，则扩充自身容量2倍（不同的编译器，vector有不同的扩容大小。在vs下是1.5倍，在GCC下是2倍）

    扩充空间需要经过的步骤：重新配置空间，元素移动，释放旧的内存空间。一旦vector空间重新配置，则指向原来vector的所有迭代器都失效了，因为vector的地址改变了

    Q：为什么加倍扩充

    A：加倍扩容将会有更多的空余空间，不然假设我们一边扩一个一边加一个将导致不停的内存拷贝复制，时间复杂度本来是O(1)将会增长为O(n)

    Q：扩容为啥1.5倍或2倍？

    A：使用k=2增长因子的问题在于，每次扩展的新尺寸必然刚好大于之前分配的总和，也就是说，之前分配的内存空间不可能被使用。这样对内存不友好，最好把增长因子设为(1, 2)，也就是1-2之间的某个数值

  • size、resize、reserve、capacity

    size：容器当前存储内容数量

    resize：改变容器size

    reserve：改变capacity

    capacity：容器最大存储内容数量

  • push_back和emplace_back

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    	vector<A> v;
    	A a;
    	v.push_back(a);		\\ 拷贝复制到vec
    	v.emplace_back(); 	\\ 直接进入到vec

    	cout << &a << endl;
    	cout << &v[0] << endl;
    	cout << &v[1] << endl;

    000000B570AFFB24
    000002A0CF71A400
    000002A0CF71A401

  • 迭代器失效

    resize、reserve、insert、assign、push_back等会引起其底层空间改变的操作，都有可能使迭代器失效

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    vector<int> vec_int = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int main() {
    	std::vector<int>::iterator it = vec_int.begin();
    	for (int i = 0; i < 10; i++)
    	{
    		if( i == 5)
    			vec_int.erase(it);
    		cout << *it << endl;	// Error: it is not valid iterator
    		it++;
    	}
    }

    vector<int> vec_int = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int main() {
    	std::vector<int>::iterator it = vec_int.begin();
    	for (int i = 0; i < 10; i++)
    	{
    		if (i == 5)
    		{
    			it = vec_int.erase(it);
                /// vec_int.erase(it);
                /// it++; ///error
    			continue;
    		}
    		cout << *it << endl;
    		it++;
    	}
    }
    /// 1, 2, 3, 4, 5, 7, 8, 9, 10

  • vector交换技巧释放空间

    例子1

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    #include <vector>
    #include <iostream>

    int main() {
        std::vector<int> vec(100); // 假设有一个很大的vector
        std::cout << "Capacity before: " << vec.capacity() << std::endl;
        // 清除元素
        vec.clear();
        // 请求释放内存（不保证成功）
        vec.shrink_to_fit();
        // 保证减小容量的方法：使用交换技巧
        std::vector<int>(vec).swap(vec); // 创建一个临时vector并与原vector交换
        std::cout << "Capacity after: " << vec.capacity() << std::endl;
        return 0;
    }

    关键在于创建一个新的 std::vector 对象（在本例中是通过复制构造函数，但因为我们之前已经调用了 clear，所以它是空的），然后与原来的 vec 交换内容。由于新创建的 vector 是空的，这将有效地减少原 vec 的容量，释放多余的空间。在交换后，临时 vector 将被销毁，从而释放了原本 vec 占用的多余内存

    vector()使用vector的默认构造函数建立临时vector对象，再在该临时对象上调用swap成员，swap调用之后原来vector占用的空间就等于一个默认构造的对象的大小，临时对象就具有原来对象v的大小，而该临时对象随即就会被析构，从而其占用的空间也被释放

    例子2

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    	vector<int> vec (100,100);   // three ints with a value of 100
        vec.push_back(1);
        vec.push_back(2);
        cout <<"vec.size(): " << vec.size() << endl;
        cout <<"vec.capasity(): " << vec.capacity() << endl;

        vector<int>(vec).swap(vec); //清空vec中多余的空间，相当于vec.shrink_to_fit();

        cout <<"vec.size(): " << vec.size() << endl;
        cout <<"vec.capasity(): " << vec.capacity() << endl;

        vector<int>().swap(vec); //清空vec的全部空间

        cout <<"vec.size(): " << vec.size() << endl;
        cout <<"vec.capasity(): " << vec.capacity() << endl;

        return 0;

    vec.size(): 102
    vec.capasity(): 150
    vec.size(): 102
    vec.capasity(): 102
    vec.size(): 0
    vec.capasity(): 0
list

底层原理：list底层是一个双向链表（前闭后开），以结点为单位存储数据，节点地址在内存空间不一定连续，区别于vector，每次插入和删除就配置或释放一个空间。它还是一个环状双向链表，所以它只需要一个指针

双向链表允许向前向后，单向链表slist只有push_front()

deque

双端队列， 用空间换了时间，支持首尾（中间不能）快速增删（与vector最大差异），也支持随机访问

优点：

  1. 两端插入/删除操作高效：std::deque 允许在容器的前端和后端进行快速插入和删除操作，时间复杂度大约是 O(1)，这比 std::vector 的前端插入和删除效率要高得多。【这也是vector最大差异】
  2. 随机访问：与 std::vector 类似，std::deque 也支持通过索引进行快速随机访问，访问时间复杂度为 O(1)

缺点：

  1. 内存使用可能更高：由于 std::deque 的实现通常需要额外的中央控制结构来管理各个块，以及块内的间接寻址，这可能导致其比 std::vector 使用更多的内存。
  2. 缓存利用率可能较低：虽然 std::deque 支持随机访问，但其元素可能分布在不连续的内存块中，这可能导致在遍历时缓存命中率低于 std::vector。
  3. 某些操作可能较慢：虽然在两端的操作很快，但在 std::deque 的中间插入或删除元素仍然需要移动一部分元素，这可能比在 std::vector 中慢，尤其是当元素分布在多个内存块中时。
map

底层实现为一个自平衡的二叉搜索树（红黑树，红黑树的旋转操作比AVL树少，红黑树的这种宽松平衡使其在插入和删除操作中相对更高效，因为它不需要像AVL树那样频繁地进行平衡调整，但是这也意味着在最坏情况下，红黑树的查找操作可能会稍慢于AVL树，因为其树高可能稍高），意味着在对数时间复杂度内完成插入、查找和删除的操作，内部元素排列是有序的。

优点：有序，查找时间nlogn

缺点：空间占用率高

map插入方式有哪几种？

1
2
3
4
mapStudent.insert(pair<int, string>(1, "student_one")); 
mapStudent.insert(map<int, string>::value_type (1, "student_one"));
mapStudent.insert(make_pair(1, "student_one")); 
mapStudent[1] = "student_one";
set

底层是一个基于红黑树实现，存储唯一的元素（不重复），按照特定的顺序进行排序的，关联容器。并且set仅存储单个值而非键值对，他的值就是键。

Q:为什么map和set和插入删除效率比其他序列容器高，而且每次insert之后，以前保存的iterator不会失效

A：**关于效率：**set和map是一种关联式容器，底层实现是红黑树实现的，他们的插入和删除效率高于其他容器是因为插入删除操作均是在节点进行操作，对红黑树节点的操作也只是指针操作，节点的存储内存不变。所以效率高，而vector往中间插入会涉及到对后序的内存中的元素复制再拷贝。

关于迭代器失效： 在 std::map 和 std::set 中，插入和删除操作不会使指向其他元素的迭代器失效。这是因为这些操作只影响到特定的节点，并且由于红黑树的性质，树的其他部分保持有效。但需要注意，删除操作会使指向被删除元素的迭代器失效。相比之下，序列容器如 std::vector 在进行插入或删除操作时可能会导致所有指向插入或删除点之后元素的迭代器、指针和引用失效，因为这些操作可能涉及到元素的移动或内存重新分配

Q:map和set不能像vector一样有个reserve函数来预分配数据

A:vector是一种序列式容器，底层实现是一个连续的内存空间，可以动态添加删除数据。而map&set基于红黑树结构他们并不支持连续的内存布局，他们的底层设计和数据结构决定了它们不支持 reserve 功能，这是与它们存储元素和保持结构平衡方式密切相关的。

Q:红黑树

A：二叉排序树，但是没有AVL树限制严格

  • 树中所有节点非红即黑。
  • 根节点必为黑节点。
  • 红节点的子节点必为黑（黑节点子节点可为黑）
  • 从根到叶子的任何路径上黑结点数相同
  • O(log2nlog_2n) 查询
unordered_map

底层实现是一个哈希表 ，排列顺序是无序的,把关键码值映射到Hash表中一个位置来访问记录，查找时间复杂度可达O（1）

优点：查找时间更低

缺点：建立费时

stack & queue

stack 与 queue 二者实现一般用list或者deque, 不用vector的原因是大小限制，扩容耗时。

priority_queue

priority_queue其实就是heap（堆）是完全二叉树

  • std::priority_queue 默认使用 std::vector 作为其底层容器，并使用 std::less 作为比较函数，这意味着最大的元素总是位于队列的前端。
  • 它不提供遍历其元素的能力，因为 std::priority_queue 只允许访问最顶端的元素。
  • 插入和删除操作（添加和移除队列中的元素）的时间复杂度大约是 O(log n)，这里的 n 是队列中元素的数量。
vector vs List

这个对比类似于数组和链表的对比

std::vector

优点：

  1. 快速随机访问：由于 vector 在内存中是连续线性空间存储的，它支持通过索引快速随机访问元素，访问时间复杂度为 O(1)
  2. 空间效率和缓存友好性：连续的内存布局使得 vector 在迭代访问时拥有较好的缓存一致性，通常可以提高遍历效率
  3. 末尾插入/删除高效：在 vector 的末尾添加或删除元素通常非常快速，时间复杂度为 O(1)，尽管当容器需要扩容时会涉及到复制或移动所有元素，但这通过分摊复杂度依然保持了较高效率

缺点：

  1. 中间插入/删除低效：由于需要移动插入点之后的所有元素，所以在 vector 中间插入或删除元素的操作效率较低，时间复杂度为 O(n)
  2. 可能的内存重新分配：当超出当前容量时，需要重新分配内存并复制或移动所有元素，这可能导致较大的性能开销。【这里可以牵扯出频繁push_back导致性能影响】

std::list

优点：

  1. 中间插入/删除高效：list 是基于链表实现的，可以在任何位置快速插入或删除元素，只需要改变前后元素的指针即可，操作的时间复杂度为 O(1)。
  2. 不需要连续内存：链表不需要一块连续的内存空间，这在某些情况下可能更加灵活和高效。

缺点：

  1. 不支持随机访问：list 不支持通过索引直接访问元素，访问任何一个元素都需要从头开始遍历，时间复杂度为 O(n)。
  2. 内存使用更高：每个元素都需要额外的空间来存储前后元素的指针，相比于 vector 的紧凑存储，list 的内存使用效率较低。
  3. 缓存利用率低：由于元素不是连续存储的，链表遍历时缓存命中率较低，可能导致较低的遍历效率。

vector和list增删元素对迭代器的影响

对于vector而言，删除某个元素以后，该元素后边的每个元素的迭代器都会失效，后边每个元素都往前移动一位，erase返回下一个有效的迭代器。

对于list而言，删除某个元素，只有“指向被删除元素”的那个迭代器失效，其它迭代器不受任何影响

  1. vector插入、查找、删除时间复杂度分别为：O(n)、O(1)、O(n)；
  2. list插入、查找、删除时间复杂度分别为：O(1)、O(n)、O(1)。

如何访问倒数第二个元素？

1
2
3
4
vector<int> s = {1,2,3,4,5};
list<int> l = { 1, 2, 3, 4, 5 };
// 输出容器中的最后一个元素
std::cout << *(std::next(s.rbegin())) << std::endl;

运用好std::pre和std::next

queue vs List vs deque

queue是STL中的容器适配器，依赖底层序列容器通过一定的方法对容器的数据操作方式进行控制；List是STL中的序列容器，底层原理是双向链表实现，deque也是序列容器，双向开口的连续线性空间，但是它内部底层原理涉及到了map，因为他要将一定的内存块通过map连接起来，这样deque不但能实现双向队列基础上还能以O(1)进行随机访问（而vector不可以）

map vs set

map和set都是STL中的关联式容器，都是基于红黑树实现

map:

  • map以RBTree作为底层容器
  • 所有元素都是键+值存在
  • 不允许键重复
  • 所有元素是通过键进行自动排序的
  • map的键是不能修改的，但是其键对应的值是可以修改的

set: read-only

  • set以RBTree作为底层容器

  • 所得元素的只有key没有value，value就是key

  • 不允许出现键值重复

  • 所有的元素都会被自动排序

  • 不能通过迭代器来改变set的值，因为set的值就是键，set的迭代器是const的【对比map】

    Q:为啥const?

    因为 std::set 的迭代器是常量迭代器（const_iterator），这意味着您不能通过迭代器直接修改元素的值。这是设计上的选择，以确保集合中的元素始终保持正确排序且不重复，所以我们对set的值修改就是删除旧值再添加。

    Q:set存储对象时根据什么作为键值

    A：对象值作为键值，向set中插入对象时，这些对象会根据它们的值被比较。例如，如果你有一个自定义对象类型，并向set中添加这种类型的对象，你需要确保该类型支持比较操作（如通过重载<操作符），这样set才能根据对象的值来进行排序和唯一性检查

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    #include <iostream>
    #include <set>

    class MyClass {
    public:
        int value;
        MyClass(int v) : value(v) {}
        
        // 重载<操作符，以便set可以根据对象的value排序
        bool operator<(const MyClass& other) const {
            return value < other.value;
        }
    };

    int main() {
        std::set<MyClass> mySet;

        // 向set中插入对象
        mySet.insert(MyClass(10));
        mySet.insert(MyClass(20));
        mySet.insert(MyClass(10)); // 这个插入操作不会成功，因为值10已经存在

        // 输出set的大小，预期是2，因为有两个唯一的值
        std::cout << "Set size: " << mySet.size() << std::endl;

        return 0;
    }
map | set vs multimap | multiset

唯一区别就是：multimap调用的是红黑树的insert_equal(),可以重复插入而map调用的则是独一无二的插入insert_unique()，multiset和set也一样，底层实现都是一样的，只是在插入的时候调用的方法不一样

vector vs map in index [key or index]

关于越界访问查找，通过下标访问vector中的元素时会做边界检查，但该处的实现方式要看具体IDE，不同IDE的实现方式不一样，确保不可访问越界地址

map的下标运算符[]的作用是：将key作为下标去执行查找，并返回相应的值；如果不存在这个key，就将一个具有该key和value的值插入这个map

map中[ ]与find的区别

  • map的下标运算符[ ]的作用是：将关键码作为下标去执行查找，并返回对应的值；如果不存在这个关键码，就将一个具有该关键码和值类型的默认值的项插入这个map。
  • map的find函数：用关键码执行查找，找到了返回该位置的迭代器；如果不存在这个关键码，就返回尾迭代器。

查找+插入 vs 查找

hash_map vs map

hash_map被C++11标准化为unordered_map, 二者底层实现不一样，hash_map底层实现是hash_table，而map 底层实现是红黑树，前者查找时间是O(1)，后者O(n)

Q：hash_table底层机制？

A：开链法构造

迭代器 ++it vs it++

++it（前缀递增）

  • 行为：首先增加迭代器的值（即让迭代器指向下一个元素），然后返回增加后的迭代器的引用。
  • 性能：通常推荐使用前缀递增，因为它不需要创建迭代器的临时副本。在迭代器或者对象本身较大时，使用前缀递增可以避免不必要的复制，从而提高效率。
1
2
3
4
5
int& operator++()
{
  *this += 1;
  return *this;
}

it++（后缀递增）

  • 行为：首先创建当前迭代器的一个副本，然后增加原迭代器的值（让原迭代器指向下一个元素），最后返回副本。这意味着返回的是增加之前的迭代器的值
  • 性能：后缀递增需要创建迭代器的一个临时副本，这可能导致额外的性能开销，尤其是对于那些复制成本较高的迭代器（如某些容器的迭代器）
1
2
3
4
5
6
int operator++(int)                 
{
   int temp = *this;                   
   ++*this;                       
   return temp;                  
}

普通 i++与++i

  1. 前置递增（++i）:
    • ++i 首先将 i 的值增加 1。
    • 然后返回 i 增加后的新值。
    • 这意味着如果你使用 ++i 在表达式中，你将得到增加后的值。
  2. 后置递增（i++）:
    • i++ 首先返回 i 当前的值（增加前的值）。
    • 然后将 i 的值增加 1。
    • 这意味着如果你在表达式中使用 i++，你首先得到的是增加前的原始值。
1
2
3
4
5
int i = 5;
int a = ++i; // a 是 6, i 也是 6
int b = i++; // b 是 6, i 变成了 7

//对于复杂的数据类型，如迭代器和自定义对象，使用 ++i 可能更高效，因为 i++ 需要临时对象来存储原始值，这可能涉及额外的复制构造成本

STL容器删除元素

我们在刚才提到，我们用迭代器删除元素将会导致某些种类容器结构变化，进而导致我们后续的容器失效

  1. 对于序列容器vector，deque来说，使用erase后，后边的每个元素的迭代器都会失效，后边每个元素都往前移动一位，erase返回下一个有效的迭代器；
  2. 对于关联容器map，set来说，使用了erase后，当前元素的迭代器失效，但是其结构是红黑树，删除当前元素，不会影响下一个元素的迭代器，所以在调用erase之前，记录下一个元素的迭代器即可；
  3. 对于list来说，它使用了不连续分配的内存，并且它的erase方法也会返回下一个有效的迭代器，因此上面两种方法都可以使用

顺序容器用迭代器删除一个元素和关联容器用迭代器删除一个元素？

顺序容器：It = c.erase(it); 因为顺序容器删除元素将导致后续迭代器失效，所以要更新it，不能c.erase(it++)

关联容器：c.erase(it++); erase迭代器只是被删除元素的迭代器失效,所以c.erase(it++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
set<int> s = {1, 2, 3, 4, 5};
for (auto it = s.begin(); it != s.end(); it++) {
	if (*it == 3) {
		// ok, erase will return the next element's iterator
		// it++ is valid
		// map is a related container, so it++ is valid
		s.erase(it++);
		continue;
	}
}
for (auto it = s.begin(); it != s.end(); it++) {
	cout << *it << endl;
}

vector<int> v = {1, 2, 3, 4, 5};
for (auto it = v.begin(); it != v.end(); it++) {
	if (*it == 3) {
		// v.erase(it++); 
		// ERROR because it++ is invalid, vector is a series container, 
		// if erase an element, next element will be moved to the previous position, so it++ is invalid

		it = v.erase(it);
		// ok, erase will return the next element's iterator
		continue;
	}
}
for (auto it = v.begin(); it != v.end(); it++) {
	cout << *it << endl;
}

STL中迭代器失效

  • vector & deque

  1. 尾部插入

    插入后size<capacity，首迭代器不失效尾迭代失效；size == capacity时，所有迭代器均失效

  2. 尾部以外插入

    插入后size < capacity，首迭代器不失效但插入元素之后所有迭代器失效，size == capacity时，所有迭代器均失效

  • list/map/set

    仅当前迭代器失效，不会影响其他节点的迭代器, 使用递增方法获取下一个迭代器

STL hash_table解决冲突办法

线性探测

使用hash函数计算出的位置如果已经有元素占用了，则向后依次寻找，找到表尾则回到表头，直到找到一个空位

开链

每个表格维护一个list，如果hash函数计算出的格子相同，则按顺序存在这个list中

再散列

发生冲突时使用另一种hash函数再计算一个地址，直到不冲突

综合 📚

CPP编译步骤*

**预处理阶段：**在这个阶段，预处理器处理源文件中的预处理指令，比如 #include、#define 等。预处理器会根据这些指令展开头文件并替换宏定义，生成一个经过预处理的源文件 .ii

**编译阶段：**编译器将预处理后的源文件转换成汇编代码。在这个阶段，编译器会对源文件进行词法分析、语法分析和语义分析，并生成相应的中间代码或汇编代码 .s

汇编阶段：汇编器将汇编代码转换成机器码或者目标文件。在这个阶段，汇编器会将汇编代码转换成可重定位的机器码，并生成目标文件 .o

链接阶段：链接器将目标文件和库文件链接在一起，生成最终的可执行文件。在这个阶段，链接器会解析目标文件之间的引用关系，将它们连接到正确的位置上，并将库文件中的函数和变量链接到可执行文件中，.out

静态链接：

在编译链接可执行文件时，链接器从库中复制这些函数和数据并把它们和应用程序的其它模块组合起来创建最终的可执行文件

优点：可执行程序中已经具备了所有执行程序所需要的任何东西， 在执行的时候运行速度快

缺点：导致内存中副本代码过多，源库代码修改了，链接过该库的程序要重新进行编译链接

动态链接：

动态链接的基本思想是把程序按照模块拆分成各个相对独立部分，在程序运行时才将它们链接在一起形 成一个完整的程序

优点：多个程序在执行时共享同一份副本,更新时只需要替换原来的目标文件，而无需将所有的程序再重新链接一遍

缺点:为把链接推迟到了程序运行时，所以每次执行程序都需要进行链接，所以性能会有一定损 失

变量存储区域*(内存管理机制)

1
2
3
4
5
6
7
8
9
10
11
|	Text	| low address //代码区（文本段）
|---------------|
|  data		|			  // 这里又分为全局数据区和常量区
|  segment	|
|---------------|
|	HEAP	|			  // new delete 作用区域 向高地址增长
|---------------|
|   空闲 	|				 // 不等价于heap
|   内存 	|
|---------------|
|	stack	| high address // 向低地址增长

代码段：它包含可执行指令（机器代码），代码段通常是只读的，即程序代码区

数据段：数据段分为两部分：

  • 初始化数据段：所有全局、静态static和常量数据都存储在数据段中，即**静态存储区 **.data

  • 未初始化数据段：所有未初始化的全局变量和静态变量都存储在该段中，也称为BSS段 .bss

堆段：当程序在运行时使用calloc和malloc函数分配内存时，内存在堆中分配，向高地址增长
栈段：栈用于存储局部变量、函数参数和其他与函数相关的信息，向低地址增长

堆栈存储：

  • A a;：在栈（Stack）上分配内存。栈是一种自动管理内存的区域，变量在定义所在的作用域结束时会自动销毁。
  • A *a = new A();：在堆（Heap）上分配内存。堆用于动态内存分配，通过new操作符分配的内存必须显式地通过delete操作符释放，否则会导致内存泄漏
堆 栈
管理方式 堆中资源由程序员控制（容易产生memory leak） 栈资源由编译器自动管理，无需手工控制
内存管理机制 系统有一个记录空闲内存地址的链表，当系统收到程序申请时，遍历该链表，寻找第一个空间大于申请空间的堆结点，删除空闲结点链表中的该结点，并将该结点空间分配给程序 只要栈的剩余空间大于所申请空间，系统为程序提供内存，否则报异常提示栈溢出
空间大小 堆是不连续的内存区域 栈是一块连续的内存区域
碎片问题 对于堆，频繁的new/delete会造成大量碎片，使程序效率降低 对于栈，它是有点类似于数据结构上的一个先进后出的栈，进出一一对应，不会产生碎片
生长方向 向高地址方向增长。 向低地址方向增长
分配方式 堆都是动态分配 栈有静态分配和动态分配，静态分配由编译器完成，但栈的动态分配的资源由编译器进行释放
分配效率 堆由C/C++函数库提供，效率低 栈是其系统提供的数据结构，计算机在底层对栈提供支持，效率高

静态&动态的类型与绑定

绑定(Binding)：指将变量和函数名转换为地址的过程。

静态类型：编译期间绑定，静态类型的语言要求在编译时确定所有变量的类型

动态类型：运行期决定，动态类型的语言允许变量在运行时改变其类型

静态绑定：绑定的是静态类型，将函数和对应的属性依赖绑定到相应的对象的静态类型。指的是对象的方法调用在编译时就已经解析，编译器知道具体调用哪个方法

动态绑定：绑定的是动态类型，将函数和对应的属性依赖绑定到相应的对象的动态类型（例如虚函数）。指的是方法调用的目标在运行时才确定

虽然 C++ 是静态类型的语言，但你可以在运行时查询一个对象的类型，使用 typeid 运算符或 dynamic_cast 操作

静态断言和动态断言区别

静态断言（Static Assertion）：

  • 静态断言是在编译时进行的，即在代码被编译之前就会执行。
  • 使用静态断言可以对编译期间已知的条件进行检查。
  • 静态断言使用静态表达式来定义条件，并且如果条件为假，则会导致编译错误。
  • 静态断言通常用于验证编译期常量、类型属性或其他与类型相关的约束。

动态断言（Dynamic Assertion）：

  • 动态断言是在运行时进行的，即在程序执行过程中才会执行。
  • 使用动态断言可以对运行时条件进行检查。
  • 动态断言使用 assert() 宏来定义条件，并且如果条件为假，则会触发一个运行时错误，并终止程序执行。
  • 动态断言通常用于验证假设、调试程序或捕获意外情况。

纯虚函数与抽象类

纯虚函数（也称为抽象函数）是一个在基类中声明但不定义的虚函数，用来指定派生类必须提供该函数的实现。纯虚函数的声明以= 0结尾，这个语法表明函数没有实现体。含有纯虚函数的类称为抽象基类，抽象基类不能被实例化

1
2
3
4
5
6
7
8
9
10
class Base {
public:
    virtual void show() = 0; // 纯虚函数
};
class Derived : public Base {
public:
    void show() override { // 实现基类中的纯虚函数
        std::cout << "Derived show function" << std::endl;
    }
};

虚函数*

  1. 虚函数（Virtual Functions）

  • 定义与目的：通过在函数声明前添加virtual关键字来定义虚函数。虚函数允许派生类重写（override）基类中的成员函数，实现运行时多态

  • 运行时多态：虚函数的调用是在运行时决定的，而非编译时。这意味着当通过基类指针或引用调用一个虚函数时，将执行对象实际类型的函数版本

    *编译时多态：函数重载或者模板【问模板的原理？】

  • **存储在内存的什么区：**存储在代码段，而非静态区

  1. 纯虚函数（Pure Virtual Functions）
  • 定义：纯虚函数是一种没有实现的虚函数，通过在函数声明的结尾处添加= 0来指定
  • 抽象基类：包含至少一个纯虚函数的类称为抽象基类。抽象基类不能实例化对象
  1. 虚析构函数（Virtual Destructors）
  • 目的：确保通过基类指针删除派生类对象时能够调用正确的析构函数，从而避免资源泄漏
  • 实现：将基类的析构函数声明为虚函数
  1. 虚继承（Virtual Inheritance）
  • 解决问题：用于解决多重继承中的菱形继承问题（钻石问题），避免基类被多次继承导致的成员重复
  • 实现：通过在继承时使用virtual关键字（如class Derived : virtual public Base）来声明虚继承

Vptr 与 Vtable*

vptr和vtable是实现c++的多态特征的底层机制。

  • 虚指针 vptr

    定义：虚指针是一个指针，每个使用虚函数的对象都会持有一个指向相应虚表的虚指针。

    作用：虚指针使得对象能够在运行时通过虚表找到正确的虚函数实现。当对象的虚函数被调用时，编译器通过对象的虚指针访问虚表，从而找到对应的函数实现进行调用。在构造函数执行时会对虚表指针进行初始化

  • 虚表 vtable

    定义：虚表是一个包含指向类的虚函数地址的数组。每个有虚函数的类或包含虚函数的类的派生类都有一个为它生成的虚表

    作用：当调用对象的虚函数时，编译器会使用虚表来决定需要调用的实际函数。这允许在运行时进行函数的动态绑定，是实现多态的关键。

  • 工作原理

    初始化：当一个对象被创建时，编译器会自动在对象的内存布局中添加一个虚指针（vptr），并将其初始化为指向该类的虚表

    在构造函数中创建虚表并对虚表初始化。在构造子类对象时，会先调用父类的构造函数，此时，编译器只“看到了”父类，并为父类对象初始化虚表指针，令它指向父类的虚表；当调用子类的构造函数时，为子类对象初始化虚表指针，令它指向子类的虚表

    即导致一种情况：覆盖

    当派生类对基类的虚函数没有重写时，派生类的虚表指针指向的是基类的虚表；当派生类对基类的虚函数重写时，派生类的虚表指针指向的是自身的虚表；当派生类中有自己的虚函数时，在自己的虚表中将此虚函数地址添加在后面

    继承与多态：如果一个类被继承，派生类会有它自己的虚表（如果它覆盖了基类的虚函数或添加了新的虚函数）。当通过基类指针或引用调用虚函数时，运行时会查找对象实际类型的虚表，从而调用正确的函数实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <memory>
#include <vector>
#include <unordered_map>
#include <cmath>
#include <string>
#include <set>

using std::string;
using std::vector;
using std::unordered_map;
using std::cout;
using std::endl;

class A {
public:
    virtual void sum(int a, int b) {
        std::cout << "::sum()" << std::endl;
        std::cout << a + b << std::endl;
    }
};

class B : public A {

};

int main() {
    A a;
    void* objPtr = &a; // 获取对象实例的地址
    // 根据C++对象模型，对象的第一个成员是指向虚表的指针
    void** vTablePtr = *(void***)objPtr;
    // 获取虚表中第一个函数的地址
    void (*funcPtra)(A*, int, int) = (void (*)(A*, int, int))vTablePtr[0];
    // 调用这个函数，传递参数
    funcPtra(&a, 5, 3);
    

    B b;
    objPtr = &b;
    vTablePtr = *(void***)objPtr;
    void (*funcPtrb)(B*, int, int) = (void (*)(B*, int, int))vTablePtr[0];
    funcPtrb(&b, 5, 3);
   

    B another_b;
    objPtr = &another_b;
	vTablePtr = *(void***)objPtr;
    void (*funcPtrAnotherB)(B*, int, int) = (void (*)(B*, int, int))vTablePtr[0];
    funcPtrAnotherB(&another_b, 5, 3);
    
    cout << "A sum address" << funcPtra << endl;
    cout << "B sum address" << funcPtrb << endl;
    cout << "Another B sum address" << funcPtrAnotherB << endl;

    cout<<"A vtable address: "<<*(void***)&a<<endl;
    cout<<"B vtable address: "<<*(void***)&b<<endl;
    cout<<"Another B vtable address: "<<*(void***)&another_b<<endl;

    return 0;
}

::sum()
8
::sum()
8
::sum()
8
A sum address00007FF754421555
B sum address00007FF754421555
Another B sum address00007FF754421555
    
A vtable address: 00007FF75442BC18
B vtable address: 00007FF75442BC38
Another B vtable address: 00007FF75442BC38

Q:解释下中间那一坨

A：这里其实不必深究，简单讲解一下

1
void** vTablePtr = *(void***)objPtr;

objPtr：这是指向对象的指针。我们假设这是一个指向类实例的指针

(void***)objPtr：这里发生了类型转换。我们首先将objPtr转换为void***。在C++中，void*是一个通用指针类型，可以指向任何类型的数据。这里的void***表示一个指向指针的指针的指针，这里具体指的是指向虚表指针的指针

*(void***)objPtr：通过解引用操作（*），我们得到了对象的第一个成员，即虚表指针。在大多数情况下，虚表指针是对象布局中的第一个成员

void** vTablePtr：最后，我们得到了虚表指针，并将其存储在vTablePtr中。void**表示指向指针的指针，这里具体指的是指向虚表的指针

在标准C++中没有直接支持这种操作，这是一种与实现相关的技术，可能在不同的编译器或不同的编译器版本中行为不同。在实际的C++编程中，直接操作虚表通常是不推荐的。

Q:为什么此时B继承了A输出的函数地址是一样的呢?

A:当B继承自A且没有覆盖A中的虚函数sum时，B的虚表会复用A中相应的虚函数入口。这就意味着，即便是B的实例，其虚表中指向sum函数的指针也会是指向A::sum的。这是因为B没有提供一个自己的sum实现来“覆盖”或者说“重写”基类A中的那个，所以继承了A的实现。

C++的虚表（vtable）机制是用于支持运行时多态的。每个包含虚函数的类都有一个虚表，虚表中存储了指向类的虚函数的指针。当类B继承自类A而不覆盖（重写）其虚函数时，B的虚表会包含指向A的虚函数实现的指针，因此你会看到相同的函数地址。

这个机制确保了，即使通过基类的指针或引用调用虚函数，也总是会执行到对象实际类型的那个版本，从而实现多态。由于B并没有提供一个新的sum实现，所以它就继承了A的实现，包括使用相同的函数地址

修改以上B类代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class A {
public:
    virtual void sum(int a, int b) {
        std::cout << "A::sum()" << std::endl;
        std::cout << a + b << std::endl;
    }
};

class B : public A {
    // 添加 override
    virtual void sum(int a, int b) override {
        std::cout << "B::sum()" << std::endl;
        std::cout << a + b << std::endl;
    }
};

int main() {
    A a;
    void* objPtr = &a; // 获取对象实例的地址
    // 根据C++对象模型，对象的第一个成员是指向虚表的指针
    void** vTablePtr = *(void***)objPtr;
    // 获取虚表中第一个函数的地址
    void (*funcPtra)(A*, int, int) = (void (*)(A*, int, int))vTablePtr[0];
    // 调用这个函数，传递参数
    funcPtra(&a, 5, 3);
    

    B b;
    objPtr = &b;
    vTablePtr = *(void***)objPtr;
    void (*funcPtrb)(B*, int, int) = (void (*)(B*, int, int))vTablePtr[0];
    funcPtrb(&b, 5, 3);
   

    B another_b;
    objPtr = &another_b;
	vTablePtr = *(void***)objPtr;
    void (*funcPtrAnotherB)(B*, int, int) = (void (*)(B*, int, int))vTablePtr[0];
    funcPtrAnotherB(&another_b, 5, 3);
    
    cout << "A sum address" << funcPtra << endl;
    cout << "B sum address" << funcPtrb << endl;
    cout << "Another B sum address" << funcPtrAnotherB << endl;

    cout<<"A vtable address: "<<*(void***)&a<<endl;
    cout<<"B vtable address: "<<*(void***)&b<<endl;
    cout<<"Another B vtable address: "<<*(void***)&another_b<<endl;

    return 0;
}

A::sum()
8
B::sum()
8
B::sum()
8
A sum address00007FF6CC381555
B sum address00007FF6CC38155F
Another B sum address00007FF6CC38155F
A vtable address: 00007FF6CC38BC18
B vtable address: 00007FF6CC38BC38
Another B vtable address: 00007FF6CC38BC38

Q:1和2对sum函数修改都有相同效果，所以二者相同吗？

当派生类提供一个与基类虚函数签名完全相同的成员函数时，不论是否显式地使用virtual关键字，该成员函数都会被视为覆盖了基类的虚函数，实现多态行为

A：使用virtual关键字：在派生类中重写基类的虚函数时，即使不用virtual关键字，函数依然是虚的，并且覆盖了基类的虚函数。但在早期的C++代码中，显式地使用virtual可以增加代码的可读性，表明这个函数是虚函数，意图是覆盖基类的虚函数。

使用override关键字：C++11引入了override关键字，其目的是明确指示编译器这个函数是用来覆盖基类中的一个虚函数的。如果标记了override但没有实际覆盖任何基类中的虚函数（比如因为函数签名不匹配），编译器会报错。这个机制提供了一个额外的安全检查，有助于捕获潜在的错误。因此，使用override可以增强代码的健壮性和可维护性。

Q:Vptr和Vtable是什么时候创建？

A:虚表是在编译阶段为每个含有虚函数的类生成的，而虚指针在类的对象实例化过程中，具体是在构造函数执行过程中初始化，并指向相应的虚表

虚表和虚指针创建和初始化的过程，涉及到类的实例化：

编译阶段： 编译器在编译阶段识别出哪些类含有虚函数，并为这些类生成虚表。虚表中存储了虚函数的地址。如果类有继承，并且子类覆盖了基类的虚函数，子类的虚表中会用子类函数的地址替换相应的基类函数地址。
构造函数执行阶段： 当创建一个类的对象时，该对象的构造函数会被调用。在构造函数的执行过程中，对象的虚指针（vptr）被初始化，指向其对应类的虚表。如果有继承关系，每个构造函数（从基类到派生类）在其执行过程中都可能更新vptr以指向正确的虚表，以反映当前构造阶段对象的动态类型。
构造函数完成后： 一旦对象的构造函数（包括所有基类和派生类的构造函数，如果有继承的话）执行完成，对象的vptr将最终指向最派生类的虚表。此时，对象已经完全构建好，可以正常使用虚函数了。

Q：你上面那个不太好理解，换个说法

A:虚指针 (vptr)

  • 创建和初始化时机：每个含有虚函数的类的对象都会有一个虚指针。这个虚指针是在对象创建时自动被编译器添加到对象中的。对于类的每个实例，虚指针在对象的构造函数中被初始化。
  • 指向：虚指针指向相应的虚表。

所以我们说只有在vptr完成初始化后才能访问到虚表

虚表 (vtable)

  • 创建时机：虚表是在编译时期创建的。对于每一个含有虚函数的类，编译器会生成一个虚表。虚表是类的一个静态属性，因此对于该类的所有实例来说，虚表是共享的。
  • 初始化时机：虚表在编译期间就已经被初始化了。编译器会将类中所有的虚函数地址填入虚表中。这意味着，当程序编译完成后，每个含有虚函数的类对应的虚表中已经填充了所有虚函数的地址。
  • 填入虚函数地址：虚函数的地址是在编译器编译时期填入虚表的。这个过程发生在程序编译阶段，而不是运行时或者类的初始化时期。

Q:vtable和vptr和类和实例

A:我们上面的实验可以看出，对于同一个类的所有实例，它们共享同一个虚表（vtable）。虚表是每个类的一份，而不是每个对象一份。虚表中包含了该类的所有虚函数地址。每个对象有自己的虚指针（vptr），这个虚指针指向它们共同的虚表。这意味着，如果你输出同一个类的两个不同实例的虚指针值，这两个值是相同的，因为它们都指向同一个虚表。

  1. 节省内存：如果每个对象都有自己的虚表，将会非常占用内存。共享虚表可以大大减少内存使用。
  2. 提高效率：因为虚表是共享的，所以在对象间调用虚函数时不需要额外的查找或是切换虚表，可以直接通过虚指针访问到虚表，然后调用相应的函数。
  3. 支持多态：通过虚指针和虚表的机制，C++实现了运行时多态。即使在基类指针或引用指向派生类对象时，也能通过虚指针找到正确的虚表，进而调用正确版本的虚函数。

**NOTE:**请仔细观察以下地址区别

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
没有覆写版本
A sum address00007FF754421555
B sum address00007FF754421555
Another B sum address00007FF754421555
    
A vtable address: 00007FF75442BC18
B vtable address: 00007FF75442BC38
Another B vtable address: 00007FF75442BC38

被覆写的版本
A sum address00007FF6CC381555
B sum address00007FF6CC38155F
Another B sum address00007FF6CC38155F
    
A vtable address: 00007FF6CC38BC18
B vtable address: 00007FF6CC38BC38
Another B vtable address: 00007FF6CC38BC38

Q:我们发现用指针才能实现这种相应虚函数调用，那么我们可不可以用基类引用实现？

A:可以

virtual搭配*

虚函数实现C++多态的必要基础

静态函数可以声明为虚函数吗

不行，虚函数是用于实现多态的概念，在运行时动态绑定到对象的成员函数。而静态函数是与类关联的，而不是与类的实例（对象）关联的，因此它们不具有动态绑定的特性。

*构造函数可以为虚函数吗

原因

不可以，虚函数表和虚指针是在对象被创建完成后才进行初始化的。在对象的构造函数执行之前，对象的内存空间已经分配，但虚指针尚未初始化。因此，在构造函数中无法使用虚函数表和虚指针来实现动态绑定

当一个虚函数被调用时,它通过虚表(vtable)来解析，而虚函数的调用需要我们通过虚指针去查询虚表进行访问，但此时我们的虚指针的构造是跟随着对象构造函数一起走的，既然我们的虚指针还未初始化那我们访问虚表的行为可能就是未知的，得不到相应调用。此时就会导致一个悖论:

解释1：虚指针还未还没有初始化,对象未完成构造,编译器就需要使用它来调用构造函数;

解释2：虚函数是在运行时动态确定其类型的。在构造一个对象时对象还未创建成功，编译器无法知道对象的实际类型，无法进行调用

'鸡和蛋相互依赖:鸡来自蛋,而蛋又是由鸡生的。这导致了一个看似无法解决的循环因果关系,同样,在构造函数和虚函数的情况下,也存在一种循环依赖:

  1. 为了调用虚函数,对象需要通过vptr访问其虚表。
  2. 但是,访问虚表我们需要一个已经初始化好了的vptr才行，而虚指针是在构造函数执行期间初始化的,对象完成构造后才能得到虚指针
  3. 如果构造函数本身是一个虚函数,那么在调用构造函数之前,就需要访问尚未初始化的虚指针进而访问虚表，很明显这有问题。

这就产生了一个类似于"先有鸡还是先有蛋"的悖论:为了调用构造函数(虚函数),需要虚指针访问虚表;但为了初始化虚指针,需要先调用构造函数’

虚表和虚指针的构造与绑定

对象的虚指针（指向虚表的指针）设置通常是在构造函数开始执行的早期阶段进行的，这是为了确保即使在构造过程中，对象的虚函数也能正确解析到当前构造阶段对应类的实现。这意味着，虚指针和虚表的设置发生在对象的构造过程中，而不是在构造函数完成后【是逐步逐步完成的】。

假设有三个类，Base，Derived1继承自Base，以及Derived2继承自Derived1。每个类都有其虚函数和相应的虚表。

  1. 构造Derived2对象时的过程：
    • 当Derived2的构造函数被调用时，它首先会调用Derived1的构造函数。
    • 在Derived1的构造函数执行之前，Base的构造函数会被自动调用。
    • 在Base构造函数执行的早期阶段，对象的虚指针被设置为指向Base的虚表。这确保了即使在Base构造函数内部，任何虚函数调用都能正确地解析到Base类的实现。
    • 然后，控制权回到Derived1的构造函数，在它开始执行的早期，对象的虚指针更新为指向Derived1的虚表。
    • 同样地，当Derived2的构造函数开始执行时，对象的虚指针最终被更新为指向Derived2的虚表。
    • 当Derived2的构造函数执行完毕，整个对象被完全构造完成，此时虚指针指向Derived2的虚表，确保任何对虚函数的调用都会解析到Derived2或它正确的基类实现。

因此，虚指针的设置和更新发生在每个构造阶段的开始，确保了即使在构造过程中发生虚函数调用，也能够调用到正确版本的函数【但是一般不在构造函数中调用虚函数，不推荐】。这也意味着虚指针和虚表的“生成”（或更准确地说，虚指针的设置）是在构造对象的过程中逐步完成的，而不是在整个对象构造完成后。

析构函数可以为虚函数吗*

可以，而且如果你的类是基类，将基类的析构函数声明为虚函数是非常重要且推荐的做法。这是面向对象设计中的一个关键原则，特别是当涉及到多态和继承时。

有一个指向派生类对象的基类指针，并且通过这个基类指针删除对象时，如果基类的析构函数不是虚的，那么只有基类的析构函数会被调用，导致派生类部分可能不会被正确清理，从而造成资源泄漏或其他问题。这是因为在这种情况下，编译器无法确定要调用哪个析构函数，因为它只依据指针的静态类型来做决定。

构造函数和析构函数可以调用虚函数吗

【effective c++: 绝不在构造和析构过程中调用虚函数】

语法上讲可以，但不推荐这种做法

  • 父类对象会在子类之前进行构造，此时子类部分的数据成员还未初始化，因此调用子类的虚函数时不安全的，故而C++不会进行动态联编【构造函数和析构函数调用虚函数时都不使用动态联编】

  • 析构函数是用来销毁一个对象的，在销毁一个对象时，先调用子类的析构函数，然后再调用基类的析构函数

《Effective C++》的解释是： 派生类对象构造期间进入基类的构造函数时，对象类型变成了基类类型，而不是派生类类型。 同样，进入基类析构函数时，对象也是基类类型

  • 在构造函数中调用虚函数,调用的是当前正在构造的类的版本,而不是最终的重写版本
  • 在析构函数中调用虚函数,调用的是当前正在析构的类的版本,而不是原始的基类版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Base {
public:
	Base() {
		cout << "Base()" << endl;
		print();
	}
	virtual ~Base() {
		cout << "~Base()" << endl;
		out();
	}

	virtual void print() {
		cout << "Base::print()" << endl;
	}

	virtual void out() {
		cout << "Base::out()" << endl;
	}
};

class Derived : public Base {
public:
	Derived() {
		cout << "Derived()" << endl;
		print();
	}
	~Derived() {
		cout << "~Derived()" << endl;
		out();
	}

	void print() override {
		cout << "Derived::print()" << endl;
	}

	virtual void out() override {
		cout << "Derived::out()" << endl;
	}
};

int main() {
	Derived d;
	return 0;
}

Base()
Base::print()
Derived()
Derived::print()
    
~Derived()
Derived::out()
~Base()
Base::out()
    
// 谁构造谁调用
// 谁析构谁调用
// 让我们从虚表虚指针的角度讨论
// 构造的时候，我们的派生类对象还未生成完成，此时vptr也是指向基类的虚表，所以无论是从vptr&vtable角度讲还是一般构造来讲调用的是本类的虚函数（即虚函数还未被派生类的定义所覆盖），然后进入到派生类构造函数，此时才开始调用新的覆写的函数
// 同理析构的时候，先从本派生类开始析构，此时vptr是指向派生类虚表，所以无论是从vptr&vtable角度讲还是一般构造来讲调用的是本类的虚函数（即调用的是被覆盖的版本），然后进入到基类的析构函数，此时调用的是原虚函数

以下表格可以联系虚指针去记忆，和类实例无关的函数

不可以为虚函数的函数 备注
构造函数 （不可以） 虚指针未初始化，矛盾
内联函数 （不推荐） 派生类指针调用不会内联展开；对象本身调用内联展开
静态函数 （不可以） 因为不属于对象属于类，静态成员函数没有this指针
友元函数 （不可以） 因为友元函数不属于类的成员函数，不能被继承，不会进入虚表

以下此表提醒：

内联问题
虚函数内联（类中本身调用才展开，指针调用情况下不会）
构造函数内联（没意义）
析构函数内联（没意义）

C++的继承

  1. 公有继承（Public Inheritance）：

    公有继承意味着基类的公有成员和保护成员在派生类中保持其原有的访问属性。基类的私有成员在派生类中仍然是私有的，但派生类无法直接访问它们。这是最常用的继承类型，用于实现“是一个（is-a）”关系。

  2. 保护继承（Protected Inheritance）：

    保护继承意味着基类的公有成员和保护成员在派生类中变为保护成员。这允许派生类的成员和派生类的派生类访问这些成员，但其他任何类都不能。这种继承方式比较少见。

  3. 私有继承（Private Inheritance）：

    私有继承意味着基类的公有成员和保护成员在派生类中变为私有成员。这意味着这些成员只能被派生类自己的成员函数和友元函数访问。私有继承并不表明“是一个（is-a）”关系，而是表明“有一个（has-a）”关系或者是一种实现细节的继承。

  4. 菱形继承与虚继承

    当两个类继承自同一个基类，并且另一个类再从这两个类继承时，最顶层的基类会被继承多次，导致资源浪费和访问歧义

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
        A
       / \
      B   C
       \ /
        D
        
    class A {
    public:
        int value;
    };

    class B : virtual public A { /* ... */ };
    class C : virtual public A { /* ... */ };
    class D : public B, public C { /* ... */ };

    虚继承通过引入虚基类来解决菱形继承问题。在虚继承中，无论基类被继承了多少次，派生类中只会包含一个基类的实例

    虚继承工作原理:

    • 虚基类表（vbase table）：编译器会为使用虚继承的类构建一个虚基类表。这个表用于存储虚基类相对于派生类对象的偏移量。
    • 初始化虚基类：虚基类的构造函数由最开始的派生类调用，确保虚基类只被初始化一次。
    • 但是引入了额外性能开销,因为要引入虚基类表

构造与析构问题一览*

初始化列表概念

Q:为什么好一点

A:如果是在构造函数体内进行赋值的话，等于是一次默认构造加一次赋值，而初始化列表只做一次赋值操作

Q:为什么多一次默认构造

A:首先了解对象生命周期过程：

当一个类的对象被创建时，其成员变量的构造过程遵循以下步骤：

  1. 内存分配：首先为对象分配内存，包括其所有成员变量。

  2. 成员初始化

    • 使用初始化列表：如果提供了初始化列表，则成员变量将通过在列表中指定的构造函数直接初始化。这意味着对于类类型成员，将直接调用相应的构造函数（可能是参数化构造函数或复制构造函数），而对于内置类型成员，则直接进行赋值。
    • 未使用初始化列表：如果没有为类类型的成员变量提供初始化列表，则这些成员变量首先通过默认构造函数进行初始化。之后，如果在构造函数体内有赋值操作，这些成员变量将经历一次赋值操作。

  3. 执行构造函数体：完成成员的初始化后，执行构造函数体中的代码

对于类类型的成员变量，如果在构造函数体内对它们进行赋值，而不是在初始化列表中直接初始化，会发生以下情况：

  • 默认构造阶段：在进入构造函数体之前，类类型的成员需要被初始化。如果没有在初始化列表中明确指定如何初始化，那么这些成员将通过默认构造函数进行初始化。这是成员对象的生命周期的开始。
  • 赋值操作：在构造函数体内，对这些已经默认构造的成员进行赋值，实际上是调用赋值操作符。这不是成员对象的初始化，而是在一个已经构造的对象上进行的赋值。

类静态分配Only&动态分配Only

只静态分配

将类的 operator new 和 operator new[] 重载函数声明为 private 或 delete

1
2
3
4
5
6
7
8
9
10
11
12
13
class OnlyStatic {
public:
    OnlyStatic() { /* ... */ }
    ~OnlyStatic() { /* ... */ }
    // ...

private:
    void* operator new(size_t) = delete;
    void* operator new[](size_t) = delete;
};

OnlyStatic obj1;  // 正确，静态分配
// OnlyStatic* obj2 = new OnlyStatic();  // 错误，无法动态分配

只动态分配

要使类的对象只能动态分配，可以将类的构造函数声明为 private，并提供一个静态的公有成员函数来创建对象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class OnlyDynamic {
public:
    static OnlyDynamic* Create() {
        return new OnlyDynamic();
    }
    ~OnlyDynamic() { /* ... */ }
    // ...

private:
    OnlyDynamic() { /* ... */ }
};

// OnlyDynamic obj1;  // 错误，无法静态分配
OnlyDynamic* obj2 = OnlyDynamic::Create();  // 正确，动态分配

构造函数析构函数的执行顺序

构造：基类构造函数->成员对象的构造函数->派生类构造函数

析构：派生类析构函数<-成员对象的析构函数<-基类析构函数

如果有多个成员类对象则构造函数的调用顺序是对象在类中被声明的顺序，而不是它们出现在成员初始化表中的顺序

构造函数析构函数可否抛出异常

**构造函数：**当构造函数抛出异常时，对象被认为是没有成功构造的。如果在构造期间抛出异常，C++运行时系统会自动调用已经成功构造的成员对象和基类的析构函数来清理资源，然后将异常传播给上一级的异常处理程序。如果你在构造函数中使用资源（如动态分配内存、文件句柄、锁等），并且在构造过程中抛出异常，你必须确保到目前为止已经构造的部分能够被正确地清理，以避免资源泄漏

**析构函数：**析构函数抛出异常是非常危险的，通常应该避免。如果析构函数抛出异常，并且没有在析构函数内部捕获它，这可能导致程序的不正常终止，因为析构函数通常在对象生命周期结束时被自动调用，包括在处理其他异常时。如果在处理一个异常的过程中，一个析构函数抛出了另一个异常（这被称为异常嵌套），C++标准规定，程序将调用std::terminate()，导致程序立即终止.

构造函数种类

解释 备注
普通构造函数 完成对象的初始化工作 含参数
默认构造函数 完成对象的初始化工作 无参数
拷贝构造函数 复制构造函数用于复制本类的对象，拷贝构造函数在用一个对象初始化另一个新对象时被调用 默认实现是浅拷贝而非深拷贝
转换构造函数 转换构造函数用于将其他类型的变量，隐式转换为本类对象
移动构造函数 特殊的构造函数，用于在对象之间转移资源的所有权，而不是复制资源
委托构造函数 构造函数可以委托同类型的另一个构造函数对对象进行初始化

赋值运算符在将一个已存在的对象赋值给另一个已存在的对象时被调用

  • 如果用户没有定义这些函数，则编译器会隐式声明一个构造函数
  • 在编译器需要的情况下（如带有虚函数，虚拟继承等等），会隐式定义函数，这时函数为非平凡的(no-trivial)；否则则编译器不会添加代码来定义一个函数，这时的函数为平凡的（trivial）

普通构造函数

**初始化方式：**赋值初始化，通过在函数体内进行赋值初始化；列表初始化，在冒号后使用初始化列表进行初始化

委托构造函数

1.被委托的构造函数在委托构造函数的初始化列表里被调用，而不是在委托构造函数的函数体里被调用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class student {
public:
	int age = 18;
	int weight = 120;
	student(int give_age)
	{
		student(give_age, 180);
			std::cout << "委托老兄办点事！" << std::endl;
	}
	student(int give_age, int give_weight) :age(give_age), weight(give_weight)
	{
		std::cout << "我被委托做一些事情！" << std::endl;
	}
};

int main() {
	const student stu = student(20);
	std::cout << stu.age << std::endl << stu.weight << std::endl;
	return 0;
}
我被委托做一些事情！
委托老兄办点事！
18
120

我们发现我们的“委托构造（伪版）”不成功，并没有被构造为20,120，逐步调用我们发现进入student(give_age, 180);后对象变为20,120，但是完成student(give_age, 180);语句后对象恢复为18,120。忽略了被委托构造函数的初始化列表。原因是这段代码的意思是创建了一个匿名student对象然后销毁了它所以不成功。

2.委托构造函数的初始值列表中，只允许出现被委托的构造函数，而不能直接给成员变量进行初始化

3.先执行被委托构造函数的初始化列表，然后执行被委托构造函数的函数体，最后返回执行委托构造函数的函数体。

4.被委托的构造函数同样可以是一个委托构造函数，它继续委托另一个构造函数完成初始化任务。

移动构造函数

C++11 引入的一种特殊的构造函数，用于在对象之间转移资源的所有权，而不是复制资源。它通常用于优化那些包含动态分配资源（如指针）的对象的移动操作，以避免不必要的复制和资源分配

移动构造函数的特点：

  1. 它接受一个右值引用（rvalue reference）作为参数，表示要从中移动资源的对象。
  2. 它将源对象的资源转移到新创建的对象，而不是复制资源。
  3. 在转移资源后，它将源对象的状态设置为有效的默认状态，但不分配任何新的资源
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class MyClass {
private:
    int* data;

public:
    MyClass(int size) {
        data = new int[size];
    }
    // 移动构造函数
    MyClass(MyClass&& other) noexcept {
        // 转移资源的所有权
        data = other.data;        
        // 将源对象设置为默认状态
        other.data = nullptr;
    }
    ~MyClass() {
        delete[] data;
    }
};

需要注意的是，移动构造函数不应该抛出异常，因此通常被标记为 noexcept。此外，只有在源对象是一个右值（rvalue）时，移动构造函数才会被调用。对于左值（lvalue），仍然会调用常规的拷贝构造函数。

感觉很像是右值引用的移动语义

拷贝构造函数

语法：

1
2
3
4
5
6
class A{
public:
    A(const A& t){
        ...
    }
}

常见的使用场景（什么时候会发起拷贝函数调用）：

1.以一个对象初始化另一个对象

2.函数参数的对象传递

3.作为参数的返回值（无移动构造函数）

1
2
3
4
5
6
7
8
9
10
class MyClass{......};
MyClass a;
MyClass b = a; // 1.对象初始化

fun(b); // 2.将对象b作为参数传入fun

MyClass fun(){ 
 MyClass b; 
 return b; //3.返回
}

深拷贝浅拷贝

浅拷贝(Shallow Copy)

浅拷贝是指在创建新对象时,简单地将源对象的非静态数据成员的值复制到新对象中,而不复制指针所指向的动态分配的内存区域。换句话说,源对象和新对象共享相同的动态分配的内存区域。

浅拷贝可能会导致以下问题:

  1. 资源重复释放: 当源对象和新对象被销毁时,它们都会尝试释放相同的动态分配的内存区域,从而导致程序崩溃或未定义行为。
  2. 资源泄漏: 如果只销毁了源对象或新对象中的一个,而另一个对象仍然存在,则动态分配的内存区域将无法被释放,从而导致资源泄漏

深拷贝(Deep Copy)

深拷贝是指在创建新对象时,不仅复制源对象的非静态数据成员的值,还为指针类型的数据成员分配新的动态内存区域,并将源对象中指针指向的数据复制到新分配的内存区域中。这样,源对象和新对象就拥有独立的动态分配的内存区域。

深拷贝可以避免浅拷贝可能导致的资源重复释放和资源泄漏问题,但是它需要更多的内存和复制开销

Q:拷贝构造函数拷贝是深拷贝还是浅拷贝?

A:拷贝构造函数默认执行的是浅拷贝（shallow copy），但你可以显式地定义它来执行深拷贝(deep copy)

零拷贝

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

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

例如vector的emplace_back()方法

什么时候合成构造函数

没有任何构造函数，但他含有一个成员对象，该成员对象含有默认构造函数

没有任何构造函数的类派生自一个带有默认构造函数的基类

带有虚函数的类

含有虚基类

如何禁止自动生成拷贝构造函数

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

什么时候合成拷贝构造函数

被当做参数交给某个函数

如果返回的对象是一个函数参数或类的成员变量，而不是局部对象，则会调用拷贝构造函数

没有拷贝构造函数，但是含有一个类类型的成员变量，该类型含有拷贝构造函数

没有拷贝构造函数，但是该类继承自含有拷贝构造函数的基类

带有虚函数的类

含有虚基类

注意：返回一个局部对象，编译器会优先调用移动构造函数来创建返回值，而不是拷贝构造函数

为什么拷贝构造函数必须传引用不能传值

1
2
3
4
5
6
7
8
9
10
11
12
13
class MyClass {
public:
    MyClass() { /* ... */ }
    MyClass(MyClass obj) { /* ... */ } //错误的定义方法
};
MyClass obj1;
MyClass obj2(obj1);  // 调用拷贝构造函数

class MyClass {
public:
    MyClass() { /* ... */ }
    MyClass(const MyClass& obj) { /* ... */ } //正确的定义方法
};

这里发生的事情是:

  1. obj1 被创建。
  2. 为了创建 obj2,拷贝构造函数 MyClass(MyClass obj) 被调用。
  3. 但是,为了将 obj1 作为参数传递给拷贝构造函数,obj1 需要被复制,因为参数是按值传递的。
  4. 为了复制 obj1,拷贝构造函数 MyClass(MyClass obj) 需要被调用。
  5. 为了将 obj1 作为参数传递给这个新的拷贝构造函数调用,obj1 需要再次被复制。
  6. 这个过程会无限地重复下去,导致无限递归和栈溢出。

为了避免这个问题,拷贝构造函数应该接受一个对象的引用作为参数，这是 C++ 语言的一个基本规则和惯用法（这个问题很类似于在析构函数里用delete this）

模板问题

模板原理

模板的底层实现机制称为模板实例化。模板本身不是直接编译成机器代码的，而是在编译器遇到模板使用时（例如，通过指定模板参数来创建对象或调用函数）【两次编译】在声明的地方对模板代码本身进行编译，在调用的地方对参数替换后的代码进行编译

  • 函数模板实例化：当你使用特定类型调用一个函数模板时，编译器会生成一个该类型的特定版本的函数。如果你用相同的类型参数再次调用该函数模板，编译器通常会重用之前生成的实例。这意味着对于每一种类型的函数调用，编译器都可能生成一个专门的函数实例。
  • 类模板实例化：类模板的实例化过程与函数模板类似。当你声明一个类模板的实例（即对象）时，需要为模板参数提供具体的类型。编译器随后为这些具体类型生成一个特定的类定义。每个不同的参数化类型都会生成一个新的类实例。
1
2
3
4
5
template <typename T>

bool compare(const T& a, const T& b) {
	return a < b;
}

模板类和模板函数的区别

函数模板的实例化是由编译程序在处理函数调用时自动完成的，而类模板的实例化必须由程序员在程序中显式地指定。即函数模板允许隐式调用和显式调用而类模板只能显示调用。在使用时类模板必须加，而函数模板不必。

模板的声明和实现通常写在哪

通常都放在头文件中，这是因为模板需要在编译时实例化。如果编译器在处理模板使用（即实例化）的文件时看不到模板定义，它就无法生成模板实例的代码。将模板的声明和定义分离到不同的文件中会导致链接错误，因为编译器在实例化模板时找不到模板定义，所以不能分开放。

引用与指针

二者区别

  • 指针是一个变量，存储地址，引用是别名

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

  • 指针可以为空，引用必须初始化

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

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    void f(int* a) {
    	a = new int(10);
        //	delete *a;
    	//  *a = new int(10);
        // 要修改 a 指向的指针所指向的整数，使用 **a。
        // 要修改 a 指向的指针本身（即让它指向一个新的整数），使用 *a
    	cout<<a<<endl;
    }

    int main() {
    	int *v = new int(5);
    	cout << *v << endl;
    	cout << v << endl;
    	f(v);
    	cout << v << endl;
    	cout<<*v<<endl;
    	return 0;
    }
    5
    00000232C16B2E30
    00000232C16AC870
    00000232C16B2E30
    5

Q：什么时候用引用什么时候用指针？

A：需要返回局部变量的内存时用指针，返回局部变量的引用没有意义，需要传递类对象作为参数时需要使用引用

指针参数传递&引用参数传递

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

引用参数传递过程中，被调函数的形式参数也作为局部变量在栈中开辟了内存空间，但是这时存放的是由主调函数放进来的实参变量的地址，提高函数调用和运行的效率（避免拷贝构造副本）

相似之处：

  • 都可以用来修改外部变量的值。
  • 都是通过传递地址来实现的，相比值传递有更好的性能，尤其是对于大型对象。

不同之处：

  • 安全性：引用更安全，因为它们保证了引用的对象一定存在（除非你非常努力地去破坏这一点）。指针可以为空，使用前需要检查是否为空。
  • 可选性：指针可以是 nullptr，这允许表示“没有对象”或“可选”语义。引用必须绑定到一个实际的对象。
  • 语法：引用的语法更简洁，不需要使用 *（解引用）和 &（取地址）操作符。
  • 重新赋值：指针可以在其生命周期内改变指向的对象，而引用一旦初始化后就不能被改变指向另一个对象。

指针分辨

1
2
3
4
int *p[10]
int (*p)[10]
int *p(int)
int (*p)(int)

右左法则：

使用右左法则时，你从变量名开始，然后根据优先级（括号 > 数组/函数 > 指针）向右看，如果到达声明的末尾，就转向左边继续

int *p[10]

  • 分析: 首先看到的是 []，表示 p 是一个数组；然后移动到左边，看到 *，表示数组的元素是指针；最后到最左边，看到 int，表示这些指针指向整型数据。
  • 结论: p 是一个有10个元素的数组，每个元素是指向 int 类型数据的指针。
  • 类型: int *[]

int (*p)[10]

  • 分析: 首先看到的是 (*p)，括号表示 p 是被 * 解引用的，所以 p 是一个指针；然后外面是 []，表示这个指针指向的是一个数组；最后是 int，表示数组的元素是整型数据。
  • 结论: p 是一个指针，指向一个有10个整型元素的数组。
  • 类型: int (*)[]

int *p(int)

  • 分析: 这是一个函数声明。首先看到的是 (int)，表示有一个整型参数的函数；然后到左边，看到 *p，这里 p 是函数名，* 表示函数返回的是指针；最后到最左边，int 表示这个指针指向整型数据。
  • 结论: p 是一个函数，接受一个整型参数，返回一个指向整型数据的指针。
  • 类型: int *(int)

int (*p)(int)

  • 分析: 首先看到的是 (*p)，括号里的 * 表示 p 是一个指针；外面的 (int) 表示这个指针指向的是一个接受整型参数的函数；最后是 int，表示这个函数返回整型数据。
  • 结论: p 是一个指针，指向一个函数，该函数接受一个整型参数并返回一个整型数据。
  • 类型: int (*)(int)

左右值引用*

  • 左值：指的是表达式结束后依然存在的对象。左值可以出现在赋值表达式的左侧。例如，变量、对数组元素的引用、解引用指针、返回引用的函数调用都是左值。
  • 右值：通常指的是表达式结束就不再存在的临时对象。右值不能出现在赋值表达式的左侧。字面量（除了字符串字面量外）、返回非引用的函数调用、算术表达式的结果都是右值。

左值引用（常规）

右值引用（new）

右值引用能够绑定到一个临时将要被销毁的对象上，避免不必要复制，提升程序性能，同时还能将右值引用的对象的资源移动到另外的对象中去【移动语义】，使得资源转移更加高效。允许函数模板以透明的方式转发参数，保持原有的左值或右值属性【完美转发】

右值引用的主要优点包括：

  1. 支持移动语义：右值引用允许将资源（如动态分配的内存）从一个对象移动到另一个对象，而不是传统的复制，从而提高性能和效率。

    允许对象“窃取”另一个对象的资源而不是拷贝它们

    1
    std::vector<int> v = std::move(otherVector);

    std::move将otherVector转换为一个右值引用，这允许v的构造函数接管otherVector的内部数据，而不是复制它们。otherVector在操作后变为处于有效但不可预测的状态，并且应该不再使用

  2. 可用于完美转发：右值引用可以用于实现完美转发，即在函数模板中将参数以原始形式传递给其他函数，保留参数的值类别（左值或右值）【即左值被处理后仍然是左值】

    1
    2
    3
    4
    5
    template<typename T>
    void wrapper(T&& arg) {
        // 将arg完美转发给另一个函数
        otherFunction(std::forward<T>(arg));
    }

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <utility> // for std::move

// 定义一个类
class MyObject {
public:
    MyObject() { std::cout << "Default constructor\n"; }
    MyObject(const MyObject&) { std::cout << "Copy constructor\n"; }
    MyObject(MyObject&&) noexcept { std::cout << "Move constructor\n"; }
};

// 接受右值引用参数的函数
void processObject(MyObject&& obj) {
    // process the object
}

int main() {
    MyObject obj1; // 调用默认构造函数
    MyObject obj2(obj1); // 调用拷贝构造函数

    // 创建临时对象，并传递给 processObject 函数
    processObject(MyObject());

    // 使用 std::move 将左值转换为右值
    processObject(std::move(obj1));

    return 0;
}

MyObject 类有一个移动构造函数，当创建临时对象并将其传递给 processObject 函数时，会调用移动构造函数。同时，通过使用 std::move 将左值 obj1 转换为右值后，也会调用移动构造函数

传递参数时引用和指针的选择

需要返回函数内局部变量的内存的时候用指针，使用指针传参需开辟内存

对栈空间大小比较敏感（比如递归）的时候使用引用

类对象作为参数传递的时候使用引用

智能指针

智能指针是一个类，指向动态分配对象，负责自动释放动态分配的对象，防止内存泄漏

1
2
3
// std::unique_ptr
// std::shared_ptr 
// std::weak_ptr

std::unique_ptr：是一种独占所有权的智能指针，意味着同一时间内只能有一个unique_ptr指向给定资源。当unique_ptr离开作用域时，它指向的对象会被自动销毁。这种智能指针不允许复制，确保了资源的独占性，但它允许移动，使得资源的所有权可以转移

std::shared_ptr：是一种共享所有权的智能指针，允许多个shared_ptr实例指向同一个对象。内部使用引用计数机制来跟踪有多少个shared_ptr共享同一个资源。当最后一个指向对象的shared_ptr被销毁时，对象会被自动删除。shared_ptr适用于需要通过多个指针访问同一资源的情况。shared_ptr内部的引用计数是线程安全的，但是对象的读取需要加锁

std::weak_ptr：是一种不拥有对象的智能指针，它设计用来解决shared_ptr间的循环引用问题。weak_ptr指向shared_ptr管理的对象，但不增加引用计数。因此，weak_ptr不会阻止其指向的对·象被销毁。通常，weak_ptr用于临时访问shared_ptr管理的对象，而不希望对对象的生命周期产生影响。可以通过lock函数检查对象是否失效，未失效则转换到shared_ptr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <memory>

int main() {
    std::unique_ptr<int> ptr = std::make_unique<int>(10);
    std::cout << *ptr << std::endl; // 输出: 10
    ...
    
    // ptr会在这里自动释放内存
}

int main() {
    std::shared_ptr<int> ptr1 = std::make_shared<int>(10);
    std::shared_ptr<int> ptr2 = ptr1; // ptr2现在与ptr1共享所有权

    std::cout << *ptr1 << std::endl; // 输出: 10
    std::cout << ptr1.use_count() << std::endl; // 输出: 2，因为有两个shared_ptr指向同一个对象
    // ptr1和ptr2会在这里自动释放内存
}

int main() {
    std::shared_ptr<int> sharedPtr = std::make_shared<int>(10);
    std::weak_ptr<int> weakPtr = sharedPtr;

    if (auto tempSharedPtr = weakPtr.lock()) { // 尝试获取一个shared_ptr
        std::cout << *tempSharedPtr << std::endl; // 输出: 10
        // tempSharedPtr会在这里自动释放内存
    } else {
        std::cout << "对象已被销毁" << std::endl;
    }
}

循环引用：指两个或多个对象相互持有对方的强引用（如 shared_ptr），导致这些对象的引用计数永远不会降为零，从而造成内存泄漏。a 和 b 就形成了循环引用。当 a 和 b 离开作用域时，它们的引用计数都是 2，因为它们分别被对方持有一次引用。结果是，a 和 b 的引用计数永远不会降到 0，它们占用的内存就无法被释放，导致内存泄漏

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 智能指针的循环引用 导致内存泄漏
class A {
public:
    std::shared_ptr<B> b_ptr;
};

class B {
public:
    std::shared_ptr<A> a_ptr;
};

std::shared_ptr<A> a = std::make_shared<A>();
std::shared_ptr<B> b = std::make_shared<B>();
a->b_ptr = b;
b->a_ptr = a;

拷贝

当使用一个智能指针来初始化另一个智能指针时,会调用智能指针的拷贝构造函数。不同的智能指针类型,其拷贝构造行为也不尽相同:

  • std::unique_ptr: 由于unique_ptr是独占所有权的,不允许拷贝构造,只能进行移动构造。
  • std::shared_ptr: 拷贝构造会使新的shared_ptr与原shared_ptr共享同一个控制块,从而共享对象的所有权。引用计数会加1。
  • std::weak_ptr: 拷贝构造不会影响引用计数,新旧weak_ptr指向同一个控制块。

赋值

对智能指针进行赋值操作时,行为也因类型而异:

  • std::unique_ptr: 不允许普通的赋值操作,只能通过移动赋值转移所有权。
  • std::shared_ptr: 赋值后,两个shared_ptr共享同一个控制块,引用计数会加1。
  • std::weak_ptr: 赋值不会影响引用计数

总结

拷贝 赋值
shared_ptr T T
unique_ptr F F
weak_ptr T T

auto_ptr

C++98 引入的一种智能指针,可以自动管理动态分配（使用 new）的对象的生命周期，以避免内存泄漏,当 std::auto_ptr 的实例离开作用域时，它会自动删除所管理的对象. 由于缺陷建议被3大智能指针替代

std::auto_ptr 的主要问题:

  1. 所有权转移：std::auto_ptr 在进行拷贝或赋值时，会发生所有权的转移。这意味着原 std::auto_ptr 会失去对对象的所有权（变为 nullptr），而新的 std::auto_ptr 获得所有权。这种行为很容易导致意外的所有权转移，造成资源管理上的困惑。
  2. 容器兼容性：由于所有权转移的行为，std::auto_ptr 不能安全地用于标准容器（如 std::vector、std::list 等）。尝试存储 std::auto_ptr 的拷贝在容器中会导致未定义行为，因为容器操作经常需要元素的复制和赋值。
  3. 多线程问题：std::auto_ptr 没有考虑到多线程环境中的安全性问题。其设计不包含对并发访问的保护，这在多线程程序中可能会导致数据竞争和其他同步问题。

野指针 vs 悬空指针

野指针（Wild Pointer）

野指针是指未初始化的指针。其指向的内存地址是不确定的，因为它没有被明确初始化为NULL或指向有效的内存地址。使用野指针的结果是不可预测的，因为它可能指向任何内存地址，包括系统保留的内存。尝试访问或操作野指针所指向的内存通常会导致不可预测的行为，包括程序崩溃、数据损坏或者安全漏洞。

悬空指针（Dangling Pointer）

悬空指针是指向了一块已经被释放的内存的指针。当使用例如free或delete操作释放了一块内存之后，原本指向那块内存的指针就成了悬空指针。与野指针不同，悬空指针之前是指向有效内存的，但在内存释放后继续使用它就变得危险了。因为那块内存可能已经被重新分配给其他用途，对悬空指针的引用或操作可能会导致数据损坏或者不稳定的行为。

this指针

概念此处不再叙述，详情在前面章节

Q: 什么时候被创建

A: this在成员函数的开始执行前构造，在成员的执行结束后清除

Q: 存储位置？

A：this指针会因编译器不同而有不同的放置位置

Q: this如何找到需要调用的函数的?

A: this指针的传递实质上是通过函数参数的首参数（很像python的self）进行传递。this指针使得成员函数能够知道它们是为哪个对象的实例操作

Q: this指针是如何访问类中的变量的？

A: 成员函数内部访问成员变量时,编译器会隐式地将其转换为通过this指针的访问.编译器在大多数情况下会自动处理对成员变量的访问,将其转换为通过this指针的访问.

RAII

Resource Acquisition Is Initialization(RAII)

核心思想是：在对象的生命周期内获取所需的资源，并在对象销毁时释放这些资源。这种方式利用了C++的构造函数和析构函数自动调用的特性，确保资源使用安全且高效，这也是为什么C++比C安全的原因之一。

RTTI

Run Time Type Identification

通过运行时类型识别，程序能够使用基类的指针或引用来检查着这些指针或引用所指的对象的实际派生类型

  • typeid操作符，返回指针和引用所指的实际类型；

  • dynamic_cast操作符，将基类类型的指针或引用安全地转换为其派生类类型的指针或引用

OO

封装:信息隐藏

继承:继承是使用已存在的类的定义作为基础建立新类

多态

  • 多态:发出的方法调用在编程时并不确定，而是在程序运行期间才确定
  • 多态是以封装和继承为基础的。
  • C++ 多态分类及实现：
    1. 重载多态（Ad-hoc Polymorphism，编译期）：函数重载、运算符重载
    2. 子类型多态（Subtype Polymorphism，运行期）：虚函数
    3. 参数多态性（Parametric Polymorphism，编译期）：类模板、函数模板
    4. 强制多态（Coercion Polymorphism，编译期/运行期）：基本类型转换、自定义类型转换

静态多态 - 函数重载

动态多态 -

  • 虚函数：用 virtual 修饰成员函数，使其成为虚函数
  • 动态绑定：当使用基类的引用或指针调用一个虚函数时将发生动态绑定

注意：

  • 可以将派生类的对象赋值给基类的指针或引用，反之不可
  • 普通函数（非类成员函数）不能是虚函数
  • 静态函数（static）不能是虚函数
  • 构造函数不能是虚函数（因为在调用构造函数时，虚表指针并没有在对象的内存空间中，必须要构造函数调用完成后才会形成虚表指针）
  • 内联函数不能是表现多态性时的虚函数

友元

友元函数和友元类

  • 能访问私有成员
  • 破坏封装性
  • 友元关系的单向性
  • 友元关系不可传递（不可被继承不可被传递）
  • 友元关系的单向性
  • 友元声明的形式及数量不受限制

锁

  1. std::mutex:

    • 最基本的互斥锁。
    • 提供了排他性访问，即一次只有一个线程可以持有锁。
    • 使用 lock() 加锁，使用 unlock() 解锁。

  2. std::recursive_mutex:

    • 递归互斥锁，允许同一个线程多次获取同一互斥锁。
    • 对于递归函数或循环中需要多次加锁的情况很有用。

  3. std::timed_mutex 和 std::recursive_timed_mutex:

    • 这些锁提供了基于时间的锁定功能。
    • 允许尝试在指定的时间段内获取锁。
    • 如果在指定时间内无法获得锁，线程可以停止等待，执行其他操作。

  4. std::shared_mutex (自 C++14 开始支持, 在 C++17 中更名为 std::shared_timed_mutex):

    • 允许多个线程同时读取共享数据，但写入时需要独占访问。
    • 适用于读多写少的场景，可以提高并发性。

    【读写锁】

  5. std::lock_guard:

    • 是一个作用域锁，使用 RAII（资源获取即初始化）方式管理 std::mutex。
    • 当 std::lock_guard 对象创建时自动加锁，当作用域结束时自动解锁，避免忘记解锁的问题。

  6. std::unique_lock:

    • 比 std::lock_guard 更灵活的作用域锁。
    • 可以在生命周期内多次锁定和解锁。
    • 支持条件变量 std::condition_variable。

  7. std::scoped_lock (自 C++17 引入):

    • 改进版的作用域锁，可以一次锁定多个互斥器。
    • 提供了死锁避免算法，如采用锁定多个互斥器时的避免死锁技巧。

C++11引入哪些新特性

智能能指针、移动语义、右值引用 etc

经典排序

可能会针对个人提出问题

语言方面

C# 和 C++区别

C#

  • C#通常运行在托管环境中，例如.NET Framework或.NET Core。它依赖于CLR（Common Language Runtime）来执行代码，并使用CIL（Common Intermediate Language）作为中间语言
  • C#具有自动垃圾回收机制，开发人员不需要手动释放内存。CLR会周期性地检查不再使用的对象，并自动释放它们所占用的内存
  • C#通过.NET Core实现了跨平台支持

GC机制：

标记(Mark:找出所有引用不为0(live)的实例) → 计划(Plan:判断是否需要压缩) → 清理(Sweep:回收所有的free空间) → 引用更新(Relocate:将所有引用的地址进行更新) → 压缩(Compact:减少内存碎片)

C++

  • C++可以编译为本地机器代码，不依赖于特定的运行时环境
  • C++需要手动管理内存，开发人员需要显式地分配和释放内存，避免内存泄漏和野指针等问题
  • C++本身是跨平台的，可以通过适当的编译器和工具链在各种平台上进行开发和运行

C#装箱拆箱机制

装箱（Boxing）：

  • 装箱是将值类型转换为引用类型的过程。
  • 当将值类型转换为 object 或任何引用类型时，就会发生装箱。
  • 装箱会将值类型的实例包装在一个堆分配的对象中，这个对象可以被当作引用类型使用，但实际上仍然包含了值类型的数据。
  • 装箱操作会引起性能开销，因为需要在堆上分配内存空间，并且可能会导致额外的垃圾回收压力

拆箱（Unboxing）

  • 拆箱是将引用类型转换为值类型的过程。
  • 当从 object 或任何引用类型中提取值类型的值时，就会发生拆箱。
  • 拆箱会从堆分配的对象中提取值类型的实例，并将其转换为相应的值类型。
  • 拆箱操作可能会导致类型转换异常（InvalidCastException），因此在进行拆箱时需要注意目标值类型是否与实际值类型匹配。

C# 编译机制

源代码->编译为托管模块->托管模块合并为程序集（IL&元数据）->加载CLR（JIT对IL执行编译）->执行程序据代码

IL

IL（Intermediate Language）是.NET平台中的一种中间语言，也称为CIL（Common Intermediate Language），它是.NET程序的一种中间表示形式

CLR

CLR（Common Language Runtime）是.NET平台的核心组件，它负责在运行时执行IL代码，并保证应用和底层操作系统之间必要的分离，CLR提供了以下功能

  1. 虚拟机：CLR包含一个IL解释器和一个即时编译器（JIT编译器），它负责将IL代码转换为机器码，并在运行时执行这些机器码。
  2. 垃圾回收：CLR提供了自动垃圾回收（Garbage Collection）功能，负责管理.NET程序的内存，自动释放不再使用的对象，减少内存泄漏和野指针等问题。
  3. 类型安全检查：CLR在运行时对IL代码进行类型安全检查，确保类型转换和操作的正确性，提高程序的稳定性和安全性。
  4. 异常处理：CLR提供了强大的异常处理机制，允许开发人员捕获和处理异常，保护程序免受意外错误的影响。

C# 委托

在 C# 中，委托（Delegate）是一种类型，代表了对方法的引用。委托可以用来声明、创建和调用方法的实例，可以将委托看作是函数指针的类型安全版本。

  • 委托是类型安全的，它们在编译时会进行类型检查，确保委托实例只能指向与其声明的签名兼容的方法
  • 委托可以组合多个方法，形成委托链。当调用这个委托时，所有链中的方法依次被调用

delegate：可以指定返回类型的委托

action：无返回类型泛型委托

Func：必须有返回值的泛型委托

predict：返回值为bool类型的委托

C# List queue dictionary linkedList

List 动态数组 queue 动态数组 dictionary hash_table linkedlist 双向链表 sortedDictionary RBTree sortedList RBTree

C vs C++

  1. 面向对象支持：C++是一种面向对象的编程语言，支持类、继承、多态等面向对象的特性。而C语言则是一种面向过程的编程语言，没有直接支持面向对象的特性。
  2. 扩展性和封装性：由于支持面向对象编程范式，C++提供了更丰富的特性和功能，可以实现数据与方法的封装，并支持继承和多态等机制。这使得代码可重用性更强、模块化更好，并能够构建大型复杂软件系统。相比之下，C语言相对简单，更适合于较小规模的项目或者需要对硬件进行底层操作的场景。
  3. 标准库差异：C标准库主要提供了基本输入输出、字符串处理等功能函数。而C++标准库除了包含了所有C标准库函数外，还添加了对面向对象特性（如容器、算法）的支持。
  4. 异常处理机制：C++引入了异常处理机制，在程序出现错误时可以抛出异常并在适当位置进行捕获和处理。而C语言没有内置的异常处理机制，错误通常通过返回特定值或使用全局变量来处理。
  5. 编译器支持：C++编译器一般也可以编译C代码，因为C++是在C的基础上发展起来的。但是C编译器不一定能够完全支持C++语法和特性。

计网

OSI TCP/IP

物理层 传输原始比特流
数据链路层 负责在相邻节点间的可靠传输，包括帧的传输、物理地址寻址和错误检测
网络层 负责数据包从源到目的地的传递和路由选择
传输层 负责提供端到端的可靠传输服务
会话层 负责建立、管理和终止会话
表示层 负责数据的表示、编码和解码，包括数据压缩和加密
应用层 提供网络服务给最终用户的应用程序
链路层 负责在相邻节点间的可靠传输，包括帧的传输、物理地址寻址和错误检测
网络层 负责数据包从源到目的地的传递和路由选择
传输层 负责提供端到端的可靠传输服务
应用层 结合了OSI模型的会话层、表示层和应用层，负责处理特定的应用程序细节

HTTP

1.0:短链接

1.1:长连接，传输复用

2.0:多路复用

TCP相关

三次握手和四次挥手

3次握手

syn=1, seq =x ->

syn=1,seq=y,ack=x+1,ACK=1 <-

seq = x+1, ack = y+1 ->

Q：两次握手为什么不行？

A：假设client第一次发包超时，重传，服务器收到第二次重传的，回复，准备建立连接，此时超时包到达，服务器回复准备建立连接，但是client将抛弃这个回复。

4次挥手

fin=1,seq = u->

seq = v ,ack=u+1 <-

…

seq = w , ack = u+1<-

seq = u+1, ack = w+1->

Q:为何4次

A：任何一方都可以在数据传送结束后发出连接释放的通知，待对方确认后进入半关闭状态。当另一方也没有数据再发送的时候，则发出连接释放通知，对方确认后就完全关闭了TCP连接

2MSL

等待 2MSL 的真正目的是为了避免前后两个使用相同四元组的连接中的前一个连接的报文干扰后一个连接，换句话说，就是为了让此次 TCP 连接中的所有报文在网络中消失**[等待 2MSL 可以保证 A 发送的最后一个 ACK，和 B 发送的最后一个 FIN 都在网络中消失]**

拥塞控制算法[区别流量控制]

慢启动

cwnd窗口大小接受一个ACK则以指数上升

拥塞避免

cwnd大于阈值进入拥塞避免，cwnd呈线性上升

快恢复

3个ACK则快恢复，降低cwnd为当前的阈值的1/2继续线性增长

超时

若超时则进入到慢启动

*拥塞控制目的是防止过多的数据注入到网络中，避免出现网络负载过大的情况

*流量控制目的是接收方通过TCP头窗口字段告知发送方本方可接收的最大数据量，为的是不让报文淹没对方

TCP vs UDP

  • TCP是面向连接的，UDP是无连接的
  • TCP是可靠的，UDP是不可靠的
  • TCP是面向字节流的，UDP是面向报文的
  • TCP只支持点对点通信，UDP支持一对一，一对多，多对多
  • TCP报文首部20个字节，UDP首部8个字节
  • TCP有拥塞控制机制，UDP没有
  • TCP协议下双方发送接受缓冲区都有，UDP并无实际意义上的发送缓冲区，但是存在接受缓冲区

TCP如何保证可靠

  • 确认和重传：接收方收到报文就会确认，发送方发送一段时间后没有收到确认就会重传。
  • 数据校验：TCP报文头有校验和，用于校验报文是否损坏。
  • 数据合理分片和排序：tcp会按最大传输单元(MTU)合理分片，接收方会缓存未按序到达的数据，重新排序后交给应用层。而UDP：IP数据报大于1500字节，大于MTU。这个时候发送方的IP层就需要分片，把数据报分成若干片，是的每一片都小于MTU。而接收方IP层则需要进行数据报的重组。由于UDP的特性，某一片数据丢失时，接收方便无法重组数据报，导致丢弃整个UDP数据报。
  • 流量控制：当接收方来不及处理发送方的数据，能通过滑动窗口，提示发送方降低发送的速率，防止包丢失。
  • 拥塞控制：当网络拥塞时，通过拥塞窗口，减少数据的发送，防止包丢失

OS

内存管理

虚拟技术

总述

主要有两种虚拟技术：时（时间）分复用技术和空（空间）分复用技术。

多进程与多线程：多个进程能在同一个处理器上并发执行使用了时分复用技术，让每个进程轮流占用处理器，每次只执行一小个时间片并快速切换。

虚拟内存使用了空分复用技术，它将物理内存抽象为地址空间，每个进程都有各自的地址空间。地址空间的页被映射到物理内存，地址空间的页并不需要全部在物理内存中，当使用到一个没有在物理内存的页时，执行页面置换算法，将该页置换到内存中

虚拟内存

内存管理技术，它将计算机硬盘空间作为临时的扩展内存，以便在主存储器（RAM）不足时，能够支持系统运行。虚拟内存的主要目的是扩展可用的物理内存大小，使得系统能够运行更大的程序或者同时运行多个程序，而无需担心内存不足的问题。

分段：

在分段技术中，程序的地址空间被划分成不同长度的段，每个段对应于不同的功能或数据，操作系统根据程序的需要将段加载到主存或硬盘中

产生外部碎片，不产生内部碎片

分页：

在分页技术中，主存和硬盘被划分成固定大小的页，操作系统将程序的地址空间也划分成同样大小的页，并根据需要将页从硬盘加载到主存中

产生内部碎片，不产生外部碎片

页面置换算法

OPT：每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面

FIFIO：每次选择淘汰的页面是最早进入内存的页面【发生缺页时的置换算法采用FIFO（先进先出）算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象】

LRU：每次淘汰的页面是最近最久未使用的页面

CLOCK：通过访问位进行选择换入换出

CLOCK改：新增修改位

算法规则 优缺点
OPT 优先淘汰最长时间内不会被访问的页面 缺页率最小，性能最好;但无法实现
FIFO 优先淘汰最先进入内存的页面 实现简单;但性能很差，可能出现Belady异常
LRU 优先淘汰最近最久没访问的页面 性能很好;但需要硬件支持，算法开销大
CLOCK (NRU) 循环扫描各页面 第一轮淘汰访问位=0的，并将扫描过的页面访问位改为1。若第-轮没选中，则进行第二轮扫描。 实现简单，算法开销小;但未考虑页面是否被修改过。
改进型CLOCK (改进型NRU) 若用(访问位，修改位)的形式表述，则 第一轮:淘汰(0,0) 第二轮:淘汰(0,1)，并将扫描过的页面访问位都置为0 第三轮:淘汰(1, 0) 第四轮:淘汰(1, 1) 算法开销较小，性能也不错

进程&线程

区别

表看看就行

进程 线程 协程
定义 资源分配和拥有的基本单位 程序执行的基本单位 用户态的轻量级线程，线程内部调度的基本单位
切换情况 进程CPU环境(栈、寄存器、页表和文件句柄等)的保存以及新调度的进程CPU环境的设置 保存和设置程序计数器、少量寄存器和栈的内容 先将寄存器上下文和栈保存，等切换回来的时候再进行恢复
切换者 操作系统 操作系统 用户
切换过程 用户态->内核态->用户态 用户态->内核态->用户态 用户态(没有陷入内核)
调用栈 内核栈 内核栈 用户栈
拥有资源 CPU资源、内存资源、文件资源和句柄等 程序计数器、寄存器、栈和状态字 拥有自己的寄存器上下文和栈
并发性 不同进程之间切换实现并发，各自占有CPU实现并行 一个进程内部的多个线程并发执行 同一时间只能执行一个协程，而其他协程处于休眠状态，适合对任务进行分时处理
系统开销 切换虚拟地址空间，切换内核栈和硬件上下文，CPU高速缓存失效、页表切换，开销很大 切换时只需保存和设置少量寄存器内容，因此开销很小 直接操作栈则基本没有内核切换的开销，可以不加锁的访问全局变量，所以上下文的切换非常快
通信方面 进程间通信需要借助操作系统 线程间可以直接读写进程数据段(如全局变量)来进行通信 共享内存、消息队列

背：

  • 调度：线程是调度的基本单位（PC，状态码，通用寄存器，线程栈及栈指针）；进程是拥有资源的基本单位（打开文件，堆，静态区，代码段等）。
  • 并发性：一个进程内多个线程可以并发（最好和CPU核数相等）；多个进程可以并发。
  • 拥有资源：线程不拥有系统资源，但一个进程的多个线程可以共享隶属进程的资源；进程是拥有资源的独立单位。
  • 系统开销：线程创建销毁只需要处理PC值，状态码，通用寄存器值，线程栈及栈指针即可

Q：什么时候该用多线程，什么时候该用多进程

A：

  • 频繁修改：需要频繁创建和销毁的优先使用多线程
  • 计算量：需要大量计算的优先使用多线程 因为需要消耗大量CPU资源且切换频繁，所以多线程好一点
  • 相关性：任务间相关性比较强的用多线程，相关性比较弱的用多进程。因为线程之间的数据共享和同步比较简单。
  • 多分布：可能要扩展到多机分布的用多进程，多核分布的用多线程

进程通信方式：

管道、共享内存、消息队列、套接字、信号、信号量

进程状态

1
2
3
创建--->就绪<---------->运行--->终止
	|		 |
	+---<--阻塞---<--+

用户态内核态状态切换

三种方式进行状态切换：系统调用、中断、异常

内核空间比用户空间拥有更高的操作级别，只有在内核空间中才可以调用操作硬件等核心资源。

进程调度算法

FCFS,SJF,最短时间优先,时间片轮转,多级反馈队列

多线程

允许单个程序中同时运行多个任务的技术。在操作系统中，线程是进程内的一个执行路径。与进程相比，线程是更轻量级的执行单元，因为所有的线程共享其父进程的地址空间和资源，而独立的进程则拥有自己独立的地址空间和资源

死锁

  • 死锁检测与死锁恢复
  • 死锁预防（破坏死锁的条件）
  • 死锁避免（银行家算法）

有哪些锁

互斥锁

读写锁

悲观锁

乐观锁

文件系统

B+树，为什么文件索引、数据库索引用B+树形结构存储

  • B+树常被用于文件系统中的索引结构，例如在磁盘上维护文件的目录结构。通过B+树，可以实现对文件的高效查找、插入和删除操作。
  • B+树的平衡性和有序性使得文件系统能够快速定位到目标文件或目录，减少了磁盘IO次数，提高了文件系统的性能和效率。