C/C++：难点总篇

术语

trivial：平凡类型（或称普通类型），STL中对于平凡类型的处理会进行特化，以提高速度。非平凡类型，在创建、销毁，移动时均需要采取最保守的方式，调用用户定义的函数，因此是非平凡的。

这些类型满足：
1. 没有虚函数、虚基类
2. 没有非平凡成员函数、操作符（构造、析构、拷贝、移动、赋值等）
3. 数据成员均是平凡类型
standard-layout：标准布局类型。由于内存布局受编译器、优化等级的影响，因此委员会制定了一个最基础的标准布局类型，这些类型去掉了一些C++特性，用于保证对C等语言的内存布局兼容性。

这些类型满足
1. 没有虚函数和虚基类
2. 所有非静态数据成员都有相同的访问说明符（access specifiers：public/protected/private）
3. 没有与第一个非静态数据成员类型相同的基类（C++不允许相同类型的不同对象地址相同，这一条能避免产生1字节偏移）
4. 没有引用类型的非静态数据成员
5. 满足以下任意一个条件：（保证非静态数据成员地址连续）
  1. 没有非静态数据成员，且具有非静态数据成员的基类不超过一个
  2. 基类均不包含非静态数据成员
6. 所有非静态数据成员、所有基类均是标准布局类型。
POD：简单旧数据类型。同时满足trivial和standard-layout的类型，这些数据类型的内存布局完全是连续的，后定义的成员地址一定高于先定义的成员，可以逐字节进行拷贝。

C++17后对POD进行了划分，is_pod<>将逐渐弃用，取而代之的是根据应用场景需要，使用is_trivial<>、is_standard_layout<>
文本类型：可以在编译期确定布局的类型，包括：
1. void，及其数组
2. 标准类型（Scalar Type，即基本数据类型），及其数组
3. 引用，及其数组
4. 类：具有普通析构，一个或多个constexpr构造函数，没有移动和复制构造函数，且所有非静态数据成员、基类，均需是文本类型。

高级特性

模板编程

模板的类型
- 类模板
- 函数模板
- 类型别名模板
- 变量模板（C++17）
类型萃取
1. 参考
  - type_traits类型萃取
类型擦除
1. 参考
  - C++类型擦除和std::function性能测试

STL

STL是由容器、算法、迭代器、函数对象、适配器、内存分配器这6 部分构成。其中后四部分主要是为了前两个部分服务。

allocator空间配置器

作用：空间配置器主要负责从系统申请/释放存储空间（不一定非得是内存），并调用构造/析构函数。注意std::allocator在C++11、C++20前后都有大的变动（尤其是construct/destroy）。
分配器的核心成员
1. 分配内容物类型：value_type
2. 内容物指针类型：pointer，C++20后应使用std::allocator_traits<>::pointer
3. 容量类型：size_type
4. 迭代器距离类型：difference_type
5. 空间分配：allocate
6. 空间释放：deallocate
7. 内容物构造：construct，C++20后应使用std::allocator_traits<>::construct
8. 内容物析构：destroy，C++20后应使用std::allocator_traits<>::destroy
分配器的工作流程：
1. 由使用者（如容器）调用allocate分配空间
2. 将内存指针，传递给construct
3. construct根据类型信息（是否平凡），决定构造方式
4. 由使用者调用destroy，触发析构，根据类型信息（是否平凡），决定析构方式
5. deallocate回收空间
SGI STL的内存配置器实现：提供了一个更高效率的alloc，它并不属于C++标准，SGI对其进行了封装，其核心特性如下
1. 提供两级配置器：一级是最基础的malloc、free的封装；二级额外实现了一个小对象内存池，对于大对象，仍使用一级配置器。配置器均工作在堆空间。
2. 二级配置器的实现核心
  1. 核心数据结构
