C++ vector 容器底层原理与实战使用指南

注意： string 类拷贝函数执行的也是深拷贝。

3. 迭代器的使用

示例代码与讲解

#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> v = {10, 20, 30, 40};

    // 反向遍历详解
    // v.rbegin() -> 指向最后一个元素 40
    // v.rend() -> 指向第一个元素 10 之前的一个'虚空'位置
    cout << "反向输出结果: ";
    for (auto rit = v.rbegin(); rit != v.rend(); ++rit) {
        cout << *rit << " ";
    }
    cout << endl;

    // 实用技巧：获取最后一个元素
    cout << "最后一个元素是：" << *v.rbegin() << endl;

    return 0;
}

4. 容量增长问题

注意事项

1. 增容倍数

当 vector 的 size == capacity 时再插入元素，就会触发扩容。不同编译器的实现有所不同：

• GCC (Linux)：通常采用 2 倍 扩容。
• MSVC (Windows)：通常采用 1.5 倍 扩容。

2. reserve vs resize

• reserve：只开辟空间，不影响 size。就像预订餐厅位子，位子给你留好了，但还没人坐。如果你知道要插入 1000 个元素，提前 reserve(1000) 可以避免频繁触发'重新分配 + 数据搬移'。
• resize：开辟空间 + 初始化 + 影响 size。不仅订了位子，还直接安排了'假人'坐进去。

建议：如果想优化性能避免多次插入导致的频繁搬家，用 reserve；如果想立刻操作这些元素或改变容器长度，用 resize。

5. 增删查改

示例代码与讲解

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class VectorDemo {
private:
    vector<int> _v;
public:
    VectorDemo() {}

    void initData() {
        _v.push_back(10); _v.push_back(20); _v.push_back(30);
        cout << "[初始化] 已手动添加 10, 20, 30" << endl;
    }

    void addElements() {
        _v.push_back(40);
        _v.insert(_v.begin() + 1, 15);
        cout << "[增] 执行完毕" << endl;
    }

    void removeElements() {
        if (!_v.empty()) {
            _v.pop_back();
            _v.erase(_v.begin() + 1);
            cout << "[删] 执行完毕" << endl;
        }
    }

    void findAndAccess() {
        cout << "[查] 索引 1 的元素为：" << _v[1] << endl;
        auto it = find(_v.begin(), _v.end(), 20);
        if (it != _v.end()) {
            cout << "[查] 找到 20，索引为：" << distance(_v.begin(), it) << endl;
        }
    }

    void modifyElement(int index, int newVal) {
        if (index < _v.size()) {
            _v[index] = newVal;
            cout << "[改] 将索引" << index << "修改为" << newVal << endl;
        }
    }

    void swapData(vector<int>& other) {
        _v.swap(other);
        cout << "[换] 数据空间已交换" << endl;
    }

    void display() const {
        cout << "当前容器内容：";
        if (_v.empty()) cout << "(空)";
        for (int x : _v) cout << x << " ";
        cout << "\n" << endl;
    }
};

int main() {
    VectorDemo demo;
    demo.initData();
    demo.display();

    demo.addElements();
    demo.display();

    demo.findAndAccess();
    demo.modifyElement(0, 100);
    demo.display();

    demo.removeElements();
    demo.display();

    vector<int> target = {1, 2, 3};
    demo.swapData(target);
    demo.display();

    return 0;
}

6. 在线 OJ 算法题

以下是一些经典的 LeetCode 题目，适合练习 vector 的使用：

• 只出现一次的数字：考察位运算与容器结合。
• 杨辉三角：考察二维数据结构构建。
• 删除有序数组中的重复项：考察双指针与原地修改。

7. 底层原理与模拟实现

7.1 底层原理

在主流的 STL 实现（如 GCC 的 libstdc++）中，vector 的核心状态仅仅由 三个指针 来维护：

template<class T, class Alloc = alloc>
class vector {
protected:
    iterator start;           // 指向目前使用空间的头部
    iterator finish;          // 指向目前使用空间的尾部（最后一个元素的下一个位置）
    iterator end_of_storage;  // 指向目前可用容量的尾部
};

借助这三个核心指针，vector 能够轻松计算出当前的状态：

• 当前元素个数（size）：finish - start
• 当前最大容量（capacity）：end_of_storage - start
• 是否为空（empty）：start == finish

核心要点：vector 的底层就是一段连续的线性内存空间。start 和 finish 之间是已经被初始化的有效数据，而 finish 到 end_of_storage 之间则是备用的未初始化内存。

7.2 动态扩容机制

当空间不足以容纳新元素时，vector 必须经历一次痛苦的'搬家'过程：

1. 开辟新空间：在内存中寻找一块更大的连续空间。
2. 数据迁移：将旧空间里的数据 拷贝（或移动） 到新空间中。
3. 释放旧空间：销毁旧空间上的对象，并把旧内存归还给操作系统。
4. 更新指针：将 start、finish、end_of_storage 指向新空间。

为什么是 1.5 倍或 2 倍？如果是每次增加固定大小，均摊时间复杂度会退化为 O(n)。而采用按比例（几何级数）增长，插入操作的均摊时间复杂度可以被平摊为 O(1)。

7.3 模拟实现

#include <iostream>
#include <algorithm>
#include <assert.h>
using namespace std;

template<class T>
class my_vector {
public:
    typedef T* iterator;

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

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

