请解释vector容器和它的特点。

八股文_C++STL面试题 0 2

参考回答

std::vector 是 C++ 标准模板库 (STL) 中的一个动态数组容器。它的特点包括：

动态扩展：vector 会根据需要自动调整大小，因此无需手动管理内存。
连续存储：它的元素存储在连续的内存中，可以通过指针或索引随机访问，性能接近普通数组。
高效的插入与删除：在尾部插入和删除元素非常高效（时间复杂度为 (O(1))），但在中间或头部操作时会较慢（时间复杂度为 (O(n))）。
支持 STL 算法：vector 与 STL 算法（如 std::sort、std::find）无缝兼容。
元素自动初始化：新增元素时可以自动调用默认构造函数进行初始化。

详细讲解与拓展

1. 内存管理与动态扩展

vector 的动态扩展是通过分配更大的连续内存并拷贝原有数据实现的。当容量不足时，vector 会以 倍增策略 增加容量（通常是 2 倍），这会导致一定的开销。但由于倍增策略的使用，均摊时间复杂度仍然是 (O(1))。例如：

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

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

输出示例：

Size: 1, Capacity: 1
Size: 2, Capacity: 2
Size: 3, Capacity: 4
...

通过 v.capacity() 可以观察容量的倍增现象。

2. 连续存储

由于 vector 的存储是连续的，因此它可以像数组一样使用下标访问，同时支持与 C 风格数组互操作。例如：

vector<int> v = {1, 2, 3, 4};
cout << v[2] << endl;       // 输出 3
int* arr = v.data();        // 获取指向底层数组的指针
cout << arr[2] << endl;     // 输出 3

连续存储使得 vector 非常适合需要随机访问的场景，但对于需要频繁插入和删除的场景（尤其是非尾部操作），则可能性能不佳。

3. 成员函数

以下是常用成员函数及其时间复杂度：
– push_back：在尾部插入，均摊 (O(1))。
– pop_back：删除尾部元素，时间复杂度 (O(1))。
– insert：在指定位置插入，时间复杂度 (O(n))。
– erase：删除指定位置的元素，时间复杂度 (O(n))。
– resize：调整大小，可能触发元素拷贝。
– clear：清空容器，时间复杂度 (O(n))。

4. 注意事项

频繁动态扩展的代价：扩展时会重新分配内存并拷贝数据，因此建议预先使用 reserve 设置合适的容量。
迭代器失效问题：当 vector 进行插入、删除或扩展操作时，可能导致迭代器失效。例如：

vector<int> v = {1, 2, 3};
auto it = v.begin();
v.push_back(4);  // 插入新元素
cout << *it << endl;  // 未定义行为，迭代器已失效

5. 扩展：`vector` 与其他容器的对比

相较于 std::array 或 C 风格数组，vector 的大小是动态的，使用更灵活。
相较于 std::deque，vector 的内存使用更紧凑，但在频繁的头部插入删除场景中性能不如 deque。
相较于 std::list，vector 支持随机访问，但在频繁的插入删除中效率较低。

总结

std::vector 是一种动态数组，提供了灵活的内存管理和高效的尾部操作，同时保持了数组的随机访问能力。它适用于需要动态大小且以随机访问为主的场景。理解其内存管理和迭代器特性是熟练使用它的关键。