从小白的视角探究 vector

[dustchens]

从小白的视角探究 vector

学习C++就像盲人摸象，好吧，其实大部分编程语言的学习都是这样，但是C++还是更难一点，它既有厚重历史又在不断现代化，在现代化的同时又不像Java那样可以抛弃旧版本，直接从一个更新更容易理解的阶段开始学习，知识点散落在不同的地方，摸一摸只能知晓部分。
这篇文章便是我摸不同内容给出的自己的一个浅薄理解，如有错误，也请大伙指正。

---

1 初识 vector

最小实现

struct DefaultAllocator {

public:
    using Address = unsigned long long;

    static void * allocate(int bytes) {
        void *memPtr = ::malloc(bytes);
        return memPtr;
    }

    static void deallocate(void *addr, int bytes) {
        if (addr == nullptr) {
            std::exit(-1);
        }else {
            ::free(addr);
        }
    }

};

template <typename T, typename Alloc = DefaultAllocator>
class Vector {
public:

    Vector() : mSize_e { 0 }, mDataPtr_e { nullptr } { }

    Vector(int size) : mSize_e { size } {
        mDataPtr_e = static_cast<T *>(Alloc::allocate(sizeof(T) * mSize_e));
        for (int i = 0; i < mSize_e; i++) {
            new (mDataPtr_e + i) T();
        }
    }
    ~Vector() {
        if (mSize_e) {
            for (int i = 0; i < mSize_e; i++) {
                (mDataPtr_e + i)->~T();
            }
            Alloc::deallocate(mDataPtr_e, mSize_e * sizeof(T));
        }
    }

private:
    int mSize_e;
    T * mDataPtr_e;
};

这段来自 sunrisepeak 大佬的教学代码，是很多新手小白对 vector 的第一印象。
从中既能看出C++继承C的内容，比如熟悉的for循环，又可以窥见C++偏向应用层的截然不同思想。这段简单的vector实现包含了模板、内存分配和构造函数等内容，下面将拆解这段程序，并讲述我自己的理解。。

1.1 模板

问题：template 是什么？typename 是什么？T 又是什么？

话说 long long years ago，在西牛贺州的平顶山莲花洞里，有金角大王和银角大王两个妖怪，他们手中有一件来自太上老君的法宝: 紫金葫芦。葫芦有个逆天功能，叫到了名字，回答一声就可以被吸进去顷刻炼化。拿着葫芦叫一声者行孙，猴子就被收了进去。名字就是代号，代号就是名字，在 C++ 的世界中，每一个东西也都有一个名字，这就是类型，比如我们常用的 int。

但是如果孙悟空不叫孙悟空，也不叫行者，葫芦是收不进去的。如果要收所有人，就要知道所有人的名字。这显然只有现代人可以实现: 建一个数据库，再配合盒武器。而模板就是这样的武器。

• template 是使用模板的前置说明。
• typename 说明接下来会有一个叫 T 的的万能类型。
• T 本质上是一个占位符。

在 C++ 宇宙中，所有基本类型都是确定的，那么由这些基本类型构成的复杂类型也同样可以确定。切换到西游世界，那就是世界上只有三个名字: 孙悟空、孙行者、行者孙。在你使用 vector<者行孙> 的那一刻，编译器便帮你生成了对应类型的容器；如果孙悟空拔出毫毛变出一堆孙悟空，那就用一个 class 包裹，编译器会生成一个 vector<class{者行孙*n}> 这样类型的容器。

这就是模板的用处。由此可见，T 不是万能类型，因为 C++ 宇宙中并没有万能的类型；只是编译器会根据你写下的类型，根据其中的基本元素，帮你推导并生成对应代码。

当然，模板和葫芦还是不一样的。收尽所有人确实需要知道所有人的名字，但一个葫芦只能收一种人。在写下类型的那一刻，就会生成一个相应的葫芦，而不是收尽所有人的万能葫芦。这也正是<mark><strong>模板生成代码</strong></mark>的含义。

1.2 内存

