STL序列操作与高效算法实践
一、非修改型遍历算法 这些函数仅读取数据，不改变原始容器内容。
1.1 定位查找
find：在指定范围内寻找首个匹配值。find_if：基于条件表达式定位首个满足的元素。find_end：查找子序列最后一次出现的位置。
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 << '\n';
}
// 找出首个大于6的数
auto first_gt = std::find_if(data.begin(), data.end(), [](int x) {
return x > 6;
});
std::cout << "First greater than 6: " << *first_gt << '\n';
// 检查子数组{3,5}是否存在
std::vector<int> pattern = {3, 5};
auto match = std::find_end(data.begin(), data.end(), pattern.begin(), pattern.end());
if (match != data.end()) {
std::cout << "Pattern starts at index: " << (match - data.begin()) << '\n';
}
1.2 统计分析
count：统计特定值的出现次数。count_if：计算符合谓词条件的元素数量。
std::vector<int> numbers = {1, 2, 3, 2, 4, 2};
int count_twos = std::count(numbers.begin(), numbers.end(), 2); // 3
int even_count = std::count_if(numbers.begin(), numbers.end(), [](int x) {
return x % 2 == 0;
}); // 4
1.3 遍历执行 对每个元素调用指定函数。
std::vector<int> values = {1, 2, 3, 4, 5};
std::for_each(values.begin(), values.end(), [](int& item) {
item *= 2; // 原地加倍
});
// 结果：{2, 4, 6, 8, 10}
1.4 等价性判断
equal：比较两个范围是否完全一致。mismatch：返回第一个差异位置的迭代器对。
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());
if (diff.first != a.end()) {
std::cout << "Mismatch at: " << *diff.first << " vs " << *diff.second << '\n';
}
1.5 条件验证 检查范围中所有、任意或无元素满足某条件。
std::vector<int> nums = {2, 4, 6, 8};
bool all_even = std::all_of(nums.begin(), nums.end(), [](int x) {
return x % 2 == 0;
}); // true
bool has_odd = std::any_of(nums.begin(), nums.end(), [](int x) {
return x % 2 != 0;
}); // false
bool no_negative = std::none_of(nums.begin(), nums.end(), [](int x) {
return x < 0;
}); // true
二、修改型序列操作
2.1 数据复制
copy：将源范围复制到目标起始位置。copy_if：仅复制满足条件的元素。
std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> target(5);
std::copy(source.begin(), source.end(), target.begin());
// 只复制偶数
std::vector<int> evens;
std::copy_if(source.begin(), source.end(), std::back_inserter(evens), [](int x) {
return x % 2 == 0;
});
2.2 映射变换 对每个元素应用函数并输出结果。
std::vector<int> input = {1, 2, 3};
std::vector<int> squares(3);
// 单参数转换：平方
std::transform(input.begin(), input.end(), squares.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(), [](int x, int y) {
return x + y;
});
2.3 替换操作
replace：替换所有匹配值。replace_if：按条件替换。replace_copy：原样复制同时替换。
std::vector<int> list = {1, 2, 3, 2, 5};
// 将所有2替换为20
std::replace(list.begin(), list.end(), 2, 20);
// 替换大于10的元素为0
std::replace_if(list.begin(), list.end(), [](int x) {
return x > 10;
}, 0);
// 复制时替换3为300
std::vector<int> result;
std::replace_copy(list.begin(), list.end(), std::back_inserter(result), 3, 300);
2.4 删除逻辑处理
remove：移动待删元素至末尾，返回新结尾。remove_if：按条件移动。- 实际删除需配合
erase。
std::vector<int> nums = {1, 2, 3, 2, 4};
auto new_end = std::remove(nums.begin(), nums.end(), 2);
nums.erase(new_end, nums.end()); // 移除多余元素
// 使用lambda移除偶数
nums = {1, 2, 3, 4, 5};
nums.erase(std::remove_if(nums.begin(), nums.end(), [](int x) {
return x % 2 == 0;
}), nums.end());
2.5 去重处理
移除连续重复项，需后续 erase。
std::vector<int> dupes = {1, 1, 2, 2, 3, 3, 3, 4, 5};
auto last = std::unique(dupes.begin(), dupes.end());
dupes.erase(last, dupes.end());
2.6 逆序与旋转
reverse：反转整个范围。rotate：以指定位置为轴旋转。
std::vector<int> data = {1, 2, 3, 4, 5};
std::reverse(data.begin(), data.end()); // {5, 4, 3, 2, 1}
std::rotate(data.begin(), data.begin() + 2, data.end()); // {3, 4, 5, 1, 2}
2.7 随机打乱 使用随机引擎实现均匀分布重排。
#include <random>
std::vector<int> arr = {1, 2, 3, 4, 5};
std::random_device rd;
std::mt19937 gen(rd());
std::shuffle(arr.begin(), arr.end(), gen);
三、排序与查找优化
3.1 排序策略
sort：快速排序，不稳定。stable_sort：归并排序，保持相等元素顺序。partial_sort：仅排序前N个最小元素。
std::vector<int> vec = {5, 3, 1, 4, 2};
std::sort(vec.begin(), vec.end()); // 升序
std::sort(vec.begin(), vec.end(), std::greater<int>()); // 降序
std::vector<std::pair<int, int>> pairs = {{1, 2}, {2, 1}, {1, 1}};
std::stable_sort(pairs.begin(), pairs.end(), [](const auto& a, const auto& b) {
return a.first < b.first;
});
// 取最小三个元素并排序
std::partial_sort(vec.begin(), vec.begin() + 3, vec.end());
3.2 第k小元素
nth_element 使第n个位置为正确排序后的值。
std::vector<int> nums = {5, 3, 1, 4, 2, 6};
std::nth_element(nums.begin(), nums.begin() + 2, nums.end());
// nums[2] 是第三小的数（即3），左边≤3，右边≥3
3.3 二分查找系列 必须作用于已排序范围。
std::vector<int> sorted = {1, 3, 3, 5, 7};
bool found = std::binary_search(sorted.begin(), sorted.end(), 3); // true
auto lower = std::lower_bound(sorted.begin(), sorted.end(), 3); // 指向第一个≥3的位置
auto upper = std::upper_bound(sorted.begin(), sorted.end(), 3); // 指向第一个>3的位置
3.4 合并有序范围 将两个已排序容器合并为一个新有序容器。
std::vector<int> left = {1, 3, 5}, right = {2, 4, 6};
std::vector<int> merged(left.size() + right.size());
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：返回两个值中的较小/较大者。- 支持初始化列表。
int min_val = std::min(5, 3); // 3
auto min_list = std::min({4, 2, 8, 5, 1}); // 1
5.2 迭代器级极值
min_element/max_element：返回极值对应的迭代器。minmax_element：一次返回最小和最大迭代器。
std::vector<int> vals = {3, 1, 4, 2, 5};
auto min_it = std::min_element(vals.begin(), vals.end());
auto max_it = std::max_element(vals.begin(), vals.end());
auto mm = std::minmax_element(vals.begin(), vals.end());
// mm.first → 1, mm.second → 5
六、数值计算工具
6.1 累积求和 支持自定义操作。
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<int>()); // 120
6.2 内积计算 两个向量对应项乘积之和。
std::vector<int> a = {1, 2, 3}, b = {4, 5, 6};
int dot_product = std::inner_product(a.begin(), a.end(), b.begin(), 0); // 32
6.3 连续赋值 填充递增序列。
std::vector<int> buffer(5);
std::iota(buffer.begin(), buffer.end(), 10); // {10,11,12,13,14}
6.4 部分和 生成累计和序列。
std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> partial(src.size());
std::partial_sum(src.begin(), src.end(), partial.begin()); // {1,3,6,10,15}
6.5 相邻差值 计算相邻元素差。
std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> diffs(src.size());
std::adjacent_difference(src.begin(), src.end(), diffs.begin()); // {1,1,1,1,1}
七、生成与集合运算
7.1 数据生成
generate：用函数填充整个范围。generate_n：仅填充前n个元素。
std::vector<int> data(5);
int counter = 0;
std::generate(data.begin(), data.end(), [&]() { return counter++; });
std::vector<int> buf(5);
std::generate_n(buf.begin(), 3, [&]() { return 10++; }); // 前三项为10,11,12
7.2 集合关系判断
includes：检查一个有序范围是否包含另一个。set_union,set_intersection,set_difference,set_symmetric_difference：执行标准集合操作。
std::vector<int> set1 = {1, 2, 3, 4, 5}, set2 = {2, 4};
bool contains = std::includes(set1.begin(), set1.end(), set2.begin(), set2.end()); // true
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}
八、关键注意事项
- 稳定性选择：若需维持相等元素顺序，应使用
stable_sort而非sort。 - 删除机制：
remove仅"逻辑删除"，必须与erase配合才能物理清除。 - 前提条件：如
binary_search、merge、集合操作等均要求输入范围已排序。
