CC++ & Algorithm

vector动态数组详解

困难34
语言版本：通用
概述：就像可以自动伸缩的书包，vector是C++中最常用的动态数组，能根据需要自动变大或变小。

vector动态数组：自动伸缩的智能书包

从生活中的例子引入

想象一下，你有一个书包，里面可以装文具。刚开学时，你只带了5支笔，书包刚好装满。可是随着课程增加，你需要装更多笔和本子，书包就不够用了。你只好换一个更大的书包。过了一段时间，有些笔用完了，书包又变大了，背起来不方便。要是书包能自动变形，需要的时候变大，不需要的时候变小，那该多好！在编程世界里，vector 就是这样的“智能书包”——它是一个动态数组，可以自动调整大小，随时添加或删除元素，而不用你手动管理内存。

比如在一个班级管理系统中，学生人数经常变化，新学期有转学生进来，有人退学。如果用固定大小的数组，就得事先估算最大人数，要么浪费空间，要么不够用。而 vector 可以根据实际人数自动伸缩，非常方便。

讲解STL的原理和使用方法

什么是vector？

vector 是C++标准模板库（STL）中的一个序列容器，它本质上是一个动态数组。你不需要预先知道元素个数，在程序运行时可以随时添加或删除元素，vector 会自动分配和释放内存。所有元素在内存中是连续存储的，因此可以通过索引快速访问（像普通数组一样），时间复杂度为O(1)。

内存模型：vector内部维护三个指针：起始、当前末尾、容量末尾。当元素数量超过容量时，vector会申请一块更大的内存（通常是原来的2倍），然后把所有元素复制（或移动）到新内存，再释放旧内存。这个过程称为“扩容”。扩容很耗时，但发生的次数是log级别的（因为每次翻倍），所以平均下来尾部插入仍是O(1)（均摊复杂度）。

vector的常用操作

要使用 vector，首先需要包含头文件 <vector>，并写出 std::vector<类型> 变量名; 这样的语句。

下面是一些最常用的成员函数，我按照“增删改查”的顺序给你介绍。每个函数都配一个生活小例子，让你更容易记住。

1. 添加元素

  • push_back(值) —— 在末尾添加一个元素。就像往书包里再塞一个东西，放在最上面。

    vector<int> scores;           // 空成绩列表
scores.push_back(85);         // 添加第一个成绩，就像往书包里放第一本书
scores.push_back(92);         // 再放一本

  • insert(迭代器, 值) —— 在指定位置插入一个元素。比如你想把一支笔插到书包中间，需要把后面的都往后挪一挪。这个操作比较慢，需要移动后面的所有元素。

    // 在第二个位置（索引1）前面插入100
vector<int>::iterator it = scores.begin() + 1;  // 指向第二个元素
scores.insert(it, 100);                         // 插入后，原来的第二个变成第三个

2. 删除元素

  • pop_back() —— 删除末尾的元素。就像从书包最上面拿掉一个东西，非常快。

    scores.pop_back();  // 去掉最后一个成绩

  • erase(迭代器) —— 删除指定位置的元素。删除中间的元素时，后面的元素会向前移动填补空缺，同样比较慢。

    vector<int>::iterator it = scores.begin() + 2;  // 删除第三个元素
scores.erase(it);

  • clear() —— 清空所有元素。书包被彻底倒空了。

    scores.clear();           // 所有成绩清零

3. 访问元素

  • operator[] —— 像普通数组那样通过下标访问，比如 vec[0]。不检查下标是否越界，用起来快但危险。

    int first = scores[0];    // 直接拿第一个成绩，如果越界会得到垃圾值或崩溃

  • at(索引) —— 安全访问，如果越界会抛出异常，建议新手多用它。

    int second = scores.at(1);  // 如果索引1不存在，程序会报错，而不是悄悄出错

  • front() —— 返回第一个元素。

  • back() —— 返回最后一个元素。

