在我本科上图形学课的时候，老师先给我们出了几个小题让我们熟悉 C++ 的语法以及基本思想。当时老师给的例子就是实现一个“动态数组”，类似标准库的 std::vector。不过当时我对这个语言的了解还不够深入，所以当时写的东西在现在看来真的是千疮百孔，到处是漏洞。实现 std::vector 类似的功能其实触及了 C++ 很多的知识点，所以这个问题仍然还是一个了解各种语言特性和方法的好起始点。
如果真的从零开始的话可能需要的篇幅会太长，所以我姑且认为读者都懂 C++ 基础中的基础（甚至目前就以为 C++ 是“C with new”都没太大问题）。
1. RAII，三/五/零原则
为了不重复说明同样的内容，如果不知道 RAII 以及三五零原则，请先看一下我的这篇文章，在其中我已经写过了一个非常基础的框架 dyn_array，我们就从这里出发。
namespace mystd
{
struct int_vector
{
size_t size = 0;
int* ptr = nullptr;
int_vector() = default;
explicit int_vector(const size_t size):
size(size), ptr(new int[size]{}) {}
~int_vector() noexcept { delete[] ptr; }
int_vector(const int_vector& other):
size(other.size)
{
ptr = new int[other.size];
std::copy_n(other.ptr, size, ptr);
}
int_vector& operator=(const int_vector& other)
{
if (&other == this) return *this;
delete[] ptr;
size = other.size;
ptr = new int[other.size];
std::copy_n(other.ptr, size, ptr);
return *this;
}
int_vector(int_vector&& other) noexcept:
size(std::exchange(other.size, 0)),
ptr(std::exchange(other.ptr, nullptr)) {}
int_vector& operator=(int_vector&& other) noexcept
{
delete[] ptr;
size = other.size;
ptr = std::exchange(other.ptr, nullptr);
return *this;
}
};
}
void test()
{
mystd::int_vector vec(10);
for (size_t i = 0; i < 10; i++)
std::cout << vec.ptr[i] << ' ';
}
2. 维持数据的不变性
虽然目前这个 int_vector 不会泄漏它保持的内存资源了，但是它用起来还是不太方便，使用方需要直接去访问这个结构的内部信息 ptr 才能获取到它的数据，而且这样也并不会阻止用户直接去修改 size 和 ptr 的值。在这里因为我们需要保持这个结构的某种“不变性”，所以我们不能直接向用户开放所有细节，而应该隐藏这些细节只给用户提供访问的接口，这也是 OOP 中“封装”的一个作用。注意 C++ 的 class 和 struct 其实并没有本质的区别，只是 struct 默认访问性是 public 而 class 的默认访问性是 private 而已。这与比如说 C# 之类的其他语言不太一样。
这里我们提供对数组大小的只读访问以及对内部数组的下标访问（使用 C++ 的运算符重载）。
（注：本人的习惯是给私有数据成员的名字后面加一个下划线以便区分。）
class int_vector
{
private:
size_t size_ = 0;
int* ptr_ = nullptr;
public:
int_vector() = default;
/* Rule of five functions omitted here */
size_t size() const { return size_; }
int& operator[](const size_t index) { return ptr_[index]; }
const int& operator[](const size_t index) const { return ptr_[index]; }
}
在 C++ 中 const 正确性是一个重要的话题，我们一定要保证不改变类内部信息的成员函数都是 const 的。C 语言中因为没有引用类型，函数的返回值并不能作为左值进行修改，而这里我们希望下标访问获得的值是可以修改的，所以使用了左值引用类型。左值引用代表了一个对可修改的左值的“别名”，在此基本可以认为是一个可以自动解引用的指针。至此我们就完成了一个好像还勉强能用的动态数组类型，我们可以使用熟悉的类似普通 C 数组的语法来进行对动态数组的操作。
void test()
{
mystd::int_vector vec(10);
for (size_t i = 0; i < vec.size(); i++)
vec[i] = static_cast<int>(i);
for (size_t i = vec.size(); i-- > 0;)
std::cout << vec[i] << ' ';
// should print out 9 8 7 ... 0
}
3. 适配不同的类型——类模板
不过到现在为止我们的类还只支持存储 int，如果换一个类型需要存储的话我们就需要复制粘贴一遍所有代码并且把 int 换成对应的类型。这太麻烦了，而且很容易出错，不过幸好 C++ 为我们提供了一种方便的对不同类型生成类似代码的机制，那就是模板 (templates)。模板是编译时的，编译器会利用你给的模板来生成对不同类型类似的代码，而不是像 Java 中的泛型那样进行类型擦除。C++ 模板是一个特别强力的工具，它要比那些泛型能做的事情多得多，不过在这里我只会提到模板最基础的使用方法。
要使用类模板，我们就需要在 class 的前面加上模板的格式，这里我们的模板只需要一个参数，那就是要存储的数据的类型，所以模板的格式就是 template <typename T>。在类模板的定义中我们只需要把所有的 int 都换成模板参数 T 就可以达到我们要的效果了。
template <typename T>
class vector
{
private:
size_t size_ = 0;
T* ptr_ = nullptr;
public:
vector() = default;
explicit vector(const size_t size):
size_(size), ptr_(new T[size]{}) {}
/* ... */
}
注意此时我们的 vector 本身已经不是一个类了，它是一个类模板，顾名思义就是一个用来生成类的模板。使用时大概就是像这样：
void test()
{
mystd::vector<float> vec(10);
for (size_t i = 0; i < vec.size(); i++)
vec[i] = static_cast<float>(i);
for (size_t i = vec.size(); i-- > 0;)
std::cout << vec[i] << ' ';
}
大功告成，我们可以随意生成不同类型的动态数组。
4. 变长数组和预留空间
前面的代码中我们只是实现了一个长度可在运行时给出的数组，但是这个数组的长度并不可变，我们无法往数组里面添加新的元素。一个最朴素的实现就是在每次添加新元素的时候，申请一片新的能容纳下新数组的内存，之后把原来的数据都复制到新内存中，再释放原来的内存。不过一般对动态数组的操作都会涉及到比较多的插入新元素的操作，如果每次都要重新申请新的内存空间未免效率太低了，所以我们采用几何增长的方法，申请一些多余的空间来容纳之后的数据添加。（注：据说这个几何增长的比例选择 1.5 时候为最佳，不知道是什么理论得来的。）
我们可以给我们的 vector 增加一个新的数据成员 capacity 用来保存目前已申请内存的数组的大小，之前的 size 仍然保存目前数组的实际大小。
size=3 capacity=6
memory [0] [1] [2] [-] [-] [-]
因为如果要使用现代 C++ 的范式以及 STL 的话对指针的操作其实比对数组大小的访问要多得多（至于为什么如此……等我讲到迭代器再说吧），所以目前主流编译器的实现一般都是存储三个指针而不是一个指针和两个大小，但是其本质其实是一样的。
first last end
memory [0] [1] [2] [-] [-] [-] ???
(last - first == size)
(end - first == capacity)
用这种预留空间的方法，我们在连续增加元素时就省去了不少次的内存申请。不过一个后果就是我们的实现变得复杂了很多……在下面就是本人的一个示例实现，比之前多了几个成员函数：增加元素的 emplace_back，改变数组大小的 resize，手动预留空间的 reserve，清除所有元素的 clear，以及请求移除未使用的容量的 shrink_to_fit。有兴趣的读者可以先不看我的实现自己试着做一下（当然，如果发现有 bug 的话也请指出）。
template <typename T>
class vector
{
private:
T* first_ = nullptr;
T* last_ = nullptr;
T* end_ = nullptr;
void allocate_and_move(const size_t new_capacity)
{
T* new_first = new T[new_capacity];
last_ = std::move(first_, last_, new_first);
delete[] first_;
first_ = new_first;
end_ = first_ + new_capacity;
}
size_t calculate_growth(const size_t new_size) const
{
const size_t geometric = capacity() + capacity() / 2;
return std::max(geometric, new_size);
}
void grow_if_needed(const size_t new_size)
{
if (new_size <= capacity()) return;
allocate_and_move(calculate_growth(new_size));
}
public:
vector() = default;
explicit vector(const size_t size):
first_(new T[size]{}), last_(first_ + size) {}
~vector() noexcept { delete[] first_; }
vector(const vector& other)
{
first_ = new T[other.size()];
end_ = last_ = std::copy(other.first_, other.last_, first_);
}
vector& operator=(const vector& other)
{
if (&other == this) return *this;
delete[] first_;
first_ = new T[other.size()];
end_ = last_ = std::copy(other.first_, other.last_, first_);
return *this;
}
vector(vector&& other) noexcept:
first_(std::exchange(other.first_, nullptr)),
last_(std::exchange(other.last_, nullptr)),
end_(std::exchange(other.end_, nullptr)) {}
vector& operator=(vector&& other) noexcept
{
delete[] first_;
first_ = std::exchange(other.first_, nullptr);
last_ = std::exchange(other.last_, nullptr);
end_ = std::exchange(other.end_, nullptr);
return *this;
}
size_t size() const { return last_ - first_; }
size_t capacity() const { return end_ - first_; }
T& operator[](const size_t index) { return first_[index]; }
const T& operator[](const size_t index) const { return first_[index]; }
T& emplace_back(const T& value)
{
grow_if_needed(size() + 1);
return *last_++ = value;
}
T& emplace_back(T&& value)
{
grow_if_needed(size() + 1);
return *last_++ = std::move(value);
}
void clear() { last_ = first_; }
void resize(const size_t new_size)
{
reserve(new_size);
last_ = first_ + new_size;
}
void reserve(const size_t new_capacity)
{
if (new_capacity > capacity())
allocate_and_move(new_capacity);
}
void shrink_to_fit()
{
if (capacity() != size())
allocate_and_move(size());
}
};
调用方：
void test()
{
mystd::vector<size_t> vec;
for (size_t i = 0; i < 10; i++)
vec.emplace_back(i);
for (size_t i = 0; i < vec.size(); i++)
std::cout << vec[i] << ' ';
// Should output 0 1 2 ... 9
}
我们可以在 allocate_and_move 函数里面加上一行输出来看看我们一共重新申请了几次内存：
Allocated: new capacity = 1
Allocated: new capacity = 2
Allocated: new capacity = 3
Allocated: new capacity = 4
Allocated: new capacity = 6
Allocated: new capacity = 9
Allocated: new capacity = 13
开始的增长速度很慢，这意味着我们只想存少数几个元素的时候不会浪费空间；而如果我们本就想存储很多的元素的话，这种方法又可以很好地减少重复申请内存带来的开销。比如说，用这种重新分配的方法，如果要从 0 连续插入 100 个元素，只需要申请 13 次内存；连续插入 1000 个元素也只需要申请 18 次内存。
4*. 对右值以及右值引用的补充
对于 std::move 的使用我在这里补充一下。在前面的 RAII 与三五零规则的文章里我讲过，像 T&& 的这种右值引用是用于对临时值做优化的。
void f(const S&); // 1
void f(S&&); // 2
void test()
{
S s;
f(s); // s is lvalue, calling 1
f(S{}); // S{} is temporary, thus an rvalue, calling 2
}
这里如果想表达“虽然它是个左值，但是我后面不会用到这个变量了，请把它当成临时值”的语义，就需要一个到右值引用的强制转换。
void test()
{
S s;
f(s); // lvalue, calling 1
f(static_cast<S&&>(s)); // rvalue, calling 2
}
因为这个到右值引用的强制转换实在是太常用，所以标准库里就有一个帮助函数就做这件事情，它就是 std::move。很多初学者会以为 std::move 这个函数做了什么了不起的事情，是这个函数移动了对象，其实不是的。std::move 只是把左值强制类型转换成右值引用而已。（所以这个函数起名是不是有点问题？改名叫 as_temporary 估计就没什么人搞错这个函数的意义了，不过这种常用函数起个长名字好像也不是很好。）
void test()
{
S s;
f(std::move(s)); // rvalue, calling 2
}
来个简单问答，下面打星号的地方调用的是哪个重载？
void test(S&& s)
{
f(s); // *
}
没错，就是函数 1。有没有感觉被骗到？
这是因为类型和值类别是分开的两个东西。s 的类型是 S&& 没错，但是它的值类别是左值，因为有名字的都是左值。而正因为 s 是左值，它就不能绑定到右值引用上，所以会调用函数 1。要是想调用函数 2，还是需要传递 std::move(s)。这一点很坑，希望读者不要搞错。
至此就是一般的 C++ 课上会讲到的部分了（很可能除去讲右值引用的部分，毕竟据我了解没有哪个地方会仔细讲 C++11 的右值引用，虽然它是现代 C++ 最重要的组成部分）。当时的我也以为 std::vector 也不过大致如此，不过当时的我还是太天真了，实际的实现比这要复杂得多。
5. 默认构造与对象的生存期
有时候这语言让你很喜欢，有时候你只想开骂。不过大部分时候是开骂。Pardon my French, 玛德这个傻逼语言。—— Chlorie
前面都算是热身，接下来我们要接受 C++ 这个语言中最精密的细节，最容易出错的构造，以及最血淋淋的现实了。
上面所用的元素类型都是基本类型，它们都有平凡的构造和析构函数。如果在我们写的这个 vector 里面存储一些构造和析构不平凡的对象会怎么样呢？我们用下面的这个类来测试 vector 对数组元素的生存期的控制，当这个类的对象实例被构造/复制/析构的时候我们可以直观地在控制台中看到这些函数被调用的的前后顺序以及次数。
struct LifetimeLogger
{
LifetimeLogger() { std::puts("default c'tor"); }
~LifetimeLogger() noexcept { std::puts("d'tor"); }
LifetimeLogger(const LifetimeLogger&) { std::puts("copy c'tor"); }
LifetimeLogger(LifetimeLogger&&) noexcept { std::puts("move c'tor"); }
LifetimeLogger& operator=(const LifetimeLogger&)
{
std::puts("copy operator=");
return *this;
}
LifetimeLogger& operator=(LifetimeLogger&&) noexcept
{
std::puts("move operator=");
return *this;
}
};
void test()
{
LifetimeLogger logger;
// Should output:
// default c'tor
// d'tor
}
我们用这个类来测试一下我们的 vector。
void test()
{
mystd::vector<LifetimeLogger> vec;
vec.reserve(2);
// Outputs:
// default c'tor
// default c'tor
// d'tor
// d'tor
}
等下，我只说让你给我留存两个对象的内存空间，没说让你给我默认构造啊……
在这里我们的对象只是在构造的时候输出一些东西，但是有些对象构造起来是需要消耗另外的资源的，我们显然不想莫名其妙地就构造多余的对象。这么来看，对数组中存储的对象生存期的控制是 vector 实现中非常重要的一环，但在基础的教学中这一部分总是会被忽视，也许教的真的是“C with classes”而不是 C++？其实也不能怪平时的课堂上不教这些实现的细节，毕竟我们大致知道实现的思路就可以了，实际在使用的时候直接用标准库提供给我们的现成的类就好了。也许真的要涉及到这些细节的话就不能完全算是“入门”的范围了吧，毕竟这些细节可能正是 C++“麻烦”的地方。
下面这一小部分内容作为后面代码正确性的一些解释，如果不想看的话可以直接跳过。
实际上，用一个字符数组为对象提供存储是 C++ 中一个极其复杂的话题，这种事情非常易错甚至一不小心就会搞出未定义行为，这里我尽量查了各种资料确保自己不写出 UB。另外，一个非常残酷的现实是，若采用现在的 C++17 标准的说明，你无法不用 UB 来实现 vector 的 data 函数，这很搞笑但是我笑不出来。你问我那标准库里是怎么实现的？大概是魔法吧，不过更可能是标准库里面就是 UB 但告诉你没有 UB，就像各种优惠券上写的“最终解释权归 xx 所属”一样。
经过又一段时间的搜索调研（我真的是吃饱了撑的，为这么一个没人看的文章花这么多心思……）我发现 C++20 的标准中似乎修正了这种问题，也就是说我们终于可以用符合 C++ 标准的代码自己实现 vector 了，具体请参看 C++ 标准提案 P0593R6 §2.3。这一篇提案本来是要错过 C++20，赶下一班车 C++23 的，但是最后还是作为 C++17 语言缺陷修订进入了 C++20 标准。非常幸运，我们等这个不用再等三年。在后面的内容中，我会假定我们用的主流编译器都遵循该缺陷修订的规范，而不是像之前的标准中说明的那样把我们下面的部分代码划分为未定义行为。（在实际上也确实如此，不然我们用的标准库里面的 std::vector 是怎么实现的……）
5.1. 分离内存和生存期
我们需要把申请内存的操作跟对象的构造析构分开。如何只分配一片内存但不初始化对象呢？用 malloc 吗？这里给出一个 C++ 的方法，那就是 new 表达式的亲妹妹（？？？）new 运算符。
这里读者可能要报警了，new 表达式跟这 new 运算符有什么区别和联系？联系就在于它们用的是同一个单词它们都与内存分配有关（这不是废话吗），而区别在于，new 表达式在分配内存以外，还会初始化对象，返回的一般是特定类型的指针 T*，而 new 运算符只会分配内存，返回的是与类型无关的 void*。
非常方便地，从 C++17 开始，new 运算符可以采用一个对齐参数来指定分配的内存块的对齐，比如下面的代码就申请了一片能够容纳一个 T 对象的内存。同样，有 new 运算符当然就有对应的 delete 运算符。
void* data = operator new(sizeof(T), std::align_val_t(alignof(T)));
operator delete(data, std::align_val_t(alignof(T)));
在 C++17 缺陷修正中，数组类型被视作隐式生存期类型，即数组类型的生存期可以从 operator new 分配内存就开始（这与 C++17 标准出版时的说明不同，不过这种不同被视作是语言缺陷予以修正）。不用因为看不懂这句话说的是什么鬼而思考人生的意义，简而言之前面这句话的意思就是，我们可以直接将前面的 data 指针转换到 T* 并且期待一切正常。
当然，光有内存空间不行，我们还得构造和析构我们要的对象。这里就要用到布置 new 这个工具了，它可以在我们给定的内存地址构造对象。
void* data = operator new(sizeof(T), std::align_val_t(alignof(T)));
T* ptr = new(data) T(value);
T& ref = *ptr; // Here is our reference to T
析构这个对象比想象中的简单，只需要像调用其他成员函数一样调用析构函数就好了。
ref.~T();
5.2. 重新实现 vector
有了上面这些知识我们就可以开始重新实现我们的 vector 了。三个成员变量当然还是老样子，三个指针分别指向数组的开始，实际存放元素部分的结尾，以及整个数组的结尾。我们的默认构造函数当然还是老样子，什么都不做就可以了。
template <typename T>
class vector
{
private:
T* first_ = nullptr;
T* last_ = nullptr;
T* end_ = nullptr;
public:
vector() = default;
}
有了前面那么多铺垫，给定数组大小的构造函数实现起来其实也并不困难，先申请一片内存之后在这一片内存上面进行默认初始化就好了。这里可以用标准库提供给我们的便捷函数 std::uninitialized_default_construct 来在原始内存上面创建一串对象，当然如果你觉得用这个就太作弊了你也可以使用布置 new 加循环来实现，毕竟也不难嘛。（算法库 <algorithm> 中提供了一系列的对原始内存操作的辅助函数 std::uninitialized_*）
static T* allocate_raw(const size_t size)
{
void* data = operator new(size * sizeof(T), std::align_val_t(alignof(T)));
return static_cast<T*>(data);
}
explicit vector(const size_t size)
{
first_ = allocate_raw(size);
end_ = last_ = first_ + size;
std::uninitialized_default_construct(first_, last_);
}
复制构造函数的实现过程也类似，先申请内存再复制元素：
vector(const vector& other)
{
const size_t size = other.size();
first_ = allocate_raw(size);
end_ = last_ = first_ + size;
std::uninitialized_copy(other.first_, other.last_, first_);
}
移动构造函数倒是与之前一样，因为移动一个动态数组并没有对数组的内存和元素做什么操作，只是把临时数组的内存“偷过来”而已。
vector(vector&& other) noexcept:
first_(std::exchange(other.first_, nullptr)),
last_(std::exchange(other.last_, nullptr)),
end_(std::exchange(other.end_, nullptr)) {}
看完构造函数我们来看析构函数。标准库同样为我们提供了可以批量析构数组元素的便捷函数 destroy。
static void deallocate_raw(void* data)
{
operator delete(data, std::align_val_t(alignof(T)));
}
~vector() noexcept
{
std::destroy(first_, last_);
deallocate_raw(first_);
}
这里已经给出这么多例子了，其他的函数实现起来思想其实也都与此大同小异，只要注意同时控制好对象的生存期以及数组内存的申请和释放就好了。其他的包括两个赋值运算符，数组元素的清除，重新设置数组大小，设置数组预留空间大小以及向数组最后插入新元素的成员函数，就留给有兴趣的读者当作练习了。这里仅给出前面的一个辅助函数 allocate_and_move 的实现。我对这些函数的完整实现就留给下一期的开头吧，如果还有下一期的话。
void allocate_and_move(const size_t new_capacity)
{
T* new_first = allocate_raw(new_capacity);
T* new_last = std::uninitialized_move(first_, last_, new_first);
std::destroy(first_, last_);
deallocate_raw(first_);
first_ = new_first;
last_ = new_last;
end_ = first_ + new_capacity;
}
用我们现在这个考虑了对象生存期的实现来测试一下前面那个 LifetimeLogger 的例子吧！你写出的实现是不是会有正确的结果——什么也不输出呢？
void test()
{
mystd::vector<LifetimeLogger> vec;
vec.reserve(3);
// Should output nothing
}
你也可以试一下增加一些元素，看看你的数组内部是怎么处理这些对象的生存期的。
void test()
{
mystd::vector<LifetimeLogger> vec;
vec.emplace_back(LifetimeLogger());
vec.emplace_back(LifetimeLogger());
}
/*
* default c'tor
* move c'tor
* d'tor
* default c'tor
* move c'tor
* d'tor
* move c'tor
* d'tor
* d'tor
* d'tor
*/
（注：下面这个表对上面那个插入两个元素的例子的输出做一个分析）
| 输出 | 解释 |
|---|---|
| - | 默认构造了动态数组 vec，初始容量为 0 |
| default c’tor | 构造了临时对象 #1 作为 emplace_back 的参数 |
| - | 数组容量从 0 扩充到 1 以提供容纳 #1 的空间 |
| move c’tor | 将临时对象 #1 移动到数组里面 |
| d’tor | 销毁临时对象 #1 |
| default c’tor | 构造了临时对象 #2 |
| - | 数组容量从 1 扩充到 2 以提供容纳 #2 的空间 |
| move c’tor | 把在原内存存储的 #1 移动到新内存里 |
| d’tor | 销毁原内存里面的 #1 |
| move c’tor | 将临时对象 #2 移动到数组里面 |
| d’tor | 销毁临时对象 #2 |
| - | 函数 test() 执行完毕，开始析构 vec |
| d’tor | 销毁数组内存储的 #1 |
| d’tor | 销毁数组内存储的 #2 |
| - | vec 申请的内存被释放，vec 析构完成 |
本次讲的内容就到这里了，我们至此已经有了一个真实能用的对象生存期正确的动态数组了。有没有觉得自己的 C++ 水平增长了不少呢？