C++ vector 容器底层原理与模拟实现

2.2.2 迭代器范围构造函数

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

这个构造函数是函数模板，可以接受任意类型的迭代器：

int arr[] = {1, 2, 3, 4, 5};
vector<int> v1(arr, arr + 5);   // 从数组构造
vector<int> v2(v1.begin(), v1.end()); // 从另一个 vector 构造

2.2.3 拷贝构造函数（现代写法）

vector(const vector<T>& v) {
    vector<T> tmp(v.begin(), v.end());
    swap(tmp);
}

现代写法通过创建临时对象并交换资源，代码简洁且异常安全。

2.3 赋值运算符重载

vector<T>& operator=(vector<T> tmp) {
    swap(tmp);
    return *this;
}

2.4 容量相关操作

2.4.1 reserve 开空间

void reserve(size_t n) {
    if (n > capacity()) {
        size_t sz = size();
        T* tmp = new T[n];
        if (_start) {
            for (size_t i = 0; i < sz; i++) {
                std::swap(tmp[i], _start[i]);
            }
            delete[] _start;
        }
        _start = tmp;
        _finish = _start + sz;
        _end_of_storage = _start + n;
    }
}

• 使用 std::swap 而不是直接赋值，这样可以高效地交换资源。
• 如果直接使用 memcpy，对于管理资源的类（如 string）会导致浅拷贝问题！
• 重新计算 _finish 和 _end_of_storage 指针

2.4.2 用 resize 调整大小

void resize(size_t n, T val = T()) {
    if (n < size()) {
        // 缩小 size，只是移动_finish 指针
        _finish = _start + n;
    } else {
        reserve(n); // 可能需要扩容
        while (_finish < _start + n) {
            *_finish = val;
            ++_finish;
        }
    }
}

这里使用匿名对象做缺省参数。

使用示例：

vector<int> v = {1, 2, 3};
v.resize(5);      // 变为 {1, 2, 3, 0, 0}
v.resize(2);      // 变为 {1, 2}

2.4.3 size 和 capacity

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

2.5 元素访问操作

2.5.1 下标运算符

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

提供 const 和非 const 版本，支持读写访问和只读访问。

2.6 修改操作

2.6.1 push_back 尾部添加元素

void push_back(const T& x) {
    if (_finish == _end_of_storage) {
        reserve(capacity() == 0 ? 4 : capacity() * 2);
    }
    *_finish = x;
    ++_finish;
}

扩容策略：初始为 0 时分配 4 个元素空间，否则每次扩容为原来的 2 倍。

2.6.2 pop_back 尾部删除元素

void pop_back() {
    assert(!empty());
    --_finish;
}

2.6.3 insert 在指定位置插入元素

iterator insert(iterator pos, const T& x) {
    assert(pos >= _start);
    assert(pos <= _finish);
    // 扩容
    if (_finish == _end_of_storage) {
        size_t len = pos - _start;
        reserve(capacity() == 0 ? 4 : capacity() * 2);
        pos = _start + len;
    }
    // 挪动数据
    iterator end = _finish - 1;
    while (end >= pos) {
        *(end + 1) = *end;
        --end;
    }
    *pos = x;
    ++_finish;
    return pos;
}

扩容后需要重新计算 pos 的位置，因为_start 可能改变了。

2.6.4 erase 删除指定位置元素

iterator erase(iterator pos) {
    assert(pos >= _start);
    assert(pos < _finish);
    iterator it = pos + 1;
    while (it != _finish) {
        *(it - 1) = *it;
        ++it;
    }
    --_finish;
    return pos;
}

3 vector 迭代器失效问题

迭代器失效是使用 vector 时需要特别注意的问题，不当使用会导致未定义行为。

3.1 insert 失效问题

当在 vector 中插入元素时，如果引起扩容，所有迭代器都会失效。

void test_vector2() {
    bit::vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    auto it = v.begin() + 3;
    v.insert(v.begin(), 0); // 可能引起扩容
    // insert 以后，it 失效了，不能再使用
    // *it = 10; // 错误！未定义行为
}

3.2 erase 失效问题

erase 操作会使被删除元素及其后面所有元素的迭代器失效。

void test_vector3() {
    bit::vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    auto it = v.begin() + 2;
    v.erase(v.begin()); // 删除第一个元素
    // it 失效了，不能访问，访问结果未定义
    // cout << *it << endl; // 错误！
}

3.3 删除所有的偶数

正确使用 erase 删除元素的模式：

void test_vector4() {
    bit::vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    v.push_back(6);
    // 正确做法：接收 erase 的返回值
    auto it = v.begin();
    while (it != v.end()) {
        if (*it % 2 == 0) {
            it = v.erase(it); // erase 返回下一个有效迭代器
        } else {
            ++it;
        }
    }
    // 错误做法：直接递增迭代器
    // auto it = v.begin();
    // while (it != v.end())
    // {
    //     if (*it % 2 == 0)
    //     {
    //         v.erase(it);
    //         // erase 后 it 失效
    //     }
    //     ++it;
    //     // 错误：对失效迭代器递增
    // }
}

3.4 不同编译器对迭代器失效的检查