问题：为什么需要内存管理？内存管理又和 RAII 思想有什么关联？

1. 为什么需要申请内存

int  num  = 10;
int* ptr  = new int(10);
int  arr1 = int [99999999999999999];
int* arr2 = new int [99999999999999999];

对于 num 和 ptr，目标都是得到一个值为 10 的数字。表面上看两者效果一样，指针甚至还要根据门牌号多找一次，这样看完全是多此一举？

• <mark><strong>生命周期</strong></mark>：这是申请内存的第一个需要。num 在函数栈上，会随着函数结束而一同消失；但 ptr 不一样，ptr 本身只是一个门牌号。即使门牌号自己销毁了，在函数栈之外的空间里，系统仍然为你保留了这个 10。倘若其他地方也知道这块门牌号，就都可以进去获取甚至修改内容。
• <mark><strong>空间</strong></mark>：对于 arr1 和 arr2，则引出了申请内存的第二个需要。栈空间是有限的，C++ 程序无法在栈上稳定地开辟非常巨大的内存；而操作系统为你提供了更大的自由空间，可以让你存放相当大的内容。

仅此而已吗？显然并不是，在申请数组的时候，都确定了大小，那么不知道大小呢

• <mark><strong>灵活</strong></mark>：灵活既关系到空间又关系到生命周期。有时候数组大小并不是一开始就能确定的，程序需要在运行过程中，动态申请一个范围很大的、大小可变的空间。

以上就是申请内存的原因。那么有这么多好处，代价是什么呢？

代价

真正造成代价的原因只有一个：系统并不会为程序收拾烂摊子。

操作系统在你申请内存后，会判定这块内存正在使用，但它并不关心这块内存何时不再需要，也不会主动替你回收。于是内存泄漏、越界访问、双重释放等一系列问题都由此产生。除此之外， C++ 继承自 C 的指针语义，还给了程序员很大的权力去访问不同的内存地址，甚至超越程序本身的内存，这已经触碰到操作系统的斩杀线了。

由此，不同语言走上了两条路:

1. 自动内存管理：语言提供一套机制，程序员只管申请，回收交给 GC 或运行时系统。
2. 手动管理：内存的一切行为都交给程序员自己控制。

手动控制是好事，但是手动控制是好事不太可能？

C++ 里的 new 和 delete 对应申请与销毁，对于对象而言，他们还有两个额外的操作。一旦你忘了销毁、销毁位置错了、或者流程中途跳出了，问题就很难避免。

void memory_leak() {
    int* data = new int[1000];
    // ... 一些处理 ...
    if (some_condition) {
        return;  // 提前返回，忘记 delete[]
    }
    // ... 更多处理 ...
    delete[] data;  // 只有正常路径才执行
}

void exception_unsafe() {
    Foo* obj = new Foo();
    Bar* bar = new Bar();  // 若 Bar 构造函数抛异常，obj 泄漏
    // ... 可能抛出异常的操作 ...
    delete bar;
    delete obj;
}

void double_free() {
    int* p = new int(10);
    int* q = p;      // 两个裸指针指向同一资源
    delete p;
    delete q;        // 未定义行为：双重释放
}

以上可以看出使用指针申请内存的部分问题，这些问题的根源就是之前所说的: 裸指针只是一个门牌号，并不承担任何对申请出来空间的管理责任。一切都需要手动控制。

如果是在古老时代，编程还是少数精英程序员的专属能力，他们对内存和语言掌握得炉火纯青，可以游刃有余地解决手动管理的一系列问题；可是现代编程普及之后，以及软件的复杂度攀升，单纯使用手动管理显然不再适应时代的发展，现在用于大型软件的语言，基本上都必须提供更加简单便捷的内存管理手段。

2. RAII

机制怪来了 不对，是将军来了。原来是 Bjarne Stroustrup 来了，祖师爷的恩情还不完。

RAII原名RAII， 原名Resource Acquisition Is Initialization，<mark><strong>资源获取即初始化</strong></mark>。

