STL Vector 底层原理与核心接口详解

STL Vector 底层原理与核心接口详解

1. Vector 概述

Vector 的数据安排以及操作方式于 array 非常相似，二者唯一差别在于对空间的灵活运用。 Array 是静态空间，一旦配置，不能改变，用户要重新配置空间，移动元素，释放旧空间。Vector 的内部机制会自行扩充空间。 因此 Vector 给我们带来了很大的灵活性，不用担心空间不够用而去开一个大 Array。 Vector 的技术实现在于对大小的控制以及数据分配时的移动效率。

引：如果旧空间用满了，每加一个元素就扩容（配置新空间，挪动数据，释放旧空间），时间成本高，实为不智，所以应有未雨绸缪的考虑。

2. Vector 的迭代器

Vector 维护的是一个连续的线性空间，普通的指针可以满足要求，操作行为如：operator*, operator->, operator++, operator--, operator+, operator-, operator+=, operator-=。Vector 支持随机存取，而普通指针正有这样的能力。

底层代码：

// vector 的迭代器
template<class T, class Alloc = alloc>
class vector {
public:
    typedef T value_type;
    typedef value_type* iterator; // vector 的迭代器是普通指针
    // ...
};

3. Vector 的数据结构

非常简单，呈现连续空间，用两个迭代器 start，finish 分别指向配置得来的连续空间被已使用的范围，用迭代器 end_of_storage 指向整块连续空间（含备用空间）的尾端：其实就是最后一个空间的下一个位置。

底层代码：

template<class T, class Alloc = alloc>
class vector {
    // ...
protected:
    iterator start;      // 目前使用空间的头
    iterator finish;     // 目前使用空间的尾
    iterator end_of_storage; // 目前可用空间的尾
};

为降低空间配置速度成本，Vector 实际配置的大小可能比用户需求更大，以备扩容，这就是容量（capacity），Vector 的容量大于等于其大小。 运用 start, finish, end_of_storage 三个迭代器可以容易实现大小，容量，首尾，判断，[], begin(), end()……

底层代码：

// 用 start, finish, end_of_storage 实现
template<class T, class Alloc = alloc>
class vector {
    // ...
public:
    iterator begin() { return start; }
    iterator end() { return finish; }
    size_type size() { return size_type(end() - begin()); }
    size_type capacity() const { return size_type(end_of_storage - begin()); }
    bool empty() const { return begin() == end(); }
    reference operator[](size_type n) { return *(begin() + n); }
    reference front() { return *begin(); }
    reference back() { return *(end() - 1); }
};

4. Vector 的构造和内存管理

在 gcc 编译器下是 2 倍扩容，MSVC 是 1.5 倍扩容。（扩大，size()）

