C++ 标准库：STL 算法与容器优化

C++ 标准库（STL）提供了高性能的容器和算法，但代码的运行速度并不自动达到最优。要榨干程序性能，必须根据数据特性选择合适的容器，并配合恰当的算法。以下指南将手把手教你如何优化 STL 使用。

第一阶段：根据场景选择容器

容器的选择直接决定了内存布局和访问效率。错误的容器选择会导致频繁的内存分配或缓存未命中。

分析你的数据访问模式：是随机访问多，还是中间插入删除多？是否需要保持排序？

参考以下决策流程来确定最佳容器：

对比常用容器的操作时间复杂度，以便心中有数：

第二阶段：预分配内存以避免重分配

对于 std::vector 和 std::string 等连续内存容器，动态扩容是非常昂贵的操作：它涉及申请新内存、拷贝旧数据和释放旧内存。

估算最终数据的大致数量。

调用 reserve() 函数在插入数据前预留足够空间。

执行以下代码示例，对比预留与未预留的性能差异：

#include <vector>

// 未优化版：可能触发多次重分配
std::vector<int> data_bad;
for (int i = 0; i < 10000; ++i) {
    data_bad.push_back(i); // 容量不足时触发扩容
}

// 优化版：一次性分配
std::vector<int> data_good;
data_good.reserve(10000); // 预留空间
for (int i = 0; i < 10000; ++i) {
    data_good.push_back(i); // 不会触发扩容，仅构造
}

使用 capacity() 检查当前容量，使用 shrink_to_fit() 释放未使用的内存（仅在确定不再增长时使用）。

第三阶段：使用算法替代手动循环

手写 for 循环不仅代码冗长，而且容易阻碍编译器的自动向量化优化。STL 算法通常经过高度优化，且在 C++17 后支持并行执行策略。

替换累加循环为 std::accumulate。

替换查找循环为 std::find 或 std::any_of。

配置编译器支持 C++17 或更高版本以开启并行算法。

运行以下并行排序示例：

#include <algorithm>
#include <vector>
#include <execution> // C++17 并行算法头文件

std::vector<int> data(1000000);

// 填充数据...

// 单线程排序
std::sort(data.begin(), data.end());

// 并行排序 (利用多核 CPU)
std::sort(std::execution::par, data.begin(), data.end());

注意：并行算法 (std::execution::par) 会引入额外的线程同步开销，仅在数据量较大（例如超过 10,000 个元素）时才有明显优势。

第四阶段：利用移动语义减少拷贝

C++11 引入的移动语义可以显著减少临时对象的深拷贝开销。在向容器插入对象时，务必确保利用了这一特性。

检查你的类是否实现了移动构造函数和移动赋值运算符。

使用 std::move 将左值转换为右值引用，触发移动语义。

观察以下代码，push_back 的行为差异：

#include <vector>
#include <string>

std::vector<std::string> docs;
std::string large_text = "This is a very long string...";

// 拷贝插入：发生一次内存分配和字符串内容拷贝
docs.push_back(large_text); 

// 移动插入：无拷贝，仅指针转移
docs.push_back(std::move(large_text)); 
// 此时 large_text 变为空（或处于有效但未定义状态）

使用 emplace_back 直接在容器内存中构造对象，省去临时对象的构造和销毁步骤：

// 直接在 vector 中构造 string，无需创建临时 string 对象
docs.emplace_back("Construct directly in place");

第五阶段：优化查找操作

在大量数据中查找特定元素时，算法的选择至关重要。

判断容器是否有序。

如果有序，坚决使用 std::lower_bound、std::upper_bound 或 std::binary_search，时间复杂度为 $O(\log n)$。

如果无序且查找频繁，考虑先排序，或者直接使用哈希容器 std::unordered_map / std::unordered_set。

对比 std::find (线性查找) 与二分查找：

#include <algorithm>
#include <vector>

std::vector<int> sorted_data = {1, 3, 5, 7, 9, 11};

// 慢速：O(n) 线性查找，忽略了容器有序的事实
auto it_slow = std::find(sorted_data.begin(), sorted_data.end(), 7);

// 快速：O(log n) 二分查找
auto it_fast = std::lower_bound(sorted_data.begin(), sorted_data.end(), 7);
if (it_fast != sorted_data.end() && *it_fast == 7) {
    // 找到了
}

评估如果同时需要快速查找和动态插入，且无法预分配空间，优先选择 std::unordered_map (平均 $O(1)$) 而非 std::map ($O(\log n)$)，但需注意哈希表的内存消耗通常更高。