C++ vector 容器：底层原理、扩容机制与实战用法详解

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

vector 迭代器的使用

代码示例

#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) {
        // 这里的 ++rit 实际上是让迭代器在内存中'向左'移动
        cout << *rit << " ";
    }
    cout << endl;

    // --- 实用技巧：获取最后一个元素 ---
    // 除了 v.back()，你也可以用 *v.rbegin()
    cout << "最后一个元素是：" << *v.rbegin() << endl;

    return 0;
}

vector 的容量增长问题

注意事项

1. 增容倍数：VS (1.5 倍) vs g++ (2 倍)

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

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:
    // 1. 无参构造函数
    VectorDemo() {}

    // 2. 提供一个手动初始化的方法
    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 在线算法题参考

在实际开发或面试中，vector 常配合算法题目出现。以下是几个经典场景：

1. 只出现一次的数字：利用异或运算或哈希思想结合 vector 统计。
2. 杨辉三角：典型的二维数据结构构建问题。
3. 删除有序数组中的重复项：考察双指针与 vector 的 erase 操作。

vector 底层原理与模拟实现

底层原理

很多人以为 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 之间则是备用的未初始化内存。

动态扩容机制

既然底层是连续内存，如果备用空间（finish == end_of_storage）用完了，我们还能继续塞数据吗？答案是能，这就引出了 vector 最核心的机制：动态扩容。

• 扩容的四个步骤

当空间不足以容纳新元素时，vector 并不能直接在原内存后面'强行'拓展（因为后面的内存可能已经被其他程序占用了）。它必须经历一次痛苦的'搬家'过程：

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

• 扩容因子：1.5 倍 还是 2 倍？

新开辟的空间到底该有多大？这就是著名的'扩容因子'问题。不同编译器的实现有所不同：

• GCC (Linux) 体系：通常采用 2 倍 扩容。
• MSVC (Windows) 体系：通常采用 1.5 倍 扩容。
• 为什么是 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); // 在 20 前面插入 15
    v.erase(v.begin() + 2);      // 删除 20

    cout << "Vector contents: ";
    for (auto e : v) cout << e << " "; // 10 15 30
    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 的方法：

① 创建空的二维数组

常用于一开始不知道行数和列数，需要后续通过 push_back 动态添加的场景。

#include <vector>
using namespace std;
vector<vector<int>> matrix;

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

如果已经知道具体的行数 M 和列数 N，可以在创建时直接分配好空间，并赋予初始值。

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

语法解析： 外层 vector 的大小为 M，它的每一个元素被初始化为一个大小为 N、元素值为 0 的一维 vector<int>。

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

如果在定义时就已经确定了具体数据：

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

动态调整大小与插入数据

vector 最强大的地方在于它的动态扩容能力。

① 添加新的一行

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

② 在已有行中添加新元素

// 假设 matrix 至少有 1 行
// 在第 0 行的末尾追加一个元素 40
matrix[0].push_back(40);

③ 动态调整矩阵尺寸

// 将二维数组的行数调整为 5 行
matrix.resize(5);
// 将第 0 行的列数调整为 10 列
matrix[0].resize(10);

元素的访问与修改

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

int val = matrix[1][2]; // 获取第 1 行 第 2 列的元素
matrix[1][2] = 99;      // 修改该元素

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

如果索引越界，at() 会抛出 std::out_of_range 异常，非常适合调试代码。

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

遍历二维数组的高效方法

① C++11 范围 for 循环（最推荐，代码最简洁）

如果不需要知道元素的行号和列号，强烈建议使用此方法。

// 注意：外层循环使用 const auto& 可以避免拷贝一整行数据，提升性能
for (const auto& row : matrix) {
    for (int val : row) {
        cout << val << " ";
    }
    cout << endl;
}

② 传统的索引遍历（适用于需要知道具体坐标 i, j 的场景）

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，迭代器就是原生态指针 T*。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃。

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

