从小白的视角探究 vector 第2章

dustchens

2 改进 vector，实现 Big5

这部分内容我们依旧使用sunrisepeak大佬的代码演示，但在后半段，我们将会深入一些内容

2.1 vector需要什么？

经过第一章的描述，我们现在应该思考vector需要什么，由此我们才能得知vector需要实现什么

整块空间 类比函数栈，它由空间适配器 Allocator提供，申请一整块内存
表现的像数组 vector需要一个size，标定数组的边界
额外的空间 vector是一个动态的数组，它标志着vector的空间可以调整大小，因此需要一个容量capacity

额外的空间，并不是再申请一块内存，而是在整块内存内部，需要区分哪些已经使用，哪些未使用且将来可以使用，一旦突破这个界限，就需要再申请一大块内存进行扩容

经过以上总结，再回看第一章节的内容，可以明显发现一点，只有一个size，这个size既标定了已经使用的数量，又标定了vector能容纳的最大元素数量。这显然是不合理的，即便我们需要把这块空间内都初始化出对象，但依然缺少一个逻辑上能区分已使用量和未使用量的内容。

2.2 添加容量

代码方面我尽量复用之前的，大体讲解可以参照对应的视频讲解，后续讲解我只会说明一些我认为初学者容易不理解的地方

template <typename T, typename Alloc = DefaultAllocator>
class Vector {
public:
    // 此处添加mCapacity_e的初始化
    Vector() : mSize_e { 0 }, mCapacity_e { 0 }, mDataPtr_e { nullptr } { }

    Vector(int size) : mSize_e { 0 }, mCapacity_e { size } {
        // 1. 注意点1
        mDataPtr_e = static_cast<T *>(Alloc::allocate(sizeof(T) * mCapacity_e));
        // 2. 注意点2
        for (int i = 0; i < mCapacity_e; i++, mSize_e++) {
            new (mDataPtr_e + i) T();
        }
    }
    ~Vector() {
        if (mSize_e) {
            // 3. 注意点3
            for (int i = 0; i < mSize_e; i++) {
                (mDataPtr_e + i)->~T();
            }
            Alloc::deallocate(mDataPtr_e, mCapacity_e * sizeof(T));
        }
    }

private:
    int mSize_e;
    int mCapacity_e;
    T * mDataPtr_e;
};

可以看到，大框架基本不变，但是添加了容量后，依旧需要注意语句变化带来的含义

申请空间以容量为标定
初始化一个元素mSize_e就需要增长一个
元素析构以mSize_e为边界

再次对比到函数空间，此时我们就可以理解为什么需要用到new (mDataPtr_e + i) T(); 这样的技巧

在函数中初始化对象，我们可以直接写下 T aaa，不用我们自己管理这个对象在函数空间内部的哪个地方
在vector中，没有这种机制，让对象挨个排列在内部空间中，因此，我们需要手动告诉程序，我们需要在 new(地址) 这个位置，初始化 T() 对象 。正是这个不同之处，需要我们使用到placement new，也就是定位。如果有自动的机制，我们甚至可以直接和在函数内部初始化对象一样，丝毫不用关心在函数空间的哪里有这个对象！

如何销毁内容？

类比到函数栈中，我们已知函数在退出时会自动调用对象的析构函数，因此我们希望vector也在它自身析构时，显式调用已构建对象的析构函数
之所以不需要类似placement new这样的操作，是因为在创建时，需要强制确定内存位置，但是销毁时，我们已经知道了哪些内容已经存在，可以显式直接调用。

capacity的作用

capacity的加入，在目前还看不出区别，这是因为这几个构造函数都是直接让size和capacity相等，但是后续一旦需要再添加元素，产生扩容，那么就会体现出区别。
引入capacity后，我们就需要在脑海中将整块内存划分为不同的区域