如下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> iv(2, 9);
    cout << "size=" << iv.size() << endl; // size=2
    cout << "capacity=" << iv.capacity() << endl; // capacity=2
    iv.push_back(1);
    cout << "size=" << iv.size() << endl; // size=3
    cout << "capacity=" << iv.capacity() << endl; // capacity=4
    iv.push_back(2);
    cout << "size=" << iv.size() << endl; // size=4
    cout << "capacity=" << iv.capacity() << endl; // capacity=4
    iv.push_back(3);
    cout << "size=" << iv.size() << endl; // size=5
    cout << "capacity=" << iv.capacity() << endl; // capacity=8
    iv.push_back(4);
    cout << "size=" << iv.size() << endl; // size=6
    cout << "capacity=" << iv.capacity() << endl; // capacity=8
    for (int i = 0; i < iv.size(); ++i) cout << iv[i] << ' '; // 9 9 1 2 3 4
    cout << endl;
    iv.push_back(5);
    cout << "size=" << iv.size() << endl; // size=7
    cout << "capacity=" << iv.capacity() << endl; // capacity=8
    for (int i = 0; i < iv.size(); ++i) cout << iv[i] << ' '; // 9 9 1 2 3 4 5
    cout << endl;
    iv.pop_back(); iv.pop_back();
    cout << "size=" << iv.size() << endl; // size=5
    cout << "capacity=" << iv.capacity() << endl; // capacity=8
    iv.pop_back();
    cout << "size=" << iv.size() << endl; // size=4
    cout << "capacity=" << iv.capacity() << endl; // capacity=8
    vector<int>::iterator ivite = find(iv.begin(), iv.end(), 1);
    if (ivite != iv.end()) iv.erase(ivite);
    cout << "size=" << iv.size() << endl; // size=3
    cout << "capacity=" << iv.capacity() << endl; // capacity=8
    for (int i = 0; i < iv.size(); ++i) cout << iv[i] << ' '; // 9 9 2
    cout << endl;
    ivite = find(iv.begin(), iv.end(), 2);
    if (ivite != iv.end()) iv.insert(ivite, 3, 7);
    cout << "size=" << iv.size() << endl; // size=6
    cout << "capacity=" << iv.capacity() << endl; // capacity=8
    for (int i = 0; i < iv.size(); ++i) cout << iv[i] << ' '; // 9 9 7 7 7 2
    cout << endl;
    iv.clear();
    cout << "size=" << iv.size() << endl; // size=0
    cout << "capacity=" << iv.capacity() << endl; // capacity=8
}

gcc(linux):

MSVC(vs):

Vector 提供许多 constructors:

底层代码：

// 构造函数，允许指定 vector 的大小和初值
vector(size_type n, const T& value) { fill_initialize(n, value); }

// 填充并初始化
void fill_initialize(size_type n, const T& value) {
    start = allocate_and_fill(n, value);
    finish = start + n;
    end_of_storage = finish;
}

// 配置后填充
iterator allocate_and_fill(size_type n, const T& x) {
    iterator result = data_allocator::allocate(n);
    uninitialized_fill_n(result, n, x);
    return result;
}

push_back() 尾插元素时，检查是否还有备用空间，有就在其上插入元素，调整 finish，Vector 变大，没有，就扩容（重新配置，移动数据，释放旧空间）。

底层代码： （篇幅有限，这里只做简略，全局函数具体实现未详细写出）

// 尾插
void push_back(const T& x) {
    if (finish != end_of_storage) {
        construct(finish, x);
        ++finish;
    } else insert_aux(end(), x);
}

template<class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x) {
    if (finish != end_of_storage) {
        // 还有备用空间，在其上构造元素，以最后一个元素为初值
        construct(finish, *(finish - 1));
        ++finish;
        T x_copy = x;
        copy_backward(position, finish - 2, finish - 1);
        *position = x_copy;
    } else {
        // 无备用空间
        const size_type old_size = size();
        const size_type len = old_size != 0 ? 2 * old_size : 1; // 原大小为 0，变为 1；不为 0，变为 2 倍
        iterator new_start = data_allocator::allocate(len);
        iterator new_finish = new_start;
        try {
            new_finish = uninitialized_copy(start, position, new_start);
            construct(new_finish, x);
            ++new_finish;
            new_finish = uninitialized_copy(position, finish, new_finish);
        } catch (...) {
            deallocate(new_start, new_finish - new_start);
            throw;
        }
        // ...
        // 析构并释放原 vector
        destroy(begin(), end());
        deallocate();
        // 调整迭代器，指向新的 vector
        start = new_start;
        finish = new_finish;
        end_of_storage = new_start + len;
    }
}

动态增加大小，不是在原空间后连续接新空间，因为不能保证后面有足够且可分配的空间，以原来两倍的大小配置一块新空间，将原来空间的内容拷贝过来，更新构造元素，释放旧空间。

5. Vector 的元素操作

pop_back, erase, clear, insert

底层代码：

// 尾删
void pop_back() {
    --finish;
    destroy(finish);
}

