C++ 之 vector的自我实现-EW帮帮网

vector自我实现

vector 的迭代器失效

一、vector 基本结构与核心概念

1. 数据成员

自定义 vector 类包含三个核心指针成员：

_start：指向数据块的起始位置
_finish：指向有效数据的末尾位置
_endOfStorage：指向存储容量的末尾位置

这三个指针共同定义了 vector 的三个关键区域：已分配内存空间、有效数据区域和可用扩展空间。

2. 迭代器设计

typedef T* iterator;
typedef const T* const_iterator;

迭代器是 vector 与外界交互的接口，这里定义了两种迭代器：

iterator：普通迭代器，支持读写操作
const_iterator：常量迭代器，仅支持读操作

通过提供 begin() 和 end() 方法，vector 实现了对迭代器的支持，使其能够融入 C++ 标准库的迭代器体系。

二、构造与析构函数

1. 默认构造函数

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

默认构造函数将三个指针都初始化为 nullptr，表示一个空的 vector。

2. 初始化构造函数

vector(int n, const T& value = T())
{
    resize(n, value);
}

该构造函数可以创建一个包含 n 个元素的 vector，每个元素初始化为 value（默认为 T 类型的默认值）。

3. 迭代器范围构造函数

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

这个模板构造函数允许通过任意输入迭代器范围来初始化 vector，体现了 C++ 泛型编程的强大能力。

4. 初始化列表构造函数

vector(initializer_list<T> il)
{
    reserve(il.size());
    for (auto& e : il)
    {
        push_back(e);
    }
}

C++11 引入的初始化列表构造函数，使我们可以用花括号初始化 vector，如 vector<int> v = {1, 2, 3, 4}。

5. 拷贝构造函数与赋值运算符

vector(const vector<T>& v)
{
    reserve(v.capacity());
    for (auto& e : v)
    {
        push_back(e);
    }
}

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

拷贝构造函数采用深拷贝方式，为新 vector 分配独立内存并复制数据。赋值运算符使用了 “拷贝并交换” 惯用法，先创建参数的副本，再通过交换实现赋值，这种方式异常安全。

6. 析构函数

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

析构函数负责释放动态分配的内存，避免内存泄漏。

三、容量与大小操作

1. size() 和 capacity()

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

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

size() 返回有效元素个数，capacity() 返回当前分配的总容量。由于指针是连续的，直接通过指针相减即可得到结果。

2. reserve() 与动态扩容

void reserve(size_t n)
{
    if (n > capacity())
    {
        size_t oldsize = size();
        T* tmp = new T[n];
        if (_start)
        {
            for (int i = 0; i < size();i++)
            {
                tmp[i] = _start[i];
            }
            delete[] _start;
        }
        _start = tmp;
        _finish = _start + oldsize;
        _endOfStorage = _start + n;
    }
}

reserve() 用于主动修改 vector 的容量。当 n 大于当前容量时，会分配新的更大的内存块，将数据复制到新块，然后释放旧内存。这里采用了两倍扩容策略（在 push_back 中）：

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

当空间不足时，push_back 会先扩容，通常是当前容量的两倍（首次为 4），这样可以减少扩容次数，降低时间复杂度。

3. resize() 调整大小

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

resize(n) 可以调整 vector 的大小为 n：

当 n 大于当前大小时，会先扩容，然后用 value 填充新增空间
当 n 小于当前大小时，会将有效数据截断到前 n 个元素

四、元素访问与修改操作

1. 下标运算符

T& operator[](size_t pos)
{
    return *(_start + pos);
}

const T& operator[](size_t pos)const
{
    return *(_start + pos);
}

通过重载下标运算符，vector 支持类似数组的随机访问，时间复杂度为 O(1)。

2. push_back() 和 pop_back()

push_back() 已在前面介绍过，用于在尾部添加元素。pop_back() 则用于删除尾部元素：

void pop_back()
{
    assert(_start < _finish);
    _finish--;
}

3. swap() 交换操作

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

swap() 用于交换两个 vector 的内容，通过交换三个指针实现，时间复杂度为 O(1)。

五、插入与删除操作

1. insert() 插入操作

iterator insert(iterator pos, const T& x)
{
    assert(pos >= _start);
    assert(pos <= _finish);

    if (_finish == _endOfStorage)
    {
        int len = pos - _start;
        int newcapacity = capacity() == 0 ? 4 : 2 * capacity();
        reserve(newcapacity);
        pos = _start + len;
    }
    iterator end = _finish - 1;
    while (pos != end)
    {
        *(end + 1) = *(end);
        end--;
    }
    _finish++;
    *(pos) = x;
    return pos;
}

insert() 可以在指定位置 pos 前插入元素 x：

首先检查是否需要扩容
然后将 pos 及之后的元素后移一位
最后在 pos 位置插入新元素

由于需要移动元素，插入操作的时间复杂度为 O(n)。

2. erase() 删除操作

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

erase() 用于删除指定位置的元素：

