C++标准算法库核心用法解析
- 非修改型遍历算法 这些操作不改变输入序列的元素内容。
1.1 搜索与匹配
find(first, last, value)：在区间内查找首个等于目标值的元素。find_if(first, last, pred)：定位首个满足条件的元素。find_end(first, last, sub_first, sub_last)：寻找子序列最后一次出现的位置。
std::vector<int> data = {10, 20, 30, 40, 50};
// 查找第一个大于35的元素
auto pos = std::find_if(data.begin(), data.end(), [](int x) {
return x > 35;
});
if (pos != data.end()) {
std::cout << "Found: " << *pos << '\n';
}
// 匹配子数组 [20, 30]
std::vector<int> pattern = {20, 30};
auto match = std::find_end(data.begin(), data.end(), pattern.begin(), pattern.end());
1.2 统计分析
count(first, last, value)：统计指定值的出现次数。count_if(first, last, pred)：计算满足谓词的元素数量。
std::vector<double> values = {1.5, 2.0, 1.5, 3.0, 1.5};
size_t count_1_5 = std::count(values.begin(), values.end(), 1.5); // 3
size_t even_count = std::count_if(values.begin(), values.end(), [](double x) {
return std::floor(x) % 2 == 0;
});
1.3 元素处理
for_each 对每个元素执行指定操作，常用于副作用。
std::vector<int> numbers = {1, 2, 3, 4, 5};
std::for_each(numbers.begin(), numbers.end(), [](int& n) {
n *= 3; // 所有元素乘以3
});
1.4 范围比较
equal(first1, last1, first2)：判断两个等长范围是否完全相同。mismatch(first1, last1, first2)：返回首个不一致位置的迭代器对。
std::vector<int> a = {1, 2, 3}, b = {1, 2, 4};
bool same = std::equal(a.begin(), a.end(), b.begin()); // false
auto diff = std::mismatch(a.begin(), a.end(), b.begin());
1.5 条件验证 检查所有、部分或无元素满足特定条件。
std::vector<bool> flags = {true, true, false, true};
bool all_true = std::all_of(flags.begin(), flags.end(), [](bool b) { return b; }); // false
bool any_false = std::any_of(flags.begin(), flags.end(), [](bool b) { return !b; }); // true
bool none_zero = std::none_of(flags.begin(), flags.end(), [](bool b) { return !b; }); // false
- 修改型数据处理算法
2.1 数据复制与筛选
copy(first, last, dest)：将源范围复制到目标起始位置。copy_if(first, last, dest, pred)：仅复制符合条件的元素。
std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> result;
// 复制偶数
std::copy_if(source.begin(), source.end(), std::back_inserter(result), [](int x) {
return x % 2 == 0;
});
2.2 变换运算
transform 将函数应用于每个元素并输出结果。
std::vector<int> input = {1, 2, 3, 4};
std::vector<int> output(4);
// 单输入变换：平方
std::transform(input.begin(), input.end(), output.begin(), [](int x) {
return x * x;
});
// 双输入变换：对应元素相加
std::vector<int> a = {1, 2, 3}, b = {4, 5, 6};
std::vector<int> sum(3);
std::transform(a.begin(), a.end(), b.begin(), sum.begin(), std::plus<>());
2.3 替换与移除
replace(first, last, old_val, new_val)：替换所有匹配值。replace_if(first, last, pred, new_val)：替换满足条件的元素。replace_copy(first, last, dest, old_val, new_val)：复制时替换。
std::vector<int> nums = {1, 2, 3, 2, 5};
std::replace(nums.begin(), nums.end(), 2, 99); // 替换所有2为99
std::vector<int> temp;
std::replace_copy(nums.begin(), nums.end(), std::back_inserter(temp), 99, 0); // 原始值不变
2.4 移除与清理
remove 和 remove_if 将要删除元素"移至末尾"，需配合 erase 实现物理删除。
std::vector<int> data = {1, 2, 3, 2, 4};
auto new_end = std::remove_if(data.begin(), data.end(), [](int x) {
return x % 2 == 0; // 移除偶数
});
data.erase(new_end, data.end()); // 真正释放内存
2.5 去重
unique 移除相邻重复项，通常与 erase 配合使用。
std::vector<int> duplicates = {1, 1, 2, 2, 2, 3};
auto last = std::unique(duplicates.begin(), duplicates.end());
duplicates.erase(last, duplicates.end()); // 得到{1,2,3}
2.6 重排操作
reverse(first, last)：反转区间顺序。rotate(first, middle, last)：以中间点为基准旋转。shuffle(first, last, rng)：随机打乱元素（需随机引擎）。
std::vector<int> nums = {1, 2, 3, 4, 5};
std::reverse(nums.begin(), nums.end()); // {5,4,3,2,1}
std::rotate(nums.begin(), nums.begin() + 2, nums.end()); // {3,4,5,1,2}
std::random_device rd;
std::mt19937 gen(rd());
std::shuffle(nums.begin(), nums.end(), gen);
- 排序与检索算法
3.1 排序方法
sort：快速排序（不稳定），时间复杂度 O(n log n)。stable_sort：归并排序（稳定），保持相等元素顺序。partial_sort：仅排序前k个最小元素。
std::vector<int> data = {5, 3, 1, 4, 2};
std::sort(data.begin(), data.end()); // 升序排列
std::sort(data.begin(), data.end(), std::greater<>()); // 降序
std::partial_sort(data.begin(), data.begin() + 3, data.end()); // 前三个最小元素已排序
3.2 第k小元素
nth_element 将第n个位置的元素置于正确排序位置。
std::vector<int> vec = {5, 3, 1, 4, 2};
std::nth_element(vec.begin(), vec.begin() + 2, vec.end()); // vec[2] 是第三小元素
3.3 二分查找系列 要求输入范围已排序。
binary_search：判断值是否存在。lower_bound：首个不小于目标值的位置。upper_bound：首个大于目标值的位置。
std::vector<int> sorted = {1, 3, 3, 5, 7};
auto lb = std::lower_bound(sorted.begin(), sorted.end(), 3); // 指向第一个3
auto ub = std::upper_bound(sorted.begin(), sorted.end(), 3); // 指向5
3.4 合并有序序列
merge 将两个已排序范围合并为一个新有序范围。
std::vector<int> left = {1, 3, 5}, right = {2, 4, 6};
std::vector<int> merged(6);
std::merge(left.begin(), left.end(), right.begin(), right.end(), merged.begin());
- 堆结构操作 利用容器实现堆功能。
std::vector<int> heap_data = {4, 1, 3, 2, 5};
std::make_heap(heap_data.begin(), heap_data.end()); // 构建最大堆
heap_data.push_back(6);
std::push_heap(heap_data.begin(), heap_data.end()); // 插入新元素
std::pop_heap(heap_data.begin(), heap_data.end()); // 最大值移到末尾
int max_val = heap_data.back();
heap_data.pop_back();
std::sort_heap(heap_data.begin(), heap_data.end()); // 排序成升序
- 极值查找算法
5.1 基础极值
min,max：返回两个值中的较小/较大者。min_element,max_element：返回范围中极值的迭代器。
int a = 5, b = 3;
int min_val = std::min(a, b); // 3
std::vector<int> vals = {3, 1, 4, 2};
auto min_iter = std::min_element(vals.begin(), vals.end());
5.2 同时获取极值
minmax_element 返回最小和最大元素的迭代器对。
auto range = std::minmax_element(vals.begin(), vals.end());
- 数值计算算法
6.1 累加与内积
accumulate：计算累加和或自定义操作。inner_product：计算两范围的内积。
std::vector<int> nums = {1, 2, 3, 4, 5};
int total = std::accumulate(nums.begin(), nums.end(), 0); // 15
int product = std::accumulate(nums.begin(), nums.end(), 1, std::multiplies<>()); // 120
6.2 序列生成
iota：用递增数值填充范围。partial_sum：计算前缀和。adjacent_difference：计算相邻差值。
std::vector<int> seq(5);
std::iota(seq.begin(), seq.end(), 10); // {10,11,12,13,14}
std::vector<int> sums(5);
std::partial_sum(seq.begin(), seq.end(), sums.begin()); // {10,21,33,46,60}
- 其他实用算法
7.1 生成数据
generate：使用生成函数填充范围。generate_n：填充前n个元素。
std::vector<int> buffer(5);
int counter = 0;
std::generate(buffer.begin(), buffer.end(), [&]() { return counter++; });
7.2 集合关系检测
includes：判断一个有序范围是否包含另一个。set_union,set_intersection,set_difference,set_symmetric_difference：集合运算。
std::vector<int> set_a = {1, 2, 3, 4, 5};
std::vector<int> set_b = {3, 4, 5, 6, 7};
std::vector<int> result;
std::set_intersection(set_a.begin(), set_a.end(), set_b.begin(), set_b.end(),
std::back_inserter(result));
- 关键概念澄清
- sort vs stable_sort：前者更快但不保证相等元素顺序；后者更慢但保持相对顺序。
- remove + erase：remove仅逻辑移动元素，必须调用erase才能真正删除。
- 有序前提：binary_search、lower_bound、set算法等必须作用于已排序范围。