// 清除 [first, last) 所有元素
iterator erase(iterator first, iterator last) {
    iterator i = copy(last, finish, first);
    destroy(i, finish);
    finish = finish - (last - first);
    return first;
}

// 删除某个
iterator erase(iterator position) {
    if (position + 1 != end()) copy(position + 1, finish, position);
    --finish;
    destroy(finish);
    return position;
}

void clear() {
    erase(begin(), end());
}

erase 逻辑：

insert 逻辑：

6. 接口具体使用介绍

6.1. constructor

#include <vector>
#include <iostream>
using namespace std;

// 构造与访问
void test_vector1() {
    vector<int> v1;
    vector<int> v2(10, 1);
    vector<int> v3(v2.begin(), v2.end());
    for (size_t i = 0; i < v3.size(); i++) {
        cout << v3[i] << " "; // 用 [] 访问
    }
    cout << endl;
    vector<int>::iterator it = v3.begin();
    while (it != v3.end()) {
        cout << *it << " "; // 迭代器
        ++it;
    }
    cout << endl;
    for (auto e : v3) { // 范围 for，底层就是迭代器
        cout << e << " ";
    }
    cout << endl;
}

int main() {
    test_vector1();
    return 0;
}

6.2. resize

n < size(), 删除数据，不缩容；n > size(), 空间不够，扩容。 不支持头插，头删，支持尾插，尾删（v.push_back(), v.pop_back()）

6.3. reserve

要求向量容量至少能够容纳 n 个元素。 若 n 大于当前向量容量，该函数将导致容器重新分配存储空间，使其容量增加至 n（或更大）。 其他情况，string: n 比 size() 小最多也就缩容到 size()，不会影响长度，内容。Vector: vs, linux 不缩容。

void test_vector2() {
    // 不缩容
    vector<int> v(10, 1);
    v.reserve(20);
    cout << v.size() << endl;
    cout << v.capacity() << endl;
    v.reserve(20);
    cout << v.size() << endl;
    cout << v.capacity() << endl;
    v.reserve(5);
    cout << v.size() << endl;
    cout << v.capacity() << endl;
}

6.4. insert

只支持迭代器。 v.insert(v.begin(), 1); v.insert(v.begin() + 3, 2); 3 后插入 为了 STL 统一，因为后面 list 那些没有下标的概念。 insert, erase 本质上要挪动数据，效率低。

6.5. erase

v.erase(v.begin()); v.erase(v.begin() + 1, v.begin() + 4); 2~5

void test_vector3() {
    vector<int> v(5, 6);
    v.push_back(7);
    v.insert(v.begin(), 1);
    v.insert(v.begin() + 3, 9);
    for (auto e : v) {
        cout << e << " ";
    }
    cout << endl;
    v.pop_back();
    v.erase(v.begin());
    v.erase(v.begin() + 1, v.begin() + 4);
    for (auto e : v) {
        cout << e << " ";
    }
    cout << endl;
}

v.clear() 清除所有数据。 Vector 可以比较大小。 Vector 不支持流插入/提取，很灵活。 Vector v; （没有\0）不能代替 string(有\0，兼容 c 语言)。String 还有很多需求和特性。 Vector, vector, (二维数组)，还可存自定义类型，范围 for 里面用引用，减少拷贝。

void test_vector4() {
    vector<string> v1;
    string s1("xxxx");
    v1.push_back(s1);
    v1.push_back("yyyyy");
    for (const auto& e : v1) // 每次都是取得 string,&减少拷贝，const 不变
    {
        cout << e << " ";
    }
    cout << endl;
    // 二维数组 10 * 5
    vector<int> v(5, 1);
    vector<vector<int>> vv(10, v);
    vv[2][1] = 2; // 实际是连续的两个 operator[][] 的调用
                  // vv.operator[](2).operator[](1) = 2; 两个 operator[] 不同
    for (size_t i = 0; i < vv.size(); i++) {
        for (size_t j = 0; j < vv[i].size(); ++j) {
            cout << vv[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}