容器是一种保存值的集合的数据结构。C 提供了较原始的内建容器，例如数组和结构体；C++ 标准库在此基础上提供了更丰富、更强大的容器。

标准库还有很多有用的算法和迭代器，在开发程序过程中，应该优先选用这些工具。虽然 C++ 标准库提供了这些容器，但是 C++ 也为用户提供了编写自己容器的方法——也就是说，C++ 没有将容器的设计限定到某种单一的方法上。

通过研究斯坦福 C++ 库，我们发现了一个现象。早期教材配套库在设计 Vector 时，使用的是基于动态数组的相对原始的设计策略；而最新版采用的策略，却是基于标准库 std::vector 进行的扩展，增加了很多参数方面的检查，为初学者的使用提供了更多方便。这也给了我们一个启示：即便标准库没有我们需要的工具，也应该基于标准库进行扩展，而不是采用原始的方式编码。

但作为练习，我们接下来将要实现一个基于动态数组的 vector，接口类似标准库的 std::vector。通过这几个小任务，我们尝试构建一个小型的 C++ 知识框架，目的是能够写出一个兼容标准库（STL-compliant）的容器，体会 C++ 标准库容器的开发过程。所谓兼容标准库，就是让我们的容器能够复用大量现有的标准库算法。

这里采用的开发策略是逐步求精。也就是说，先实现一个基本的容器，逐步添加模板、重载等技术，而不用太关心标准库的细节。在基本实现完成后，再尝试添加迭代器等技术，以便让容器可以兼容标准库的框架。

Task 1：类 class

本小节视频讲解时间段 00:24:05-00:35:36

在 C++ 中，我们通过类来定义自己的数据类型。用类来表示概念，可以使我们更容易编写、调试和修改程序。在这个任务中，我们将实现一个基本的 vector 接口：

class vector {
public:
    // Special Member Functions
    vector(size_t capacity = 10);
    ~vector();

    // Element Access
    int& at(size_t index);
    int& front();
    int& back();

    // Iterators
    int* begin();
    int* end();

    // Capacity
    bool empty();
    size_t size();
    size_t capacity();

    // Modifiers
    void clear();
    void reserve(size_t n);
    int* insert(int* pos, int value);
    int* erase(int* pos);
    void push_back(int value);
    void pop_back();

private:
    int* m_elems;
    size_t m_capacity;
    size_t m_size;
};

命名空间

C++ Primer，Ch 18.2

当程序开发用到多个库时，难免会发生名称冲突的情况。传统的方式是通过定义特殊的命名规范来避免冲突，比如 m_data 表示成员变量，p_arr 表示指针数组。

C++ 还提供了命名空间（namespace）来防止名称冲突。每个命名空间都是一个作用域，变量名必须通过命名空间才可识别。

由于我们的 vector 和标准库中的容器同名，所以，此处发生了名称冲突。这里可以使用 namespace 增加 cs101 名称限定符，在使用时也需要 cs101::vector 加以限定。

namespace cs101 {
    class vector { 
        ... // starting from here
	};
}

动态数组

C++ Primer，Ch 12.2

认识一个类，应该先从 private 部分开始，了解其底层表示。参考标准库，我们使用动态数组作为底层的表示结构。除此之外，我们还有必要记录数组的分配大小和逻辑大小，方便其他接口的使用。虽然分配大小可以通过数组名和元素类型计算得出，但为了使用上的便利和不必要的计算，我们增加这个成员。

private:
    int* m_elems;
    size_t m_capacity;
    size_t m_size;

NOTE

大多数应用应该使用标准库容器而不是动态数组。使用容器更为简单，更不容易出现内存管理错误，并且可能有更好的性能。

构造/析构函数

默认构造函数（default constructor）没有参数，标准库 vector 默认不分配数组；我们的 vector 使用默认参数，不提供参数时将分配 10 个元素的数组。此处的构造函数，既充当了默认构造函数的功能，又充当了带参数构造函数的功能。

析构函数（destructor）此处只需要删除动态数组，注意使用 delete[]。

vector(size_t capacity = 10);
~vector();

其他一些查询函数的实现较为简单：

bool empty();
size_t size();
size_t capacity();

指针和迭代器

Textbook，Ch 20.6

