当前位置：首页 > 技术 > 正文内容

C++ STL 算法详解

访客技术 2026年6月14日 1

一、非变动型算法

这类算法在处理数据时不更改原始容器内容。

1.1 元素搜索算法

find(start, finish, target)：定位首个匹配目标值的元素，返回其迭代器；若不存在则返回finish。
find_if(start, finish, condition)：找出首个符合特定条件的元素。
find_end(start, finish, sub_start, sub_finish)：寻找子序列最后出现的位置。

vector<int> data = {1, 3, 5, 7, 9};

// 定位数值为5的项
auto pos = find(data.begin(), data.end(), 5);
if (pos != data.end()) {
    cout << "found: " << *pos << endl;  // 输出：5
}

// 寻找首个大于6的项目
auto pos2 = find_if(data.begin(), data.end(), [](int val) {
    return val > 6;
});
cout << "first >6: " << *pos2 << endl;  // 输出：7

// 子串查询示例
vector<int> pattern = {3, 5};
auto pos3 = find_end(data.begin(), data.end(), pattern.begin(), pattern.end());
if (pos3 != data.end()) {
    cout << "subsequence starts at index: " << pos3 - data.begin() << endl;  // 输出：1
}

1.2 统计类算法

count(start, finish, target)：统计等于target的元素数量。
count_if(start, finish, condition)：统计满足condition的元素数目。

std::vector<int> items = {1, 2, 3, 2, 4, 2};
int total = std::count(items.begin(), items.end(), 2); // 结果为3
int even_total = std::count_if(items.begin(), items.end(), [](int val) { 
    return val % 2 == 0; 
}); // 结果为4

1.3 遍历执行算法

对指定区间内每一项应用函数对象：

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)：获取首组不同元素对应的迭代器对。

vector<int> first = {1, 2, 3};
vector<int> second = {1, 2, 4};
vector<int> third = {1, 2, 3, 4};

// 对比first和second前三项
bool match = equal(first.begin(), first.end(), second.begin());
cout << "first == second? " << boolalpha << match << endl;  // 输出：false

// 查找first与third首个差异点
auto diff_pair = mismatch(first.begin(), first.end(), third.begin());
if (diff_pair.first != first.end()) {
    cout << "difference: " << *diff_pair.first << " vs " << *diff_pair.second << 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 allEven = std::all_of(values.begin(), values.end(), [](int num) { 
    return num % 2 == 0; 
}); // true
bool anyOdd = std::any_of(values.begin(), values.end(), [](int num) { 
    return num % 2 != 0; 
}); // false
bool noNegative = std::none_of(values.begin(), values.end(), [](int num) { 
    return num < 0; 
}); // true

二、变动型算法

此类算法会对容器中的数据进行修改操作。

2.1 数据复制算法

copy(source_start, source_end, destination)：将源区间的元素拷贝至目标位置。
copy_if(source_start, source_end, destination, condition)：仅拷贝符合条件的元素。

vector<int> origin = {1, 2, 3, 4, 5};
vector<int> target(5);  

// 全部复制
copy(origin.begin(), origin.end(), target.begin());  // target: [1,2,3,4,5]

// 只复制偶数
vector<int> evens_only;
copy_if(origin.begin(), origin.end(), back_inserter(evens_only), [](int val) {
    return val % 2 == 0;
});  // evens_only: [2,4]

2.2 映射变换算法

将输入范围映射到输出范围：

vector<int> inputs = {1, 2, 3};
vector<int> outputs(3);

// 单参数转换
transform(inputs.begin(), inputs.end(), outputs.begin(), [](int x) {
    return x * x;
});  // outputs: [1,4,9]

// 双参数转换
vector<int> left = {1, 2, 3};
vector<int> right = {4, 5, 6};
vector<int> sums(3);
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)：复制过程中替换（不影响原数组）。

vector<int> dataset = {1, 2, 3, 2, 5};

// 将所有2替换为20
replace(dataset.begin(), dataset.end(), 2, 20);  // dataset: [1,20,3,20,5]

// 将大于10的元素设为0
replace_if(dataset.begin(), dataset.end(), [](int x) {
    return x > 10;
}, 0);  // dataset: [1,0,3,0,5]

// 复制时将3替换为300
vector<int> result;
replace_copy(dataset.begin(), dataset.end(), back_inserter(result), 3, 300);  // result: [1,0,300,0,5]

2.4 删除算法

remove(start, finish, value)：逻辑上移除指定值，返回新的结束迭代器。
remove_if(start, finish, condition)：按条件逻辑删除元素。

vector<int> list = {1, 2, 3, 2, 4};

// 移动所有2到尾部
auto newEnd = remove(list.begin(), list.end(), 2);  // list: [1,3,4,2,2]

// 实际删除这些元素
list.erase(newEnd, list.end());  // list: [1,3,4]

// 结合lambda表达式清除偶数
list = {1, 2, 3, 4, 5};
list.erase(remove_if(list.begin(), list.end(), [](int x) {
    return x % 2 == 0;
}), list.end());  // list: [1,3,5]