    size_t size() const { return _finish - _start; }
    size_t capacity() const { return _end_of_storage - _start; }
    iterator begin() { return _start; }
    iterator end() { return _finish; }
    T& operator[](size_t i) { return _start[i]; }

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

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

    iterator insert(iterator pos, const T& x) {
        if (_finish == _end_of_storage) {
            size_t len = pos - _start;
            reserve(capacity() == 0 ? 4 : capacity() * 2);
            pos = _start + len; // 解决迭代器失效
        }
        for (iterator it = _finish; it > pos; --it) {
            *it = *(it - 1);
        }
        *pos = x;
        ++_finish;
        return pos;
    }

    iterator erase(iterator pos) {
        for (iterator it = pos + 1; it < _finish; ++it) {
            *(it - 1) = *it;
        }
        --_finish;
        return pos;
    }

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

int main() {
    my_vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.insert(v.begin() + 1, 15);
    v.erase(v.begin() + 2);
    cout << "Vector contents: ";
    for (auto e : v) cout << e << " ";
    cout << "\nSize: " << v.size() << ", Capacity: " << v.capacity() << endl;
    return 0;
}

8. 动态二维数组

在 C++ 中，使用 std::vector 来构建动态二维数组是非常主流且安全的做法。相比于传统的 C 语言风格指针，它能够自动管理内存。

8.1 核心结构与内存布局

vector<vector<int>> 的本质是'容器的容器'。它在内存中并不是一块完整连续的矩阵。

• 外层 vector：是一个一维数组，里面存储的是内层 vector 的控制结构。
• 内层 vector：代表每一行。每一行各自在堆区开辟一块连续的内存空间。

核心推论：因为每一行是独立分配的，所以二维 vector 完全支持锯齿数组，即每一行的列数可以完全不同。

8.2 创建与初始化方式

① 创建空的二维数组

vector<vector<int>> matrix;

② 指定行数和列数（最常用）

int M = 3; // 行数
int N = 4; // 列数
// 创建一个 3 行 4 列 的二维数组，所有元素默认初始化为 0
vector<vector<int>> matrix(M, vector<int>(N, 0));

③ 使用初始化列表

vector<vector<int>> matrix = {{1, 2, 3}, {4, 5}, {6, 7, 8, 9}};

8.3 动态调整与访问

• 添加新的一行：matrix.push_back(newRow);
• 在已有行中添加新元素：matrix[0].push_back(40);
• 访问元素：matrix[1][2] 或 matrix.at(1).at(2)（带边界检查）。
• 遍历：推荐使用 C++11 范围 for 循环。

for (const auto& row : matrix) {
    for (int val : row) {
        cout << val << " ";
    }
    cout << endl;
}

8.4 函数参数传递

将二维 vector 传递给函数时，切记要使用引用传递，否则会触发整个二维数组的深度拷贝，极其消耗性能。

void printMatrix(const vector<vector<int>>& mat) { /* ... */ }
void modifyMatrix(vector<vector<int>>& mat) { /* ... */ }

9. 迭代器失效问题

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了。

对于 vector 可能会导致其迭代器失效的操作有：

1. 会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back 等。
2. 指定位置元素的删除操作 erase。

9.1 常见错误示范

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> vec = {1, 2, 3, 3, 4, 5};
    // 试图删除所有的 3
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        if (*it == 3) {
            vec.erase(it); // 🚨 灾难发生！
            // erase 之后，it 已经失效。
            // 循环末尾还要执行 ++it，对失效的迭代器进行 ++ 操作会导致程序直接崩溃。
        }
    }
    return 0;
}

9.2 正确示范

erase() 函数的设计非常巧妙，它在删除元素后，会返回一个指向被删除元素下一个位置的全新且有效的迭代器。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> vec = {1, 2, 3, 3, 4, 5};
    // 注意：这里的 for 循环去掉了第三个部分的 ++it
    for (auto it = vec.begin(); it != vec.end(); ) {
        if (*it == 3) {
            // ✅ 核心操作：重新赋值！
            // erase 删除了当前的 3，并返回指向下一个元素的有效迭代器，覆盖掉失效的 it。
            it = vec.erase(it);
        } else {
            // 只有在没有删除元素时，才手动移动迭代器
            ++it;
        }
    }
    return 0;
}

10. memcpy 引起的浅拷贝问题

使用 memcpy 进行的拷贝，以下代码会发生什么问题？

int main() {
    vector<string> v;
    v.push_back("1111");
    v.push_back("2222");
    v.push_back("3333");
    return 0;
}

深度原因分析

memcpy 的功能是按字节拷贝。

1. 扩容前（旧空间）：vector 内部存储了 3 个 string 对象。每个 string 对象内部都有一个指针指向堆上的字符数据。
2. 执行 memcpy 拷贝：把旧空间里 string 对象的字节直接复制到新空间。这意味着：新空间里 string 对象的 _str 指针指向的地址，和旧空间里一模一样。
3. 释放旧空间（核心死穴）：扩容逻辑中会调用 delete[] _start。这会触发旧空间里每个 string 对象的析构函数，执行 delete[] _str。
   • 结果：新空间里的 string 对象现在全是指向已释放内存的野指针！
4. 再次访问或析构：当 main 函数结束，新空间的 vector 析构时，会再次对那些已经被释放过的地址调用 delete[]。
   • 结论：触发 Double Free（两次释放同一块内存），程序直接挂掉。

因此，对于包含指针成员的类（如 string），严禁使用 memcpy 进行拷贝，应依赖编译器生成的拷贝构造函数或显式调用 copy 算法。