C++ STL算法实战指南：从基础到高级应用

1. C++ STL算法概述

作为一名有着十年C++开发经验的老手，我经常看到新手开发者重复造轮子——手写各种查找、排序算法。实际上，C++标准模板库(STL)提供了丰富高效的算法，可以覆盖90%的日常需求。STL算法主要分为以下几类：

• 非修改序列算法：如find、count等，只读取不修改容器内容
• 修改序列算法：如copy、replace等，会改变容器内容
• 排序和相关算法：sort、binary_search等
• 数值算法：accumulate、inner_product等

这些算法通过迭代器与容器解耦，可以灵活应用于各种数据结构。下面我将结合实例详细解析各类常用算法。

2. 非修改序列算法详解

2.1 查找算法实战

查找是日常开发中最常用的操作之一。STL提供了多种查找算法：

cpp复制vector<int> nums = {1, 3, 5, 7, 9};

// 基本查找：找到第一个等于5的元素
auto it = find(nums.begin(), nums.end(), 5);
if (it != nums.end()) {
    cout << "Found at index: " << distance(nums.begin(), it) << endl;
}

// 条件查找：找到第一个大于6的元素
auto it2 = find_if(nums.begin(), nums.end(), [](int x) {
    return x > 6; 
});

// 子序列查找：查找{3,5}最后一次出现的位置
vector<int> sub = {3, 5};
auto it3 = find_end(nums.begin(), nums.end(), sub.begin(), sub.end());

经验之谈：find_if配合lambda表达式非常灵活，可以构建任意复杂的查找条件。对于大型容器，如果已排序，应优先使用binary_search等更高效的算法。

2.2 计数与遍历算法

count和for_each是另外两个常用的非修改算法：

cpp复制vector<int> vec = {1, 2, 2, 3, 2, 4};

// 计数
int twos = count(vec.begin(), vec.end(), 2); // 3
int evens = count_if(vec.begin(), vec.end(), [](int x) {
    return x % 2 == 0;
}); // 4

// 遍历修改
for_each(vec.begin(), vec.end(), [](int& x) {
    x *= 2; // 每个元素乘以2
});

注意点：

• count需要遍历整个范围，时间复杂度O(n)
• for_each可以修改元素，但不改变容器结构（如不会增删元素）

3. 修改序列算法深度解析

3.1 复制与转换算法

copy和transform是最常用的修改算法：

cpp复制vector<int> src = {1, 2, 3, 4, 5};

// 基本复制
vector<int> dest(src.size());
copy(src.begin(), src.end(), dest.begin());

// 条件复制
vector<int> evens;
copy_if(src.begin(), src.end(), back_inserter(evens), [](int x) {
    return x % 2 == 0;
});

// 转换
vector<int> squares(src.size());
transform(src.begin(), src.end(), squares.begin(), [](int x) {
    return x * x;
});

避坑指南：使用copy时务必确保目标容器有足够空间，或者使用back_inserter让容器自动扩容。直接复制到未分配空间会导致未定义行为。

3.2 删除与替换算法

remove和replace系列算法需要特别注意其行为特点：

cpp复制vector<int> nums = {1, 2, 3, 2, 4};

// 删除所有2（逻辑删除）
auto new_end = remove(nums.begin(), nums.end(), 2); 
// nums变为{1,3,4,2,2}，new_end指向第二个2

// 物理删除
nums.erase(new_end, nums.end()); // nums现在为{1,3,4}

// 替换操作
replace(nums.begin(), nums.end(), 3, 30); // 1,30,4
replace_if(nums.begin(), nums.end(), [](int x) {
    return x > 10;
}, 0); // 1,0,4

关键点：

• remove只是把要删除的元素移到末尾，不改变容器大小
• erase-remove是删除元素的惯用法
• replace是原地修改，replace_copy可以保留原容器

4. 排序与查找算法优化

4.1 排序算法对比

STL提供了多种排序算法，各有特点：

cpp复制vector<pair<in