C++ STL 详解：从零实现 vector 容器

注意：如果我们想要实现允许用花括号 {} 的方式直接初始化对象，仅使用直接的无参构造是不够的。通常还需要配合初始化列表构造函数，从而实现以下的初始化对象功能。

析构

析构函数在对象生命周期结束时自动调用。对于容器来说，最重要的就是 释放堆上申请的内存，避免内存泄漏。

~vector() {
    if (_start) {
        delete[] _start;
        _start = _finish = _end_of_storage = nullptr;
    }
}

• if (_start) 判断 _start 是否为空指针，防止对空指针执行 delete[]。如果容器里没有分配过空间，那就啥也不做。
• delete[] _start 释放之前用 new[] 申请的动态数组空间。注意必须用 delete[] 而不是 delete，因为申请时用的是数组形式。
• _start = _finish = _end_of_storage = nullptr 把三个指针全部置为 nullptr，防止出现 悬空指针 问题。虽然对象马上要销毁了，但这是一个良好的习惯，尤其是如果你以后想写 clear() 或者 析构后继续 debug，可以避免野指针引发错误。

operator=

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

三、迭代器相关函数

begin 和 end 的 iterator / const_iterator

在 STL 中，迭代器是通过 typedef 或 using 声明出来的，它可能是指针，也可能是一个类对象。在我们模拟实现的 vector 里，可以直接把迭代器类型定义为 T*（指向元素的指针），这样最简单直观。除了普通迭代器 iterator，还需要一个 只读版本 —— const_iterator。它的类型是 const T*，也就是指向常量对象的指针。

区别：

• iterator → 可读可写（适合普通对象）。
• const_iterator → 只读（适合 const 对象）。

typedef T* iterator;
const typedef T* const_iterator;

iterator begin() {
    return _start;
}

iterator end() {
    return _finish;
}

const_iterator begin() const {
    return _start;
}

const_iterator end() const {
    return _finish;
}

四、容量大小相关函数

size 和 capacity

由于仅仅是获取 size 和 capacity 的值，并不对 vector 的成员变量进行修改，所以可以使用 const 修饰 this 指针，让普通对象和 const 对象都可以进行调用。

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

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

reserve

reserve 的实现逻辑拆解

只扩不缩 当 n > capacity 时才扩容。当 n <= capacity 时不做任何操作。因为缩容同样涉及'异地缩容'，代价大，不划算。

扩容前保存有效数据个数 扩容时会进行'异地扩容'，即申请新空间并释放旧空间。如果直接释放旧空间，再次调用 size() 无法再获取有效元素数量。所以扩容前要用变量 old_size 保存当前元素个数。

申请新空间 使用 new[] 申请 n 个 T 类型的空间。用指针 tmp 指向这片新空间。

拷贝旧数据到新空间 如果 _start 为空（容器中没数据），就不需要拷贝。如果有数据，需要把旧空间的数据拷贝到新空间。

为什么不用 memcpy？ 对于内置类型（int、double 等），memcpy 按字节拷贝没问题。但对自定义类型（需要深拷贝的对象），memcpy 只会浅拷贝，导致错误。

如何实现深拷贝？ 使用 for 循环和下标 []，让每个元素通过 赋值运算符重载 进行拷贝。这样自定义类型就会自动调用它的赋值运算符，完成深拷贝。

释放旧空间，更新指针 数据拷贝完成后，调用 delete[] 释放原空间。让 _start 指向新空间，同时更新 _finish 和 _end_of_storage。

// reserve 扩容
void reserve(size_t n) {
    if (n > capacity()) {
        size_t old_size = size();
        T* tmp = new T[n];

        // 拷贝旧空间的数据到新空间
        if (_start) {
            for (size_t i = 0; i < old_size; i++) {
                tmp[i] = _start[i];
            }
            // memcpy(tmp, _start, sizeof(T) * old_size);
            delete[] _start;
        }

        _start = tmp;
        _finish = _start + old_size;
        _end_of_storage = _start + n;
    }
}

resize

vector::resize 的两种情况解析：

在 vector 的 resize 实现中，常常会涉及到一个默认参数：