将 pos 之后的元素前移一位
调整 _finish 指针

删除操作同样需要移动元素，时间复杂度为 O(n)。

vector 的迭代器失效

在使用 vector 的 insert 和 erase 操作时，迭代器失效是一个常见且容易引发错误的问题。

一、迭代器失效的本质原因

vector 的迭代器本质上是指向其内部数组元素的指针。当 vector 的内部结构发生变化时，这些指针可能不再指向有效的内存位置，从而导致迭代器失效。具体来说，迭代器失效主要有两种情况：

指针指向的内存被释放：当 vector 扩容时，会分配新的内存块并将数据复制过去，原内存被释放，此时原迭代器指向的内存已无效。
元素位置发生移动：当插入或删除元素时，可能会导致后续元素前移或后移，使得迭代器指向错误的元素。

二、insert 操作导致的迭代器失效

1. 扩容引起的迭代器失效

void insert(iterator pos, const T& x)
{
    if (_finish == _endOfStorage)
    {
        int len = pos - _start;
        int newcapacity = capacity() == 0 ? 4 : 2 * capacity();
        reserve(newcapacity);
        pos = _start + len; // 重新计算 pos 位置
    }
    // ...
}

当插入导致扩容时，vector 会分配新内存并复制数据，原迭代器全部失效。例如：

vector<int> v = {1, 2, 3};
auto it = v.begin() + 1; // it 指向 2
v.insert(it, 10); // 插入导致扩容，原 it 失效
cout << *it; // 错误！it 已失效

2. 元素移动引起的迭代器失效

即使不扩容，插入操作也会导致插入点及之后的元素后移，使得这些位置的迭代器失效：

vector<int> v = {1, 2, 3, 4};
auto it1 = v.begin() + 1; // it1 指向 2
auto it2 = v.begin() + 3; // it2 指向 4

v.insert(it1, 10); // 插入后，2及之后元素后移

cout << *it1; // 错误！it1 失效
cout << *it2; // 错误！it2 失效

安全使用 insert 的方法：

auto it = v.begin() + 1;
it = v.insert(it, 10); // insert 返回指向新插入元素的迭代器
// 现在 it 指向新插入的 10

三、erase 操作导致的迭代器失效

1. 元素移动引起的迭代器失效

iterator erase(iterator pos)
{
    iterator it = pos + 1;
    while (it < _finish)
    {
        *(it - 1) = *(it); // 元素前移
        it++;
    }
    _finish--;
    return pos; // 返回被删除元素的下一个位置
}

删除元素后，被删除位置及之后的元素会前移，导致这些位置的迭代器失效：

vector<int> v = {1, 2, 3, 4};
auto it1 = v.begin() + 1; // it1 指向 2
auto it2 = v.begin() + 3; // it2 指向 4

v.erase(it1); // 删除 2，3 和 4 前移

cout << *it1; // 错误！it1 失效
cout << *it2; // 错误！it2 失效

安全使用 erase 的方法：

auto it = v.begin() + 1;
it = v.erase(it); // erase 返回被删除元素的下一个位置
// 现在 it 指向 3

2. 删除最后一个元素的特殊情况

vector<int> v = {1, 2, 3};
auto it = v.end(); // it 指向尾后位置

v.pop_back(); // 删除 3

cout << *it; // 错误！it 失效，end() 已改变

四、循环中使用 insert/erase 的陷阱

在循环中使用 insert 或 erase 时，迭代器失效可能导致死循环或未定义行为：

1. 错误示例：循环中 erase

vector<int> v = {1, 2, 3, 4, 5};
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it % 2 == 0) {
        v.erase(it); // it 失效，++it 导致未定义行为
    }
}

2. 正确示例：循环中 erase

vector<int> v = {1, 2, 3, 4, 5};
for (auto it = v.begin(); it != v.end();) {
    if (*it % 2 == 0) {
        it = v.erase(it); // erase 返回下一个有效位置
    } else {
        ++it; // 只有不删除时才递增
    }
}

3. 循环中 insert 的正确方式

vector<int> v = {1, 3, 5};
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it == 3) {
        it = v.insert(it, 2); // 插入 2 在 3 前面
        ++it; // 跳过新插入的元素，指向 3
    }
}
// v 现在是 {1, 2, 3, 5}

五、总结与最佳实践

1. insert 操作的迭代器失效规则

扩容情况：所有迭代器（包括 begin() 和 end()）全部失效
非扩容情况：插入点及之后的迭代器失效

2. erase 操作的迭代器失效规则

被删除位置及之后的迭代器失效

3. 最佳实践

避免保存迭代器：尽量在使用时直接获取迭代器，避免长时间保存
使用返回值：insert 和 erase 都会返回有效迭代器，应使用这些返回值更新迭代器
小心循环中的操作：在循环中使用 insert 或 erase 时，必须特别注意迭代器的更新
在使用insert和erase函数之后，用迭代器接受其返回值

C++ 之 vector的自我实现