前言

vector 的数据安排以及操作方式，与 array 非常相似。两者的唯一差别在于空间的运用的灵活性。array 是静态空间，一旦配置了就不能改变；vector 是动态空间，随着元素的加人，它的内部机制会自行扩充空间以容纳新元素。因此，vector 的运用对于内存的合理利用与运用的灵活性有很大的帮助，vector 的实现技术，关键在于其对大小的控制以及重新配置时的数据移动效率。
———— 《STL源码剖析》侯捷

本篇博客将会分析 STL 中 vector 的实现。

vector 的型别定义与数据结构

这里摘取部分 TinySTL::vector 的型别及成员变量定义部分代码进行分析。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 模板类 vector
template <class T>
class vector {

// 静态断言，用于在编译期间判断 T 是否为 bool 类型
static_assert(!std::is_same<bool, T>::value, "vector<bool> is abandoned in tinystl");
public:
    // vector 的嵌套型别定义
    typedef tinystl::allocator<T>                         allocator_type;
    typedef tinystl::allocator<T>                         data_allocator;

    typedef typename allocator_type::value_type           value_type;
    typedef typename allocator_type::pointer              pointer;
    typedef typename allocator_type::const_pointer        const_pointer;
    typedef typename allocator_type::reference            reference;
    typedef typename allocator_type::const_reference      const_reference;
    typedef typename allocator_type::size_type            size_type;
    typedef typename allocator_type::difference_type      difference_type;

    // vector 的迭代器是普通指针
    typedef value_type*                                   iterator;
    typedef const value_type*                             const_iterator;
    typedef tinystl::reverse_iterator<iterator>           reverse_iterator;
    typedef tinystl::reverse_iterator<const_iterator>     const_reverse_iterator;

    allocator_type get_allocator() { return data_allocator(); }

private:
    iterator begin_;        // 表示目前使用空间的头
    iterator end_;          // 表示目前使用空间的尾
    iterator cap_;          // 表示目前可用空间的尾

public:  // 一些函数
    ...

private:  // 一些函数
    ...
};

可以看出，vector 的型别定义与数据结构都较为简单，下面将分析其中重要的两个部分。

vector 的迭代器

1
2
typedef value_type*                                   iterator;
typedef const value_type*                             const_iterator;

由上面的型别定义可以看出，vector 的迭代器就是普通的指针。由于 vector 维护的是一个连续线性空间，所以不论其元素型别为何，普通指针都可以作为 vector 的迭代器而满足所有必要条件，因为 vector 迭代器所需要的操作行为，如 operator*， operator->，operator++，operator--，operator+，operator-，operator+=，operator-=，普通指针天生就具备。vector 支持随机存取，而普通指针正有着这样的能力。所以，vector 提供的是 Random Access lterators。

vector 的数据结构

1
2
3
4
private:
    iterator begin_;        // 表示目前使用空间的头
    iterator end_;          // 表示目前使用空间的尾
    iterator cap_;          // 表示目前可用空间的尾

vector 所采用的数据结构非常简单：线性连续空间。它以两个迭代器 begin_ 和 end_ 分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器 cap_ 指向整块连续空间（含备用空间〉的尾端。

这里的变量名称与 SGI-STL 中并不一致，但作用相同。

为了降低空间配置时的速度成本，vector 实际配置的大小可能比客户端需求量更大一些，以备将来可能的扩充。这便是容量 (capacity) 的观念。换句话说，一个 vector 的容量水远大于或等于其大小。一且容量等于大小，便是满载，下次再有新增元素，整个vector 就得另觅居所，见图4-2。

使用 begin_、end_、cap_ 三个迭代器，便可以轻易地提供收尾标示、大小、容量、空容器判断、注标 ([]) 运算子、最前端元素值、最后端元素值等功能。

5.png

vector 的构造、析构与内存管理

构造与析构函数

vector 提供了多种构造的方式，下面将连同析构函数逐一分析。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// =========================  构造函数  ========================= // 
    
vector() noexcept { try_init(); }  // 不会引发异常

