深入理解 C++ 中的 std::vector

在 C++ 标准库中，std::vector 是一个动态数组类。相较于静态数组，std::vector 能够根据需求自动扩展或缩小，非常适合在算法竞赛中使用。在蓝桥杯比赛中，std::vector 常用于存储动态数据、处理数组扩展问题，甚至可以代替二维数组以简化代码。

1. std::vector 的基础概念

std::vector 是一种动态数组容器，可以根据需要动态调整大小。其底层实现是连续的内存块，能够支持随机访问（即通过索引访问元素）。与普通数组相比，它不仅支持增删操作，还能自动扩展容量，从而更灵活。
std::vector 的内部机制
std::vector 的动态扩展机制基于 容量（capacity） 的概念。vector 会在内部维护一个预分配的内存块以存储元素。当容量不足时，vector 会自动扩展为原来的 1.5 倍或 2 倍，从而减少频繁分配内存的开销。

2. 创建 std::vector

在创建 std::vector 时，可以通过不同的方式初始化它：

3. 动态扩展和容量管理

3.1 动态扩展

当使用 push_back() 向 vector 中添加元素时，如果容量不够，vector 会自动分配更多的内存，重新拷贝现有元素，从而扩展容量。

std::vector<int> vec;
for (int i = 0; i < 10; i++) {
    vec.push_back(i);
    std::cout << "Size: " << vec.size() << ", Capacity: " << vec.capacity() << std::endl;
}

3.2 手动管理容量

如果预先知道 vector 大小，可以使用 reserve() 函数来分配内存，从而避免多次扩展的性能开销：

std::vector<int> vec;
vec.reserve(10); // 预分配容量为10
for (int i = 0; i < 10; i++) {
    vec.push_back(i);
}

4. 常用操作和方法

4.1添加和删除元素

• push_back(): 在末尾添加元素
• pop_back(): 删除末尾元素
• insert(): 在指定位置插入元素
• erase(): 删除指定位置的元素
• clear(): 清空所有元素

std::vector<int> vec = {1, 2, 3, 4, 5};
vec.push_back(6); // {1, 2, 3, 4, 5, 6}
vec.pop_back();   // {1, 2, 3, 4, 5}
vec.insert(vec.begin() + 2, 10); // {1, 2, 10, 3, 4, 5}
vec.erase(vec.begin() + 2); // {1, 2, 3, 4, 5}
vec.clear(); // 清空所有元素，size 为 0

4.2 访问元素

• 随机访问：可以使用索引访问 vector 中的元素。
• 边界检查：使用 at() 方法可以提供越界检查，防止非法访问。

std::vector<int> vec = {1, 2, 3, 4, 5};
std::cout << vec[0] << std::endl;   // 输出: 1
std::cout << vec.at(1) << std::endl; // 输出: 2，带边界检查

4.3 迭代器遍历

可以使用迭代器来遍历 vector。使用 begin() 和 end() 可以获取 vector 的首尾位置。

std::vector<int> vec = {1, 2, 3, 4, 5};
for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::cout << *it << " ";
}
std::cout << std::endl;

5. std::vector 在竞赛中的应用场景

5.1 动态数据存储

在算法竞赛中，我们常常需要存储未知数量的数据。例如，读取输入数据时，std::vector 可以轻松地进行动态扩展：

int n;
std::cin >> n;
std::vector<int> data;

for (int i = 0; i < n; i++) {
    int x;
    std::cin >> x;
    data.push_back(x);
}

// 输出所有数据
for (int x : data) {
    std::cout << x << " ";
}

5.2 模拟栈结构

std::vector 提供的 push_back() 和 pop_back() 操作，与栈的数据结构操作类似，因此可以用 vector 模拟栈来解决括号匹配等问题。

std::string s = "((()))";
std::vector<char> stack;

for (char c : s) {
    if (c == '(') {
        stack.push_back(c);
    } else if (!stack.empty() && stack.back() == '(') {
        stack.pop_back();
    }
}

if (stack.empty()) {
    std::cout << "匹配成功！" << std::endl;
} else {
    std::cout << "匹配失败！" << std::endl;
}

5.3 模拟二维数组

在图的算法中，可以用 std::vector<std::vector> 来表示邻接矩阵。以下是一个示例：

int n = 5; // 顶点个数
std::vector<std::vector<int>> graph(n, std::vector<int>(n, 0));

// 添加边
graph[0][1] = 1;
graph[1][2] = 1;
graph[2][3] = 1;
graph[3][4] = 1;

// 输出邻接矩阵
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        std::cout << graph[i][j] << " ";
    }
    std::cout << std::endl;
}

6.注意事项

• 性能优化：频繁的动态扩展可能会导致性能下降。可以在已知大小的情况下提前 reserve() 容量。
• 边界检查：at() 提供了安全访问，但如果对性能要求高，可以直接使用 [] 操作符。
• 二维 vector：在图的算法中，尽量选择合适的数据结构以提高代码效率。