面试题：C++ 中 STL 容器之 vector 的常见操作

Question

请描述 C++ 中 vector 容器的特点，并举例说明如何向 vector 中添加元素、删除元素以及访问特定位置的元素。另外，阐述一下 vector 在内存管理方面是如何实现动态增长的。

Answer 1

C++ vector 容器特点

1. 动态数组：可以在运行时动态调整大小，无需预先知道确切元素数量。
2. 连续内存存储：元素在内存中连续存储，这使得通过索引访问元素非常高效，时间复杂度为 O(1)。
3. 支持随机访问：可以像普通数组一样使用 [] 操作符或者 at() 方法访问元素。
4. 内存管理自动：vector 会自动管理其内部内存，在添加或删除元素时，自动调整内存大小。

向 vector 中添加元素

1. push_back()：在 vector 的末尾添加一个元素。

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec;
    vec.push_back(10);
    vec.push_back(20);
    return 0;
}

2. insert()：在指定位置插入元素。

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {10, 20};
    vec.insert(vec.begin() + 1, 15); // 在索引1的位置插入15
    return 0;
}

删除元素

1. pop_back()：删除 vector 末尾的元素。

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {10, 20, 30};
    vec.pop_back(); // 删除30
    return 0;
}

2. erase()：删除指定位置或指定范围的元素。

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {10, 20, 30};
    vec.erase(vec.begin() + 1); // 删除索引1位置的元素（20）
    return 0;
}

访问特定位置的元素

1. 使用 [] 操作符：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {10, 20, 30};
    std::cout << vec[1] << std::endl; // 输出20
    return 0;
}

2. 使用 at() 方法：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {10, 20, 30};
    std::cout << vec.at(1) << std::endl; // 输出20，at() 会进行边界检查
    return 0;
}

vector 在内存管理方面动态增长的实现

vector 内部维护一块连续的内存空间来存储元素。当添加元素导致当前容量（capacity）不足时，vector 会重新分配内存：

1. 分配新内存：分配一块更大的内存空间，通常是当前容量的两倍（不同实现可能不同）。
2. 复制元素：将原内存中的元素复制到新的内存空间。
3. 释放旧内存：释放原来的内存空间。

这种机制使得 vector 能够在需要时动态增长，但由于重新分配内存和复制元素的开销，在频繁添加元素时可能会有性能问题。为了避免频繁的重新分配，可以使用 reserve() 方法预先分配足够的内存。例如：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec;
    vec.reserve(100); // 预先分配能容纳100个元素的空间
    for (int i = 0; i < 50; ++i) {
        vec.push_back(i);
    }
    return 0;
}

这样在添加 50 个元素时，就不会发生频繁的内存重新分配。