explicit vector(size_type n) { fill_init(n, value_type()); }  // explicit 防止隐式转换

vector(size_type n, const value_type& value) { fill_init(n, value); }

// 这里使用 std::enable_if 来确保只有当迭代器类型满足输入迭代器的要求时，该函数模板才会被实例化。
template <class Iter, typename std::enable_if<
    tinystl::is_input_iterator<Iter>::value, int>::type = 0>
vector(Iter first, Iter last) {
    TINYSTL_DEBUG(!(last < first));
    range_init(first, last);
}

vector(const vector& rhs) { range_init(rhs.begin_, rhs.end_); }

/// @brief 移动构造函数
/// @param rhs  右值引用
vector(vector&& rhs) noexcept : begin_(rhs.begin_), end_(rhs.end_), cap_(rhs.cap_) {
    rhs.begin_ = nullptr;
    rhs.end_ = nullptr;
    rhs.cap_ = nullptr;
}

/// @brief 列表初始化
/// @param ilist  列表
vector(std::initializer_list<T> ilist) { range_init(ilist.begin(), ilist.end()); };

// =========================  析构函数  ========================= //

~vector() {
    destroy_and_recover(begin_, end_, cap_ - begin_);
    begin_ = end_ = cap_ = nullptr;
}

首先，默认构造函数 vector() 由 try_init() 完成，来看看这个函数的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/// @brief 初始化 vector, 具有 commit or rollback 机制
/// @tparam T  元素类型
template <class T>
void vector<T>::try_init() noexcept {
    try {
        begin_ = data_allocator::allocate(16);
        end_ = begin_;
        cap_ = begin_ + 16;
    }
    catch (...) {
        begin_ = nullptr;
        end_ = nullptr;
        cap_ = nullptr;
    }
}

可以看出，默认构造函数会申请 16 个空间，也就是说，默认构造下的 vector 初始容量为 16，并且具有 commit or rollback 机制。即，如果没有申请到全部的空间，那么就不申请任何空间，将所有的迭代器均置为空指针。

其次，vector(n) 与 vector(n, value) 这两个最常用的构造函数使用 fill_init() 完成，看看这个函数的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/// @brief 以 n 个 value 初始化 vector
/// @tparam T  元素类型
/// @param n  元素个数
/// @param value  元素的值
template <class T>
void vector<T>::fill_init(size_type n, const value_type& value) {
    const size_type init_size = tinystl::max(static_cast<size_type>(16), n);
    init_space(n, init_size);
    tinystl::uninitialized_fill_n(begin_, n, value);
}

/// @brief 初始化 vector, 并设置初始元素个数与容量, 失败则抛出异常
/// @tparam T 元素类型
/// @param size  元素个数
/// @param cap  容量
template <class T>
void vector<T>::init_space(size_type size, size_type cap) {
    try {
        begin_ = data_allocator::allocate(cap);
        end_ = begin_ + size;
        cap_ = begin_ + cap;
    }
    catch (...) {
        begin_ = nullptr;
        end_ = nullptr;
        cap_ = nullptr;
        throw;
    }
}

fill_init() 先调用 init_space() 函数，申请指定大小的空间，值得注意的是这里申请空间失败的话会抛出异常；再利用 uninitialized_fill_n() 在申请到的空间上构造元素，uninitialized_fill_n() 会根据第一参数的型别特性，决定使用算法 fill_n() 或反复调用 construct() 来完成任务。

还有一些构造函数使用到了 range_init()，原理与 fill_init() 类似，不同之处在于调用的是 uninitialized_copy()，也会根据参数的性别特性来调用最有效率的函数。

1
2
3
4
5
6
7
8
9
10
11
12
/// @brief 以 [first, last) 区间初始化 vector
/// @tparam T  元素类型
/// @param first  区间起始位置
/// @param last  区间终止位置
template <class T>
template <class Iter>
void vector<T>::range_init(Iter first, Iter last) {
    const size_type len = tinystl::distance(first, last);
    const size_type init_size = tinystl::max(static_cast<size_type>(16), len);
    init_space(len, init_size);
    tinystl::uninitialized_copy(first, last, begin_);
}

