C++ STL vector 容器底层实现详解

前言

在学习了 vector 类的基本使用的前提下，本文将重点分析 vector 类的常用接口及其应用实现。

一、vector 成员变量

vector 本质上是一个动态数组，通过原生指针来实现底层维护。为了使得 STL 接口调用的统一性，我们需要将原生指针重命名为迭代器。

其核心目的是：将数据结构（容器）与操作（算法）分离，并通过一种统一的接口（迭代器）将它们粘合在一起。

成员变量分析

template <class T> class vector {
public:
    // 将原生指针重命名为迭代器，实现接口统一
    typedef T* iterator;
    typedef const T* const_iterator;
private:
    iterator _start;       // 指向目前使用空间的头
    iterator _finish;      // 指向目前使用空间的尾
    iterator _end_of_storage; // 指向目前可用空间的尾
};

成员变量说明：

1. iterator _start：指向目前使用空间的头
2. iterator _finish：指向目前使用空间的尾
3. iterator _end_of_storage：指向目前可用空间的尾

二、默认成员函数

2.1 无参构造

vector 默认支持无参构造函数，此时将对象的三个成员变量初始化为空指针。

vector() :_start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {}

2.2 构造函数：构造 n 个同类型的值

vector 的带参构造函数，作用是创建一个初始包含 n 个元素的 vector，并且将这些元素全部初始化为给定的 value。

函数原型： vector(size_t n, const T& value = T())

代码示例：

// 构造函数：构造出 n 个同类型的值
vector(size_t n, const T& value = T()) {
    // 避免多次扩容
    reserve(n);
    // 尾插元素
    for (size_t i = 0; i < n; i++) {
        push_back(value);
    }
}

解析：

1. 核心优化 reserve(n)：提前调用 reserve(n)，一次性向系统申请好足够容纳 n 个元素的内存，可以直接把后续插入的扩容开销降为 0。
2. 数据填充：在确保容量足够的前提下，循环 n 次，每次将 value 尾插到动态数组中，顺便更新内部维护的数组有效元素个数。

2.3 构造函数：迭代器区间构造

迭代器区间构造，接收任意一段具有迭代器特性的区间 [first, last)，并把这段区间里的数据拷贝过来构造一个新的 vector。

函数原型： template<class InputIterator> vector(InputIterator first, InputIterator last)

代码实现：

template<class InputIterator>
vector(InputIterator first, InputIterator last) {
    while (first != last) {
        push_back(*first);
        ++first;
    }
}

使用示例：

// 1. 用数组的指针区间来构造
int arr[] = {1, 2, 3, 4, 5};
vector<int> v1(arr, arr + 5);

// 2. 用 std::list 的迭代器来构造
list<int> myList = {10, 20, 30};
vector<int> v2(myList.begin(), myList.end());

// 3. 用 std::string 的迭代器来构造字符
string str = "hello";
vector<char> v3(str.begin(), str.end());

原理： 原生指针 int* 支持 !=, *, ++ 操作，因此满足迭代器要求，编译器会自动实例化对应版本。

2.4 拷贝构造函数

自定义 vector 类的拷贝构造函数，作用是使用一个已经存在的 vector 对象（v1）来初始化一个新的 vector 对象（v2），需实现深拷贝。

函数原型： vector(const vector<T>& v)

现代写法：

vector(const vector<T>& v) {
    // 现代写法
    reserve(v.capacity());
    for (size_t i = 0; i < v.size(); i++) {
        push_back(v[i]);
    }
}

解析：

1. reserve 实现了'空间独立'：申请一块全新的堆内存，新对象与原对象物理隔离。
2. push_back 实现了'数据复制'：遍历源对象元素放入新空间，触发类型 T 的拷贝行为，保证深拷贝。

2.5 赋值重载函数

自定义 vector 类的赋值运算符重载函数，用于处理两个已存在对象间的赋值操作，例如：v1 = v2。

函数原型： vector<T>& operator=(vector<T> v)

代码实现：Copy-and-Swap

template<class T>
void vector<T>::swap(vector<T>& v) {
    std::swap(_start, v._start);
    std::swap(_finish, v._finish);
    std::swap(_end_of_storage, v._end_of_storage);
}

// 赋值重载函数
vector<T>& operator=(vector<T> v) {
    swap(v);
    return *this;
}

核心拆解：Copy-and-Swap 的三步魔法

1. 传值触发拷贝构造：参数按值传递，自动调用拷贝构造函数生成临时对象 v。
2. 交换指针：执行 swap(v)，当前对象窃取临时对象的新内存，临时对象持有旧内存。
3. 自动清理：函数结束，临时对象析构，释放旧内存。

三、迭代器相关函数