已构建对象的内存 [data, size) 这部分内容上已经有了对象，可以看到析构也是以此为界限
未构建对象的内存 [size, capacity) 这部分没有任何内容，构建新内容必须使用placement new这样的技术
需要再次强调placement new技术，只有在裸内存上才能使用，也就是如果已经在一个地方用此技术初始化了一个对象，那么再次使用placement new在同一位置创建一个新内容是不允许的！除非先调用析构函数，将对象销毁，变为裸内存的状态才能继续使用。这部分对于新手来说直接理解依旧是非常抽象的，并且这个行为是未定义行为，也就是编译器不会给你强制警告！
类比到函数中，那就是无法第二次调用对象的构造函数进行初始化！因为构造就已经开启了生命周期，再次使用会产生一些列问题，比如内存泄漏，多次析构等等。
```
graph TD
subgraph 正确方式
    A[已有元素位置: 活对象 T] --> B[调用赋值运算符 *p = val]
    B --> C[对象值更新，无泄漏 ✅]
end

subgraph 错误方式
    A --> D[❌ 直接 placement new 覆盖]
    D --> E[旧对象未析构，资源泄漏<br/>或二次析构风险（未定义行为）]
end
```
```
graph TD
subgraph 正确方式
    S[栈上对象 T x 已构造] --> T[使用赋值 x = val]
    T --> U[对象值更新 ✅]
end

subgraph 错误方式
    S --> V[❌ 尝试第二次调用构造函数]
    V --> W[编译错误：不能直接调用构造函数<br/>或 显式析构后 placement new<br/>导致作用域结束时二次析构]
end
```
接上一条，那么在某一位置已有对象的情况下，除了调用析构函数将对象销毁，变成裸内存，另外的方法就是调用赋值运算符，以更新内容，包括拷贝赋值和移动赋值。这也和我们在函数内使用 = 进行赋值和更新是同一个道理。

flowchart LR
    subgraph stack_frame[函数栈帧]
        V[vector对象\n data / size / capacity]
    end

    subgraph heap_buffer[堆上的连续存储]
        E1[元素0]
        E2[元素1]
        S1[空槽位]
    end

    V --> E1
    V --> E2
    V --> S1

data                     data+size               data+capacity
  ↓                         ↓                         ↓
  ┌─────────────────────────┬─────────────────────────┐
  │   已构造对象区           │    未构造预留区          │
  └─────────────────────────┴─────────────────────────┘

区域	地址范围	对象状态	可执行操作
已构造对象区	`[data, data+size)`	存在活对象	• 改变内容：用拷贝/移动赋值<br>• 若必须整体替换：先析构，再 placement new（一般不推荐）
未构造预留区	`[data+size, data+capacity)`	原始内存（无对象）	• 创建对象：必须通过 placement new 构造<br>• 无“修改”一说，因为没有对象可以修改

这里也可以看出我们类比函数栈的好处，那就是不必拘泥于抽象的、高深的内容，不用一开始就去理解STL标准库的思想
毕竟这是该领域顶级专家的成果，想要短时间内容入门是非常困难的。
但是一旦我们将它和我们日常使用的内容相连，我们就可以通过共性去理解其原理，通过不同之处的探究，带着问题探究其深意

2.3 全部构造函数

此处不会详细讲解3/5/0法则，只需要知道如果我们显式定义了析构函数、拷贝构造函数、拷贝赋值运算符、移动构造函数、移动赋值运算符，其中的任意一项，就需要把这几项全部定义出来（或者删除掉）
简而言之，如果有任意一项资源需要我们手动管理，这几个函数就必须认真对待。因为有手动管理，才需要定义这些内容，而这些内容一旦定义任意一项，移动相关的内容就不会由编译器自动生成，其余的哪怕生成，也是有问题的！

1 构造函数的类型

此处简单讲解一下不同类型构造函数的作用和区别，以及一些隐式的条件

默认构造函数 不需要参数就能调用，用于 ClassT t 或 ClassT t{} 这样声明一个对象，没有参数
同时这个函数还有一系列的规则，包括自动生成、被抑制生成等
普通构造函数 需要提供参数才能调用用于 ClassT t(10) 这样的调用
之所以区分，是因为默认构造函数有一系列特殊规则
复制构造函数 深拷贝 用于ClassT t_copy(other)这样的形式对于有手动管理资源的类，不能使用编译器提供的复制构造，必须自己实现深拷贝，否则只会拷贝指针这样的门牌号，指向同一块内存，产生双重释放的问题
移动构造函数 窃取资源 用于ClassT t_copy(std::move(other))这样的形式将资源从别的对象转移到自身，并且需要切断别的对象对于资源的所有权

注：不需要参数 不代表没有参数，因为还涉及到默认值等问题。且以上调用形式可能存在部分问题，需要后续研究。这里研究的重点还是这几个内容如何实现
注2：std::move 只是代表将对象转换为右值引用的形式，让我们能够调用移动构造函数，但并没有字面意义上的移动功能

1 默认构造函数

在上文中，Vector() : mSize_e { 0 }, mCapacity_e { 0 }, mDataPtr_e { nullptr } { } 就是一个默认构造函数，但是这个函数被我们显式声明了，因为声明了一般的构造函数后，编译器是不会再生成默认构造函数的，除非我们自己再写出来