4. 获取状态

  • size() —— 当前元素个数。你现在书包里到底装了多少东西？

    int count = scores.size();  // 比如输出4，表示有4个成绩

  • capacity() —— 当前已分配的内存能容纳多少个元素。相当于书包的“最大容量”，但里面的东西可能没装够。当 size 超过 capacity 时，vector 会重新分配更大的内存（通常是原来容量的2倍），然后把所有元素复制过去，这个过程比较耗时。

    cout << "容量：" << scores.capacity() << endl;  // 可能比size大

  • empty() —— 判断是否为空。

    if (scores.empty()) {
    cout << "书包是空的" << endl;
}

5. 调整大小

  • resize(新大小) —— 手动改变元素个数。如果新大小比原来大，会用默认值填充；如果小，会截断多余的元素。

    scores.resize(10);    // 原来有4个，现在扩大成10个，新增的6个都是0

  • reserve(新容量) —— 预先分配内存，避免频繁扩容。比如你知道最终要装10000个元素，可以先 vec.reserve(10000)，这样只扩容一次，提升性能。

    scores.reserve(100);  // 告诉书包：“我要装100本书，你直接准备好100个格子”

时间复杂度总结

操作时间复杂度说明
末尾添加/删除（push_back/pop_back）均摊O(1)偶尔触发扩容时O(n)，但平均下来是常数
中间插入/删除（insert/erase）O(n)需要移动后续所有元素
随机访问（[ ] / at）O(1)连续存储的优势
查找（按值）O(n)需要遍历

新手容易犯的错误

1. 越界访问（下标越界）

vector<int> v = {1, 2, 3};
cout << v[100];          // 危险！不报错，输出垃圾值或崩溃
cout << v.at(100);       // 安全！会抛出std::out_of_range异常

解决方法：优先使用 at()，或先检查 size() 再使用 []。

2. 迭代器失效

vector<int> v = {1, 2, 3};
auto it = v.begin();     // 指向第一个元素
v.push_back(4);          // 可能引发扩容，迭代器it失效！
cout << *it;             // 未定义行为（可能崩溃）
v.insert(v.begin(), 0);  // insert也可能导致迭代器失效

解决方法：在可能改变容量的操作之后，重新获取迭代器：

v.push_back(4);
it = v.begin();          // 重新获取

3. 混淆 reserve 和 resize

  • reserve 只增加容量，不改变元素个数。调用后 size 不变，capacity 变大。
  • resize 改变元素个数，可能会新增或删除元素。新增的元素用默认值填充。
vector<int> v = {1, 2, 3};
v.reserve(10);           // size=3, capacity=10
cout << v[5];            // 错误！索引5不存在，[5]越界
v.resize(10);            // size=10, 新增7个0
cout << v[5];            // 正确，输出0

4. 用 [] 赋值但越界

vector<int> v;           // size=0
v[0] = 10;               // 错误！v[0]没有分配内存，越界

正确做法：先 push_back 或用 resize 分配空间。

5. 在遍历中删除元素导致迭代器失效

vector<int> v = {1, 2, 3, 4};
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it == 2) {
        v.erase(it);     // 删除后it失效，继续++it会出问题
    }
}

解决方法：erase返回下一个有效迭代器：

for (auto it = v.begin(); it != v.end(); ) {
    if (*it == 2) {
        it = v.erase(it);   // it指向被删除元素的下一个
    } else {
        ++it;
    }
}

给出C++完整代码实现

下面是一个C++程序，演示了 vector 的各种用法，并带有详细注释：

#include <iostream>
#include <vector>  // 使用vector需要包含这个头文件
using namespace std;