析构函数就是直接调用deallocate 空间配置器，先从头到尾析构所有数据，最后再将内存还给空间配置器。

vector因为是类，所以我们并不需要手动的释放内存，生命周期结束后就自动调用析构从而释放调用空间，当然我们也可以直接调用析构函数释放内存。

1
2
3
4
5
6
7
8
9
10
/// @brief 清除 [first, last) 区间上的元素，并回收内存
/// @tparam T  元素类型
/// @param first  区间起始位置
/// @param last  区间终止位置
/// @param n  区间长度
template <class T>
void vector<T>::destroy_and_recover(iterator first, iterator last, size_type n) {
    data_allocator::destroy(first, last);
    data_allocator::deallocate(first, n);
}

内存管理

我们以 push_back() 为例分析一下 vector 的内存管理，该函数首先检是否还有备用空间，如果有就直接在备用空间上构造元素，并调整迭代器 end_，使 vector 变大。如果没有备用空间了，就扩充空间(重新配置,移动数据、释放原空间)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/// @brief 在尾部插入元素
/// @tparam T  元素类型
/// @param value  元素的值
template <class T>
void vector<T>::push_back(const value_type& value) {
    // 如果空间足够就直接构造元素
    if (end_ != cap_) {
        data_allocator::construct(tinystl::address_of(*end_), value);
        ++end_;
    }
    // 否则重新分配内存，并构造元素
    else {
        reallocate_insert(end_, value);
    }
}

/// @brief 重新分配内存，并在 pos 处插入元素
/// @tparam T  元素类型
/// @param pos  插入位置
/// @param value  元素的值
template <class T> 
void vector<T>::reallocate_insert(iterator pos, const value_type& value) {
    const auto new_size = get_new_cap(1);
    auto new_begin = data_allocator::allocate(new_size);
    auto new_end = new_begin;
    const value_type& value_copy = value;
    try {
        // 将 pos 之前的元素移动到新的位置
        new_end = tinystl::uninitialized_move(begin_, pos, new_begin);
        // 在 pos 处构造元素
        data_allocator::construct(tinystl::address_of(*new_end), value_copy);
        ++new_end;
        // 将 pos 之后的元素移动到新的位置
        new_end = tinystl::uninitialized_move(pos, end_, new_end);
    }
    catch (...) {
        data_allocator::deallocate(new_begin, new_size);
        throw;
    }
    // 回收旧的内存
    destroy_and_recover(begin_, end_, cap_ - begin_);
    // 重新设置迭代器
    begin_ = new_begin;
    end_ = new_end;
    cap_ = new_begin + new_size;
}

/// @brief 增加 vector 容量大小，每一次默认增加 1.5 倍
/// @tparam T  元素类型
/// @param add_size  增加的大小
/// @return  返回新的容量大小
template <class T>
typename vector<T>::size_type vector<T>::get_new_cap(size_type add_size) {
    const auto old_size = capacity();
    THROW_LENGTH_ERROR_IF(old_size > max_size() - add_size, 
        "vector<T>'s size too big");
    if (old_size > max_size() - old_size / 2) {
        return old_size + add_size > max_size() - 16 ? 
            old_size + add_size : old_size + add_size + 16;
    }
    // 每一次默认增加 1.5 倍
    const auto new_size = old_size == 0 ? 
        tinystl::max(add_size, static_cast<size_type>(16)) : 
        tinystl::max(old_size + old_size / 2, old_size + add_size);
    return new_size;
}

注意，所谓动态增加大小，并不是在原空间之后接续新空间（因为无法保证原空间之后尚有可供配置的空间），而是以原大小的两倍（这里设为 1.5 倍）另外配置一块较大空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间。因此，对 vector 的任何操作，一旦引起空间重新配置，指向原 vector 的所有迭代器就都失效了。这是程序员易犯的一个错误，务需小心。

vector 一些函数的实现

这部分介绍一下 vector 内的常用函数。