2.5 去重算法

消除连续重复项：

std::vector<int> sequence = {1, 1, 2, 2, 3, 3, 3, 4, 5};
auto endIter = std::unique(sequence.begin(), sequence.end());
sequence.erase(endIter, sequence.end()); // sequence变为{1, 2, 3, 4, 5}

2.6 反转算法

颠倒序列顺序：

std::vector<int> order = {1, 2, 3, 4, 5};
std::reverse(order.begin(), order.end()); // order变为{5, 4, 3, 2, 1}

2.7 循环移位算法

调整元素位置使其循环左移：

std::vector<int> elements = {1, 2, 3, 4, 5};
std::rotate(elements.begin(), elements.begin() + 2, elements.end()); // elements变为{3, 4, 5, 1, 2}

2.8 打乱算法

随机化元素排列：

#include <random>
#include <algorithm>

std::vector<int> samples = {1, 2, 3, 4, 5};
std::random_device rd;
std::mt19937 gen(rd());
std::shuffle(samples.begin(), samples.end(), gen); // 随机打乱samples

三、排序相关算法

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::sort(unsorted.begin(), unsorted.end(), [](int a, int b) { 
    return a < b; 
}); // 自定义比较

std::vector<std::pair<int, int>> pairs = {{1, 2}, {2, 1}, {1, 1}, {2, 2}};
std::stable_sort(pairs.begin(), pairs.end(), [](const auto& lhs, const auto& rhs) {
    return lhs.first < rhs.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 分割选择算法

将某个位置的元素置于排序后的正确位置：

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 二分查找算法

要求容器必须已排序：

binary_search(start, finish, target)：判断是否存在该值。
lower_bound(start, finish, target)：返回首个不小于目标值的元素。
upper_bound(start, finish, target)：返回首个大于目标值的元素。

vector<int> ordered = {1, 3, 3, 5, 7};  

// 判断3是否存在
bool found = binary_search(ordered.begin(), ordered.end(), 3);  // true

// 查找第一个≥3的元素
auto low = lower_bound(ordered.begin(), ordered.end(), 3);
cout << "lower_bound index: " << low - ordered.begin() << endl;  // 输出：1

// 查找第一个>3的元素
auto up = upper_bound(ordered.begin(), ordered.end(), 3);
cout << "upper_bound index: " << up - ordered.begin() << endl;  // 输出：3

3.4 归并算法

合并两个有序序列：

vector<int> partA = {1, 3, 5};
vector<int> partB = {2, 4, 6};
vector<int> combined(partA.size() + partB.size());

merge(partA.begin(), partA.end(), partB.begin(), partB.end(), combined.begin());  // combined: [1,2,3,4,5,6]

四、堆结构操作算法

提供堆相关的操作方法：

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()); // 插入新元素，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 = 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.1 最大最小值提取

int x = 5, y = 3;
int minimum = std::min(x, y); // 3
int maximum = std::max(x, y); // 5

auto minInList = std::min({4, 2, 8, 5, 1}); // 1
auto maxInList = std::max({4, 2, 8, 5, 1}); // 8

5.2 区间最值定位

std::vector<int> array = {3, 1, 4, 2, 5};
auto minPos = std::min_element(array.begin(), array.end()); // 指向1
auto maxPos = std::max_element(array.begin(), array.end()); // 指向5

5.3 同时获取最值

std::vector<int> collection = {3, 1, 4, 2, 5};
auto extremes = std::minmax_element(collection.begin(), collection.end());
// extremes.first指向1，extremes.second指向5

六、数值运算算法

6.1 累积求和

#include <numeric>

std::vector<int> digits = {1, 2, 3, 4, 5};
int sumResult = std::accumulate(digits.begin(), digits.end(), 0); // 和为15
int productResult = std::accumulate(digits.begin(), digits.end(), 1, std::multiplies<int>()); // 乘积为120

6.2 内积计算

std::vector<int> vectorA = {1, 2, 3};
std::vector<int> vectorB = {4, 5, 6};
int dotProduct = std::inner_product(vectorA.begin(), vectorA.end(), vectorB.begin(), 0); // 1*4 + 2*5 + 3*6 = 32

6.3 序列填充

std::vector<int> fillTarget(5);
std::iota(fillTarget.begin(), fillTarget.end(), 10); // 填充为10, 11, 12, 13, 14

6.4 部分累积

std::vector<int> base = {1, 2, 3, 4, 5};
std::vector<int> partialSums(base.size());
std::partial_sum(base.begin(), base.end(), partialSums.begin()); // partialSums变为{1, 3, 6, 10, 15}

6.5 差分计算

std::vector<int> input = {1, 2, 3, 4, 5};
std::vector<int> differences(input.size());
std::adjacent_difference(input.begin(), input.end(), differences.begin()); // differences变为{1, 1, 1, 1, 1}

七、其他实用算法

7.1 动态赋值

std::vector<int> generated(5);
int counter = 0;
std::generate(generated.begin(), generated.end(), [&counter]() { 
    return counter++; 
}); // 填充为0, 1, 2, 3, 4

7.2 指定长度赋值

std::vector<int> limited(5);
int startValue = 10;
std::generate_n(limited.begin(), 3, [&startValue]() { 
    return startValue++; 
}); // 前三项为10, 11, 12，其余不变

7.3 子集包含检验

std::vector<int> fullSet = {1, 2, 3, 4, 5};
std::vector<int> subset = {2, 4};
bool contained = std::includes(fullSet.begin(), fullSet.end(), subset.begin(), subset.end()); // true

7.4 集合操作

std::vector<int> setA = {1, 2, 3, 4, 5};
std::vector<int> setB = {3, 4, 5, 6, 7};
std::vector<int> results;

// 并集
std::set_union(setA.begin(), setA.end(), setB.begin(), setB.end(), std::back_inserter(results));
// results为{1, 2, 3, 4, 5, 6, 7}

// 交集
results.clear();
std::set_intersection(setA.begin(), setA.end(), setB.begin(), setB.end(), std::back_inserter(results));
// results为{3, 4, 5}

// 差集 (setA - setB)
results.clear();
std::set_difference(setA.begin(), setA.end(), setB.begin(), setB.end(), std::back_inserter(results));
// results为{1, 2}

// 对称差集 (setA ∪ setB - setA ∩ setB)
results.clear();
std::set_symmetric_difference(setA.begin(), setA.end(), setB.begin(), setB.end(), std::back_inserter(results));
// results为{1, 2, 6, 7}

八、常见疑问解答

`sort` 与 `stable_sort` 区别？
- sort 使用快排优化版（introsort），不稳定，O(n log n)。
- stable_sort 采用归并排序，稳定，O(n log n)，内存消耗稍高。
为何`remove`需配合`erase`使用？
- remove仅将有效元素前移，返回新边界，不实际缩减尺寸。
- erase负责物理删除多余部分，改变真实大小。
哪些算法要求预排序？
- 二分查找系（binary_search, lower_bound, upper_bound）
- 集合操作系（set_intersection, set_union 等）
- merge等，依赖有序性提升效率（如O(log n)）。

标签: STL C++Algorithm sorting heap

返回列表

上一篇：基于Matlab/Simulink的同步整流移相全桥变换器双闭环控制系统设计

下一篇：深入理解React路由机制

Linux crontab 详解

1) crontab 是什么cron 是 Linux 的定时任务守护进程；crontab 是用来编辑/查看“按时间周期执行命令”的表（cron table）。常见两类：用户 crontab：每个用户一份（crontab -e 编辑）系统级 crontab / cron.d：可指定执行用户（/etc/crontab、/etc/cron.d/*）2) crontab 时间...

富文本里可以允许的 HTML 属性

一、所有标签默认允许的安全属性（极少）class （可选）id （通常建议禁用）title️ 注意：id 容易被滥用做锚点注入，很多系统直接禁用class 允许的话最好只允许固定前缀（如 editor-*）二、a 标签允许属性<a href="" t...

方法一：通过官网安装包（最简单，适合初学者）如果你只是想快速安装并开始使用，这是最直接的方法。访问 Node.js 官网。页面会显示两个版本：LTS (Recommended For Most Users)：长期支持版，最稳定。建议选这个。Current：最新特性版，包含最新功能但可能不够稳定。下载 .pkg 安装包并运行。按照安装向导点击“下一步”即可完成。方法二：使用 Homebrew 安装（...

Dom\HTML_NO_DEFAULT_NS 的副作用：自动加闭合标签

在使用Dom\HTMLDocument时，Dom\HTML_NO_DEFAULT_NS 将禁止在解析过程中设置元素的命名空间, 此设置是为了与DOMDocument向后兼容而存在的。当使用它时，已知的一个副作用就是：自动加闭合标签例如 </img> 为什么会这样？当你使用：Dom\HTML_NO_DEFAULT_NS文档会变成无命名空间模式，此时内部更接近 XML...

Laravel 事件和监听器创建

在 Laravel 中，使用 Artisan 命令创建 Events（事件）和 Listeners（监听器）是非常高效的。你可以通过以下几种方式来实现：1. 手动创建单个 Event如果你只想创建一个事件类，可以使用 make:event 命令：Bashphp artisan make:event UserRegistered执行后，文件将生成在 app/Even...

自定义域名解析神器 dnsmasq

什么是 dnsmasq？dnsmasq 是一个轻量级、功能强大的网络服务工具，专为小型和中等规模网络设计。它是一个综合的网络基础设施解决方案[1]。dnsmasq 能做什么？功能说明应用场景DNS 转发与缓存将 DNS 查询转发到上游服务器（ISP、Google DNS 等），并在本地缓存结果加快 DNS 查询速度，减少外部 DNS 流量本地 DNS解析本地网络设备的主机名，无需编辑&n...

老程序员博客