它的核心思路是: 用一个栈上对象的生命周期，去绑定对应资源的生命周期。对象进入作用域时拿到资源，对象离开作用域时自动释放资源。如果对象会随着函数栈退出而销毁，那么连带的内存资源也同样销毁。这是现代C++保证内存不泄漏的唯一机制。

这是一个机制怪，C++对于类定义了一系列的特殊函数，而那个随着对象销毁而自动调用的析构函数显然是最特殊的，对象总有死的那天，伴随死亡的还有一场风光大葬。

struct RAII {
    RAII() {
        // 申请资源
        ptr = new T();
    }
    // 此处省略其他构造函数

    ~RAII() {
        // 释放资源
        if(ptr) {
            delete ptr;
        }
    }

    T* ptr;
}

{
    // 资源被包裹在对象内
    RAII r1 = xxxx;
    // 离开作用域自动调用 ~RAII() 销毁
}

需要申请内存的资源绑定到对象上，用对象的构造函数去申请资源，然后对象因作用域的销毁自动调用析构函数，销毁申请的资源。这样资源的收尾就被封装进类型本身，不再散落在业务流程里。

但如果包裹资源的对象本身也需要申请内存呢？比如写成 RAII* r = new RAII 这样的形式，依旧产生了裸指针的问题。好在 C++ 还提供了继续“套壳”的办法，对裸指针进行托管，也就是智能指针。

现代C++管理内存的精髓就在于利用好这个可以自动调用的析构函数，以及相应的构造函数，将资源包裹起来，尽量避免直接使用new去申请内存，将一切托管。这也要求我们在设计一个持有手动管理资源的类时，必须要考虑如何将一切手动管理封装在类内部，由此引申出3/5/0原则。可以说RAII的思想贯穿了整个现代C++，这种思想也即将应用在我们对于vector的学习之中。

1.3 讲解和总结

前几节讲的内容算是一个简单的前置信息，有了这些内容，我们才能对vector有一个简单的理解。

1. 成员

成员	作用
T* mDataPtr_e	指向申请空间的指针，且指明了申请的类型
int mSize_e	申请空间的大小，后续我们将会对size进行一个解耦

从语义上看，它说明了几件事:

1. vector 内部有自己申请的空间。
   且有一个指针指向这块空间的起点。根据 RAII 思想，申请和销毁必须被构造函数和析构函数托管。
2. 空间大小必须声明。
   数组不是指针！如果我们想让 vector 表现得像数组，必须显式声明大小，因为数组必须包含数量这一本质。哪怕数组在 C++ 中可以用指针访问，如果不关心数量这一核心语义，而去关心用什么实现或者使用，从而得出底层实现等于顶层语义，就是巨大的谬误！
3. 需要人为划分整块内存，并提供对应操作。
   只有这样，才能在一块连续空间上实现数组的语义。

2. 解耦内存操作

• mDataPtr_e = static_cast<T *>(Alloc::allocate(sizeof(T) * mSize_e));
• new (mDataPtr_e + i) T();
• Alloc::deallocate(mDataPtr_e, mSize_e * sizeof(T));
• (mDataPtr_e + i)->~T();

以上的内存分配和构造函数、析构函数的调用和新手的印象产生了偏差，new的形式变了，与new配对的delete也不见了，取而代之的是调用了free，还有一堆奇怪的内容，这些云里雾里的东西成了新手的第一道门槛，我称之为new和delete的解耦。

首先先解释一下new和delete的作用:

• new
  1. 向内存申请空间，对应底层的 malloc 一类动作，大小由 size 决定。
  2. 调用构造函数，在C++中，new直接调用了构造函数，这是解耦的关键。

类比到new，delete同样也是两步操作

• delete
  1. 且由于栈的先进后出，new先申请空间再调用构造。delete先调用析构函数，结束对象生命周期。
  2. 再释放整块空间。

但是即使拆解了new和delete，知道他们分别对应两个步骤，可是为什么要分开来呢，十万个为什么始终在我们初学者的心中萦绕。

土木佬的故事