那这样的函数还是默认构造函数吗？

// 注意此处的参数
Vector(int size = 0) : mSize_e { 0 }, mCapacity_e { size } {
    mDataPtr_e = static_cast<T *>(Alloc::allocate(sizeof(T) * mCapacity_e));
    for (int i = 0; i < mCapacity_e; i++, mSize_e++) {
        new (mDataPtr_e + i) T();
    }
}

这依然是一个默认构造函数

依旧是前文所讲内容，size有一个默认值，无需参数就能调用，符合规则
默认值 需要以后额外补充，大家也可以自行查找相关资料了解
同时这个默认构造函数也可以提供参数调用，但这个问题暂时无法深入

2 普通构造函数

此处划分这两个构造函数的方式可能有问题，希望大家可以指出

Vector(int size) : mSize_e { 0 }, mCapacity_e { size } 完整代码参照上文中出现的

这里的size决定了我们调用的时候必须给出参数才能匹配到该函数，比如用{} 初始的形式，Vector v1{10}; 10代表了初始的容量，以及将这10个空位都初始化上对应的对象
: mSize_e { 0 } 使用了C++11提供的初始化器，可以方便地将成员进行初始化，避免遗漏等问题。需要注意的是，初始化的顺序并不由我们写的顺序决定，不考虑继承等情况下，由成员在声明时的顺序决定

3 复制构造函数

为什么需要深拷贝？

指针这是一切问题的根源，编译器生成的复制构造，只会去复制指针的值，这一段同样对应第一章补充内容，正如函数作用域不会管理指针背后的资源，默认生成的拷贝构造也不会去考虑远在天边的内存。
内存复制 拷贝的主要意义是对资源的拷贝，简单指针复制是无效的，必须手动提供对资源内存的复制，我们希望得到的是另一块独立的内存资源，而不是当前资源的影子。

由此，我们的目标也就很明确了，申请一块大小相同的内容，并在其上一一复制对象

Vector(const Vector& other) : mSize_e {0}, mCapacity { other.mCapacity } {
    mDataPtr_e = static_cast<T *>(Alloc::allocate(sizeof(T) * mCapacity));
    for (int i = 0; i < other.mSize_e; i++, mSize_e++) {
        new (mDataPtr_e + i) T(other.mDataPtr_e[i]);
    }
}

接收参数 const Vector& 复制复制，首先就是要有另一个对象，因此采用引用的方式，同时不会修改也不允许修改另一个对象的内容，因此使用const修饰
size capacity 可以看出，这二者是有区别的，再次反映出了前文的内容。整体容量和已构造元素是要区分开的
placement new new (mDataPtr_e + i) T(other.mDataPtr_e[i]); 需要注意，我们依旧是在裸内存上进行构造，因此仍然需要使用定位new技术

4 移动构造函数

快！

Vector(Vector &&other) : mSize_e { other.mSize_e }, mCapacity { other.mCapacity }, mDataPtr_e {other.mDataPtr_e} noexcept {
    // reset
    other.mSize_e = 0;
    other.mCapacity = 0;
    other.mDataPtr_e = nullptr;
}

接收参数 Vector &&other 移动也是要有另一个对象，因此采用右值引用的方式，同时必须修改另一个对象的内容，所以无需const修饰
浅拷贝 可以看到移动的本质是浅拷贝，但是之前在复制构造时说不能使用浅拷贝，但是此处又使用了浅拷贝，这是为什么？
```
    // reset
other.mSize_e = 0;
other.mCapacity = 0;
other.mDataPtr_e = nullptr;
```
原因在于，我们 “抛弃” 了拿来移动的那个对象，更准确地说，我们宣布另一个对象不再持有资源了。而之前的复制构造，需要两个对象都有资源，这才是关键区别
快快是最关键的好处，因为只复制几个指针和大小容量等内容，是非常迅速的，但是代价就是另一个vector对象失去了资源

关于右值引用请大家自行查阅相关内容。其实就是为了区别调用的函数，调用移动必须要用这种方式。其他方式依旧可以完成这种内部资源转移，但是为了语义上的区分，这样做是最好的

2.4 特殊运算符 =

注意，此处的主体是运算符，而不是构造函数

既然是运算符，区别于构造函数，那就意味着vector对象已经经历过调用构造函数的阶段，也就是初始化成功后，才能调用运算符
既然已经初始化过了，说明对象内部是有内容的
运算符可以出现自赋值的情况比如 vec1 = vec1