迭代器（iterator）是指针（pointer）的泛化或抽象，允许 C++ 程序（特别是标准库算法）以统一的方式操作不同的数据结构。为了正确、高效地操作不同的数据结构，C++ 标准不仅规定了迭代器的接口，还规定了迭代器的语义和其复杂度。

由于数组结构的特殊性，此处为了开发的简便，只用了裸指针的别名表示迭代器：

using iterator = int*;

为了支持基于范围的 for 循环，我们需要实现 begin 和 end。

for (vector::iterator itr = intVec.begin(); itr < intVec.end(); ++itr) {
    std::cout << *itr << std::endl;
}

for(auto item: vec){
    cout << item << endl;
}

动态扩容

插入操作 insert 的第一次尝试，无扩容操作。使用策略是分配一个足够大的数组，防止溢出；但缺点是造成了空间的浪费。

vector::iterator vector::insert(iterator pos, int value) {
    // 移动 pos 后面的元素，留出插入空间
    for (int* i = end() - 1; i >= pos; i--) {
        *(i + 1) = *i;
    }
    // 插入 value
    *pos = value;
    // 更新 m_size
    m_size++;
    // 返回插入位置的指针
    return pos;
}

我们需要实现一种新的策略，在程序运行过程中，可以根据元素的数量动态地调整内存的空间，即动态分配（dynamical allocation）。

参考标准库文档编写 std::vector<T,Allocator>::reserve 方法，实现动态数组内存管理：

  • 当 n 小于等于当前 capacity 时，不作任何操作
  • 当 n 大于当前 capacity 时，增加 capacity 以便可以容纳 n 个元素

TIP

扩容系数 Growth factor

为了避免多次调整大小产生的成本，动态数组会大幅度调整大小。动态数组的扩容系数取决于几个因素，包括时空权衡和内存分配器本身使用的算法。在 C++ 中，一般选择的扩容系数为 2。

借助摊销分析，扩容操作的平均时间复杂度为 $O(1)$，这是教学中的一个常见示例，参考教材 12.9 节。

参考标准库文档编写 std::vector<T,Allocator>::insert 方法，注意参数 pos 为迭代器（裸指针）：

  • 在 pos 指向的位置插入 value 值
  • 必要时需要扩容，可以利用 reserve 方法
  • 返回 pos 迭代器，以便需要时可以访问插入的元素
  • 查看测试案例，了解客户端用法

Task 2：模板 template

C++ Primer，Ch 16

本小节视频讲解时间段 00:35:36-00:47:48

面向对象语言，例如 Python，所有类型都是动态的，类型在运行时确认；C++ 使用模板技术，类型在编译期就能够确认。在这个任务中，我们将使用模板技术，让 vector 容器支持不同的类型。

模板是泛型编程的基础，是创建类或函数的公式。我们已经接触过函数模板，模板可以看作是以类型为参数的编译期函数。

当编译器遇到一个模板定义时，并不会生成代码。只有当代码中实例化一个特定版本时，编译器才会生成代码。这一特性将影响我们如何组织代码，本课程中采用定义和实现放在同一个头文件中的策略。

类模板的定义和函数模板类似，但使用上有所区别，类模板必须使用前括号明确类型信息，否则编译器无法自动推断模板类型。

类模板定义以 template 开始，后面尖括号包含类模板参数列表。根据 C++ 标准要求，类模板定义中需要添加 value_type 成员类型，所以在后续的接口声明中，可以用此别名替换所有类型：

namespace cs101 {

template <typename T>     // 类模板定义
class vector {
public:
	using value_type = T; // 类成员定义（标准要求）
	
	value_type &at(size_t index);
	value_type &front();
	value_type &back();

private:
    ...
    
}; // end of vector

} // end of cs101

不同类型的类，拥有不同类型的成员函数实现。为了实现成员函数的模板化，同样需要以 template 开始：

template <typename T>
vector<T>::vector(size_t capacity)
    : m_elems{new int[capacity]}, m_capacity{capacity}, m_size{0} {}

template <typename T> 
bool vector<T>::empty() {
	return size() == 0;
}

当成员函数返回值包含类模板成员名时，需要结合模板和限定名来访问。例如，返回值为 value_type 需要按如下代码处理：

template <typename T>
typename vector<T>::value_type &vector<T>::at(size_t index) {
	return *(begin() + index);
}

Task 3：常量正确 const-correctness

Const Correctness, C++ FAQ (isocpp.org)

本小节视频讲解时间段 00:48:00-01:01:00