insert

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/// @brief 在 pos 处插入元素
/// @tparam T  元素类型
/// @param pos  插入位置
/// @param value  元素的值
/// @return  返回指向新构造元素的迭代器
template <class T>
typename vector<T>::iterator vector<T>::insert(const_iterator pos, const value_type& value) {
    // 确保 pos 在 [begin(), end()) 内
    TINYSTL_DEBUG(pos >= begin() && pos <= end());
    iterator xpos = const_cast<iterator>(pos);
    const size_type n = xpos - begin_;
    // 构造位置为 end_，直接构造元素
    if (end_ != cap_ && xpos == end_) {
        data_allocator::construct(tinystl::address_of(*end_), value);
        ++end_;
    }
    // 构造位置不为 end_，则需要移动元素
    else if (end_ != cap_) {
        auto new_end = end_;
        // 在 end_ 处构造元素
        data_allocator::construct(tinystl::address_of(*end_), *(end_ - 1));
        ++new_end;
        auto value_copy = value;  // 避免元素因以下复制操作而被改变
        // 将 [xpos, end_ - 1) 的元素向后移动一位
        tinystl::copy_backward(xpos, end_ - 1, end_);
        // 在 xpos 处构造元素
        *xpos = tinystl::move(value_copy);
        // 更新 end_ 的位置
        end_ = new_end;
    }
    // 空间已满，则需要重新分配内存并构造元素
    else {
        reallocate_insert(xpos, value);
    }
    return begin() + n;
}

erase

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/// @brief 删除 pos 位置上的元素
/// @tparam T  元素类型
/// @param pos  删除位置
/// @return  返回指向被删除元素的下一个元素的迭代器
template <class T>
typename vector<T>::iterator vector<T>::erase(const_iterator pos) {
    // 确保 pos 在 [begin(), end()) 内
    TINYSTL_DEBUG(pos >= begin() && pos < end());
    iterator xpos = begin_ + (pos - begin());
    // 将 [xpos + 1, end_) 的元素向前移动一位
    tinystl::move(xpos + 1, end_, xpos);
    // 销毁 end_ - 1处的元素
    data_allocator::destroy(end_ - 1);
    // 更新 end_ 的位置
    --end_;
    return xpos;
}

/// @brief 删除 [first, last) 区间上的元素
/// @tparam T  元素类型
/// @param first  删除区间的起始位置
/// @param last  删除区间的终止位置
/// @return  返回指向被删除元素（区间）的下一个元素的迭代器
template <class T>
typename vector<T>::iterator vector<T>::erase(const_iterator first, const_iterator last) {
    // 确保 first 和 last 在 [begin(), end()) 内，且 first 不大于 last
    TINYSTL_DEBUG(first >= begin() && first <= end() && !(last < first));
    const auto n = first - begin();
    iterator r = begin_ + (first - begin());
    // tinystl::move(r + (last - first), end_, r) 将被删除区间后面的元素向前移动，返回移动后的尾部位置
    // destroy(pos, end_) 销毁 [pos, end_) 区间上的元素
    data_allocator::destroy(tinystl::move(r + (last - first), end_, r), end_);
    // 更新 end_ 的位置
    end_ = end_ - (last - first);
    return begin_ + n;
}

这里用到了 move()、copy_backward() 等 STL 算法部分的内容，会在 Algorithm 部分讲解。

总结

vector 是 STL 中的一种结构较为简单的容器，vector 内部维护的是一个连续的线性空间，其迭代器为普通指针类型。vector 的特点在于其是动态空间，随着元素的加人，它的内部机制会自行扩充空间以容纳新元素。为了实现这一点，vector 以 begin_、end_、cap_ 三个迭代器分别代表 vector 目前数据的头部、尾部以及可使用空间的尾部。利用这三个迭代器可以很方便地判断当前的数据个数是否超出容量以重新分配更大的空间；

值得注意的是，vector 的重新分配空间并不是在原空间之后接续新空间（因为无法保证原空间之后尚有可供配置的空间），而是以原大小的两倍（或 1.5 倍）另外配置一块较大空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间。因此，对 vector 的任何操作，一旦引起空间重新配置，指向原 vector 的所有迭代器就都失效了。