newer 生活在一个方格世界，所有房屋都是矩形的，占有一个或多个方格，同时建造房屋必须拥有地契。

newer 是个很有能力的人，他既会疏通关系，又是个土木佬，原来是甲方和总包合体了。他的主业是建造房子租给别人住。newer 先找有关部门批了块地契，建了一个地契上规定位置和大小的房子，并招来了租客。

同时他有一个合作伙伴 deleter，专门负责帮他清理那些房租到期的房子: 先通知租客走人，然后炸掉房子，最后去有关部门销毁地契。

某天，newer 突发奇想，想建一排一样的房子，于是他一遍遍地往有关部门跑，每次只批建一个房子的条子，然后回来自己盖。最终这一排房子分散在方格世界的各个地方，本来听说房子都在一起的租客也不愿意住了，于是他破产了。他犯下的第一个错误: 有关部门给的地契，并不挨在同一个地方，整个世界哪里有空就放在哪里。同时还有很多和newer一样的人在申请地契，newer第二次去申请的地方早就被别人占据了。

东山再起后的 newer 变聪明了，这次一次申请了多块连在一起的地契，盖好了一排标准化房子，还给这排房子起名叫公寓。房子租出去不少，但等到有租客房租到期时，deleter 照常通知租客离开，炸掉了房子，又去有关部门销毁这一间房的地契。这回 newer 又破产了，因为整块地都不属于他了。

因为方格世界有两个规则怪谈:

• 地契永远只有一张纸！
• 销毁地契也只能销毁一张！

1. 去有关部门申请地契时，一次不管申请多少地契，最终只有一张地契给出。

2. 不管地契上是一间房子还是多间房子，因此多间房子的地契无法销毁掉其中一间房屋，只有整个销毁，如果被发现只销毁部分地契，这两个人都会被抹除。

发现这两个规则后，newer 这次申请了一大块连在一起的地，盖一排排房子，而且每个房间都做好了装修，最终newer还是破产了，因为根本没有那么多人租房子了，装修的钱还是借的，入不敷出的newer结束了土木佬悲剧的一生。

这个故事对应了 C++ 里的三条规则:

1. 多次 new 到的位置不保证相邻。 new申请内存时，位置是不确定的，无法保证多次申请到的位置是相邻的
2. delete 释放的是整块内存，不能只释放其中一部分。
3. 需要多少内存就申请多少，可以多申请一部分。 但是一开始就申请巨大的内存并且构建是要付出代价的，故事中的租金在操作系统中可能意味着内存频繁换页、分配巨大内存直接失败等问题

那么由这三条规则，可以推导出拆解new和delete的理由:

1. 如果直接使用 new T[]，一次性申请一大块空间并把对象全都构造出来，这对 T 有额外要求，而且会造成浪费。这对应了规则3。
2. vector 需要对元素进行精细化操作，比如增加和释放。由规则1可知，内存申请的位置是不确定的，那么就无法做到增加的空间恰好连在整体空间后，由规则2也可知，释放元素也无法做到释放中间位置，因此必须解耦，并提供更基本的操作。

还有很多其他的理由，但是初学者基本只需要知道这些即可。总结起来就是new和delete的两步特性，和vector的需求发生了冲突，vector需要自己管理内存上多个对象的生命周期，而new和delete只能掌控一整块的内存。

精细化管理

根据前文总结，我们可以看出，空间和单个元素生命周期，是vector拆分new和delete的原因，如何拆分也就顺理成章了。