```
// 空闲小对象、链表联合体
union obj {
    // 空闲时free_list_link指向下一个空闲obj
    // 当一个对象被释放，则重新加入free_list_link链表中
    union obj * free_list_link;
    // 分配后则存储client_data
    char client_data[1];
}
```
  2. 配置器关键成员：
    1. refill(size_t)：当某个大小的空闲链表不存在时，用chunk_alloc尝试创建区块，并填充到空闲链表中
    2. chunk_alloc(size_t,int&)：尽最大努力分配内存池区块，但实际分配的区块数量可能有变。是整个SGI空间配置器中最复杂的部分：
      1. 剩余的空闲堆完全能满足分配需求，直接分配
      2. 可以分配至少一个，分配，修改并返回实际分配的区块数量
      3. 完全无法直接分配
        
        重点：空闲堆未空，将所有零头分配给空闲链表。因为空闲堆指针将会变动，需要保证在没有空闲堆前提下，再继续下一步。
        
        此时空闲堆已空，尝试malloc向系统申请更多内存
        
        系统没有足够内存，尝试释放一块空闲链表中的不小于当前需求的空闲区块，并递归调用自己（利用自身步骤，修正分配区块数量，或分配零头）。如果也没有空闲区块可以释放，则调用一级配置器（一般情况下，将会可能抛出OOM）
        
        有足够内存，修改空闲堆指针等，递归调用自己
    3. start_free：当前空闲堆起始地址
    4. end_free：当前空闲堆结束位置
    5. heap_size：空闲堆总大小
    6. allocate(size_t)：对小对象，选择适当大小（向上取整到8的倍数）的空闲链表，取空闲块返回，否则返回调用一级配置器
    7. deallocate(void*,size_t)：对小对象，将当前指针所指空间，返回到对应空闲链表中，否则用一级配置器释放
    8. reallocate：
  从chunk_alloc可以看出，SGI内存配置器的内存池并不要求所用内存完全连续，只是每一次向系统申请的内存才连续，但仍然可以统一编入空闲链表中，不影响使用。而每一次空闲堆用尽前，都会保证将所有内存编入适当大小的链表中，保证没有浪费。流程可参考STL-空间配置器分析（内存的配置和释放），博主绘制了流程图
其他内存工具
1. 批量构造：C++标准要求，批量构造必须具备commit or rollback特性，要么全部成功，要么恢复到调用前。
  1. uninitialized_copy(first,last,copy)：将first到last区间内容，拷贝到copy开始的迭代器中。SGI实现同样区分了POD类型和非POD类型，对于普通类型，直接调用拷贝（copy），否则需要调用构造（拷贝构造）。还可以针对char*等，专门进行模板特化，直接用底层内存函数拷贝
  2. uninitialized_fill(first,last,x)、uninitialized_fill_n(first,count,x)：同样是根据是否是POD类型，决定是直接填充（fill、fill_n），还是调用构造。
一些语法
1. placement new：new(p) T(x)，这是一种特殊的new运算符，其使用已分配的地址p，并在其上使用参数x构造T类型实例。
2. ::operator new、::operator delete：当前域的全局new/delete函数。new/delete函数分为运算符，全局函数，类重载函数三种。当用户使用new/delete运算符的时候，实际上发生了，用类重载new申请内存（未定义则用::operator new申请内存），并在此基础上调用类构造函数。
参考:
- 《STL源码剖析》
- GCC 源代码获取
- Cpp reference: allocator

内存管理

上一小节讲了一下allocator的一个基本实现。这一小节从整体上，整理一下malloc/free，和new/delete的处理流程。从一次调用，到最终获得可用的内存，中间所有的库、操作系统、硬件的操作。

库函数以上
malloc库
系统调用
硬件

高性能IO

流
1. 参考：
  - std::streambuf从示例到应用

语法

继承和多态

虚继承：当多继承的多个基类的继承体系中有相同的基类时，可能会出现公共基类成员的重复拷贝，此时会出现空间浪费，而且在使用上也容易出现二义性，因此需要使用虚继承。
- 基本原理：使用虚继承时，类型内部会增加一个vbptr，即虚基类表指针（virtual base table pointer），该指针指向了一个虚表（virtual table），虚表中记录了vbptr与本类的偏移地址；第二项是vbptr到共有基类元素之间的偏移量。（一般来说第一个偏移地址都是0，第二项代表了vbptr地址到共有元素的差）。虚继承的类，及其子类都会保留自己这个类型的vbptr。

右值引用