以上的注意点，构成了我们接下来两个特殊运算符的要点

运算符类型

复制赋值运算符 类似赋值构造函数
移动赋值运算符 类似移动构造函数

调用方式都相同，使用 = 调用，但是同样，需要用不同的方式去匹配不同的运算符
重写operator=() 其中最重要的就是()内参数的选择
需要有返回值

1 复制赋值运算符

接下来，我们需要根据代码，来分析上文提到的特殊要点

// 1
Vector& operator=(const Vector &other) {
    // 2
    this->~Vector();
    mSize_e = other.mSize_e;
    mCapacity = other.mCapacity;
    mDataPtr_e = static_cast<T *>(Alloc::allocate(sizeof(T) * mCapacity));
    for (int i = 0; i < mSize_e; i++) {
        mDataPtr_e[i] = other.mDataPtr_e[i];
    }
    // 3
    return *this;
}

可以看出，复制赋值运算符，基本沿袭了赋值构造的思路，但是多了释放自身内容和返回的步骤

返回值是vector&
既然已经初始化过，有内容，就必须先释放掉vector对象本身的内容，因此调用了vector本身的析构函数
对this指针，解引用，获得vector对象，匹配上引用返回

this指针内容需要大家自行查阅

以上的代码符合了需要释放自身旧内容、返回对象。但是依旧是有问题的，可以看出漏掉了最关键的自赋值的问题

倘若出现 vec1 = vec1 这样的代码，那么调用之后，在this->~Vector(); 就把自身内容全部释放了，也就是说 vec1 现在变成了一个空对象，所持有的资源消失，这显然不是我们希望看到的

如何做呢？非常简单，也就是如果判断传进来的对象是自身，那就直接返回，否则就执行销毁自身内容并复制的步骤

Vector& operator=(const Vector &other) {
    // 注意
    if(this != &other) {
        this->~Vector();
        mSize_e = other.mSize_e;
        mCapacity = other.mCapacity;
        mDataPtr_e = static_cast<T *>(Alloc::allocate(sizeof(T) * mCapacity));
        for (int i = 0; i < mSize_e; i++) {
            mDataPtr_e[i] = other.mDataPtr_e[i];
        }
    }
    return *this;
}

this != &other this是指向对象本身的指针，而对对象使用 &，取得了地址，也就相当于this，因此此处是地址的比较
之所以比较地址，而不是比较对象是否相等，是因为这样最简单，而且比较对象，是需要重写比较相关的运算符才可以进行的

2 移动赋值运算符

Vector& operator=(Vector &&other) noexcept {
    // 注意
    if(this != &other) {
        this->~Vector();
        mSize_e = other.mSize_e;
        mCapacity = other.mCapacity;
        mDataPtr_e = other.mDataPtr_e;

        other.mSize_e = 0;
        other.mCapacity = 0;
        other.mDataPtr_e = nullptr;
    }
    return *this;
}

可以看出，移动赋值运算符也是类似的结构

2.5 总结

这段将简单总结一下第二章的内容

首先我们模仿了函数的效果，但是手动进行了内存管理，并且手动控制了在这块内存上对象的生命周期
解耦了已有元素数量（size）和容量（capacity），这要求我们在构造函数和析构函数以及特殊运算符中，申请空间需要以capacity为大小，控制对象生命周期，需要以size为大小
构造函数和特殊运算符的规则，使得我们必须手动实现资源的管理，实现由编译器自动生成的内容无法实现的功能

但是，显然这部分内容是非常浅显的，大部分的讲解都会提到这些内容，也不过是用几个新技术，在堆内存上模拟了一个数组的功能，并且我们大部分的接口还没有实现。如何再深入进去呢？如何理解标准库的一些思想呢？

我们要学习vector，不仅是要学习代码怎么写，怎么实现，更要学习它的思想，需要在代码中抽丝剥茧，提炼出能体现某些原则的东西。

关键！！！！

可以注意到，以上的部分函数，添加了一个叫noexcept的东西
它声明了，该函数不会抛出异常

异常是我们串联起后续内容，拆解stl思想的一个重要切入点
没有异常，我们是难以理解为什么vector的代码如此复杂，复杂的同时还有一系列的原则，仿佛数据库一样

3 noexcept 引发的血案

// TODO

感谢

本文代码的核心框架来自 bilibili LH_Mouse大佬的视频。
同时也参考了 sunrisepeak 大佬的代码和视频: BV1K1421z7kt。且本文大部分讲解代码直接用的对应的教学文档代码。

D2Learn Forums