使用场景	begin() / end() 返回类型	可读 / 可写权限	对应实现方式
普通 vector 对象	iterator (即 T*)	✅ 可读 ✅ 可写	iterator begin() iterator end()
const vector 对象	const_iterator (即 const T*)	✅ 只读 ❌ 不可写	const_iterator begin() const const_iterator end() const

3.1 begin

typedef T* iterator;
typedef const T* const_iterator;

iterator begin() { return _start; }
const_iterator begin() const { return _start; }

3.2 end

iterator end() { return _finish; }
const_iterator end() const { return _finish; }

四、容量大小相关函数

4.1 size

size_t size() const { return _finish - _start; }

4.2 capacity

size_t capacity() const { return _end_of_storage - _start; }

4.3 reserve

函数原型： void reserve(size_t n);

功能： 当 n > capacity 时才扩容；当 n <= capacity 时不做任何操作。

代码实现：

template<class T>
void vector<T>::reserve(size_t n) {
    if (n > capacity()) {
        size_t oldsize = size();
        size_t newcapacity = n;
        T* tmp = new T[newcapacity];
        
        for (size_t i = 0; i < oldsize; i++) {
            tmp[i] = _start[i];
        }
        
        if (_start) delete[] _start;
        
        _start = tmp;
        _finish = tmp + oldsize;
        _end_of_storage = tmp + newcapacity;
    }
}

解析：

1. 扩容门槛检查：判断传入容量是否大于当前容量。
2. 保存 oldsize：防止更新 _start 后计算 size() 出错。
3. 申请新空间与数据搬家：new 开辟新内存并拷贝旧数据。
4. 释放旧空间：delete[] 释放原内存，防止泄漏。
5. 更新内部指针：更新 _start, _finish, _end_of_storage。

4.4 resize

函数原型： void resize(size_t n, const T& val = T());

功能： 调整容器大小。若 n > size 则扩展并填充；若 n < size 则截断。

代码实现：

template<class T>
void vector<T>::resize(size_t n, const T& value) {
    reserve(n);
    if (n < size()) {
        _finish = _start + n;
    } else {
        while (_finish < _start + n) {
            *_finish = value;
            ++_finish;
        }
    }
}

解析：

1. 兜底保护：先调用 reserve 确保物理空间足够。
2. 缩小范围：直接移动 _finish 指针，不释放物理内存。
3. 扩大范围：在预留空间中填充新元素。

4.5 empty

bool empty() { return _start == _finish; }

五、修改容器相关函数

5.1 push_back

函数原型： void push_back(const T& x)

代码实现：

template<class T>
void vector<T>::push_back(const T& x) {
    if (_end_of_storage == _finish) {
        size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
        reserve(newcapacity);
    }
    *(_finish) = x;
    ++_finish;
}

5.2 pop_back

函数原型： void pop_back();

代码实现：

template<class T>
void vector<T>::pop_back() {
    assert(!empty());
    if (_finish != _start) {
        --_finish;
    }
}

5.3 insert

函数原型： iterator insert(iterator pos, const T& x);

代码实现：

template<class T>
typename vector<T>::iterator vector<T>::insert(iterator pos, const T& x) {
    assert(pos >= _start);
    assert(pos <= _finish);
    
    if (_end_of_storage == _finish) {
        size_t abs_site = pos - begin();
        size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
        reserve(newcapacity);
        pos = begin() + abs_site;
    }
    
    iterator last = end();
    while (last > pos) {
        *last = *(last - 1);
        --last;
    }
    
    *pos = x;
    ++_finish;
    return pos;
}

解析：

1. 门禁检查：确保 pos 合法。
2. 破解迭代器失效：扩容前记录相对偏移量，扩容后重新计算位置。
3. 挪动数据：从后往前搬运，为新元素腾位。
4. 返回值：返回新位置的迭代器。

5.4 erase

函数原型： iterator erase(iterator pos);

代码实现：

template<class T>
typename vector<T>::iterator vector<T>::erase(iterator pos) {
    assert(pos >= _start);
    assert(pos < _finish);
    
    iterator it = pos + 1;
    while (it != end()) {
        *(it - 1) = *it;
        ++it;
    }
    
    --_finish;
    return pos;
}

解析：

1. 门禁检查：确保 pos 指向有效元素。
2. 挪动数据：从前往后覆盖，填补空缺。
3. 更新尾部：_finish 前移一位。
4. 返回值：解决迭代器失效问题。

5.5 clear

函数原型： void clear();

代码实现：

void clear() {
    _finish = _start;
}

六、访问容器相关函数

6.1 operator[]

函数原型：

1. T& operator[](size_t pos)
2. const T& operator[](size_t pos) const

代码实现：

T& operator[](size_t pos) {
    assert(pos < size());
    return _start[pos];
}

const T& operator[](size_t pos) const {
    assert(pos < size());
    return _start[pos];
}