不同编译器对迭代器失效的检查严格程度不同：

• Debug 模式下通常会进行严格的迭代器检查
• Release 模式下可能没有检查，导致难以发现的 bug
• Linux 的 gcc 编译器检查就会比较宽松

3.5 扩容之后，迭代器已经失效了

vector<int> v = {1, 2, 3};
auto it = v.begin();
v.push_back(4); // 可能引起扩容
// it 已经失效，不能再使用

3.6 erase 删除的迭代器如果是最后一个元素

vector<int> v = {1, 2, 3};
auto it = v.begin() + 2; // 指向 3
it = v.erase(it); // 删除最后一个元素
// 此时 it == v.end()，不能解引用

3.7 string 的迭代器失效

与 vector 类似，string 在插入、扩容操作、erase 之后，迭代器也会失效。

4 本文代码完整展示

（一）vector.h

#pragma once
#include <iostream>
#include <cassert>
using namespace std;

namespace bit {
    template<class T>
    class vector {
    public:
        typedef T* iterator;
        typedef const T* const_iterator;

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

        // 构造函数 - 指定大小和初始值
        vector(size_t n, const T& val = T()) {
            reserve(n);
            for (size_t i = 0; i < n; i++) {
                push_back(val);
            }
        }
        vector(int n, const T& val = T()) {
            reserve(n);
            for (int i = 0; i < n; i++) {
                push_back(val);
            }
        }

        // 迭代器范围构造函数
        template <class InputIterator>
        vector(InputIterator first, InputIterator last) {
            while (first != last) {
                push_back(*first);
                ++first;
            }
        }

        // 默认构造函数
        vector() = default;

        // 拷贝构造函数（现代写法）
        vector(const vector<T>& v) {
            vector<T> tmp(v.begin(), v.end());
            swap(tmp);
        }

        // 赋值运算符（现代写法）
        vector<T>& operator=(vector<T> tmp) {
            swap(tmp);
            return *this;
        }

        // 交换两个 vector
        void swap(vector<T>& v) {
            std::swap(_start, v._start);
            std::swap(_finish, v._finish);
            std::swap(_end_of_storage, v._end_of_storage);
        }

        // 清空元素
        void clear() { _finish = _start; }

        // 判断是否为空
        bool empty() const { return _start == _finish; }

        // 预留空间
        void reserve(size_t n) {
            if (n > capacity()) {
                size_t sz = size();
                T* tmp = new T[n];
                if (_start) {
                    for (size_t i = 0; i < sz; i++) {
                        std::swap(tmp[i], _start[i]);
                    }
                    delete[] _start;
                }
                _start = tmp;
                _finish = _start + sz;
                _end_of_storage = _start + n;
            }
        }

        // 调整大小
        void resize(size_t n, T val = T()) {
            if (n < size()) {
                _finish = _start + n;
            } else {
                reserve(n);
                while (_finish < _start + n) {
                    *_finish = val;
                    ++_finish;
                }
            }
        }

        // 获取容量
        size_t capacity() const { return _end_of_storage - _start; }

        // 获取元素个数
        size_t size() const { return _finish - _start; }

        // 下标运算符
        T& operator[](size_t i) {
            assert(i < size());
            return _start[i];
        }
        const T& operator[](size_t i) const {
            assert(i < size());
            return _start[i];
        }

        // 尾部添加元素
        void push_back(const T& x) {
            if (_finish == _end_of_storage) {
                reserve(capacity() == 0 ? 4 : capacity() * 2);
            }
            *_finish = x;
            ++_finish;
        }

        // 尾部删除元素
        void pop_back() {
            assert(!empty());
            --_finish;
        }

        // 在指定位置插入元素
        iterator insert(iterator pos, const T& x) {
            assert(pos >= _start);
            assert(pos <= _finish);
            if (_finish == _end_of_storage) {
                size_t len = pos - _start;
                reserve(capacity() == 0 ? 4 : capacity() * 2);
                pos = _start + len;
            }
            iterator end = _finish - 1;
            while (end >= pos) {
                *(end + 1) = *end;
                --end;
            }
            *pos = x;
            ++_finish;
            return pos;
        }

        // 删除指定位置元素
        iterator erase(iterator pos) {
            assert(pos >= _start);
            assert(pos < _finish);
            iterator it = pos + 1;
            while (it != _finish) {
                *(it - 1) = *it;
                ++it;
            }
            --_finish;
            return pos;
        }

        // 析构函数
        ~vector() {
            if (_start) {
                delete[] _start;
                _start = _finish = _end_of_storage = nullptr;
            }
        }

    private:
        iterator _start = nullptr;
        iterator _finish = nullptr;
        iterator _end_of_storage = nullptr;
    };
}

（二）test.cpp

#include "vector.h"
#include <iostream>
using namespace std;

namespace bit {
    // 打印 vector 内容
    void Print(const vector<int>& v) {
        for (auto e : v) {
            cout << e << " ";
        }
        cout << endl;
    }