右值引用出现的原因：
- 有一些值出现在等号右侧，是匿名变量，表面上看起来它们无法取地址，但实际上并不完全。最常见的出现场景是函数的返回值。根据该值的大小，它可能直接出现在一个寄存器内（当然就无法取地址），也可能作为一个临时变量存储函数的返回值、返回的结构体。观察汇编语言可以发现，对于一个寄存器可以存放的情况，函数返回值会直接放在一个寄存器中，在函数外赋值给具名变量时只需要再执行一次mov操作。如果是过长的结构体，则会直接存入到一个指定的内存区域，直观上看就像是写入了一个临时变量（只是没有名字，但实际上是有地址的）。如果外面使用一个变量接收全部，这片内存区域直接就是这个变量，否则就将内存中的部分内容赋值给它。在C语言中，由于没有构造和析构这种生命周期，因此这样的结果是完全可以接受的。
- 但当C++拥有构造和析构之后，问题变得复杂了起来。如果函数返回值依然能够放在一个寄存器内则还好。如果是较长的非平凡的结构体、类，则创建这个临时变量的过程，是会调用构造，形成一个真正完整的变量，而赋值时又会调用复制构造，最后这个临时变量还会进行析构。除了性能问题外，还有一些需要讨论的：
  - 如果类型仍然能在一个寄存器内放得下，则它还是不具有内存空间，就是一个纯右值，无法被取值
  - 如果类型够大，且具有默认构造和析构，也就是什么都不做，此时它是平凡的（trivial），可以只按照C中对待结构体的方式，
  - 如果类型够大且有自定义构造和析构，它实际上是有内存空间的，是一个广义左值。返回值被完整赋值出去，则返回值本身就位于调用方内存栈空间上，是一个普通的左值。而如果返回值只是被部分使用，则一定会在该行语句结束后立刻析构，该返回值就是将亡值。
  - 生命周期，左值在当前代码块结束时析构，将忘值在所属语句结束时立刻析构。
  注一：字面值除了字符串字面值以外，都是纯右值，字符串字面值是一个左值（存储在程序的固定段中），类型是const char[]，注意虽然可以隐式的转换为const char*，但这本质上并不是同一种类型。很明显对二者调用sizeof会有不同的结果。注二：类型转换过程中会产生一个右值。这一点可能被忽略，但当你尝试对一个左值引用赋值一个需做类型转换的对象时，会编译失败。这一点更常见于隐式类型转换发生时。
- 这个时候可以看出，编译器决定返回值直接写入调用方栈空间的具名变量（作为lvalue），还是存入一个匿名临时变量（作为xvalue），是由调用方的代码上下文决定的。只要不能写入一个具名变量，都可以视作是一个右值，它的生命周期将会立刻结束。因此编译器不能接受直接取地址。而且虽然C++提出了引用这一概念，但作为变量的别名，而引用实际上只是指针的语法糖，因此，传统的左值引用也无法绑定将亡值，形如
```
class A {};
A getA() { return A();}
void doSth1(A &a) { /* ... */ }
void doSth2(const A &a) { /* ... */ }

A *a = &getA();          // 编译失败，&要求左值
A &a = getA();           // 编译失败，非常量引用需要绑定到左值
doSth1(getA());           // 显然失败
doSth2(getA());           // 虽然可以，但是不能做任何修改了
```
- 从上面可以看出，如果不能单独处理右值，则每一次对右值的使用都不得不将其保存到一个左值，带来一些不必要的复制构造。或者将其绑定到常量引用，这又限制了使用方式。
使用C++17及以上的版本，会比较难观察到返回值的复制构造，因为编译器已经默认支持了复制消除
右值引用的目标：
- 延长函数返回值等上下文中，右值的生命周期
- 提供完美转发、移动语义的能力
  - 移动语义：支持移动构造函数和移动赋值函数，可以将旧对象的内部成员直接转交给新对象，旧对象内部置空。对于非函数返回值的情况，需要手动调用std::move，将其“转化”为右值（只是在类型强转static_cast）
  - 完美转发：由于右值引用也可以绑定到左值，因此作为函数参数更为灵活，使用forward结合万能引用，能够完成将输入的右值引用转发给需要左值或者右值的情况（详见下面的“万能引用”）
