STL in C++11 (Vector 1)

到了今天我们开始学习 STL 中的第一个容器 —— vector。那么首先需要明确的问题就是vector是什么？

实际上 vector 是表示可以改变大小的数组的序列容器。

就像数组一样，vector内部的元素使用连续的存储位置，这意味着它们的元素也可以使用指向其元素的常规指针上的偏移量来访问，并且效率与数组相同。但是与数组不同，它们的大小可以动态更改，其存储由容器自动处理。

当我们使用数组时，可能总是烦恼数组的大小不能动态变化，每次我都要提前为一个数组指定大小(size)。而且由于数组大小是固定的，经常导致空间的浪费，有时甚至因为估计错误而造成边界溢出。这个时候我们就可以使用vector了，它的动态申请空间机制可以保证需要多少元素申请多少空间。

template<typename T, typename Alloc = free_list_allocator<T>>
class cx_vector
{
public:
    using value_type = T;
    using pointer = value_type * ;
    using iterator = value_type * ;
    using const_iterator = const value_type *;
    using reference = value_type & ;
    using const_reference = const value_type&;
    using difference_type = typename std::iterator_traits<iterator>::difference_type;
    using size_type = difference_type;


protected:
    iterator start;    //目前使用空间的头
    iterator finish;   //目前使用空间的尾
    iterator end_of_storage;        //目前可用空间的尾
}

我们首先来看一下 vector 的声明，它接收2个模板参数分别表示元素类型，与分配器类型，我们已经为 Alloc 指定了默认的参数类型 free_list_allocator<T> 。这就是我们之前实现的分配器，现在要使用它为各种容器分配内存了。

之后我们需要为使用使用的类型重命名，这是所有容器标准规定的。例如value_type 表示元素的类型，pointer代表元素类型的指针。我们重点看看迭代器类型 iterator 如何定义。迭起器顾名思义就是用于迭代访问容器元素的工具，它类似于指针，可以指向某个元素，并且通过自增操作指向下一个元素。不同容器的迭代器功能不同，实现也不同。那么对于vector，迭代器是什么？

迭代器如何设计取决于容器需要实现的功能。前面提到过vector可以看作是一个动态变化的数组，那么数组有的功能vector一定要有。数组是支持随机访问（Random Access) 的，即对于数组的指针来说可以加减一个常数来指向数组中的其他元素，那么vector的迭代器也要能加减常数指向容器的其他元素。而元素在vector中是在一段连续内存空间存放，与数组相同，所以vector的迭代器可以直接使用原始指针(raw pointer)实现。

在vector中只有3个成员变量。正如之前所说，所有元素在一段连续的内存中存放，那么就需要3个迭代器指向空间的首尾，并以此为基础访问其他空间。如下图所示

元素内部存储.png

到现在我们已经可以开始实现构造函数了，我们首先看一下相关函数声明。

protected:
    void fill_initialize(size_type n, const T& value);
    
public:
    cx_vector();
    cx_vector(size_type n, const T& value) { fill_initialize(n, value); }
    explicit cx_vector(std::initializer_list<T> list);
    cx_vector(cx_vector<T>&& vec);
    explicit cx_vector(size_type n) { fill_initialize(n, T()); }

要想实现构造函数，必须先理解构造函数做了哪些工作。

为元素存放申请内存空间
将元素复制到空间中（这一步可能没有）
为 start、finish 、end_of_storage 赋初值

理解了以上3步后我们可以开始实现默认构造函数了：

template<typename T, typename Alloc>
cx_vector<T, Alloc>::cx_vector()
{
    start = Alloc::allocate(16);
    finish = start;
    end_of_storage = start + 16;
}

首先我们默认分配16个元素大小的空间，并且返回值赋给start变量。由于默认构造函数中没有实际元素，故 finish 与 start值相等。而end_of_storage指向所有空间的尾部，故 end_of_storage == start + 16。

除了默认构造函数，我们还经常指定容器大小与元素值来构造 vector。由于这些构造函数实现基本相同，所有我们用 fill_initialize() 来实现，构造函数只需直接调用 fill_initialize() 初始化。

template<typename T, typename Alloc>
void cx_vector<T, Alloc>::fill_initialize(
            typename cx_vector<T, Alloc>::size_type n,
            const T& value)
{
    start = Alloc::allocate(n);
    finish = std::uninitialized_fill_n(start, n, value);
    end_of_storage = finish;
}

同样，使用 Alloc 为我们分配 n 个元素的空间，之后使用 std::uninitialized_fill_n() 进行初始化赋值，并且它将返回最后一个被初始化的位置的下一位置的指针。这里所有被申请的空间都已经被使用了，所有 end_of_storage 与 finish 相等。

有时我们还可能想要直接使用初值列对 vector 进行初始化：

cx_vector<int> data({1, 2, 3, 4});

所以可以提供接收 initializer_list 的构造函数：

template<typename T, typename Alloc>
cx_vector<T, Alloc>::cx_vector(std::initializer_list<T> list)
{
    start = Alloc::allocate(list.size());
    finish = std::uninitialized_copy(list.begin(), list.end(), start);
    end_of_storage = finish;
}

在 C++ 11 标准中提出了右值引用与移动语义的概念，借助它们我们可以消除对象之间进行复制的消耗，故我们还要实现移动构造函数：

template<typename T, typename Alloc>
cx_vector<T, Alloc>::cx_vector(cx_vector<T>&& vec)
{
    start = vec.start;
    finish = vec.finish;
    end_of_storage = vec.end_of_storage;

    vec.start = nullptr;
    vec.finish = nullptr;
    vec.end_of_storage = nullptr;
}

可以看到移动构造函数接收一个右值引用。比起复制构造函数根据原对象开辟新空间进行元素复制，移动构造函数直接接管（或者叫窃取）原对象的空间与迭代器，然后再将原对象的成员赋值 null。这样就在不进行复制的情况下达成所有权的变更，即被分配的内存空间只能通过新对象的成员迭代器访问了。

知道了构造函数的工作原理，析构函数就很容易理解了：

~cx_vector() {
    alloc::destroy(start, finish);
    Alloc::deallocate(start, end_of_storage - start);
}

我们首先使用之前提过的 destroy()函数为在 [strat, finish) 的对象调用析构函数，然后使用分配器回收内存就好了。

好了，这篇文章就把构造函数与析构函数讲完就差不多了，下篇文章应该会主要讲解 vector 的一些操作，希望多多支持。

如果喜欢的话可以点个赞啊~

最后附上本篇文章的代码地址：cx_vector.h

以及github地址：https://github.com/Puppas/STL-in-Cpp11