1. 空间

   • mDataPtr_e = static_cast<T *>(Alloc::allocate(sizeof(T) * mSize_e)); 对应申请空间， operator new(size)。
   • allocate 底层调用了 malloc，会向内存申请一块大小为 sizeof(T) * mSize_e 的空间，也就是申请 T 大小的单间，共size个。只申请空间而不调用构造函数！
   • static_cast<T*> malloc申请出来的空间大小确定了。但是如何划分没有确定，也就是整块内存的门牌号是按照void* 空指针去看待的，如果我申请的是10个双人间，但是用别的方式去看，看成了5个4人间，那就出现问题了。static_cast<T*>的作用就是类型转换，将门牌号转换为T*，这样在做指针运算和sizeof的时候，指针能按照正确的步长前进后退。且这个转换是现代C++要求的显式强制转换，而不要使用 (T*)(void*) 这样的转换。转换方面的知识留给大家自行去了解。。
   • Alloc::deallocate(mDataPtr_e, mSize_e * sizeof(T)); 对应 operator delete(ptr)。
   • deallocate 底层调用了 free，它只负责释放整块内存，并不关心析构函数。
   • 可以看到free只需要知道指针（第二个参数根本没有用到），也就是门牌号，就能删除当时创建的内存块，因为系统在分配内存的时候就将大小信息放在了内存块的某处。

2. 生命周期

   • new (mDataPtr_e + i) T();
   • 这里的 new 和普通 new 不是一个东西，叫做 placement new。它的作用是在指定的已开辟内存位置 (mDataPtr_e + i) 上，唤醒对应构造函数，也就是后面的T()。在此处对原本空白未初始化的内存进行装修并喊来人，开启对象的生命周期。
   • (mDataPtr_e + i)->~T()
   • 这里则是显式调用析构函数，结束对象生命周期，但并不释放整块空间。

3. 总结

相信大部分看到这里的初学者还是会有点懵。vector 作为动态数组，既包含 RAII 思想，又要自己管理内存，套了一层又一层，很难不让人心生畏惧。如何将以上散落的知识进行汇总并充分理解呢？还是拿出小例子吧。

// 2
class RAII() {
    // 代码见上文
}

signed main() {
    // 1
    // 手动申请空间，手动释放
    int* ptr = new int(10);
    delete ptr;

    // 这显然不对，违反了 RAII 的原则，如果内容多了之后手动释放很难不出现问题
    // 所以我们开始用一个对象去包裹住这个资源
    RAII ra{10};

    // 这样做以后，new 操作被包裹进了 ra 对象中
    // 一旦 main 结束，析构函数就会自动调用，释放资源
    return 0;

    // 2
    // 隐藏的自动调用内容
    // ~RAII() 此处完成清理
}

既然包裹进了对象中，析构函数会帮我们自动释放资源，那么为什么还是不推荐继续用 new 呢？

// 接上一段代码
signed main() {
    // 这样会发生什么呢？我们已知RAII的析构里是有释放资源的代码的
    RAII* ra = new RAII{10};
    return 0;
}

好了，我们辛苦写出的析构函数又失效了，因为对象不在我们的main函数里了，它被new申请在了不属于main空间掌控的内存中，而ra从对象变成了指向对象的门牌号！

如果我们确实又有这种需求怎么办？装载资源的对象本身就非常大，我们就是要搞个大房子呢？

RAII 思想套壳来了。 既然执意还要搞个空间，那就再套一层吧。

struct RAIIRAII() {
    RAIIRAII(int val) {
        ptr = new RAII(val);
    }
    ~RAIIRAII() {if(ptr) delete ptr;}
    RAII* ptr;
}

signed main() {
    // RAII* ra = new RAII{10};
    // 好了，灾难终于解决了
    RAIIRAII rara {10};
    return 0;
}

这层不断套壳的操作，可以最大程度避免直接使用裸指针申请资源；再套壳的操作，就是智能指针的思路。

光讲套壳，这和 vector 又有什么关系呢？深水区来了。

我们由上文可以看出，RAII 思想要求用对象生命周期去解决内存资源的自动释放问题；同时，vector 也要求精细化管理内部元素的生命周期。都是生命周期，在哪里有区别吗？显然，是没有的。

signed main() {
    int a = 10;
    RAIIRAII rara {10};
    char str[] = "hello world";
    vector<int> vec;
    return 0;
}

我们随手写出的 a、rara、str、vec，他们在 main 的函数栈中，都会随着函数结束，而被杀死。只不过 a 是一个 int，直接捅死；rara 这样的对象则需要先找析构函数，然后再杀死。