使用 const 声明对象（或者对象引用、对象指针），则表明对象的值无法改变。在目前的实现中，我们的 vector 容器还不支持常量接口。如果定义这样的常量对象，编译器将禁止调用 vector 的所有方法。

对于一些查询接口，例如 size()、isEmpty() 等，本身并不会改变对象的值。如果也禁用这些接口，类的通用性将变差。对于此类接口，可以使用 const 进行标记，这样不管使常量对象还是非常量对象都可以调用此类接口。

以下接口仅作查询操作，只需要在声明后面添加关键字：

bool empty() const;
size_t size() const;
size_t capacity() const;

相应的实现也需要同样的调整：

template <typename T>
size_t vector<T>::size() const {
	return m_size; 
}

而像 at()、front() 这样的接口，既可以用于查询操作又可以用于修改操作。这类接口需要同时实现两个版本：

value_type& at(size_t index);
const value_type& at(size_t index) const;

在使用迭代器时，如果不修改对象的内容，经常使用如下语法：

for(const int & item: vec){
    cout << item << endl;
}

此时也需要添加常量迭代器，以及常量版本的 begin()、end() 接口：

using iterator = T*;
using const_iterator = const T*;

iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;

NOTE

对于上述 at() 这样的接口，在实现过程中我们发现函数体内的代码完全一致。为了避免 const 和 non-const 成员函数中代码重复，参考 Scott Meyer 在《Effective C++, 3rd》中条款 3 介绍的写法。

Task 4：运算符重载 operator overloading

本小节视频讲解时间段 00:11:10-00:31:08

内置类型支持大量的运算符，这些运算符同样可以用于自定义的类型，并重新赋予新的含义，例如字符串的 + 运算符表示连接两个字符串，而不是数值类型的加法操作。这个任务中，我们将让 vector 容器支持一些运算符操作。

// 注意要保持常量正确
value_type &operator[](size_t index);
const value_type &operator[](size_t index) const;

// 注意重载为全局函数
std::ostream &operator<<(std::ostream &os, const vector<T> &vec);

运算符本质仍然是函数，函数名由关键字 operator 和运算符构成，例如 str1 + str2 会转换为类似 operator+(str1, str2) 这样的函数进行处理。运算符函数和普通函数一样，也有返回值、参数列表、函数体等内容。

关于运算符重载，标准也作了一些限制（参考 Restrictions）。

方法既可以设计为成员函数，也可以设计为全局函数。 对于运算符重载，有些应该设计为成员函数，比如 =、[]；有些推荐设计为全局函数，比如 <<、>> 等。这些约定，标准文档也作了说明，比如 Member access operators 推荐的原型示例。

将模板类接口设计为全局函数时，需要解决两个问题。首先，全局函数无法访问类的私有成员，解决这个问题可以使用 friend 关键字标记函数声明，并添加到类的接口中。其次，模板函数在类中声明时，仍然需要使用 template 模板。此时可能会遇到类型名冲突的问题，解决方法是在类中使用另一个名称标记模板的 typename 以避免和类模板类型名称冲突。参考 overloading friend operator« for template class

template <typename K, typename M, typename H = std::hash<K>>
class HashMap {
    ...
    
    template <typename K2, typename M2, typename H2>
    friend std::ostream& operator<<(std::ostream& os, const HashMap<K2, M2, H2>& map);

    ...
};

Task 5：拷贝语义 copy semantics

C++ Primer，Ch 13

本小节视频讲解时间段 00:31:08-01:04:22

在 CS101 的类实现中，我们只强调了如何创建对象（构造函数）和如何销毁对象（析构函数）。除了对象的创建和销毁，我们还需要控制对象的拷贝和赋值。这个任务中，我们将实现拷贝构造函数和拷贝赋值运算符。

vector(const vector<T> &other);               // copy constructor
vector<T> &operator=(const vector<T> &other); // copy assignment

下面的两种用法分别演示了拷贝构造函数和拷贝赋值运算符的使用场景和区别：

// create vec1
vector<std::string> vec1;
vec1.push_back("A");
vec1.push_back("B");
vec1.push_back("C");

// copy constructor: create vec2 using the contents of vec1
vector<std::string> vec2 = vec1;

// create vec3 with default value
vector<std::string> vec3;
// copy assignment: replace vec3 using the contents of vec1
vec3 = vec1;

