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

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

在之前的讨论中，我们详细了解了 vector 核心接口的使用。接下来，我们将深入剖析其底层实现机制，并通过模拟代码来加深理解。

一、vector 的基本成员变量

在着手模拟之前，必须明确 vector 内部维护了哪些关键指针。通过查阅源码可以发现，vector 主要依赖三个指针来管理内存：

• _start：指向已分配空间的头部。
• _finish：指向最后一个有效数据元素的下一个位置。
• _endofstorage：指向已分配空间的末尾。

基于此，我们可以搭建出 vector 的类框架。需要注意的是，模板类的声明和定义通常不能分离到不同文件中，因此所有实现都放在头文件内。

#include <iostream>
using namespace std;

namespace my_vector {
template<class T>
class vector {
public:
    // 迭代器直接使用原生指针
    typedef T* iterator;
    typedef const T* const_iterator;

private:
    iterator _start;      // 指向空间头部
    iterator _finish;     // 指向最后一个有效数据的下一个位置
    iterator _endofstorage; // 指向空间的末尾
};}

二、vector 核心接口的实现

2.1 构造相关接口

构造函数涵盖了多种初始化场景，包括默认构造、指定数量构造、拷贝构造、初始化列表构造以及迭代器区间构造。赋值运算符重载则通常通过交换逻辑来实现。

// 默认构造
vector() : _start(nullptr), _finish(nullptr), _endofstorage(nullptr) {}

// 使用 n 个 val 初始化
// T() 会调用类型 T 的默认构造，支持内置类型或自定义类型
vector(size_t n, T val = T()) {
    resize(n, val);
}

// 拷贝构造
vector(const vector<T>& v) {
    reserve(v.size());
    for (auto e : v) {
        push_back(e);
    }
}

// 初始化列表构造
vector(initializer_list<T> il) {
    reserve(il.size());
    for (auto e : il) {
        push_back(e);
    }
}

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

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

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

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

2.2 迭代器相关的接口实现

vector 的迭代器分为普通迭代器和常量迭代器。反向迭代器则是正向迭代器的逆序版本，rbegin() 返回 end() - 1，rend() 返回 begin() - 1。

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

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

2.3 空间相关的接口实现

空间管理是 vector 的核心，涉及 size()、capacity()、empty()、resize() 和 reserve()。其中 reserve 负责扩容但不改变有效数据个数，而 resize 既可能扩容也可能缩容并影响有效数据个数。

size_t size() const { return _finish - _start; }
size_t capacity() const { return _endofstorage - _start; }
bool empty() const { return _start == _finish; }

void resize(size_t n, T val = T()) {
    if (n > size()) {
        reserve(n);
        while (_finish != _start + n) {
            *_finish = val;
            ++_finish;
        }
    } else {
        _finish = _start + n;
    }
}

void reserve(size_t n) {
    auto oldsize = size();
    if (n > capacity()) {
        iterator tmp = new T[n];
        if (_start) {
            // 避免 memcpy 导致的浅拷贝问题，使用赋值操作符进行深拷贝
            for (size_t i = 0; i < oldsize; i++) {
                tmp[i] = _start[i];
            }
            delete[] _start;
        }
        _start = tmp;
        _finish = _start + oldsize;
        _endofstorage = _start + n;
    }
}

关于 memcpy 的浅拷贝问题

在使用 memcpy 复制对象时，如果元素类型包含指针成员，会导致浅拷贝，析构时可能引发重复释放错误。因此，在 reserve 扩容时，建议遍历并使用赋值运算符完成深拷贝。

2.4 元素访问相关的接口实现

最常用的访问方式是下标操作符 operator[]。由于迭代器本质是指针，下标访问直接转化为指针偏移。

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

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

2.5 vector 修改相关的接口实现

插入和删除操作需要特别注意内存管理和迭代器状态。尾插和尾删相对简单，任意位置的插入和删除则涉及数据搬移。

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

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

// 任意位置插入
iterator insert(iterator pos, const T& x) {
    assert(pos >= _start && pos <= _finish);
    if (_finish == _endofstorage) {
        reserve(capacity() == 0 ? 4 : 2 * capacity());
        // 扩容后原指针失效，需重新计算位置
        pos = _start + (pos - _start);
    }
    iterator end = _finish;
    while (end >= pos) {
        *(end + 1) = *end;
        end--;
    }
    *pos = x;
    ++_finish;
    return pos;
}

// 任意位置删除
iterator erase(iterator pos) {
    assert(pos >= _start && pos <= _finish);
    if (!empty()) {
        iterator it = pos;
        while (it < _finish) {
            *it = *(it + 1);
            ++it;
        }
        --_finish;
    }
    return pos;
}

三、插入删除引起的迭代器失效问题

在进行插入或删除操作时，vector 可能会发生扩容或数据搬移，导致原有迭代器指向的地址无效。

插入导致的失效示例：

void test_vector9() {
    my_vector::vector<int> v{1, 2, 3, 4};
    auto it = v.begin();
    v.push_back(5); // 触发扩容，迭代器失效
    while (it != v.end()) {
        cout << *it << " ";
        *it = 100;
        ++it;
    }
    cout << endl;
}

删除导致的失效示例：

void test_vector10() {
    my_vector::vector<int> v{1, 2, 3, 4, 5, 6};
    auto it = v.begin();
    while (it != v.end()) {
        if (*it % 2 == 0)
            v.erase(it); // erase 返回下一个有效迭代器，但此处未更新
        ++it; // 可能导致越界或野指针
    }
    for (auto e : v) cout << e << " ";
    cout << endl;
}

在删除操作中，如果使用 erase 删除当前元素，应使用 erase 返回的新迭代器继续遍历，或者调整循环逻辑，否则极易引发崩溃。

四、总结

本文梳理了 vector 的底层成员变量、核心接口实现及内存管理机制。重点掌握了 reserve 与 resize 的区别，理解了深拷贝在处理自定义类型时的必要性，并分析了插入删除操作引发的迭代器失效问题。在实际开发中，留意这些细节能有效避免潜在的内存错误。