甚至我们写出的裸指针，裸指针这块门牌号本身，也会被杀死，只不过只有通过RAII技术，才能自动调用析构函数去销毁门牌号对应的房间资源。

那么我们继续思考以下的代码:

struct vector{
    vector() {
        arr[0] = 0;
    }
    arr[10];
}

signed main() {
    int arr[10];
    arr[0] = 0;
    vector vec;
    return 0;
}

倘若 vector 是这样的，那这两个数组的生命周期其实并没有本质区别，vec 会随着 main 结束而销毁。

等等， 倘若我们把 main函数 也看成是一个类呢？

main 提供了栈空间，让我们能随心所欲地创建 int a 这样的小内容而不用 new 去申请更大的内存；同时 main 结束时又把这些内容全部清理掉。这和调用析构函数去清理有什么本质区别吗？

我们使用 RAII 去包裹资源，只是因为这个资源在更远的地方，我们只知道门牌号。而我们在函数里随便使用的各种对象、基本类型，函数这个“类” 既知道门牌号，而且资源就存储在类里，所有函数（或者说作用域）能清理掉绑定在它身上的变量和对象。

而这个“mian类”在退出的时候，又向系统归还了它的栈空间，好像我们发现了什么东西！

这和我们要实现的vector在本质上不是一样的吗？我们提供了一块空间（从内存申请来的），同时我们希望在内部能够随心所欲地添加相同类型的对象，这和我们在main函数里写的那些变量不是一样的吗？然后vector需要和函数一样，清理掉绑定在它身上的对象，在退出时清理掉申请来的空间。

我们初学者之所以觉得这些内容难以理解，就是因为这些机制太普遍了，普遍到我们根本没有意识到它的存在。我们需要意识到，内存空间都是一样的，并不因为我们用new申请了资源，申请到的空间和我们在函数中使用的空间有什么本质区别。

看到这里，我相信和我一样的初学者会对vector对内存的管理会有一个初步的了解。以下就是我个人总结的后续学习vector的一些认知

以下是我个人总结的几个关键认知:

1. vector 需要我们模仿函数栈，只不过是需要申请大块的空间（栈空间有限）同样要用RAII管理这块空间。同时我们需要对这块空间上创建的对象进行管理，至少在vector消亡的那一刻需要将他们全部带走
2. 既然是全部带走，那么我们就必须要求元素类型本身实现了对资源的保护！即使标准本身没有这样说明，但是如果类型本身携带资源，且没有实现RAII，那么vector不会为你解决这些问题，就像函数栈没有义务清理裸指针申请出来的内存空间一样。
3. 细微的不同在于，我们申请的这个空间可以调整大小，而不像函数栈一样有最大限制。同时因为可以调整大小，再根据我们之前讲过的无法申请到相邻内存的原则，我们必须释放掉当前的内存块，申请一个更大的新内存，这也是扩容的基础思想。

---

2 改进 vector，实现 Big5

// TODO 后续再发

---

感谢

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

[dustchens]

才发现没有高亮

[SPeak]

@dustchens 加粗吗? 目前不支持 <mark>html标签 </mark> 可以使用下面 md 语法

一段文字
一段文字
一段文字

[dustchens]

@SPeak 感谢大佬了。主要是没仔细看，md文档在我本地的高亮跟发布的表现不一样。

[dustchens]

@dustchens 在 从小白的视角探究 vector 中说：

光讲套壳，这和 vector 又有什么关系呢？深水区来了。

第一节的精髓在于这一段之后的内容。不过我没有给出栈和作用域等内容的讲解。这段内容本身是非常复杂的，但是副作用却很小，小到每个人编程一开始都能无障碍使用。

拿函数来类比vector，就是因为我感觉缺少一个能够切入申请空间和管理生命周期的点，如果说每个人一开始就能写的main函数，是最简化了空间管理和生命周期管理，让你意识不到它的存在，那么vector就是需要我们把这套内容拿到明面上来，且二者的本质是一样的（从空间和生命周期管理的语义来看）