理解两者的工作机制将有助于后续的代码实现。拷贝构造函数是使用另一个对象的值来创建一个新的对象；而拷贝赋值运算符操作的是一个已有的对象，只是利用另一个对象的值替换已有对象的内容。

三法则（rule of three）的要求是，假如类实现了下面任意一个成员函数，则其他两个也必须实现：

  • 析构函数
  • 拷贝构造函数
  • 赋值运算符

我们的 vector 已经包含了析构函数，所以此时编译器会自动为我们生成其他两个。由于在类中涉及到动态内存分配，这些自动生成的成员函数并不能满足内存管理的要求。底层原因是，编译器和运行时只能管理栈内存，所以堆内存并不会得到正确处理，因而造成了内存问题。

实现拷贝构造函数和拷贝赋值运算符，可以参考上述文档的示例。需要注意的是，拷贝赋值运算符可能会发生自我拷贝，例如 vec1 = vec1，此时需要作一些特别的处理。

Task 6：移动语义 move semantics

C++ Primer，Ch 13

左值引用 vs 右值引用

我们已经了解过引用在函数参数等场景下的应用，现在我们将这一概念继续细化。目前接触过的引用，称为左值引用：

  • 语法格式为 T&，这里 T 为类型名
  • 运算符 = 右边的表达式必须是命名变量，即在调试器面板中可以看到这个变量名和值
int num{3};
int& lref = num;

以下写法违背了上述第二条规则，虽然函数返回整型，但这个返回值是没有名称的：

int fn() { return 3; }
int& lref = fn();       // error

函数的返回值是一个临时的值，如果没有变量进行存储，系统将会自动丢弃该值。所以，对于上述写法可以作如下改写：

int fn() { return 3; }
int temp = fn();       // copy ctor
int& lref = temp;

以上对左值引用的修改，在函数调用的使用中，影响更大。我们使用引用的动机是避免拷贝，提升效率，但增加的临时变量 temp 却再次发生了拷贝。

为了解决这个问题，C++ 又推出了一个新的引用类型，称为右值引用：

  • 语法格式为 T&&，这里 T 为类型名
  • 用于绑定临时对象，避免销毁

左值引用的是一个对象的变量，而右值引用的是一个临时对象的表达式值。因为变量通常都是在 = 的左边，而临时对象的表达式值通常都是在 = 右边，所以左值/右值的命名在理解上也较为直接。

有了这个新技术，我们就可以更好地改写上述问题，避免拷贝：

int fn() { return 3; }
int&& rref = fn();       // oook

另外，左值是无法使用右值引用的，如果强行进行绑定，需要借助 std::move 来操作：

int num{3};
int&& rref = std::move(num);

拷贝 vs 移动

目前我们已经完成了对象的拷贝控制。将一个对象的值拷贝给另一个对象，对于基本类型来说，这是唯一合理的方式；但对于容器来说，特别是元素数量很多的情况，这样的拷贝将会消耗大量计算资源。

在某些场景下，避免拷贝并不会影响程序的逻辑。例如，交换两个对象的内容，并不需要维护一个临时容器，将所有元素拷贝两次。现实生活中也有类似的比喻，比如房产交易并不需要将房子搬来搬去，而只需要变更双方名下的房屋地址就可以完成。

C++ 增加了移动的概念来支持这一目的，通过实现移动构造函数和移动赋值运算符，我们可以为类增加移动控制。

五法则（rule of five）的要求是，一旦实现三法则，编译器将无法为我们生成移动构造函数和移动赋值运算符。所以，对于我们的 vector 容器，此时还需要实现如下两个函数：

vector(vector<T> &&other);                    // move constructor
vector<T> &operator=(vector<T> &&other);      // move assignment

Task 7: 拷贝交换习语

C++ Primer，Ch 13

涉及到资源管理的类，通常定义一个 swap 函数比较方便。交换两个对象，并不需要拷贝整个对象的内容，而只需要交换两个对象管理的内存指针。

通过 swap 函数需要定义两个版本，一个是成员函数，另一个是全局函数。swap 的内部实现需要交换所有的私有成员。

为了安全地处理异常，交换和移动都需要使用 noexcept 标记。这意味着如果发生任何异常，当前对象保持不变，避免在处理过程中破坏现有对象。

利用 swap 改写拷贝赋值、移动特殊函数，可以大大简化代码的实现，避免重复。

Enjoy!