本文是对《最好的C++教程》的动手写数据结构部分的一个整理，主要包含91p动手写Array数组和92p动手写Vector数组的内容。
自己动手来写这些数据结构是学习C++的绝佳方法，并且可以更加深刻的理解标准库中Vector和Array的实现和用法。
?? 强烈建议自己尝试实现一个包含下面这些知识点的Array和Vector，与文章中实现进行对比。强烈建议看完本文后关闭浏览器，尝试还原该实现以达到最佳学习效果。如果感觉难以理解，可以观看原视频，讲的要细致不少，如果原视频仍觉得困难，可以选择相应知识点参看系列教程前面部分。Array数组主要包含的知识点有：模板，constexpr，const成员函数
Vector数组主要包含的知识点有：动态扩容，placement new，move semantics，emplace_back
原作者视频链接：https://youtu.be/TzB5ZeKQIHM ，https://youtu.be/ryRf4Jh_YC0
文中代码github链接：https://github.com/zhangyi1357/Little-stuff
在大多数情况下，当我们需要一个数组时，我们都会优先使用vector，因为vector可以动态扩容，效率也足够高，非常好用。
但是你需要array数组的情况在于很多时候只需要一个静态大小的数组，而这种情况下vector的堆内存分配相较于array数组直接在栈上分配内存的效率就比较低了。
实际上一个Array数组的实现非常简单，如果你对模板比较熟悉的话，基本上就是给一个数组写一个模板然后给用户几个接口。
首先我们来看看其最终的API，这里我们直接以其一个使用的示例来看我们需要完成哪些功能
array[]运算符来索引，可以读取也可以写入Size方法返回其大小，其中Size需要在编译器确定Data方法返回其数据地址，可以利用memset批量设置其值int main() { constexpr int size = 5; Array<int, size> data; static_assert(data.Size() < 10, "Size is too large"); data[0] = 2; data[1] = 3; data[2] = 5; for (size_t i = 0; i < data.Size(); ++i) std::cout << data[i] << std::endl; std::cout << "-----------------" << std::endl; memset(data.Data(), 0, data.Size() * sizeof(int)); for (size_t i = 0; i < data.Size(); ++i) std::cout << data[i] << std::endl; std::cout << "-----------------" << std::endl; Array<std::string, size> data2; data2[0] = "Cherno"; data2[1] = "C++"; for (size_t i = 0; i < data2.Size(); ++i) std::cout << data2[i] << std::endl; return 0;}其输出为
2350336165216-----------------00000-----------------ChernoC++这里有一个小点需要注意，我们可以看到未经初始化的Array在其类型为int和std::string时有不同的表现，int类型其值是未定义的，所以可能输出任意值，例如上面的336165216，而std::string类型会自动初始化为一个空串。
根据以上API，可以给出如下简洁代码实现
template <typename T, size_t S>class Array {public: constexpr int Size() const { return S; } T& operator[](size_t index) { return m_Data[index]; } const T& operator[](size_t index) const { return m_Data[index]; } T* Data() { return m_Data; } const T* Data() const { return m_Data; }private: T m_Data[S];};注意到对[]运算符的重载和Data方法都给出了两个版本，一个const一个非const版本。
const版本的函数性质和返回值都是const，这主要是为了兼容const Array<T, S>的用法，因为一个const Array<T, S>类型的对象是不能调用非const成员函数的，而显然我们也不希望这样一个类型的返回值是非const的，因为我们不想通过该成员函数来改变其值。
注意到前面的main函数中有如下一条语句
static_assert(data.Size() < 10, "Size is too large");这条语句用于编译期检查，那么我们的Size方法一定也要能在编译器确定其值，这一点是完全可以做到的，因为我们要求的模板参数S需要在编译期就能确定其值，所以我们只需要在Size方法的返回值前面加上一个constexpr表示该值可以在编译期求取即可。
Vector数组相较于Array的最大特点就在于动态扩容，我们不用指定其初始容量，而在使用过程中可以不断地以O(1)的时间复杂度向其尾部插入元素或读取任意位置的元素。
后文我们将先阐述动态扩容策略，并在此策略上完成基础版本的实现，然后在此基础上逐步优化性能添加功能。
首先我们需要在O(1)的时间复杂度内读取任意位置的元素，所以肯定需要连续存储的内存空间，不考虑使用链表等数据结构。
其次需要O(1)的时间复杂度在尾部进行插入，Array数组其实可以满足这点，但是其容量有限，那么很直观的一个思路就是先分配一个有限容量的数组，如果满了还需要插入就重新分配一个更大的数组。
而动态扩容的trick就在此处，每次重新分配之后我们都需要将数组完整地挪到新的内存地址去，这一过程是非常耗时的，对于一个长度为n的数组来说其时间复杂度为O(n)。
我们解决的办法是每次分配数组的时候直接多分配一些空间，这样很多次插入操作才会有一个扩容操作，于是扩容的高消耗就被均摊到了每次的插入操作上，达到总体的O(1)时间复杂度。
那么具体多分配多少空间呢，我们要保证一次扩容操作被分摊到O(n)次插入操作上才行，所以扩大的容量必须要是O(n)这个数量级的。
实际中不同的编译器的处理方式不尽相同，MSVC中以1.5倍扩容，GCC中以2倍扩容。本文采取2倍扩容的方式。
基础版本只需要实现以下的简单API即可，拆解开来我们需要完成
PushBack方法Size方法template<typename T>void PrintVector(const Vector<T>& vector) { for (size_t i = 0; i < vector.Size(); ++i) std::cout << vector[i] << std::endl; std::cout << "---------------------------" << std::endl;}int main() { Vector<std::string> vector; vector.PushBack("Cherno"); vector.PushBack("C++"); vector.PushBack("Vector"); PrintVector(vector); return 0;}该实现较为简单，直接给出，各部分都有详细注释。注意我们的初始化策略是分配分配两个元素的空间。
template <typename T>class Vector {public: Vector() { ReAlloc(2); } ~Vector() { delete[] m_Data; } void PushBack(const T& value) { // check the space if (m_Size >= m_Capacity) ReAlloc(m_Size + m_Size); // push the value back and update the size m_Data[m_Size++] = value; } T& operator[](size_t index) { return m_Data[index]; } const T& operator[](size_t index) const { return m_Data[index]; } size_t Size() const { return m_Size; }private: void ReAlloc(size_t newCapacity) { // allocate space for new block T* newBlock = new T[newCapacity]; // ensure no overflow if (newCapacity < m_Size) m_Size = newCapacity; // move all the elements to the new block for (int i = 0; i < m_Size; ++i) newBlock[i] = m_Data[i]; // delete the old space and update old members delete[] m_Data; m_Data = newBlock; m_Capacity = newCapacity; }private: T* m_Data = nullptr; size_t m_Size = 0; size_t m_Capacity = 0;};以上的基础版本可以实现基本的功能，但是其效率却太低，存在许多复制。我们可以自己写一个class测试一下。
class Vector3 {public: Vector3() {} Vector3(float scalar) : x(scalar), y(scalar), z(scalar) {} Vector3(float x, float y, float z) : x(x), y(y), z(z) {} Vector3(const Vector3& other) : x(other.x), y(other.y), z(other.z) { std::cout << "Copy" << std::endl; } Vector3(const Vector3&& other) : x(other.x), y(other.y), z(other.z) { std::cout << "Move" << std::endl; } ~Vector3() { std::cout << "Destroy" << std::endl; } Vector3& operator=(const Vector3& other) { std::cout << "Copy" << std::endl; x = other.x; y = other.y; z = other.z; return *this; } Vector3& operator=(Vector3&& other) { std::cout << "Move" << std::endl; x = other.x; y = other.y; z = other.z; return *this; } friend std::ostream& operator<<(std::ostream&, const Vector3&);private: float x = 0.0f, y = 0.0f, z = 0.0f;};std::ostream& operator<<(std::ostream& os, const Vector3& vec) { os << vec.x << ", " << vec.y << ", " << vec.z; return os;}int main() { Vector<Vector3> vec; vec.PushBack(Vector3()); vec.PushBack(Vector3(1.0f)); vec.PushBack(Vector3(1.0f, 2.0f, 3.0f)); PrintVector(vec); return 0;}对于基础版本的API其输出为
CopyDestroyCopyDestroyCopyCopyDestroyDestroyCopyDestroy0, 0, 01, 1, 11, 2, 3---------------------------中间连着两个Copy和两个Destroy是扩容过程。除此之外的都是PushBack时产生的。
实际上我们并不需要这么多复制，在PushBack的时候可以将原来的内容直接移动到新的位置，扩容过程也是一样。这就要用到C++11的移动语义的特性了。
消除以上的Copy其实很简单，只需要重载一个接受右值的PushBack并在其中进行move即可，另外要注意扩容过程也需要改成move的。
// new PushBack Method void PushBack(T&& value) { // check the space if (m_Size >= m_Capacity) ReAlloc(m_Size + m_Size); // push the value back and update the size m_Data[m_Size++] = std::move(value); }// in ReAlloc for (int i = 0; i < m_Size; ++i) newBlock[i] = std::move(m_Data[i]);可以看到以下结果
MoveDestroyMoveDestroyMoveMoveDestroyDestroyMoveDestroy0, 0, 01, 1, 11, 2, 3---------------------------可以看到现在全都是Move，没有Copy，效率提高！
好了，现在我们有很高效的PushBack实现，但是我们发现每一次PushBack仍然在外面构造好一个变量然后移动到Vector里面。
那么有没有这样一种可能，直接把构造需要的参数给到Vector，然后直接在给定的地址空间进行对象的构造。
实际上这一节介绍的EmplaceBack和Placement New就可以做到这一点。
可以看到这里给EmplaceBack的直接是构造Vector3所需的参数而不是Vector3。
int main() { Vector<Vector3> vec; vec.EmplaceBack(); vec.EmplaceBack(1.0f); vec.EmplaceBack(1.0f, 2.0f, 3.0f); PrintVector(vec); return 0;}首先是EmplaceBack的实现，实现依赖于模板参数展开，这里不做详细讨论，仅给出其实现。
注意到实现中的new运算符，不同于一般的new运算符，这里给出了一个参数作为需要new的位置的地址，这样就可以直接在原地构造而不需要移来移去。
为了更好地理解placement new，有必要讲一下new运算符的机制，new运算符实际上会做两件事情
而这里相当于内存分配已经提前做好了，我们只需要在相应的位置调用构造函数即可。
template<typename... Args> T& EmplaceBack(Args&&... args) { // check the space if (m_Size >= m_Capacity) ReAlloc(m_Size + m_Size); // Placement new new (&m_Data[m_Size]) T(std::forward<Args>(args)...); return m_Data[m_Size++]; }测试结果为
MoveMoveDestroyDestroy0, 0, 01, 1, 11, 2, 3---------------------------Amazing! 我们只在扩容的时候进行了两次Move，所有的对象都是在原地直接进行构造的。
前面说了new运算符会干两件事，分配内存和调用构造函数，那么在ReAlloc中我们就使用了new，同时做了分配内存和调用构造函数两件事，后面又将原来的值挪到新分配的地方，那构造函数的调用不就浪费了？
是的！实际上这个问题同样会反映在delete运算符上，对于new来说只是效率降低了，但对delete来说可能会造成严重的bug。
不过不要着急后面会解决这个问题。
前面的过程中为了输出简单省略了析构函数，实际上析构函数不可或缺，否则会有内存泄漏。
同时我们增加PopBack的功能。而这二者组合起来会造成一个非常严重的问题。
int main() { Vector<Vector3> vec; vec.EmplaceBack(); vec.EmplaceBack(1.0f); vec.EmplaceBack(1.0f, 2.0f, 3.0f); PrintVector(vec); vec.PopBack(); vec.PopBack(); PrintVector(vec); return 0;}其实现非常简单
void PopBack() { if (m_Size > 0) { --m_Size; m_Data[m_Size].~T(); } } ~Vector() { delete[] m_Data; }输出也正常：
MoveMoveDestroyDestroy0, 0, 01, 1, 11, 2, 3---------------------------DestroyDestroy0, 0, 0---------------------------DestroyDestroyDestroyDestroy但是暗藏玄机的是，如果我们的Vector3类中有指针指向某一片内存空间的话，那么PopBack中会调用一次Vector3的析构函数，然后析构函数中的delete还会对该地址空间调用一次析构函数，那么该内存空间将被delete两次！
接下来我们着手解决该问题。
我们解决的办法即本小节标题::operator new/delete。首先给出测试的API。
class Vector3 {public: Vector3() { m_MemoryBlock = new int[5]; } Vector3(float scalar) : x(scalar), y(scalar), z(scalar) { m_MemoryBlock = new int[5]; } Vector3(float x, float y, float z) : x(x), y(y), z(z) { m_MemoryBlock = new int[5]; } Vector3(const Vector3& other) = delete; Vector3(Vector3&& other) : x(other.x), y(other.y), z(other.z) { std::cout << "Move" << std::endl; m_MemoryBlock = other.m_MemoryBlock; other.m_MemoryBlock = nullptr; } ~Vector3() { std::cout << "Destroy" << std::endl; delete[] m_MemoryBlock; } Vector3& operator=(const Vector3& other) { std::cout << "Copy" << std::endl; x = other.x; y = other.y; z = other.z; return *this; } Vector3& operator=(Vector3&& other) { std::cout << "Move" << std::endl; x = other.x; y = other.y; z = other.z; return *this; } friend std::ostream& operator<<(std::ostream&, const Vector3&);private: float x = 0.0f, y = 0.0f, z = 0.0f; int* m_MemoryBlock = nullptr;};std::ostream& operator<<(std::ostream& os, const Vector3& vec) { os << vec.x << ", " << vec.y << ", " << vec.z; return os;}int main() { { Vector<Vector3> vec; vec.EmplaceBack(); vec.EmplaceBack(1.0f); vec.EmplaceBack(1.0f, 2.0f, 3.0f); PrintVector(vec); vec.PopBack(); vec.PopBack(); PrintVector(vec); } std::cout << "hello" << std::endl; return 0;}对于此此前程序给出的输出为
MoveMoveDestroyDestroy0, 0, 01, 1, 11, 2, 3---------------------------DestroyDestroy0, 0, 0---------------------------DestroyDestroy可以看到并没有输出hello，应该是程序异常退出了，给程序打个断点在gdb下调试看看结果
我们使用的办法就是将new和delete的两阶段分开，其中分配和回收的过程则调用::operator new和::operator delete。
具体实现如下：
~Vector() { Clear(); ::operator delete(m_Data, m_Capacity * sizeof(T)); } void Clear() { for (int i = 0; i < m_Size; ++i) m_Data[i].~T(); m_Size = 0; } void ReAlloc(size_t newCapacity) { // allocate space for new block T* newBlock = (T*)::operator new(newCapacity * sizeof(T)); // ensure no overflow if (newCapacity < m_Size) m_Size = newCapacity; // move all the elements to the new block for (int i = 0; i < m_Size; ++i) new(&newBlock[i]) T(std::move(m_Data[i])); // delete the old space and update old members Clear(); ::operator delete(m_Data, m_Capacity * sizeof(T)); m_Data = newBlock; m_Capacity = newCapacity; }可以看到主要就是将析构函数的调用挪到了Clear函数里，只析构有元素的位置，然后删除和分配空间用::operater new/delete。
注意::operator delete的该重载函数直到C++14才得到支持，所以以上代码需要编译命令-std=c++14或更高。
其输出结果为
MoveMoveDestroyDestroy1, 2, 3---------------------------Destroy---------------------------hello没有问题！NICE！
以上的Vector模板类已经实现了动态扩容和高效的空间管理，但是仍有许多尚未完成的部分，例如迭代器，erase方法等，有能力的小伙伴可以尝试实现更多。后续我也会继续完善。
Cherno视频教程91P（Array）bilibili
Cherno视频教程92P（Vector） bilibili
C++ STL vector扩容原理分析 - Jcpeng_std - 博客园 (cnblogs.com)