右值引用本身是一个左值，它不仅有名字，实际上仍然可以在等号左边被继续赋值。但要记得它存储的内容是一个右值。
“万能引用”：
- 当我们有了右值引用后，貌似任何时候都可以通过std::move来使用，但是有些时候，我希望能够统一的调用一个wrapper函数，无论左值右值都能接受，而在接口内部，再来通过重载决定更底层的函数，这个时候单纯的右值引用无法满足我们。因为右值引用本身是一个左值。我们丢失了实参的信息。
- 模板类型推导能力，提供了这个功能，一些貌似是右值引用的代码，在部分场合下实际是万能引用，形如
```
// 这里的T &&，就是万能引用
template<typename T>
void testPrint(T && obj) { /* ... */ }

int a = 1;
testPrint(a);               // T被推导为int&
testPrint(std::move(a));    // T被推导为int&&
// 即此时可以同时接受左值和右值
```
  传递左值推导结果是左值引用的原因，是因为当我们参数列表为T &&时，已经告知编译器，结果一定是一个引用，要么是左值引用，要么是右值引用，而此处a是左值，所以只能是左值引用
- 引用折叠：当模板类型参数和函数形参出现引用的引用时，会对引用进行折叠
  - 对于T&&：T是左值引用仍是左值引用，T是右值引用仍是右值引用
  - 对于T&：T无论是什么，结果都是左值引用
- 完美转发：当我们能同时拿到左值引用和右值引用时，接下来的问题就是如何将其向外传递，问题还是在于右值引用形参本身是左值这个问题上，因此我们需要forward
```
// 一种简化实现
template<typename T>
T&& forward(T &param) // 此处折叠的要求，调用的实参必须是左值
{
    // 函数的返回值和此处的static_cast保持相同的引用折叠
    // 由折叠规则可知，输入是左值引用就返回左值引用，同理右值引用
    return static_cast<T&&>(param);
}
```
  std::move无法完成这个要求，因为std::move只能输出右值引用

右值相关的重载和实用场景：

// --- 片段1 ---
void print(string a) {}             // 1
void print(string &a) {}            // 2
void print(const string &a) {}      // 3
void print(string &&a) {}           // 4
void print(const string && a) {}    // 5
// 重载错误，1/3/4/5均可
print("hello world");

// --- 片段2 ---
template<typename T>
void print(T &t){
    // 打印左值的逻辑
}
template<typename T>
void print(T &&t){
    // 打印右值的逻辑
}
template<typename T>
void printWrapper(T &&t){
    // 根据实参的具体引用类型，决定所使用的重载函数
    print(std::forward<T>(t));
}
int a = 1;
printWrapper(a);
printWrapper(std::move(a));

当这五个函数同时实现后，调用时会出现重载错误。
重载函数的选择逻辑
- 优先选择不需要做转型的重载函数
- 右值不会自动绑定到非常量左值引用
- 其他情况下优先情况未确定
第五种几乎没有意义，不要这么用
c语言的历史遗留问题：const int和int不能作为重载函数的区分

关键字解释

static关键字：
- static修饰全局变量：普通非静态全局变量的作用域是整个程序，所有源文件都可见，静态全局变量作用域局限于一个源文件内，防止被其他源文件引用。
- static修饰局部变量：修改了生存期。
- static修饰函数：static普通函数，也限定在当前作用域内（即声明所在的源文件，其他文件不可见），普通函数则是extern的，被引用就可以使用。
- static修饰类内成员：变量的生存周期变为程序开始到退出，变量和函数的作用域变为该类。
auto和decltype：
- auto是根据赋值情况推断实际类型，并会根据相关规则改变类型（去除顶层的const和引用）
- decltype只用于进行内部表达式的类型推断，不会执行内部表达式的实际计算

定义

const和*：核心原则就一句话，const默认作用于其左侧的内容，如果没有，则作用于其右侧的内容
- 因此，为了可读性，推荐的写法是将const统一写于待修饰内容的右侧

指针篇

变量指针

对0地址的使用：0地址不能解引用，但可以用于进行指针相关的地址的运算

// linux内核
struct list_head {
    struct list_head *prev, *next;
}

struct task_struct {
    /*
    ... 
    */
    struct list_head cg_list;
}