    // 测试基本操作
    void test_vector1() {
        cout << "测试基本操作:" << endl;
        bit::vector<int> v;
        v.push_back(1);
        v.push_back(2);
        v.push_back(3);
        v.push_back(4);
        v.push_back(5);
        v[0]++; // 修改第一个元素
        Print(v);
        // 范围 for 遍历
        for (auto e : v) {
            cout << e << " ";
        }
        cout << endl;
    }

    // 测试 insert 操作
    void test_vector2() {
        cout << "\n测试 insert 操作:" << endl;
        bit::vector<int> v;
        v.push_back(1);
        v.push_back(2);
        v.push_back(3);
        v.push_back(4);
        Print(v);
        v.insert(v.begin(), 0); // 头部插入
        Print(v);
        // 注意：insert 后迭代器可能失效
        auto it = v.begin() + 3;
        v.insert(it, 30); // 指定位置插入
        Print(v);
    }

    // 测试 erase 操作
    void test_vector3() {
        cout << "\n测试 erase 操作:" << endl;
        bit::vector<int> v;
        v.push_back(1);
        v.push_back(2);
        v.push_back(3);
        v.push_back(4);
        v.push_back(5);
        Print(v);
        v.erase(v.begin()); // 删除第一个元素
        Print(v);
        auto it = v.begin() + 2;
        v.erase(it); // 删除指定位置元素
        Print(v);
    }

    // 测试删除特定元素（删除所有偶数）
    void test_vector4() {
        cout << "\n测试删除所有偶数:" << endl;
        bit::vector<int> v;
        v.push_back(1);
        v.push_back(2);
        v.push_back(2);
        v.push_back(3);
        v.push_back(4);
        v.push_back(5);
        v.push_back(6);
        cout << "删除前: ";
        for (auto e : v) {
            cout << e << " ";
        }
        cout << endl;
        // 正确删除方法
        auto it = v.begin();
        while (it != v.end()) {
            if (*it % 2 == 0) {
                it = v.erase(it); // 接收 erase 返回值
            } else {
                ++it;
            }
        }
        cout << "删除后: ";
        for (auto e : v) {
            cout << e << " ";
        }
        cout << endl;
    }

    // 测试 resize 操作
    void test_vector5() {
        cout << "\n测试 resize 操作:" << endl;
        bit::vector<int> v;
        v.push_back(1);
        v.push_back(2);
        v.push_back(2);
        v.push_back(3);
        v.push_back(4);
        v.push_back(5);
        v.push_back(6);
        cout << "原始 vector: ";
        for (auto e : v) {
            cout << e << " ";
        }
        cout << endl;
        v.resize(3); // 缩小
        cout << "resize(3): ";
        for (auto e : v) {
            cout << e << " ";
        }
        cout << endl;
        v.resize(20, 5); // 扩大并填充
        cout << "resize(20, 5): ";
        for (auto e : v) {
            cout << e << " ";
        }
        cout << endl;
    }

    // 测试拷贝构造和赋值
    void test_vector6() {
        cout << "\n测试拷贝构造和赋值:" << endl;
        bit::vector<int> v1;
        v1.push_back(1);
        v1.push_back(2);
        v1.push_back(2);
        v1.push_back(3);
        v1.push_back(4);
        v1.push_back(5);
        v1.push_back(6);
        cout << "v1: ";
        for (auto e : v1) {
            cout << e << " ";
        }
        cout << endl;
        // 拷贝构造
        bit::vector<int> v2(v1);
        cout << "v2(拷贝 v1): ";
        for (auto e : v2) {
            cout << e << " ";
        }
        cout << endl;
        // 赋值操作
        bit::vector<int> v3 = {10, 20, 30, 40};
        v1 = v3;
        cout << "v1(赋值后): ";
        for (auto e : v1) {
            cout << e << " ";
        }
        cout << endl;
        // 指定大小构造
        bit::vector<int> v4(10, 1);
        cout << "v4(10 个 1): ";
        for (auto e : v4) {
            cout << e << " ";
        }
        cout << endl;
        bit::vector<char> v5(10, 'x');
        cout << "v5(10 个 x): ";
        for (auto e : v5) {
            cout << e << " ";
        }
        cout << endl;
    }

    // 测试 string 类型 vector
    void test_vector7() {
        cout << "\n测试 string 类型 vector:" << endl;
        bit::vector<string> v1;
        v1.push_back("111111111111111111111111");
        v1.push_back("222222222222222222222222");
        v1.push_back("333333333333333333333333");
        v1.push_back("444444444444444444444444");
        v1.push_back("555555555555555555555555");
        for (auto& e : v1) {
            cout << e << " ";
        }
        cout << endl;
    }
}

int main() {
    bit::test_vector1();
    bit::test_vector2();
    bit::test_vector3();
    bit::test_vector4();
    bit::test_vector5();
    bit::test_vector6();
    bit::test_vector7();
    return 0;
}

C++ vector 基于动态数组实现，通过三个指针管理内存。核心风险是迭代器失效：insert 可能扩容使所有迭代器失效；erase 使被删位置后迭代器失效，必须通过 it=erase(it) 接收返回值。采用 2 倍扩容策略，现代写法通过 swap 实现安全拷贝。连续存储支持高效随机访问，但需警惕迭代器失效这一主要陷阱。