C++ Vector 容器：底层原理、核心用法与实战指南

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

vector iterator 的使用

示例代码与详细讲解

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

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

    // 反向遍历详解
    cout << "反向输出结果: ";
    for (auto rit = v.rbegin(); rit != v.rend(); ++rit) {
        cout << *rit << " ";
    }
    cout << endl;

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

    return 0;
}

vector 的容量增长问题

注意事项

1. 增容倍数

当 vector 的 size == capacity 时再插入元素，就会触发扩容。

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

2. reserve：只开辟空间，不影响 size

reserve 就像是预订餐厅位子，位子给你留好了，但还没人坐。 意义：如果你知道要插入 1000 个元素，提前 reserve(1000) 可以避免在插入过程中频繁触发耗时的'重新分配 + 数据搬移'操作。

3. resize：开辟空间 + 初始化 + 影响 size

resize 不仅订了位子，还直接安排了'假人'坐进去。

总结建议：

• 如果你只是想优化性能，避免多次插入导致的频繁搬家，用 reserve。
• 如果你想立刻操作这些元素（比如用下标 [] 赋值），或者想改变容器长度，用 resize。

vector 增删查改

示例代码与详细讲解

#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;
}

vector 在线 OJ 算法题

• 只出现一次的数字
• 杨辉三角
• 删除有序数组中的重复项

vector 底层原理与模拟实现

底层原理

在主流的 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 之间则是备用的未初始化内存。

动态扩容机制

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

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

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

vector 模拟实现

#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;
    }
};

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;
}

关于 vector 动态二维数组

在 C++ 中，使用 std::vector 来构建动态二维数组是非常主流且安全的做法。相比于传统的 C 语言风格指针（int** arr），它能够自动管理内存，避免了内存泄漏和繁琐的 new/delete 操作。

核心结构与内存布局

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

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

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

创建与初始化方式

① 创建空的二维数组

vector<vector<int>> matrix;

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

int M = 3; // 行数
int N = 4; // 列数
vector<vector<int>> matrix(M, vector<int>(N, 0));

③ 使用初始化列表（硬编码）

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

动态调整大小与插入数据

① 添加新的一行

vector<int> newRow = {10, 20, 30};
matrix.push_back(newRow);

② 在已有行中添加新元素

matrix[0].push_back(40);

③ 动态调整矩阵尺寸

matrix.resize(5);           // 调整行数
matrix[0].resize(10);       // 调整第 0 行列数

元素的访问与修改

① 使用 operator[] （无边界检查，速度快）

int val = matrix[1][2];
matrix[1][2] = 99;

② 使用 at() （有边界检查，更安全）

try {
    int val = matrix.at(1).at(2);
} catch (const out_of_range& e) {
    // 处理越界异常
}

遍历二维数组的高效方法

① C++11 范围 for 循环（最推荐）

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

② 传统的索引遍历

for (size_t i = 0; i < matrix.size(); ++i) {
    for (size_t j = 0; j < matrix[i].size(); ++j) {
        cout << matrix[i][j] << " ";
    }
    cout << endl;
}

函数参数传递

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

// 推荐做法：使用 const 引用传递（只读场景）
void printMatrix(const vector<vector<int>>& mat) {
    // ...
}

// 推荐做法：使用普通引用传递（需要修改数据的场景）
void modifyMatrix(vector<vector<int>>& mat) {
    // ...
}

关于 vector 的迭代器失效问题

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，继续使用已经失效的迭代器会导致程序崩溃。

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

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

经典案例：遍历时删除元素

这是引发迭代器失效最常见的灾难现场。当我们删除一个元素时，该位置之后的所有元素都会向前移动填补空缺，导致当前迭代器变成野指针。

❌ 错误示范

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

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

✅ 正确示范：使用返回值'重新赋值'

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

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

int main() {
    vector<int> vec = {1, 2, 3, 3, 4, 5};
    for (auto it = vec.begin(); it != vec.end();) {
        if (*it == 3) {
            it = vec.erase(it); // 核心操作：重新赋值！
        } else {
            ++it; // 只有在没有删除元素时，才手动移动迭代器
        }
    }
    return 0;
}

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（两次释放同一块内存），程序直接挂掉。