假设有一天你起床后说：“嘿，我要在 std::vector 擅长的领域打败它！”然后信心满满地开始编写代码。这里有一些建议供参考：
这个看似简单的任务，实际上极其难以完成：一方面，std::vector 本身就是一件艺术作品；另一方面，你所喜爱的标准库编写者都是技艺非凡的高手。
你可能仍然认为自己可以做到这一点，所以尝试一下也无妨，但请确保用两种类型的元素来测试想法：一种是易于构造的类型(例如 int 或 double)，另一种是构造较为复杂的类型(例如 std::string)，然后比较结果。对很多人来说，前者可能会带来极佳的性能，但后者却可能带来……令人沮丧的结果。
造成这种差异的原因在于，像 std::vector 这样的容器在内存管理方面极其高效(我知道，在这本书里读到这句话可能感到很惊讶！)。事实上，它的效率远高于自己编写的替代方案，除非你投入大量时间和精力(而且很可能还针对某个特定的使用场景进行了优化)。
标准库供应商确实投入了这些时间和精力，而且这一切都是为了你的利益。因此，学习如何最优地使用 std::vector，最终可能会比尝试编写你自己的等效容器带来更好的效果。当然，最终使用哪个容器由你自己决定，也可以为特定场景编写出比标准容器这类通用解决方案性能更优的代码。
本章及后续章节中，将编写(并使用)自己的容器，所以有必要进行一个简要说明，以对后续的实现方式达成共识。首先，将在容器中使用与标准容器相同的类型别名(type aliases)，这有助于与其他标准库工具(如标准算法)更顺畅地集成。其次，也会尽量使用与标准库相同的成员函数公共名称(例如，会使用 empty() 作为判断容器是否为空的谓词函数，这与标准库的现有做法一致，尽管有些人可能会认为 is_empty() 更加直观)。最后，将采用逐步改进的方式：最初的版本将较为简单但效率较低，而后续版本会逐渐变得更高效。读者们请您耐心等待：我们正在沿着自己的道路追求顿悟之路！
非正式地讲，std::vector 表示一个可以按需动态增长的数组。与普通数组一样，std::vector<T> 是一个在内存中连续排列的类型为 T 的元素序列。
为了使自制的版本与 std::vector<T> 明显区分开来，我们将它命名为 Vector<T>。
要实现一个性能合理的版本，第一个关键思想是区分“大小(size)”与“容量(capacity)”。如果不这么做，将 size 与 capacity 视为同一概念，那么 Vector<T> 实现将始终处于“满”的状态，每次插入哪怕只是一个元素，都需要扩容：所以要分配新的内存，将旧内存中的元素复制到新内存中，然后释放旧内存，如此反复。说这种实现方式会带来痛苦，恐怕都算是严重的轻描淡写了。
对于类似向量的类型的内部表示，主要有两种主要的实现方式。其中一种是维护三个指针：
一个指向已分配内存的起始位置
一个指向元素末尾(即当前最后一个元素的下一个位置)
一个指向已分配内存的末尾(请注意，这里我们指的是一个半开区间，包含起始位置，但不包含结束位置)
一段简化的代码如下所示：
template <class T>
class Vector {
T *elems;
T *end_elems;
T *end_storage;
// ...另一种方式是保存一个指向已分配内存起始位置的指针，以及两个整数(分别表示容器的“大小”和“容量”)。这种情况下，简化的代码如下所示：
template <class T>
class Vector {
T *elems;
std:size_t nelems; // 元素数量
std::size_t cap; // 容积
// ...这两种表示方式是等价的，都可以写出正确的容器，但它们在权衡上有所不同。例如：
使用三个指针可以让获取 end() 迭代器的操作非常快，但 size() 和 capacity() 则需要通过指针相减来计算；
而使用一个指针加两个整数的方式可以让 size() 和 capacity() 的调用非常高效，但获取 end() 迭代器时需要进行指针与整数的加法运算。
就占用的空间而言，使用三个指针的表示方式会使 sizeof(Vector<T>) 等于 3 * sizeof(void*)，在 64 位平台上，通常对齐为 8 字节的情况下，可能占用 24 字节。而指针加两个整数的表示方式则可能大小相同，也可能略有不同，具体取决于所使用的整数类型。例如，在 64 位机器上为 size 和 capacity 选择 32 位整数的话，将使整个结构仅占用 16 字节，并保持 8 字节对齐。
这些细节在资源受限的系统中可能会带来显著差异。但可能已经推断出，像 Vector<T> 这样的结构体，其主要的内存消耗其实来自于为 T 对象所分配的内存。
不同的实现会基于大小考量、对平均调用频率更高的成员函数的预估等因素，做出不同的表示方式选择。也必须做出选择；在本书中，我们将采用“一个指针和两个整数”的方式，但这只是几种合理选项之一(完全可以尝试用其他表示方式进行实现，看看会带来什么样的结果！)。
我们将逐步介绍最初的(简化的)Vector<T> 实现，逐步建立对整个机制的理解，并弄清楚为什么称这个实作为“简化的”。第一步已经基本完成，包括通过符合标准库规范的类型别名定义的抽象，并选择内部表示方式：
#include <cstddef>
#include <algorithm>
#include <utility>
#include <initializer_list>
#include <iterator>
#include <type_traits>
template <class T>
class Vector {
public:
using value_type = T;
using size_type = std::size_t;
using pointer = T*;
using const_pointer = const T*;
using reference = T&;
using const_reference = const T&;
private:
pointer elems{};
size_type nelems{},
cap{};
// ...该实现选择使用非静态数据成员初始化器(non-static data member initializers)来初始化 Vector<T> 的三个数据成员，将它们初始化为其默认值(整数为 0，指针为空)，这在本实现中非常合适，它表示一个空容器的状态，这对于默认构造的 Vector<T> 来说是一个合理的选择。
接下来是一些简单但基础的成员函数：
// ...
public:
size_type size() const { return nelems; }
size_type capacity() const { return cap; }
bool empty() const { return size() == 0; }
private:
full() const { return size() == capacity(); }
...注意 empty() 和 full() 的实现。在实现成员函数时，有些人更倾向于在内部直接访问数据成员(使用 nelems 和 cap 而不是 size() 和 capacity())，但建议尽量复用那些更基础的成员函数，来实现那些较为“合成”的函数。这样做可以使代码对实现细节的变化更加不敏感，而 C++ 编译器在处理函数内联方面已经非常高效，特别是对于非虚函数而言。
在当前阶段，所能设计的最有用的成员，大概是迭代器类型以及类的数据成员。这将有助于使用标准算法，以清晰且高效的方式实现其余的成员函数。
C++ 容器通常会将迭代器作为其接口的一部分公开，我们的容器也不例外。我们将为 const 和非 const 版本的迭代器定义类型别名，这样在需要实现诸如带边界检查的迭代器等替代方案时会更加方便。同时，也会实现 begin() 和 end() 成员函数的 const 与非 const 两个版本：
// ...
public:
using iterator = pointer;
using const_iterator = const_pointer;
iterator begin() { return elems; }
const_iterator begin() const { return elems; }
iterator end() { return begin() + size(); }
const_iterator end() const {
return begin() + size();
}
// 为方便用户使用
const_iterator cend() const { return end(); }
const_iterator cbegin() const { return begin(); }
// ...你可能会抱怨为 begin() 和 end() 同时编写 const 和非 const 版本所带来的语法重复问题，这些函数在语法上相似但语义不同。如果使用的是支持 C++23 的编译器，可以利用 “deduced this” 特性在一定程度上简化这一过程：
// 替代方法(需要C++23)
template <class S>
auto begin(this S && self) { return self.elems; }
template <class S>
auto end(this S && self) {
return self.begin() + self.size();
}这种方式表达上稍显复杂，但它通过转发引用(forwarding references)和类型推导系统，将 begin() 和 end() 的两个版本合并为一个，从而减少了重复代码。
现在来实现构造函数。首先来看前两个构造函数：默认构造函数和一个带参数的构造函数，后者接受元素数量和初始值作为参数，例如:Vector<char>(3, 'a') 将生成一个包含三个 ‘a’ 元素的容器。当前的实现中，默认构造函数(这里用了双重默认)实际上为隐式 constexpr，所有非静态成员初始化器都可以在 constexpr 上下文中解析：
// ...
Vector() = default;
Vector(size_type n, const_reference init)
: elems{ new value_type[n] },
nelems{ n }, cap{ n } {
try {
std::fill(begin(), end(), init);
} catch(...) {
delete [] elems;
throw;
}
}
// ...需要注意这个构造函数中的异常处理代码，会在后续不断出现。我们正在编写一个泛型容器，我们对使用的类型 T 事先一无所知。当调用 std::fill() 时，会将 init 参数的值赋给序列中的每一个 T 对象。在这个过程中，可对一个 T 对象赋值一个 T 类型的值，但并不知道这个赋值操作符是否会抛出异常。
我们有责任管理 elems —— 动态分配的 T 类型数组，如果其中一个赋值操作抛出了异常，必须确保在 Vector<T> 构造函数失败之前销毁并释放这个数组；否则，将泄漏掉这块内存，而且(更糟糕的是)在这个数组中已经构造的对象也不会正确析构。
catch(...) 块表示“捕获异常”，在这种情况下并不真正知道捕获的是什么类型的异常；而 throw; 表达式则表示“重新抛出你捕获到的异常”。事实上，并不想在这种情况下处理异常(对执行上下文了解不足，无法判断这是控制台应用程序？图形界面程序？嵌入式系统？或者其他什么？)，只是要确保：当构造 Vector<T> 对象失败时，不会泄漏资源，并让用户代码确切地了解构造函数，为何未能满足其后置条件(即无法构造一个有效的对象)。
复制构造函数的实现模式与此类似，只不过它不是用一个值的多个副本来填充序列，而是将值从源序列(other)复制到目标序列(*this 或 elems)。而移动构造函数当然就完全不同了：
// ...
Vector(const Vector &other)
: elems{ new value_type[other.size()] },
nelems{ other.size() }, cap{ other.size() } {
try {
std::copy(other.begin(), other.end(), begin());
} catch(...) {
delete [] elems;
throw;
}
}
// ...
Vector(Vector &&other) noexcept
: elems{ std::exchange(other.elems, nullptr) },
nelems{ std::exchange(other.nelems, 0) },
cap{ std::exchange(other.cap, 0) } {
}
// ...对于这种类型来说，复制构造函数是一个代价相当高的操作：需要为 other.size() 个对象分配内存(对于非简单可构造的类型 T 来说，这伴随着同样数量的默认构造函数调用)，然后进行 other.size() 次赋值操作，还要加上异常处理机制的开销。
而移动构造函数则要简单得多：它是一个常数时间复杂度(constant-time)、noexcept 的函数。从技术上讲，大多数类并不是非得有移动操作不可(毕竟在没有移动语义的年代，C++ 也运行得很好)，但当可以使用它们时，最好还是这么做。移动操作带来的性能提升可能是巨大的，而且程序的执行速度也会变得可预测。
如果仔细阅读了复制构造函数的代码，可能会注意到 *this 并没有复制 other.capacity()，而是决定让 cap 成为 other.size() 的副本。这种情况下，这样做是正确的：一个容器的 size() 称为该对象的一个显著属性(salient property)，而 capacity() 更像是该对象生命周期中的一个附属产物，反映了随时间增长的历史痕迹。我们希望，在复制一个对象之后，原对象与复制后的对象在使用 operator== 进行比较时是相等的。当然，capacity() 并不参与这个比较逻辑：两个数组如果拥有相同数量的元素，并且每个元素与对方对应元素的值相等，通常就认为相等。从实际角度来说，复制 capacity() 也能工作，但对于大多数使用场景来说将会浪费资源。
为了方便使用，我添加了一个接受 initializer_list<T> 参数的构造函数，这样就可以用一串类型为 T 的值来初始化一个 Vector<T> 对象。至于析构函数，其作用应该不言自明：
// ...
Vector(std::initializer_list<T> src)
: elems{ new value_type[src.size()] },
nelems {src.size() }, cap{ src.size() } {
try {
std::copy(src.begin(), src.end(), begin());
} catch(...) {
delete [] elems;
throw;
}
}
// ...
~Vector() {
delete [] elems;
}从源对象(这里是 other)向目标对象(*this)实现复制赋值操作符会比较复杂，尤其是在处理方式不够严谨的情况下。它涉及以下步骤：清理目标对象在赋值前的内容(清理代码)；复制源对象的状态；正确处理自赋值和复制源对象状态时可能抛出的异常。Scott Meyers 提出了一个非常巧妙的技巧(之后也被无数人重新提出)：复制赋值操作可以表示为复制构造函数(负责复制对象)、析构函数(负责清理)和一个 swap() 成员函数的组合。具体做法是：将参数复制到一个匿名临时对象中(生命周期最短)；然后将这个临时对象与 *this 的状态进行交换；最终使 *this 成为 other 的一个副本。这种编程惯用法总是有效，这也解释了它为何如此流行！
移动赋值操作符的实现方式与复制赋值类似，只不过在赋值操作符的实现中，将复制构造函数替换为移动构造函数即可：
// ...
void swap(Vector &other) noexcept {
using std::swap;
swap(elems, other.elems);
swap(nelems, other.nelems);
swap(cap, other.cap);
}
Vector& operator=(const Vector &other) {
Vector{ other }.swap(*this);
return *this;
}
Vector& operator=(Vector &&other) {
Vector{ std::move(other) }.swap(*this);
return *this;
}
// ...至此，我们已经实现了用于管理 Vector<T> 对象内部表示的特殊成员函数，但要编写一个方便使用的动态数组类型，还需要更多内容。例如，一些常见的成员函数，如允许访问第一个元素(front())、最后一个元素(back())，或通过方括号访问数组中特定索引位置的元素，这些都是用户所期望的：
// ...
reference operator[](size_type n) {
return elems[n];
}
const_reference operator[](size_type n) const {
return elems[n];
}
// 前置条件: 非空
reference front() { return (*this)[0]; }
const_reference front() const { return (*this)[0]; }
reference back() { return (*this)[size() - 1]; }
const_reference back() const {
return (*this)[size() - 1];
}
// ...在一个空的 Vector<T> 上使用 front() 或 back() 会触发未定义行为。也可以让这些函数抛出异常，但这样一来，所有程序都必须为那些偶尔行为不当的代码付出代价(也许只在所谓的“调试模式”下这样做？)。
同样地，借助 C++23 的 “deduced this” 特性，原本需要实现的6个这样的成员函数可以简化为仅3个：
// 替代方法(需要支持C++23)
// ...
template <class S>
decltype(auto) operator[](this S && self,
size_type n) {
return self.elems[n];
}
// 前置条件: 非空
template <class S>
decltype(auto) front(this S &&self) {
return self[0];
}
template <class S>
decltype(auto) back(this S &&self) {
return self[self.size()-1];
}
// ...有些人可能还希望添加一个 at() 成员函数(包括 const 与非 const 版本)，行为类似于 operator[]，但如果尝试访问超出数组边界的索引，则会抛出异常。
至于比较两个 Vector<T> 对象是否相等或不相等，只要为类型实现了迭代器，这件事就相对简单了，可以借助标准算法来实现：
// ...
bool operator==(const Vector &other) const {
return size() == other.size() &&
std::equal(begin(), end(), other.begin());
}
// 自C++20起可省略(由编译器通过operator==()合成)
bool operator!=(const Vector &other) const {
return !(*this == other);
}
// ...终于，我们来到了一本讨论内存管理的书中最令我们感兴趣的部分：如何向容器中添加元素，以及底层内存是如何管理的。
虽然我们不会逐一讨论使用端代码可以用来向 Vector<T> 添加元素的所有机制，但会重点考察 push_back() 和 emplaace_back() 这两个成员函数：
这个实现版本中，将会有两个 push_back() 函数：一个接受 const T& 参数，另一个接受 T&& 参数。前者会将传入的值复制到容器末尾，后者则会将该值移动到末尾。
emplace_back() 成员函数将接受一个可变参数模板包(variadic pack)，然后将这些参数完美转发(perfect forward)给要在容器末尾构造的 T 对象的构造函数。
为了方便起见，emplace_back() 会返回对新构造对象的引用，以便用户代码可以立即使用。而 push_back() 则不会这么做，因为它接收的是一个已经构造好的对象，用户代码本身就已经可以访问。
这三个函数中，首先会检查容器是否已满。如果已满，就会调用一个私有成员函数 grow() 来扩容容器。grow() 函数需要分配比当前容量更大的内存，而这个操作当然可能会失败(比如内存不足)。如果 grow() 抛出了异常，则新元素并未被添加，容器将保持原样不变。此外，grow() 函数还考虑到了当前容量(capacity())可能为 0 的情况，此时会选取一个任意的默认容量值(例如 1 或 8)。
当 grow() 成功完成，就可以在容器存储的末尾添加新的元素。这里元素是通过赋值操作添加的，所以赋值操作符左侧必须存在一个对象。也就是说，grow() 不仅分配了更多的存储空间，还用(很可能是)默认构造的 T 类型对象初始化了这些空间。因此可以推断出，在这种 Vector<T> 的实现中，类型 T 必须提供一个默认构造函数:
// ...
void push_back(const_reference val) {
if(full())
grow();
elems[size()] = val;
++nelems;
}
void push_back(T &&val) {
if(full())
grow();
elems[size()] = std::move(val);
++nelems;
}
template <class ... Args>
reference emplace_back(Args &&...args) {
if (full())
grow();
elems[size()] =
value_type(std::forward<Args>(args)...);
++nelems;
return back();
}
private:
void grow() {
resize(capacity()? capacity() * 2 : 16);
}
// ...在 push_back() 和 emplace_back() 中的插入代码都会执行以下操作(以添加新元素)：
elems[size()] = // 将对象插入
++nelems;你可能会忍不住想把元素数量的增加和实际的插入操作合并为一行：
elems[nelems++] = // 将对象插入千万不要这样做，原因是这会导致异常不安全的代码！具体来说，这是因为后缀自增操作符 operator++() 的优先级非常高(非常高！)，远高于赋值操作符。所以在合并的表达式中，size_++ 会非常早地执行(这可能不被注意，该表达式返回的是 size_ 的旧值)，然后才执行赋值操作。但赋值操作可能会抛出异常：将一个类型为 T 的对象赋值给另一个同类型的对象，而我们并不知道 T::operator=(const T&) 是否会抛出异常。当然，如果真的抛出了异常，那么赋值就不会完成，容器末尾也不会添加新的对象；但此时 size_ 已经递增了，这就导致 Vector<T> 对象处于不一致的状态 —— 它认为自己多了一个元素，但实际上并没有。
这里有一个通用的技巧：确认可以安全地修改对象之前，不要改变它的状态。尽量先执行可能抛出异常的操作，然后再执行会改变对象状态的操作。这样做会让你的代码更稳健，也能显著降低对象被破坏的风险。
grow() 成员函数通过调用 resize() 来完成其工作，并将容器的容量加倍，除非当前容量为 0，在这种情况下会选择一个默认容量。那么 resize() 是如何工作的呢？在实现中，这需要分配足够满足新容量需求的内存，然后将对象从旧的内存块复制或移动到新的内存块中，接着用新的内存块替换旧的内存块，并更新容量。
我们如何知道应该移动还是复制对象呢？移动可能会销毁原始对象，所以只在 T::operator=(T&&) 明确声明为 noexcept 时才进行移动。std::is_nothrow_move_assignable<T> 特性是用来判断此条件是否满足的首选工具(如果该条件不满足，则复制对象，这样更为安全，并且复制操作会保留原始对象的完整性)：
// ...
public:
void resize(size_type new_cap) {
if (new_cap <= capacity()) return;
auto p = new T[new_cap];
if constexpr(std::is_nothrow_move_assignable_v<T>){
std::move(begin(), end(), p);
} else try {
std::copy(begin(), end(), p);
} catch (...) {
delete[] p;
throw;
}
delete[] elems;
elems = p;
cap = new_cap;
}
// ...这段代码并不是特别简单，但也不算难以理解。这仅仅是我们的第一版实现，对于大量类型来说，性能会比 std::vector<T> 慢很多。
我们还需要讨论这种容器的最后一个方面：如何向容器中插入(insert())元素，以及如何从容器中删除(erase())元素。在标准库中那些工业级强度的容器里，有大量函数可以完成这两个任务，因此仅实现其中各一个最基本的功能：在容器中的指定位置插入一个元素序列，以及删除容器中指定位置的元素。
insert() 成员函数将是一个模板函数，接受一对名为 first 和 last 的源迭代器，以及一个名为 pos 的 const_iterator，用来表示在 vector<T> 对象中的插入位置。将其设计为模板，所以可以使用任何容器的迭代器作为插入值的来源。
函数内部，将使用一个名为 pos_ 的非 const 版本的 pos，这是因为正在编写一个简化版且不完整的容器。在这个容器中，许多本应支持 const_iterator 的成员函数都尚未实现。
为了执行插入操作，我们会计算两个值：remaining(剩余空间，以可容纳的对象数量来表示)和 n(即将插入的对象数量)。如果可用空间不足，将通过 resize() 成员函数分配更多内存。当然，调用 resize() 很可能导致 pos_ 变得无效(指向的是旧的内存块，resize() 完成后该内存块将替换)，因此在调整大小之前会先计算 pos_ 所在的相对索引，并在调整大小之后在新内存块中重新计算出等价的 pos_。
插入过程中一个有趣的设计点在于：需要将从 pos_ 到 end() 的对象复制(或者移动，但为了简单起见这里只考虑复制)到 end()+n 所表示的终点位置。为了避免在复制过程中覆盖正在复制的对象，这个复制操作必须从后往前进行(即从最后一个元素向第一个元素方向复制)。标准库中的 std::copy_backward() 算法正是这样设计的：其第三个参数表示复制目标的结束位置，而不是起始位置。
只有在这之后，我们才会将由 first 和 last 所确定的序列复制到 pos_ 的位置，更新 Vector<T> 对象中的元素数量，并返回标准所要求的结果(即指向第一个插入元素的迭代器；如果 first == last，表示没有插入任何元素，则返回 pos)。
template <class It>
iterator insert(const_iterator pos, It first, It last) {
iterator pos_ = const_cast<iterator>(pos);
// 有意使用无符号整型
const std::size_t remaining = capacity() - size();
const std::size_t n = std::distance(first, last);
if (remaining < n) {
auto index = std::distance(begin(), pos_);
resize(capacity() + n - remaining);
pos_ = std::next(begin(), index);
}
std::copy_backward(pos_, end(), end() + n);
std::copy(first, last, pos_);
nelems += n;
return pos_;
}我们的 erase() 成员函数将接受一个名为 pos 的 const_iterator 参数，表示要从 Vector<T> 对象中删除的元素的位置。这里再次使用了一个名为 pos_ 的非 const 迭代器，删除 end() 所指向的位置是一个空操作(这很合理)；否则，将从 next(pos_) 到 end() 的元素线性复制到从 pos_ 开始的位置，从该有效地位置开始，用每一个元素的后继元素进行覆盖。
最后，将最后一个元素替换为某个默认值。这一步看起来可能没有必要，但实际上很重要，因为末尾的 T 对象可能持有一些需要立即释放的资源。例如，在一个使用 Vector<Res> 对象的程序中，如果 Res 是一个在析构时释放资源的 RAII 类型，不替换“刚刚超出末尾”的那个对象，可能会导致相关资源直到 Vector 对象销毁时才释放，而这个时间点可能比使用端代码预期的要晚很多。
然后更新 Vector<T> 对象中的元素数量。同样，这要求 T 拥有一个默认构造函数，这并不是一个本质上的必要条件(并且本章稍后我们会解除这个限制)：
iterator erase(const_iterator pos) {
iterator pos_ = const_cast<iterator>(pos);
if (pos_ == end()) return pos_;
std::copy(std::next(pos_), end(), pos_);
*std::prev(end()) = {};
--nelems;
return pos_;
}我确信你一定在想，我们怎样才能做得更好。放心，很快就会回到这个问题上。与此同时，我们将会研究如何实现一个简单的基于节点的容器(类似于 std::forward_list<T> 的自制类型)。