// 使用时
struct list_head list;
struct task_struct *t = (task_struct *)( (char *)&list - ((size_t)&((task_struct *)0)->cg_list) );

函数指针

C：

函数签名：即函数的类型，由返回类型+参数类型列表构成。
```
// 函数签名为int(int,int)
int add(int a,int b);
```

创建一个函数指针，需要指明指向的函数的类型。pf附近的括号必须存在，否则变为声明一个返回指针的函数。

// 局部 & 全局变量
int (*pf) (int, int);
pf = add;
pf(100,100); // 使用方式1
(*pf)(100,100); // 使用方式2

// 形参定义
void func1(int pf(int, int)); // 写法1
void func2(int (*pf)(int, int)); // 写法2

创建别名

typedef int (*PF) (int, int);
PF pf_2 = add; // PF定义了一个类型，和类型用法相同

函数指针作为函数返回值

// 阅读方式从自定义名称向外，func是一个函数，形参为(int)
// 返回一个int(int, int)类型的函数指针
int (*func1(int))(int, int);

// 当然并不建议以上写法，过于隐晦
PF func2(int);

C++：

auto特性

int add(int,int);
auto pf1 = add; // auto将会自动解析类型为函数指针
// auto *pf1 = add; // 等价写法
pf1(100,100); // 可以
(*pf1)(100,100); // 可以

函数类型和函数指针类型。decltype仅解析到函数签名。

decltype(add)* pf2 = add; // 正确
decltype(add) pf1 = add; // 错误，类型不对

形参

typedef decltype(add) func_add;
typedef decltype(add)* funcP_add;
void func1(func_add a);
void func2(funcP_add a); // 错误，已有定义

成员函数指针

typedef void(A::*PF1)(); // 必须指定类型别名PF1所属的类
PF1 pf1 = &A::func; // 必须有&
A a;
(a.*pf1)(); // 使用成员函数指针，需要和类型实例关联

由于成员函数指针需要获取类成员函数，因此没有多态性。取到哪个类，就是其对应的实现。即使关联了其子类的实例。

参考
- 函数指针使用总结似乎并不完全正确，等待确认。

const重载

在C++中，提供了对于const的重载能力。这在其他语言中往往是不具备的。见下面的例子。

class Test {
public:
    void func() const {
        // const func
    }

    void func() {

    }
}

int main(){
    Test non_const_test;
    const Test const_test;
    
    non_const_test.func();
    const_test.func(); 
}

注意，const函数是可以作为重载存在的。而在决定重载函数调用时的规则如下

非常量对象，可以调用任意一种重载，优先调用的是非常量函数
常量对象，只能调用常量函数。

注意const函数和形参中带有const并不同，形参中如果使用const，必须是指针或者引用，否则会发生重载错误（实参是传值的时候，无法用const做出重载区分）

void func(const int i) {}
// 错误，函数重复定义
void func(int i) {}

void funcStr(const char *) {}
// 可以
void funcStr(char *) {}

void funcRef(const int&) {}
// 可以
void funcRef(int&) {}

参考C++函数重载(3) - 函数重载中的const关键字

&&重载

和const函数一样，C++允许对右值在重载决议时，使用对应的&&重载版本。例如

struct Foo {
    auto func() && {}
    auto func() {}
}

其他坑

由于C++目前越发庞大，在标准的演化过程中，可能出现一些未定义行为，在编程时需要注意
内存对齐是默认发生的，可以通过__attibute__((packed))禁用，如果想要自定义则可以在aligned()中使用大于0的任何2的幂，代表需要对齐到的字节数（对象的占用大小）。对内存对齐的控制已经进入C++标准定义范围。pragma pack。
注意delete和delete[]的区别，要和new、new[]分别成对使用。delete虽然也会释放等量的内存，但是只会调用一次析构

写在前面

2024年影集

Cpp Concurrency in Action读书笔记

C/C++：内存对象模型

C++ Templates 第二版：读书笔记

Linux：Web和I/O系列书籍读书笔记

Java系列：JVM篇

深入理解Nginx：模块开发与架构解析

《Hadoop权威指南（第四版）》读书笔记

函数式编程：合集