void resize(size_t n, const T& val = T());

const 表示这个参数在函数内部不会被修改。保证传进来的对象内容只读，避免误操作。

T&（引用） 避免发生一次 值传递拷贝。 如果写成 T val，调用时会先拷贝一份（可能调用拷贝构造，代价大）。 写成 const T& val，则直接绑定到传入对象上，不会额外拷贝。

这样写可以同时支持：

• 内置类型（比如 int、double）——引用绑定到临时值上，效率高。
• 自定义类型（比如 string、MyClass）——避免了多余的深拷贝。

举例

vector<int> v;
v.resize(5); // 等价于 v.resize(5, int()); -> 用 0 填充
v.resize(5, 3); // 等价于 v.resize(5, const int& val=3);

vector<string> vs;
vs.resize(3); // 等价于 vs.resize(3, string()); -> 用 "" 填充
vs.resize(3, "hi"); // 等价于 vs.resize(3, const string& val="hi");

这里的 缺省参数 T() 非常关键。

缺省值为什么能用 T()？ 对于 自定义类型：T() 会调用该类型的默认构造函数，产生一个临时对象（匿名对象），作为缺省值。 对于 内置类型：例如 int、double 等，C++ 语言标准对其进行了'升级'——同样可以使用 T() 来构造缺省值。

• int() 结果为 0
• double() 结果为 0.0
• char() 结果为 '�' 这样一来，无论 T 是内置类型还是自定义类型，T() 都能得到一个有效的缺省值，使得模板代码具备统一性和泛化能力。

resize 的两种情况

情况一：n <= size() 无需扩容：因为 n 小于等于当前有效数据个数，不涉及新增元素。 vector 的元素访问和遍历是以 有效个数 为准，有效个数通过 _finish - _start 来计算。因此我们只需要让 _finish = _start + n，有效数据范围就自动缩小为前 n 个元素。这就实现了 逻辑上删除尾部多余元素，但并不会释放容量。

情况二：n > size() 这里就要往 vector 里补充新元素。又可以分为两种子情况：

• n <= capacity()：容量足够，直接在现有内存空间中追加元素。
• n > capacity()：容量不足，需要扩容。常规策略是开辟更大的空间（一般按 2 倍扩容，或者直接扩到 n），然后迁移原有元素，再补充新元素。 为了实现逻辑简洁，我们往往 统一处理为扩容流程：直接判断如果 n > capacity() 就扩容。扩容后，从 _finish 开始，依次用 T()（或用户传入的 value）填充，直到 _start + n。最终 _finish = _start + n，有效数据范围更新完毕。

// resize 扩容或缩减
void resize(size_t n, const T& val = T()) // 如果用户没传第二个参数，就用类型的默认值，如果是自定义类 MyClass，就调用它的默认构造函数
{
    if (n > size()) {
        reserve(n);
        while (_finish != _start + n) {
            *_finish = val;
            ++_finish;
        }
    } else {
        _finish = _start + n;
    }
}

empty

empty 函数可以直接通过比较容器当中的 _start 和 _finish 指针的指向来判断容器是否为空，若所指位置相同，则该容器为空。

// 判空
bool empty() const {
    return _start == _finish;
}

五、修改容器内相关函数

push_back

在 vector 中存储的类型是不确定的，可能是 int 这样的内置类型，也可能是 string、MyClass 这样的自定义类型。

如果我们定义为传值：

void push_back(T x); // ❌ 低效

对于自定义类型，就会产生一次 额外的拷贝，效率很低。

因此我们要改为 引用传参：

void push_back(const T& x); // ✅ 推荐写法

解释：引用：避免额外拷贝，提高效率。const 修饰：保证 x 在函数体内不会被修改。

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

pop_back

// 尾删 pop_back
void pop_back() {
    assert(_start < _finish);
    assert(!empty());
    --_finish;
}

insert

insert 函数可以在所给迭代器 pos 位置插入数据，在插入数据前先判断是否需要增容，然后将 pos 位置及其之后的数据统一向后挪动一位，以留出 pos 位置进行插入，最后将数据插入到 pos 位置即可。

