STL算法详解：从查找排序到数值处理
1、非修改型序列操作
这类算法仅读取数据，不对原始容器内容做任何更改。
1.1 元素搜索算法
find(start, finish, target)：定位首个匹配目标值的元素，若未找到则返回结束迭代器。find_if(start, finish, condition)：寻找首个符合特定条件的成员。find_end(start, finish, pattern_start, pattern_finish)：确定子序列最后出现的位置。
std::vector<int> data = {1, 3, 5, 7, 9};
// 定位值为5的项
auto pos = std::find(data.begin(), data.end(), 5);
if (pos != data.end()) {
std::cout << "found: " << *pos << std::endl; // 输出：5
}
// 寻找首个大于6的数字
auto pos2 = std::find_if(data.begin(), data.end(), [](int val) {
return val > 6;
});
std::cout << "first >6: " << *pos2 << std::endl; // 输出：7
// 搜索子串首次出现位置
std::vector<int> pattern = {3, 5};
auto pos3 = std::find_end(data.begin(), data.end(), pattern.begin(), pattern.end());
if (pos3 != data.end()) {
std::cout << "subsequence starts at index: " << pos3 - data.begin() << std::endl; // 输出：1
}
1.2 统计元素数量
count(start, finish, target)：统计指定值的数量。count_if(start, finish, condition)：统计符合条件的元素数目。
std::vector<int> list = {1, 2, 3, 2, 4, 2};
int total_twos = std::count(list.begin(), list.end(), 2); // 结果为3
int even_count = std::count_if(list.begin(), list.end(), [](int val) {
return val % 2 == 0;
}); // 结果为4
1.3 遍历执行函数
for_each(start, finish, function)：对范围内所有元素依次调用给定函数。
std::vector<int> numbers = {1, 2, 3, 4, 5};
std::for_each(numbers.begin(), numbers.end(), [](int& item) {
item *= 2; // 所有元素翻倍
});
// numbers变为{2, 4, 6, 8, 10}
1.4 相等性与差异检测
equal(range1_start, range1_end, range2_start)：对比两个区间是否完全一致。mismatch(range1_start, range1_end, range2_start)：找出第一处不同的元素位置。
std::vector<int> first = {1, 2, 3};
std::vector<int> second = {1, 2, 4};
std::vector<int> third = {1, 2, 3, 4};
// 比较first和second
bool same = std::equal(first.begin(), first.end(), second.begin());
std::cout << "first == second? " << std::boolalpha << same << std::endl; // 输出：false
// 找出first和third首处不同
auto diff_pair = std::mismatch(first.begin(), first.end(), third.begin());
if (diff_pair.first != first.end()) {
std::cout << "mismatch: " << *diff_pair.first << " vs " << *diff_pair.second << std::endl; // 无输出（前三项相同）
}
1.5 条件验证算法
all_of(start, finish, condition)：检查是否所有元素都满足条件。any_of(start, finish, condition)：确认是否有至少一个元素满足要求。none_of(start, finish, condition)：验证是否没有任何元素满足条件。
std::vector<int> values = {2, 4, 6, 8};
bool all_even_check = std::all_of(values.begin(), values.end(), [](int val) {
return val % 2 == 0;
}); // true
bool any_odd_check = std::any_of(values.begin(), values.end(), [](int val) {
return val % 2 != 0;
}); // false
bool no_negative_check = std::none_of(values.begin(), values.end(), [](int val) {
return val < 0;
}); // true
2、可修改型序列操作
这些算法会对原始数据进行变更或重组。
2.1 数据复制算法
copy(source_start, source_end, destination)：将源区间的元素复制至目标区域。copy_if(source_start, source_end, destination, condition)：只复制满足条件的元素。
std::vector<int> origin = {1, 2, 3, 4, 5};
std::vector<int> target(5); // 需要预分配容量
// 复制全部元素
std::copy(origin.begin(), origin.end(), target.begin()); // target: [1,2,3,4,5]
// 提取偶数到新容器
std::vector<int> evens_only;
std::copy_if(origin.begin(), origin.end(), std::back_inserter(evens_only), [](int num) {
return num % 2 == 0;
}); // evens_only: [2,4]
说明：back_inserter(container) 自动调用 push_back() 方法，无需手动管理内存。
2.2 映射变换算法
transform(input_start, input_end, output_start, function)：将输入区间每个元素经过函数映射后写入输出区间。
std::vector<int> inputs = {1, 2, 3};
std::vector<int> outputs(3);
// 单输入映射：求平方
std::transform(inputs.begin(), inputs.end(), outputs.begin(), [](int val) {
return val * val;
}); // outputs: [1,4,9]
// 双输入映射：对应元素相加
std::vector<int> left = {1, 2, 3};
std::vector<int> right = {4, 5, 6};
std::vector<int> sums(3);
std::transform(left.begin(), left.end(), right.begin(), sums.begin(), [](int a, int b) {
return a + b;
}); // sums: [5,7,9]
2.3 替换算法族
replace(start, finish, old_value, new_value)：将旧值替换为新值。replace_if(start, finish, condition, new_value)：按条件替换元素。replace_copy(start, finish, destination, old_value, new_value)：复制过程中完成替换，不影响原数组。
std::vector<int> dataset = {1, 2, 3, 2, 5};
// 将所有的2替换成20
std::replace(dataset.begin(), dataset.end(), 2, 20); // dataset: [1,20,3,20,5]
// 替换大于10的数为0
std::replace_if(dataset.begin(), dataset.end(), [](int val) {
return val > 10;
}, 0); // dataset: [1,0,3,0,5]
// 在复制时将3改为300
std::vector<int> result_set;
std::replace_copy(dataset.begin(), dataset.end(), std::back_inserter(result_set), 3, 300); // result_set: [1,0,300,0,5]
2.4 删除算法组合
remove(start, finish, value)：将指定值"移除"到容器尾部，返回新逻辑结尾。remove_if(start, finish, condition)：依据条件筛选并移动。
std::vector<int> elements = {1, 2, 3, 2, 4};
// 逻辑上删除所有2
auto new_tail = std::remove(elements.begin(), elements.end(), 2); // elements: [1,3,4,2,2]
// 实际删除多余元素
elements.erase(new_tail, elements.end()); // elements: [1,3,4]
// 结合lambda表达式删除偶数
elements = {1, 2, 3, 4, 5};
elements.erase(std::remove_if(elements.begin(), elements.end(), [](int val) {
return val % 2 == 0;
}), elements.end()); // elements: [1,3,5]
2.5 去重算法
unique(start, finish)：消除连续重复元素，需配合 erase 清理无效数据。
std::vector<int> duplicates = {1, 1, 2, 2, 3, 3, 3, 4, 5};
auto last_unique = std::unique(duplicates.begin(), duplicates.end());
duplicates.erase(last_unique, duplicates.end()); // duplicates变为{1, 2, 3, 4, 5}
2.6 序列反转
reverse(start, finish)：颠倒区间内元素顺序。
std::vector<int> sequence = {1, 2, 3, 4, 5};
std::reverse(sequence.begin(), sequence.end()); // sequence变为{5, 4, 3, 2, 1}
2.7 循环移位
rotate(start, pivot, finish)：以pivot为界点循环调整元素位置。
std::vector<int> array = {1, 2, 3, 4, 5};
std::rotate(array.begin(), array.begin() + 2, array.end()); // 从第3个元素开始循环，array变为{3, 4, 5, 1, 2}
2.8 随机洗牌
shuffle(start, finish, random_engine)：打乱元素排列顺序。
#include <random>
#include <algorithm>
std::vector<int> items = {1, 2, 3, 4, 5};
std::random_device device;
std::mt19937 engine(device());
std::shuffle(items.begin(), items.end(), engine); // items被打乱
3、排序相关算法
3.1 排序方法分类
sort(start, finish)：快速排序，默认升序。stable_sort(start, finish)：稳定排序，保留相等元素原有顺序。partial_sort(start, middle, finish)：局部排序，确保前段是最小元素。
std::vector<int> unsorted = {5, 3, 1, 4, 2};
std::sort(unsorted.begin(), unsorted.end()); // 升序，unsorted变为{1, 2, 3, 4, 5}
std::sort(unsorted.begin(), unsorted.end(), std::greater<int>()); // 降序，unsorted变为{5, 4, 3, 2, 1}
std::vector<std::pair<int, int>> pairs = {{1, 2}, {2, 1}, {1, 1}, {2, 2}};
std::stable_sort(pairs.begin(), pairs.end(), [](const auto& a, const auto& b) {
return a.first < b.first; // 按first字段排序，维持原顺序
});
std::vector<int> mixed = {5, 3, 1, 4, 2, 6};
// 取出最小的三个元素置于前端
std::partial_sort(mixed.begin(), mixed.begin() + 3, mixed.end());
// mixed前三位为1, 2, 3，其余未排序
3.2 第K小元素选取
nth_element(start, k_position, finish)：使第k位置上的元素处于最终排序状态。
std::vector<int> pool = {5, 3, 1, 4, 2, 6};
// 找到第三小元素（索引2）
std::nth_element(pool.begin(), pool.begin() + 2, pool.end());
// 此时pool[2]=3，左侧元素≤3，右侧≥3
3.3 二分查找工具
前提：容器必须已排序。
binary_search(start, finish, target)：判断目标是否存在。lower_bound(start, finish, target)：返回首个不小于目标的元素。upper_bound(start, finish, target)：返回首个大于目标的元素。
std::vector<int> ordered = {1, 3, 3, 5, 7}; // 必须先排序
// 检查3是否存在于ordered中
bool found = std::binary_search(ordered.begin(), ordered.end(), 3); // true
// 找第一个≥3的元素
auto lower_pos = std::lower_bound(ordered.begin(), ordered.end(), 3);
std::cout << "lower_bound index: " << lower_pos - ordered.begin() << std::endl; // 输出：1
// 找第一个>3的元素
auto upper_pos = std::upper_bound(ordered.begin(), ordered.end(), 3);
std::cout << "upper_bound index: " << upper_pos - ordered.begin() << std::endl; // 输出：3
3.4 归并操作
merge(first_start, first_end, second_start, second_end, result)：合并两个有序区间。
std::vector<int> group_a = {1, 3, 5};
std::vector<int> group_b = {2, 4, 6};
std::vector<int> merged(group_a.size() + group_b.size());
// 合并group_a和group_b（两者均已排序）
std::merge(group_a.begin(), group_a.end(), group_b.begin(), group_b.end(), merged.begin()); // merged: [1,2,3,4,5,6]
4、堆结构维护
提供构建和维护堆的操作：
make_heap(start, finish)：构造最大堆。push_heap(start, finish)：插入新元素后重建堆。pop_heap(start, finish)：弹出堆顶元素。sort_heap(start, finish)：将堆转为升序排列。
std::vector<int> heap_data = {4, 1, 3, 2, 5};
std::make_heap(heap_data.begin(), heap_data.end()); // 构造最大堆，heap_data变为{5, 4, 3, 2, 1}
heap_data.push_back(6);
std::push_heap(heap_data.begin(), heap_data.end()); // 插入6并调整堆，heap_data变为{6, 4, 5, 2, 1, 3}
std::pop_heap(heap_data.begin(), heap_data.end()); // 弹出最大元素，heap_data变为{5, 4, 3, 2, 1, 6}
int top_element = heap_data.back(); // 获取最大值6
heap_data.pop_back(); // 移除堆顶
std::sort_heap(heap_data.begin(), heap_data.end()); // 转化为升序序列，heap_data变为{1, 2, 3, 4, 5}
5、极值查找算法
5.1 成员比较函数
min(val1, val2)/max(val1, val2)：返回两者的较小/较大者。min(initializer_list)/max(initializer_list)：从初始化列表中选最值。
int x = 5, y = 3;
int minimum = std::min(x, y); // 3
int maximum = std::max(x, y); // 5
auto min_from_list = std::min({4, 2, 8, 5, 1}); // 1
auto max_from_list = std::max({4, 2, 8, 5, 1}); // 8
5.2 区间极值定位
min_element(start, finish)/max_element(start, finish)：返回指向极值的迭代器。
std::vector<int> collection = {3, 1, 4, 2, 5};
auto min_iter = std::min_element(collection.begin(), collection.end()); // 指向1
auto max_iter = std::max_element(collection.begin(), collection.end()); // 指向5
5.3 同时获取最大最小
minmax_element(start, finish)：一次性获得最小和最大元素位置。
std::vector<int> dataset = {3, 1, 4, 2, 5};
auto extremes = std::minmax_element(dataset.begin(), dataset.end());
// extremes.first指向1，extremes.second指向5
6、数值运算算法
位于<numeric>头文件中。
6.1 累加求和
accumulate(start, finish, initial_value)：计算总和或自定义累积方式。
#include <numeric>
std::vector<int> nums = {1, 2, 3, 4, 5};
int sum_result = std::accumulate(nums.begin(), nums.end(), 0); // 总和为15
int product_result = std::accumulate(nums.begin(), nums.end(), 1, std::multiplies<int>()); // 乘积为120
6.2 内积运算
inner_product(first_start, first_end, second_start, initial_value)：计算两个向量点积。
std::vector<int> vector_a = {1, 2, 3};
std::vector<int> vector_b = {4, 5, 6};
int dot_product = std::inner_product(vector_a.begin(), vector_a.end(), vector_b.begin(), 0); // 1*4 + 2*5 + 3*6 = 32
6.3 连续赋值
iota(start, finish, start_value)：填充连续递增值。
std::vector<int> fill_target(5);
std::iota(fill_target.begin(), fill_target.end(), 10); // 填充为10, 11, 12, 13, 14
6.4 部分累计
partial_sum(input_start, input_end, output_start)：逐层叠加生成前缀和。
std::vector<int> input = {1, 2, 3, 4, 5};
std::vector<int> prefix_sums(input.size());
std::partial_sum(input.begin(), input.end(), prefix_sums.begin()); // prefix_sums变为{1, 3, 6, 10, 15}
6.5 差分计算
adjacent_difference(input_start, input_end, output_start)：计算相邻元素之差。
std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> differences(source.size());
std::adjacent_difference(source.begin(), source.end(), differences.begin()); // differences变为{1, 1, 1, 1, 1}
7、辅助类算法
7.1 动态填充
generate(start, finish, generator)：根据生成器填充区间。generate_n(start, count, generator)：仅填充前n个元素。
std::vector<int> generated(5);
int counter = 0;
std::generate(generated.begin(), generated.end(), [&counter]() {
return counter++;
}); // 填充为0, 1, 2, 3, 4
std::vector<int> limited_fill(5);
int base_num = 10;
std::generate_n(limited_fill.begin(), 3, [&base_num]() {
return base_num++;
}); // 前三项为10, 11, 12，其余不变
7.2 子集包含判定
includes(set1_start, set1_end, set2_start, set2_end)：判断是否包含另一个有序集合。
std::vector<int> superset = {1, 2, 3, 4, 5};
std::vector<int> subset = {2, 4};
bool inclusion = std::includes(superset.begin(), superset.end(), subset.begin(), subset.end()); // true
7.3 集合操作
set_union：并集set_intersection：交集set_difference：差集set_symmetric_difference：异或集
std::vector<int> first_set = {1, 2, 3, 4, 5};
std::vector<int> second_set = {3, 4, 5, 6, 7};
std::vector<int> results;
// 并集
std::set_union(first_set.begin(), first_set.end(), second_set.begin(), second_set.end(), std::back_inserter(results));
// results为{1, 2, 3, 4, 5, 6, 7}
// 交集
results.clear();
std::set_intersection(first_set.begin(), first_set.end(), second_set.begin(), second_set.end(), std::back_inserter(results));
// results为{3, 4, 5}
// 差集 (first_set - second_set)
results.clear();
std::set_difference(first_set.begin(), first_set.end(), second_set.begin(), second_set.end(), std::back_inserter(results));
// results为{1, 2}
// 对称差集 ((first_set ∪ second_set) - (first_set ∩ second_set))
results.clear();
std::set_symmetric_difference(first_set.begin(), first_set.end(), second_set.begin(), second_set.end(), std::back_inserter(results));
// results为{1, 2, 6, 7}