1. 会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back 等。

   #include <iostream>
   using namespace std;
   #include <vector>
   int main() {
       vector<int> v{1, 2, 3, 4, 5, 6};
       auto it = v.begin();
       // 给 vector 重新赋值，可能会引起底层容量改变
       v.assign(100, 8);
       /* 出错原因：以上操作，都有可能会导致 vector 扩容，也就是说 vector 底层原理旧空间被释放掉，
          而在打印时，it 还使用的是释放之间的旧空间，在对 it 迭代器操作时，实际操作的是一块 已经被释放的空间，而引起代码运行时崩溃。
          解决方式：在以上操作完成之后，如果想要继续通过迭代器操作 vector 中的元素，只需给 it 重新赋值即可。 */
       while (it != v.end()) {
           cout << *it << " ";
           ++it;
       }
       cout << endl;
       return 0;
   }
   

2. 指定位置元素的删除操作 erase

   #include <iostream>
   using namespace std;
   #include <vector>
   #include <algorithm>
   int main() {
       int a[] = {1, 2, 3, 4};
       vector<int> v(a, a + sizeof(a) / sizeof(int));
       // 使用 find 查找 3 所在位置的 iterator
       vector<int>::iterator pos = find(v.begin(), v.end(), 3);
       // 删除 pos 位置的数据，导致 pos 迭代器失效
       v.erase(pos);
       // 此处会导致非法访问
       cout << *pos << endl;
       return 0;
   }
   

   erase 删除 pos 位置元素后，pos 位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果 pos 刚好是最后一个元素，删完之后 pos 刚好是 end 的位置，而 end 位置是没有元素的，那么 pos 就失效了。因此删除 vector 中任意位置上元素时，认为该位置迭代器失效了。

   以下代码的功能是删除 vector 中所有的偶数，请问哪个代码是正确的，为什么？

   // ❌ 错误写法
   #include <iostream>
   using namespace std;
   #include <vector>
   int main() {
       vector<int> v{1, 2, 3, 4};
       auto it = v.begin();
       while (it != v.end()) {
           if (*it % 2 == 0) v.erase(it);
           ++it;
       }
       return 0;
   }
   
   // ✅ 正确写法
   #include <iostream>
   using namespace std;
   #include <vector>
   int main() {
       vector<int> v{1, 2, 3, 4};
       auto it = v.begin();
       while (it != v.end()) {
           if (*it % 2 == 0) it = v.erase(it);
           else ++it;
       }
       return 0;
   }
   

   第二个代码块采用了标准且安全的写法：

   • 利用返回值更新：vector::erase 会返回一个指向被删除元素之后那个元素的新迭代器。通过 it = v.erase(it)，我们让 it 重新获得了合法的身份，指向了新搬移过来的元素。
   • 分情况处理：如果删除了，it 已经指向了下一个待检查的元素；如果没有删除，才手动执行 ++it。
   • 边界安全：即使删除了最后一个元素，erase 也会返回 v.end()，循环条件依然能正确识别并退出。

迭代器失效解决办法

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

❌ 错误示范（经典的崩溃代码）

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

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

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;
        }
    }
    // 打印结果验证：输出 1 2 4 5
    for (int val : vec) cout << val << " ";
    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 对象内部都有一个指针（比如 char* _str）指向堆上的字符数据（如 "1111"）
2. 执行 memcpy 拷贝：
   • memcpy 把旧空间里 string 对象的字节直接复制到新空间。这意味着：新空间里 string 对象的 _str 指针指向的地址，和旧空间里一模一样。
3. 释放旧空间（核心死穴）：
   • 扩容逻辑中会调用 delete[] _start。这会触发旧空间里每个 string 对象的析构函数。
     • 旧空间的 string 析构了，执行了 delete[] _str。
     • 结果：新空间里的 string 对象现在全是指向已释放内存的野指针！
4. 再次访问或析构：
   • 当 main 函数结束，新空间的 vector 析构时，会再次对那些已经被释放过的地址调用 delete[]。
   • 结论：触发 Double Free（两次释放同一块内存），程序直接挂掉。

⚠️ 警告： 对于包含指针成员的类（如 string, vector 等），严禁使用 memcpy 进行拷贝，务必使用拷贝构造函数或赋值运算符。