[c++]vector容器详解

1. 概述

• vector 是可变大小的序列容器，属于 C++ 标准模板库（STL）。

• 它封装了动态数组，元素在内存中连续存储，因此支持随机访问（下标或迭代器）。

• 位于 <vector> 头文件中，命名空间 std。

cpp

#include <vector>
using namespace std;

核心特点：

• 尾部插入/删除元素高效（摊销常数时间 O(1)）。

• 在中间或头部插入/删除元素较慢（O(n) 因为要移动元素）。

• 容器自动管理内存，当元素数量超出当前容量时，会重新分配一块更大的内存，并复制/移动原有元素。

• 提供 size()（实际元素个数）和 capacity()（已分配内存能容纳的元素个数）。

2. 声明与初始化

3. 大小与容量

cpp

vector<int> v;
v.reserve(100); // capacity >= 100, size 仍为 0
v.push_back(42); // 不会触发扩容
cout << v.size() << " " << v.capacity(); // 1 至少100
v.shrink_to_fit(); // 尝试让 capacity 收缩到 1

4. 元素访问

注意：operator[] 和 at() 都要求索引 < size，否则 operator[] 导致未定义行为，at() 抛异常。

5. 修改操作

cpp

vector<string> v;
v.push_back("hello"); // 拷贝构造
v.emplace_back(3, 'A'); // 直接构造 "AAA"（更高效）
v.insert(v.begin(), "first");
v.erase(v.begin() + 1);

6. 迭代器

vector 提供随机访问迭代器，支持 +、-、++、–、[] 等操作。

cpp

for (auto it = v.begin(); it != v.end(); ++it) cout << *it << " ";
for (int x : v) cout << x << " "; // 范围 for 更简洁
for (auto rit = v.rbegin(); rit != v.rend(); ++rit) // 反向遍历

7. 比较操作

vector 重载了关系运算符（==、!=、<、<=、>、>=），按字典序比较元素。

cpp

vector<int> a{1,2,3}, b{1,2,3}, c{1,2,4};
a == b; // true
a < c; // true (第三元素 3 < 4)

8. 内存与性能特点

8.1 扩容机制

• 当 size() == capacity() 并试图添加元素时，vector 会重新分配内存。

• 新容量通常为原容量的 1.5 倍或 2 倍（具体由库实现决定，如 GCC 2 倍，VS 1.5 倍）。

• 重新分配时，所有元素会移动（C++11 后优先移动而非拷贝）到新内存，原迭代器、引用、指针全部失效。

• 可以通过 reserve() 预分配内存避免多次扩容，提高性能。

8.2 时间效率

• 随机访问：O(1)

• 尾部插入/删除：均摊 O(1)

• 中间/头部插入/删除：O(n)

• 查找（无专用函数，需用 find 算法）：O(n)

8.3 空间效率

• 元素连续存储，无额外指针开销（对比 list），空间利用率高。

• 但 capacity 可能大于 size，造成内存浪费。可使用 shrink_to_fit() 释放多余容量（非强制）。

9. 迭代器失效问题

修改 vector 结构（增加或删除元素）可能导致迭代器、引用、指针失效：

• 插入元素（insert、push_back、emplace_back、resize）：

  • 若未触发重新分配，插入点之后的迭代器失效（但引用仍有效？严格说：push_back 不导致重新分配时，之前迭代器仍有效？C++标准：push_back 若不重新分配，则所有迭代器、引用仍有效。更细致的规则可查标准，但最好认为任何插入/删除都可能使迭代器失效。）

  • 若触发重新分配，全部失效。

• 删除元素（erase、pop_back、clear）：

  • 删除点之后的所有迭代器失效。

安全做法：在修改后重新获取迭代器，或使用下标索引而非迭代器。

10. vector 与其他容器的对比

选择建议：

• 需要频繁随机访问，且主要在尾部操作 → vector

• 需要在头尾两端高效操作 → deque

• 需要在中间频繁插入删除，不需要随机访问 → list 或 forward_list

11. 完整示例

cpp

#include <iostream>
#include <vector>
#include <algorithm> // for find, sort
using namespace std;

int main() {
// 初始化
vector<int> v = {5, 2, 8, 1, 9};

// 尾部操作
v.push_back(3);
v.pop_back();

// 访问
cout << "First: " << v.front() << ", Last: " << v.back() << endl;
cout << "Size: " << v.size() << ", Capacity: " << v.capacity() << endl;

// 插入
v.insert(v.begin() + 2, 99); // 在索引 2 前插入 99
// 删除
v.erase(v.begin() + 1); // 删除索引 1 的元素

// 排序
sort(v.begin(), v.end());

// 查找
auto it = find(v.begin(), v.end(), 8);
if (it != v.end())
cout << "Found 8 at position " << (it – v.begin()) << endl;

// 遍历
cout << "Elements: ";
for (int x : v) cout << x << " ";
cout << endl;

// 清除
v.clear();
cout << "After clear, size = " << v.size() << endl;

// 预分配内存
v.reserve(1000);
cout << "Capacity after reserve: " << v.capacity() << endl;

return 0;
}

12. 注意事项

cpp

// 删除所有值为 0 的元素（正确做法）
v.erase(remove(v.begin(), v.end(), 0), v.end());

以上是 vector 容器的核心知识。如需进一步了解底层实现或 C++11/14/17/20 的新特性（如 std::vector::erase 返回迭代器、std::pmr::vector 等），可查阅 cppreference.com – std::vector。