C++ STL 容器 vector 的高效使用技巧
一、vector 基础概述
1.1 vector 是什么
C++ 标准模板库（STL）中的 vector 是一种动态数组容器，它能够在运行时根据需要动态调整自身大小。与传统的静态数组相比，vector 提供了更多的灵活性和安全性。vector 会自动管理内存，当元素添加或删除时，它会自动调整内部数组的大小。这种自动内存管理机制使得程序员无需手动处理内存分配和释放，从而减少了内存泄漏等问题。
1.2 vector 的基本操作
- 初始化：
- 可以使用默认构造函数创建一个空的
vector：
- 可以使用默认构造函数创建一个空的
#include <vector>
int main() {
std::vector<int> v;
return 0;
}
- 也可以指定初始大小和值进行初始化：
#include <vector>
int main() {
std::vector<int> v(5, 10); // 创建一个大小为 5，每个元素初始值为 10 的 vector
return 0;
}
- 还可以通过其他容器进行初始化：
#include <vector>
#include <list>
int main() {
std::list<int> l = {1, 2, 3};
std::vector<int> v(l.begin(), l.end());
return 0;
}
- 添加元素：
push_back方法用于在vector的末尾添加一个元素：
#include <vector>
#include <iostream>
int main() {
std::vector<int> v;
v.push_back(1);
v.push_back(2);
for (int i : v) {
std::cout << i << " ";
}
return 0;
}
emplace_back方法则是在vector的末尾直接构造一个元素，避免了临时对象的创建，效率更高：
#include <vector>
#include <iostream>
#include <string>
int main() {
std::vector<std::string> v;
v.emplace_back("hello"); // 直接构造字符串对象
for (const std::string& s : v) {
std::cout << s << " ";
}
return 0;
}
- 访问元素：
- 可以使用下标操作符
[]来访问vector中的元素，这种方式不会进行边界检查：
- 可以使用下标操作符
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {1, 2, 3};
std::cout << v[1] << std::endl; // 输出 2
return 0;
}
at方法也用于访问元素，但它会进行边界检查，如果越界会抛出std::out_of_range异常：
#include <vector>
#include <iostream>
#include <exception>
int main() {
std::vector<int> v = {1, 2, 3};
try {
std::cout << v.at(1) << std::endl; // 输出 2
std::cout << v.at(10) << std::endl; // 抛出异常
} catch (const std::out_of_range& e) {
std::cerr << "Out of range exception: " << e.what() << std::endl;
}
return 0;
}
- 删除元素：
pop_back方法用于删除vector末尾的元素：
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {1, 2, 3};
v.pop_back();
for (int i : v) {
std::cout << i << " ";
}
return 0;
}
erase方法可以删除指定位置或指定范围的元素：
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
v.erase(v.begin() + 2); // 删除索引为 2 的元素（即 3）
for (int i : v) {
std::cout << i << " ";
}
std::cout << std::endl;
v.erase(v.begin(), v.begin() + 2); // 删除前两个元素
for (int i : v) {
std::cout << i << " ";
}
return 0;
}
- 获取大小和容量：
size方法返回vector中当前元素的个数：
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {1, 2, 3};
std::cout << "Size: " << v.size() << std::endl;
return 0;
}
capacity方法返回vector当前分配的内存大小，即最多能容纳多少个元素：
#include <vector>
#include <iostream>
int main() {
std::vector<int> v;
for (int i = 0; i < 10; ++i) {
v.push_back(i);
std::cout << "Size: " << v.size() << ", Capacity: " << v.capacity() << std::endl;
}
return 0;
}
二、vector 的内存管理机制
2.1 动态内存分配
vector 内部使用连续的内存空间来存储元素。当 vector 中添加元素时，如果当前的容量不足以容纳新元素，vector 会进行内存重新分配。它会申请一块更大的内存空间，将原来的元素复制到新的空间，然后释放旧的内存空间。这种内存重新分配的操作代价相对较高，因为涉及到内存的申请、复制和释放。
例如，假设我们有一个初始容量为 4 的 vector，当添加第 5 个元素时，vector 会重新分配内存，可能将容量扩展到 8（具体的扩展策略因编译器而异）。
#include <vector>
#include <iostream>
int main() {
std::vector<int> v;
v.reserve(4); // 预先分配容量为 4 的内存
for (int i = 0; i < 5; ++i) {
v.push_back(i);
std::cout << "Size: " << v.size() << ", Capacity: " << v.capacity() << std::endl;
}
return 0;
}
在这个例子中，当添加第 5 个元素时，vector 的容量从 4 扩展到了 8。
2.2 内存扩展策略
不同的编译器对 vector 的内存扩展策略可能有所不同，但常见的策略是成倍增长。例如，当 vector 的容量不足时，它可能会将容量翻倍。这种策略可以减少内存重新分配的次数，因为如果只是每次增加固定大小的内存，可能会频繁地进行内存重新分配。
假设我们有一个 vector，初始容量为 1，按照翻倍策略，当添加第 2 个元素时，容量变为 2；添加第 3 个元素时，容量变为 4；添加第 5 个元素时，容量变为 8 等等。
2.3 内存释放
vector 在析构时会自动释放其占用的内存。但是，当 vector 的大小减小后，它并不会立即释放多余的内存。例如，我们从一个有 10 个元素的 vector 中删除 5 个元素，vector 的大小变为 5，但容量可能仍然保持为 10（或者根据实现可能有所不同，但不会立即释放到最小）。
如果我们希望释放多余的内存，可以使用 shrink_to_fit 方法（C++11 引入）：
#include <vector>
#include <iostream>
int main() {
std::vector<int> v(10, 1);
v.erase(v.begin() + 5, v.end());
std::cout << "Size: " << v.size() << ", Capacity: " << v.capacity() << std::endl;
v.shrink_to_fit();
std::cout << "Size: " << v.size() << ", Capacity: " << v.capacity() << std::endl;
return 0;
}
在这个例子中，先删除了 vector 后半部分的元素，此时 size 变为 5，capacity 可能仍然较大。调用 shrink_to_fit 后，capacity 会尝试调整到与 size 相近的大小，从而释放多余的内存。
三、高效使用 vector 的技巧
3.1 预先分配内存
在已知 vector 大致需要存储多少元素的情况下，使用 reserve 方法预先分配足够的内存可以显著提高效率。因为这样可以避免在添加元素过程中频繁的内存重新分配。
例如，假设我们要向 vector 中添加 1000 个元素：
#include <vector>
#include <iostream>
#include <chrono>
int main() {
auto start1 = std::chrono::high_resolution_clock::now();
std::vector<int> v1;
for (int i = 0; i < 1000; ++i) {
v1.push_back(i);
}
auto end1 = std::chrono::high_resolution_clock::now();
auto duration1 = std::chrono::duration_cast<std::chrono::microseconds>(end1 - start1).count();
auto start2 = std::chrono::high_resolution_clock::now();
std::vector<int> v2;
v2.reserve(1000);
for (int i = 0; i < 1000; ++i) {
v2.push_back(i);
}
auto end2 = std::chrono::high_resolution_clock::now();
auto duration2 = std::chrono::duration_cast<std::chrono::microseconds>(end2 - start2).count();
std::cout << "Without reserve: " << duration1 << " microseconds" << std::endl;
std::cout << "With reserve: " << duration2 << " microseconds" << std::endl;
return 0;
}
在这个例子中，通过 reserve 预先分配内存的 vector 在添加元素时花费的时间明显更少，因为避免了多次内存重新分配。
3.2 使用 emplace_back 代替 push_back
当 vector 存储的是类对象时，emplace_back 可以直接在 vector 的末尾构造对象，而 push_back 可能需要先构造一个临时对象，然后再将其复制或移动到 vector 中。
例如，我们有一个简单的类 MyClass：
#include <vector>
#include <iostream>
class MyClass {
public:
int data;
MyClass(int d) : data(d) {
std::cout << "Constructor: " << data << std::endl;
}
MyClass(const MyClass& other) : data(other.data) {
std::cout << "Copy Constructor: " << data << std::endl;
}
MyClass(MyClass&& other) noexcept : data(other.data) {
other.data = 0;
std::cout << "Move Constructor: " << data << std::endl;
}
~MyClass() {
std::cout << "Destructor: " << data << std::endl;
}
};
int main() {
std::vector<MyClass> v1;
MyClass obj(10);
v1.push_back(obj); // 可能调用复制构造函数
std::vector<MyClass> v2;
v2.emplace_back(20); // 直接构造对象
return 0;
}
在这个例子中，push_back 可能会调用复制构造函数（如果没有移动构造函数优化，在 C++11 后会优先使用移动构造函数），而 emplace_back 直接在 vector 中构造对象，减少了一次构造和复制（或移动）的开销。
3.3 避免不必要的元素删除
频繁地删除 vector 中的元素会导致性能下降，因为删除元素后，后面的元素需要向前移动。如果只是想暂时移除某个元素，可以将其标记为无效，而不是真正删除。
例如，我们有一个 vector 存储一些整数，并且希望删除值为 5 的元素：
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {1, 5, 3, 5, 5, 6};
for (auto it = v.begin(); it != v.end(); ) {
if (*it == 5) {
it = v.erase(it);
} else {
++it;
}
}
for (int i : v) {
std::cout << i << " ";
}
return 0;
}
在这个例子中，每次删除元素后，后面的元素都需要向前移动。如果我们只是标记元素无效，例如将其设为一个特殊值（假设 -1 表示无效）：
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {1, 5, 3, 5, 5, 6};
for (auto& i : v) {
if (i == 5) {
i = -1;
}
}
for (int i : v) {
if (i != -1) {
std::cout << i << " ";
}
}
return 0;
}
这样避免了频繁的元素移动，提高了效率。如果确实需要最终删除无效元素，可以在适当的时候进行一次性删除，例如使用 erase - remove 惯用法：
#include <vector>
#include <iostream>
#include <algorithm>
int main() {
std::vector<int> v = {1, 5, 3, 5, 5, 6};
for (auto& i : v) {
if (i == 5) {
i = -1;
}
}
v.erase(std::remove(v.begin(), v.end(), -1), v.end());
for (int i : v) {
std::cout << i << " ";
}
return 0;
}
3.4 正确使用迭代器
vector 的迭代器是随机访问迭代器，这意味着可以像指针一样进行算术运算。在使用迭代器时，要注意迭代器的有效性。当 vector 的大小或容量发生变化（例如添加或删除元素）时，迭代器可能会失效。
例如，在删除元素时：
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
auto it = v.begin();
v.erase(it + 2); // 删除索引为 2 的元素
// 此时 it 没有失效，因为删除的不是 it 指向的元素
std::cout << *it << std::endl; // 输出 1
v.erase(it); // 删除 it 指向的元素
// 此时 it 失效，不能再使用
// std::cout << *it << std::endl; // 这会导致未定义行为
return 0;
}
在循环中删除元素时，要特别注意迭代器的更新：
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5};
for (auto it = v.begin(); it != v.end(); ) {
if (*it % 2 == 0) {
it = v.erase(it);
} else {
++it;
}
}
for (int i : v) {
std::cout << i << " ";
}
return 0;
}
在这个例子中，当删除元素时，erase 方法会返回下一个有效的迭代器，我们需要更新 it 以确保循环正确进行。
3.5 考虑使用 std::vector 的替代方案
std::vector<bool> 是一个特殊的 vector 实现，它为了节省空间，对每个 bool 元素只使用 1 位存储。然而，这导致它的迭代器和引用行为与普通 vector 有所不同，并且性能可能也不理想。
如果需要存储布尔值的容器，可以考虑使用 std::vector<char> 或 std::vector<std::byte>（C++17 引入）。例如，使用 std::vector<char>：
#include <vector>
#include <iostream>
int main() {
std::vector<char> v;
v.push_back(true);
v.push_back(false);
for (char c : v) {
std::cout << (c? "true" : "false") << " ";
}
return 0;
}
这样可以获得更常规的 vector 行为和更好的性能。
3.6 利用 vector 的并行算法
C++17 引入了并行算法，可以利用多核处理器的优势来提高 vector 操作的性能。例如，对 vector 中的元素进行求和：
#include <vector>
#include <iostream>
#include <numeric>
#include <execution>
int main() {
std::vector<int> v(1000000);
for (int i = 0; i < 1000000; ++i) {
v[i] = i;
}
auto start1 = std::chrono::high_resolution_clock::now();
int sum1 = std::accumulate(v.begin(), v.end(), 0);
auto end1 = std::chrono::high_resolution_clock::now();
auto duration1 = std::chrono::duration_cast<std::chrono::microseconds>(end1 - start1).count();
auto start2 = std::chrono::high_resolution_clock::now();
int sum2 = std::reduce(std::execution::par, v.begin(), v.end(), 0);
auto end2 = std::chrono::high_resolution_clock::now();
auto duration2 = std::chrono::duration_cast<std::chrono::microseconds>(end2 - start2).count();
std::cout << "Sequential accumulate: " << duration1 << " microseconds" << std::endl;
std::cout << "Parallel reduce: " << duration2 << " microseconds" << std::endl;
return 0;
}
在这个例子中，使用并行的 std::reduce 比顺序的 std::accumulate 花费的时间更少，尤其是对于大数据量的 vector。
3.7 了解 vector 与其他容器的性能差异
vector 适合随机访问和在末尾添加/删除元素，但在中间插入或删除元素效率较低。与 list 相比，list 是双向链表，适合在任意位置插入和删除元素，但不支持随机访问。与 deque 相比，deque （双端队列）支持在两端高效地添加和删除元素，并且支持随机访问，但内存管理相对复杂，在某些情况下性能可能不如 vector。
例如，在频繁在中间插入元素的场景下，list 可能更合适：
#include <vector>
#include <list>
#include <iostream>
#include <chrono>
int main() {
auto start1 = std::chrono::high_resolution_clock::now();
std::vector<int> v;
for (int i = 0; i < 1000; ++i) {
v.insert(v.begin() + v.size() / 2, i);
}
auto end1 = std::chrono::high_resolution_clock::now();
auto duration1 = std::chrono::duration_cast<std::chrono::microseconds>(end1 - start1).count();
auto start2 = std::chrono::high_resolution_clock::now();
std::list<int> l;
for (int i = 0; i < 1000; ++i) {
auto it = l.begin();
std::advance(it, l.size() / 2);
l.insert(it, i);
}
auto end2 = std::chrono::high_resolution_clock::now();
auto duration2 = std::chrono::duration_cast<std::chrono::microseconds>(end2 - start2).count();
std::cout << "Vector insert in middle: " << duration1 << " microseconds" << std::endl;
std::cout << "List insert in middle: " << duration2 << " microseconds" << std::endl;
return 0;
}
在这个例子中，list 在中间插入元素的性能明显优于 vector。因此，在选择容器时，要根据具体的应用场景和操作特点来决定是否使用 vector 以及如何优化其使用。
通过以上这些技巧，可以在使用 vector 时提高程序的性能和效率，充分发挥 vector 作为 C++ STL 中重要容器的优势。在实际编程中，要根据具体需求灵活运用这些技巧，以达到最佳的编程效果。