int main() {
    // 1. 创建vector：存储整数的动态数组
    vector<int> scores;  // 一开始是一个空的书包

    // 2. 尾部添加元素
    scores.push_back(85);  // 加入第一个成绩
    scores.push_back(92);
    scores.push_back(78);
    scores.push_back(95);
    cout << "当前人数: " << scores.size() << endl;      // 输出: 4
    cout << "当前容量: " << scores.capacity() << endl;  // 容量可能大于4

    // 3. 随机访问（使用[]，不检查越界）
    cout << "第一名成绩: " << scores[0] << endl;  // 85

    // 4. 使用at安全访问
    cout << "第二名成绩: " << scores.at(1) << endl; // 92

    // 5. 遍历所有元素（基于范围的for循环，C++11起支持）
    cout << "所有成绩: ";
    for (int s : scores) {
        cout << s << " ";
    }
    cout << endl;

    // 6. 在中间位置插入元素（第2个位置插入100）
    // 注意：scores.begin()指向第一个，+2表示第三个元素前（索引2）
    vector<int>::iterator it = scores.begin() + 2;  // 指向第三个元素（索引2）
    scores.insert(it, 100);  // 在第三个元素前插入，原来的第三个变成第四个
    // 现在顺序: 85, 92, 100, 78, 95
    cout << "插入后: ";
    for (int s : scores) {
        cout << s << " ";
    }
    cout << endl;

    // 7. 删除中间的某个元素（删除100）
    it = scores.begin() + 2;  // 现在索引2是100
    scores.erase(it);
    cout << "删除后: ";
    for (int s : scores) {
        cout << s << " ";
    }
    cout << endl;

    // 8. 尾部删除
    scores.pop_back();  // 删除最后一个95
    cout << "pop_back后: ";
    for (int s : scores) cout << s << " ";
    cout << endl;

    // 9. 手动扩容：reserve
    scores.reserve(100);  // 预先分配100个元素的内存，避免后续多次扩容
    cout << "reserve后容量: " << scores.capacity() << endl; // 100

    // 10. 重置大小并填充默认值
    scores.resize(10);  // 当前只有3个，扩容到10个，新增的用0填充
    cout << "resize后: ";
    for (int s : scores) cout << s << " ";
    cout << endl;
    cout << "size: " << scores.size() << ", capacity: " << scores.capacity() << endl;

    // 11. 清空
    scores.clear();
    cout << "clear后 size: " << scores.size() << ", empty? " << (scores.empty() ? "yes" : "no") << endl;

    // 12. 使用迭代器遍历
    scores.push_back(1);
    scores.push_back(2);
    scores.push_back(3);
    cout << "使用迭代器遍历: ";
    for (vector<int>::iterator it = scores.begin(); it != scores.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    return 0;
}

运行这段代码，你可以看到 vector 如何自动管理大小，以及各种操作的效果。

给出Python等价功能的代码实现

在Python中，list 就是最常用的动态数组，它和C++的 vector 功能非常相似。下面是Python的对应代码，同样带详细注释：

# Python中的list就是动态数组，用法和vector类似

# 1. 创建空列表
scores = []  # 相当于C++的vector<int> scores;

# 2. 尾部添加元素
scores.append(85)
scores.append(92)
scores.append(78)
scores.append(95)
print("当前人数:", len(scores))  # 4

# 3. 随机访问，直接用下标（越界会报错）
print("第一名成绩:", scores[0])  # 85

# 4. 使用try...except安全访问（类似at）
try:
    print("第二名成绩:", scores[1])
except IndexError as e:
    print("索引超出范围")

# 5. 遍历所有元素
print("所有成绩:", end=" ")
for s in scores:
    print(s, end=" ")
print()

# 6. 在中间位置插入元素（第2个位置，索引1前面插入100）
scores.insert(1, 100)  # insert(索引, 值) 在指定索引前插入
# 现在: 85, 100, 92, 78, 95
print("插入后:", scores)

# 7. 删除中间某个元素（删除100，通过值删除）
# scores.remove(100)  # 按值删除第一个匹配项
# 或者按索引删除，pop可以指定索引
scores.pop(1)  # 删除索引1的元素（100）
print("删除后:", scores)

# 8. 尾部删除
scores.pop()  # 删除最后一个
print("pop后:", scores)

# 9. Python的list没有reserve功能，但可以通过预先分配列表长度来减少动态扩容
# 可以先创建一个全零列表，再赋值（但通常不需要）
# 预分配示例：extended = [0] * 100 然后赋值

# 10. 重置大小并填充默认值（通过切片赋值）
scores = [0] * 10  # 创建一个包含10个0的列表
# 但原来的内容就全丢了。如果只是想改变大小而不丢失已有数据，可以用extend
# 这里我们新创建一个
print("resize后:", scores, "长度:", len(scores))

# 11. 清空
scores.clear()
print("clear后长度:", len(scores), "是否为空:", len(scores) == 0)

# 12. 使用迭代器遍历（Python的for本质就是迭代器）
scores.append(1)
scores.append(2)
scores.append(3)
print("使用迭代器遍历:", end=" ")
for it in scores:   # 这里it就是元素本身，而不是迭代器对象
    print(it, end=" ")
print()

# 如果想获得索引和值，可以用enumerate
print("带索引遍历:")
for idx, val in enumerate(scores):
    print(f"索引{idx}: {val}")

Python的 list 底层也是动态数组（在CPython中用了连续数组实现），自动管理扩容。和C++的 vector 一样，尾部插入和删除平均O(1)，中间插入删除O(n)。

总结要点和注意事项

C++ vector要点

  1. 自动扩容：当元素数量超过容量时，vector 会重新分配更大的内存（通常是2倍），然后移动所有元素，可能导致迭代器失效（指向原来内存的迭代器变无效）。
  2. 连续存储：vector 的元素在内存中是连续的，所以支持高效随机访问，也可以传给C风格数组函数（通过 data() 获取指针）。
  3. 推荐使用at：新手容易忽略越界，使用 at() 可以在越界时抛出异常，更容易调试。
  4. 预先reserve：如果你知道最终大概要多少元素，提前 reserve 可以避免多次扩容，提升性能。
  5. 迭代器失效：在进行插入、删除等操作后，原先保存的迭代器可能会失效，需要重新获取。

Python list要点

  1. 类似 vector：Python的 list 是高级的动态数组，几乎所有特性都和 vector 相同，但自动内存管理更“透明”。
  2. 没有capacity概念：Python不提供 capacity 方法，你无法控制底层容量。
  3. 类型可以不同：Python的 list 可以同时存放不同类型的数据，这是和C++ vector 的主要区别之一（C++必须指定类型）。
  4. pop和append：尾部操作非常高效，但中间插入和删除性能较差（和C++一样是O(n)）。
  5. 安全访问：超出索引会直接抛出 IndexError，不需要像C++那样调用 at。

应用场景

当你需要频繁在末尾添加或删除元素，并且偶尔随机访问时，vector（或Python的 list）是首选。如果需要在中间频繁插入和删除，可以考虑 list（C++的双向链表）或 deque（双端队列）。

相关指引

  • C++其他常用容器：list（双向链表，中间插入快，随机访问慢）、deque（双端队列，头尾插入都快）、map/unordered_map（关联容器，适合按键查找）。
  • Python其他序列：tuple（不可变元组）、deque（双端队列，来自collections模块）。
  • 内存管理：可以进一步了解C++的 new/delete 和智能指针，理解vector自动管理内存的好处。

现在你已经掌握了 vector 这个“智能书包”的使用方法，快用它去解决实际问题吧！

例题精讲

1单选题

关于C++中vector的size()和capacity()函数，以下说法正确的是？

Asize()返回当前存储的元素个数，capacity()返回当前分配的内存可容纳的元素个数
Bsize()和capacity()返回的值总是相等的
Csize()返回分配的内存大小（字节数），capacity()返回元素个数
Dsize()返回的是vector的容量，capacity()返回的是元素个数
2单选题

关于vector的resize()和reserve()，下列说法正确的是？

Aresize()可以改变vector的大小，并可能用默认值初始化新元素
Breserve()可以改变vector的大小，增加或减少容量
Cresize()只会改变size，不会影响capacity
Dreserve()会改变size，使其等于capacity
3判断题

当使用push_back()向vector添加元素导致容量不足时，vector会重新分配更大的内存块，并将所有元素移动到新内存中。这个过程会导致之前所有指向vector元素的迭代器、指针和引用失效。

4填空题
以下代码使用vector存储0到4，请填写空白处补全push_back操作。

vector<int> vec;
for (int i = 0; i < 5; ++i) {
    vec.___(i);  // 将i添加到vector末尾
}
for (int num : vec) {
    cout << num << " ";
}
5填空题
以下代码用于删除vector中所有值为val的元素，请在空白处填入正确的函数调用。

vector<int> vec = {1, 2, 3, 2, 4, 2};
int val = 2;
for (auto it = vec.begin(); it != vec.end(); ) {
    if (*it == val) {
        it = vec.___(it);  // 删除当前元素并获取下一个迭代器
    } else {
        ++it;
    }
}