C++ STL算法全面指南
1、不可变序列算法
这些算法不会修改它们操作的容器中的元素。
1.1 查找算法
find(start, end, value)：查找第一个等于value的元素，返回迭代器（未找到返回end）。find_if(start, end, condition)：查找第一个满足条件的元素。find_end(start, end, sub_start, sub_end)：查找子序列最后一次出现的位置。
std::vector<int> data = {2, 4, 6, 8, 10};
// 查找值为6的元素
auto position = std::find(data.begin(), data.end(), 6);
if (position != data.end()) {
std::cout << "找到: " << *position << std::endl; // 输出：6
}
// 查找第一个大于5的元素
auto pos = std::find_if(data.begin(), data.end(), [](int num) {
return num > 5;
});
std::cout << "第一个>5: " << *pos << std::endl; // 输出：6
// 查找子序列
std::vector<int> subsequence = {4, 6};
auto sub_pos = std::find_end(data.begin(), data.end(),
subsequence.begin(), subsequence.end());
if (sub_pos != data.end()) {
std::cout << "子序列起始索引: " << sub_pos - data.begin() << std::endl; // 输出：1
}
1.2 计数算法
count(start, end, value)：统计等于value的元素数量。count_if(start, end, condition)：统计满足条件的元素数量。
std::vector<int> numbers = {1, 3, 2, 3, 5, 3, 4};
int three_count = std::count(numbers.begin(), numbers.end(), 3); // 计算3的个数，结果为3
int even_count = std::count_if(numbers.begin(), numbers.end(), [](int num) {
return num % 2 == 0;
}); // 偶数个数，结果为3
1.3 遍历算法
对范围内的每个元素应用一个函数
std::vector<double> values = {1.1, 2.2, 3.3, 4.4, 5.5};
std::for_each(values.begin(), values.end(), [](double& val) {
val *= 1.5; // 将每个元素乘以1.5
});
// 现在values变为{1.65, 3.3, 4.95, 6.6, 8.25}
1.4 比较算法
equal(seq1_start, seq1_end, seq2_start)：判断两个序列是否相等。mismatch(seq1_start, seq1_end, seq2_start)：返回两个序列中第一个不匹配元素的迭代器对。
std::vector<char> str1 = {'a', 'b', 'c'};
std::vector<char> str2 = {'a', 'b', 'd'};
std::vector<char> str3 = {'a', 'b', 'c', 'd'};
// 比较str1和str2的前3个元素
bool is_same = std::equal(str1.begin(), str1.end(), str2.begin());
std::cout << "str1 == str2? " << std::boolalpha << is_same << std::endl; // 输出：false
// 查找str1和str3的第一个不匹配元素
auto diff = std::mismatch(str1.begin(), str1.end(), str3.begin());
if (diff.first != str1.end()) {
std::cout << "不匹配: " << *diff.first << " vs " << *diff.second << std::endl; // 无输出（str1和str3前3元素相等）
}
1.5 条件检查算法
检查范围内元素是否全部、存在或没有满足条件的
std::vector<std::string> words = {"hello", "world", "cpp", "stl"};
bool all_alpha = std::all_of(words.begin(), words.end(), [](const std::string& s) {
return std::all_of(s.begin(), s.end(), ::isalpha);
}); // true
bool has_digit = std::any_of(words.begin(), words.end(), [](const std::string& s) {
return std::any_of(s.begin(), s.end(), ::isdigit);
}); // false
bool empty_str = std::none_of(words.begin(), words.end(), [](const std::string& s) {
return s.empty();
}); // true
2、可变序列算法
这些算法会修改它们操作的容器中的元素。
2.1 复制算法
copy(start, end, destination)：将元素复制到目标位置。copy_if(start, end, destination, condition)：复制满足条件的元素到目标位置。
std::vector<int> source = {10, 20, 30, 40, 50};
std::vector<int> target(source.size()); // 需预先分配足够空间
// 复制所有元素
std::copy(source.begin(), source.end(), target.begin()); // target: [10,20,30,40,50]
// 复制大于25的元素到新容器
std::vector<int> filtered;
std::copy_if(source.begin(), source.end(), std::back_inserter(filtered), [](int val) {
return val > 25;
}); // filtered: [30,40,50]
注意：std::back_inserter(target) 会自动调用 push_back，无需提前分配空间。
2.2 转换算法
对范围内的每个元素应用一个函数，并将结果存储在另一个范围内
std::vector<float> measurements = {1.5f, 2.5f, 3.5f};
std::vector<int> rounded(measurements.size());
// 四舍五入（单参数转换）
std::transform(measurements.begin(), measurements.end(), rounded.begin(),
[](float f) { return static_cast<int>(f + 0.5f); }); // rounded: [2,3,4]
// 两容器元素相乘（双参数转换）
std::vector<int> vec_a = {1, 2, 3};
std::vector<int> vec_b = {4, 5, 6};
std::vector<int> product(vec_a.size());
std::transform(vec_a.begin(), vec_a.end(), vec_b.begin(), product.begin(),
[](int x, int y) { return x * y; }); // product: [4,10,18]
2.3 替换算法
replace(start, end, old_value, new_value)：将所有old_value替换为new_value。replace_if(start, end, condition, new_value)：替换满足条件的元素。replace_copy(start, end, destination, old_value, new_value)：复制时替换元素（不修改原容器）。
std::vector<std::string> names = {"Alice", "Bob", "Charlie", "Bob", "David"};
// 替换所有"Bob"为"Robert"
std::replace(names.begin(), names.end(), std::string("Bob"), std::string("Robert"));
// names: ["Alice","Robert","Charlie","Robert","David"]
// 替换长度大于5的名字为"Long"
std::replace_if(names.begin(), names.end(),
[](const std::string& s) { return s.length() > 5; },
std::string("Long"));
// names: ["Alice","Robert","Long","Robert","David"]
// 复制时替换"Long"为"Short"（原容器不变）
std::vector<std::string> result;
std::replace_copy(names.begin(), names.end(), std::back_inserter(result),
std::string("Long"), std::string("Short"));
// result: ["Alice","Robert","Short","Robert","David"]
2.4 移除算法
remove(start, end, value)：将等于value的元素 "移动" 到容器末尾，返回新的逻辑尾迭代器（不实际删除元素，需配合erase）。remove_if(start, end, condition)：移动满足条件的元素到末尾。
std::vector<int> scores = {85, 92, 78, 92, 88, 65};
// 逻辑删除所有92（移动到末尾）
auto new_end = std::remove(scores.begin(), scores.end(), 92);
// scores: [85,78,88,65,92,92]
// 物理删除（真正移除元素）
scores.erase(new_end, scores.end());
// scores: [85,78,88,65]
// 结合lambda删除低于80的分数
scores = {85, 92, 78, 92, 88, 65};
scores.erase(std::remove_if(scores.begin(), scores.end(),
[](int s) { return s < 80; }), scores.end());
// scores: [85,92,92,88]
2.5 去重算法
移除范围内连续的重复元素，返回新的逻辑结尾迭代器。通常与erase结合使用。
std::list<std::string> items = {"apple", "apple", "banana", "banana", "banana", "orange", "orange"};
auto last = std::unique(items.begin(), items.end());
items.erase(last, items.end()); // items变为{"apple", "banana", "orange"}
2.6 反转算法
反转范围内的元素顺序
std::deque<int> numbers = {10, 20, 30, 40, 50};
std::reverse(numbers.begin(), numbers.end()); // numbers变为{50, 40, 30, 20, 10}
2.7 旋转算法
旋转范围内的元素，使中间元素成为新的第一个元素
std::array<int, 7> arr = {1, 2, 3, 4, 5, 6, 7};
std::rotate(arr.begin(), arr.begin() + 3, arr.end()); // 以4为起点旋转，arr变为{4, 5, 6, 7, 1, 2, 3}
2.8 随机打乱算法
随机重排范围内的元素（需要C++11或更高版本）
#include <random>
#include <algorithm>
std::vector<char> chars = {'a', 'b', 'c', 'd', 'e'};
std::random_device rd;
std::mt19937 generator(rd());
std::shuffle(chars.begin(), chars.end(), generator); // 随机打乱chars中的元素
3、排序和相关算法
3.1 排序算法
sort(start, end)：对元素进行快速排序（不稳定，平均时间复杂度 O (n log n)）。stable_sort(start, end)：稳定排序（相等元素相对位置不变）。partial_sort(start, mid, end)：部分排序，使[start, mid)为整个范围中最小的元素并排序。
std::vector<double> values = {3.14, 2.71, 1.41, 1.61, 0.57};
std::sort(values.begin(), values.end()); // 默认升序，values变为{0.57, 1.41, 1.61, 2.71, 3.14}
std::sort(values.begin(), values.end(), std::greater<double>()); // 降序，values变为{3.14, 2.71, 1.61, 1.41, 0.57}
std::sort(values.begin(), values.end(), [](double a, double b) {
return a < b;
}); // 升序，自定义比较
std::vector<std::pair<std::string, int>> students = {{"Alice", 20}, {"Bob", 22}, {"Alice", 19}, {"Bob", 21}};
std::stable_sort(students.begin(), students.end(),
[](const auto& a, const auto& b) {
return a.first < b.first; // 按名字排序，保持相等名字的相对顺序
});
std::vector<int> data = {9, 3, 5, 2, 8, 1};
// 将最小的4个元素放在前面并排序
std::partial_sort(data.begin(), data.begin() + 4, data.end());
// 现在data前四个元素是1, 2, 3, 5，后面是未排序的8, 9
3.2 选择算法
重新排列范围，使得指定位置的元素等于排序后的元素，并且左边的元素都不大于它，右边的元素都不小于它
std::vector<int> numbers = {5, 3, 1, 4, 2, 6};
// 找到第四小的元素（索引3）
std::nth_element(numbers.begin(), numbers.begin() + 3, numbers.end());
// 现在numbers[3]是4，它左边的元素<=4，右边的>=4
3.3 二分查找算法
需在已排序的容器上使用
binary_search(start, end, value)：判断value是否存在（返回bool）。lower_bound(start, end, value)：返回第一个不小于value的元素迭代器。upper_bound(start, end, value)：返回第一个大于value的元素迭代器。
std::vector<int> sorted_list = {10, 20, 30, 30, 40, 50}; // 必须先排序
// 判断30是否存在
bool found = std::binary_search(sorted_list.begin(), sorted_list.end(), 30); // true
// 查找第一个>=30的元素
auto lower = std::lower_bound(sorted_list.begin(), sorted_list.end(), 30);
std::cout << "lower_bound索引: " << lower - sorted_list.begin() << std::endl; // 输出：2
// 查找第一个>30的元素
auto upper = std::upper_bound(sorted_list.begin(), sorted_list.end(), 30);
std::cout << "upper_bound索引: " << upper - sorted_list.begin() << std::endl; // 输出：4
3.4 合并算法
合并两个已排序的范围到新容器（保持排序）
std::list<std::string> list1 = {"apple", "banana", "cherry"};
std::list<std::string> list2 = {"apricot", "blueberry", "date"};
std::list<std::string> merged;
// 合并list1和list2（均需已排序）
std::merge(list1.begin(), list1.end(), list2.begin(), list2.end(),
std::back_inserter(merged));
// merged: ["apple", "apricot", "banana", "blueberry", "cherry", "date"]
4、堆算法
STL提供了将范围作为堆来操作的算法，包括make_heap, push_heap, pop_heap, sort_heap等。
std::vector<int> heap_data = {3, 1, 4, 1, 5, 9, 2, 6};
std::make_heap(heap_data.begin(), heap_data.end()); // 构建最大堆，heap_data变为{9, 6, 4, 1, 5, 3, 2, 1}
heap_data.push_back(10);
std::push_heap(heap_data.begin(), heap_data.end()); // 将新元素加入堆，heap_data变为{10, 6, 9, 1, 5, 3, 2, 1, 4}
std::pop_heap(heap_data.begin(), heap_data.end()); // 将最大元素移到末尾，heap_data变为{9, 6, 4, 1, 5, 3, 2, 1, 10}
int max_value = heap_data.back(); // 获取最大元素10
heap_data.pop_back(); // 移除最大元素
std::sort_heap(heap_data.begin(), heap_data.end()); // 将堆排序为升序序列，heap_data变为{1, 1, 2, 3, 4, 5, 6, 9}
5、最小/最大值算法
5.1 二元最小/最大
返回两个值或初始化列表中的最小/最大值
int x = 15, y = 25;
int smaller = std::min(x, y); // 15
int larger = std::max(x, y); // 25
auto smallest = std::min({7, 3, 9, 1, 5}); // 1
auto biggest = std::max({7, 3, 9, 1, 5}); // 9
5.2 范围最小/最大
返回范围内的最小/最大元素的迭代器
std::vector<float> measurements = {3.14f, 2.71f, 1.41f, 1.61f};
auto min_it = std::min_element(measurements.begin(), measurements.end()); // 指向1.41f
auto max_it = std::max_element(measurements.begin(), measurements.end()); // 指向3.14f
5.3 最小最大对 (C++11)
同时返回范围内的最小和最大元素的迭代器
std::vector<int> scores = {85, 92, 78, 96, 88};
auto minmax = std::minmax_element(scores.begin(), scores.end());
// minmax.first指向78，minmax.second指向96
6、数值算法（在<numeric>中）
6.1 累积算法
计算范围内元素的累加和（或自定义操作）
#include <numeric>
std::vector<int> numbers = {1, 2, 3, 4, 5};
int total = std::accumulate(numbers.begin(), numbers.end(), 0); // 和，初始值为0，结果为15
int factorial = std::accumulate(numbers.begin(), numbers.end(), 1,
[](int a, int b) { return a * b; }); // 乘积，初始值为1，结果为120
6.2 内积算法
计算两个范围的内积（或自定义操作）
std::vector<double> vec1 = {1.1, 2.2, 3.3};
std::vector<double> vec2 = {4.4, 5.5, 6.6};
double dot_product = std::inner_product(vec1.begin(), vec1.end(), vec2.begin(), 0.0);
// 1.1*4.4 + 2.2*5.5 + 3.3*6.6 = 38.72
6.3 连续值填充
用连续递增的值填充范围
std::vector<int> sequence(5);
std::iota(sequence.begin(), sequence.end(), 100); // 填充为100, 101, 102, 103, 104
6.4 部分和
计算部分和，将结果存储在目标范围内
std::vector<int> input = {1, 2, 3, 4, 5};
std::vector<int> output(input.size());
std::partial_sum(input.begin(), input.end(), output.begin()); // output变为{1, 3, 6, 10, 15}
6.5 相邻差值
计算相邻元素的差值，将结果存储在目标范围内
std::vector<int> source = {10, 12, 15, 19, 25};
std::vector<int> differences(source.size());
std::adjacent_difference(source.begin(), source.end(), differences.begin());
// differences变为{10, 2, 3, 4, 6}
7、其他算法
7.1 生成算法
用生成函数填充范围
std::vector<std::string> words(5);
int counter = 0;
std::generate(words.begin(), words.end(), [&counter]() {
return "Word" + std::to_string(counter++);
}); // 填充为"Word0", "Word1", "Word2", "Word3", "Word4"
7.2 生成n个元素
用生成函数填充范围的开始n个元素
std::vector<int> values(10);
int start = 50;
std::generate_n(values.begin(), 5, [&start]() {
return start++;
}); // 前五个元素为50, 51, 52, 53, 54，后五个保持不变
7.3 包含检查
检查一个排序范围是否包含另一个排序范围的所有元素
std::vector<std::string> dictionary = {"apple", "banana", "cherry", "date", "elderberry"};
std::vector<std::string> search = {"banana", "date"};
bool contains = std::includes(dictionary.begin(), dictionary.end(),
search.begin(), search.end()); // true
7.4 集合操作
执行集合操作：并集、交集、差集和对称差集
std::set<int> set1 = {1, 2, 3, 4, 5};
std::set<int> set2 = {3, 4, 5, 6, 7};
std::vector<int> result;
// 并集
std::set_union(set1.begin(), set1.end(), set2.begin(), set2.end(),
std::back_inserter(result));
// result为{1, 2, 3, 4, 5, 6, 7}
// 交集
result.clear();
std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(),
std::back_inserter(result));
// result为{3, 4, 5}
// 差集 (set1 - set2)
result.clear();
std::set_difference(set1.begin(), set1.end(), set2.begin(), set2.end(),
std::back_inserter(result));
// result为{1, 2}
// 对称差集 (set1 ∪ set2 - set1 ∩ set2)
result.clear();
std::set_symmetric_difference(set1.begin(), set1.end(), set2.begin(), set2.end(),
std::back_inserter(result));
// result为{1, 2, 6, 7}
8、常见问题
sort与stable_sort的区别？
sort采用快速排序（实际是 introsort 算法），不稳定（相等元素的相对位置可能改变），平均时间复杂度 O (n log n)。stable_sort采用归并排序，稳定（相等元素相对位置不变），时间复杂度 O (n log n)，但空间开销略大。
- 为什么
remove算法需要配合erase使用？remove算法的原理是 "覆盖" 要删除的元素，将保留的元素移到前面，返回新的逻辑尾迭代器，但不修改容器的实际大小。erase则通过迭代器范围真正删除元素，修改容器大小。因此需结合使用：container.erase(remove(...), container.end())。 - 哪些算法需要容器是已排序的？
二分查找系列（
binary_search、lower_bound、upper_bound）、集合算法（set_intersection、set_union等）、merge等，这些算法依赖有序性实现高效操作（如二分查找 O (log n)）。