// insert pos 位置插入
iterator insert(iterator pos, const T& x) // 给迭代器
{
    assert(pos >= _start);
    assert(pos <= _finish);

    if (_finish == _end_of_storage) {
        // reserve(capacity() == 0 ? 4 : capacity() * 2); // 如果——capacity 不够 reserve 会进行扩容，导致空间变化，
        // 然后 pos 还指向的旧空间，迭代器会失效
        size_t len = pos - _start;
        reserve(capacity() == 0 ? 4 : capacity() * 2);
        pos = _start + len; // 更新 pos 位置，解决上述问题
    }

    iterator end = _finish - 1; // 指向最后一个数据
    while (end >= pos) {
        *(end + 1) = *end; // 向后移动
        --end;
    }
    *pos = x;
    ++_finish; // 更新大小
    return pos;
}

注意： 若需要增容，则需要在增容前记录 pos 与 _start 之间的间隔，然后通过该间隔确定在增容后的容器当中 pos 的指向，否则 pos 还指向原来被释放的空间。

erase

erase 函数可以删除所给迭代器 pos 位置的数据，在删除数据前需要判断容器释放为空，若为空则需做断言处理，删除数据时直接将 pos 位置之后的数据统一向前挪动一位，将 pos 位置的数据覆盖即可。

// 数据删除 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; // 返回删除数据的下一个位置，删除了往前覆盖，就是 pos 位置
}

swap

需要交换的参数 v 类型是 vector<T>，这里必须通过引用传参，避免不必要的拷贝开销，同时 v 本身就作为要交换对象的别名来使用。实际交换时直接调用标准库的 swap 来交换两个对象的三个指针。由于堆上真实存储的数据并没有移动，只是两个对象内部的指针被互换，因此能高效完成两个 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);
}

clear

// clear 清理
void clear() {
    _finish = _start;
}

六、访问容器相关函数

operator[] 和 由 const 修饰的 operator[]

vector 底层是顺序表数组，在类的私有成员变量中通过 _start 指针指向该数组。访问元素时，_start[pos] 实际等价于 *(_start + pos)。由于 _start 是私有成员，只能在类内直接访问，因此我们在成员函数中返回 _start[pos] 即可。返回值使用引用的方式更合适。因为元素本身存储在对象的空间中，只要对象未销毁，该元素就一直存在，不会因作用域结束而失效。这样不仅避免了拷贝开销，还能支持对元素进行修改。

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

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

七、构造函数的延伸

拷贝构造

拷贝构造函数的现代写法也比较简单，使用范围 for（或是其他遍历方式）对容器 v 进行遍历，在遍历过程中将容器 v 中存储的数据一个个尾插过来即可。

// 拷贝构造 v2(v1)
vector(const vector<T>& v) : _start(nullptr), _finish(nullptr), _end_of_storage(nullptr) {
    reserve(capacity());
    for (auto e : v) {
        push_back(e);
    }
}

使用 n 个 T 类型的 val 进行构造

// n 个 val 构造
vector(int n, T val = T()) {
    resize(n, val);
}

（使用函数模板构造）使用迭代器区间进行构造

使用迭代器区间这个构造函数只能接受特定类型（例如 vector::iterator）的区间作为输入。本质上就是不断从 [start, end) 区间取元素，通过 push_back 插入到新构造的 vector 中。缺点显而易见：通用性差，只能拷贝相同容器（甚至是相同类型的 vector）的区间。

使用模板参数 InputIterator，它不局限于 vector 的迭代器。任何符合输入迭代器要求的类型（如 list::iterator、deque::iterator、甚至原始指针 int*）都可以作为参数。

这让 vector 的构造函数更泛型化，与 STL 其他容器之间能很好地协作。

// 迭代器区间构造
/*
vector(iterator start, iterator end) {
    while (start != end) {
        push_back(*start);
        ++start;
    }
}
*/

// 使用函数模版，任意类型容器迭代器初始化
template <class InputIterator>
vector(InputIterator first, InputIterator last) {
    while (first != last) {
        push_back(*first);
        ++first;
    }
}