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

C++ STL 算法精要指南

访客技术 2026年6月12日 1

1. 只读算法（不修改容器）

这类算法仅读取容器内的元素，不会改变数据本身。

1.1 find 与 find_if

find(b, e, val)：搜索首个等于 val 的元素，返回迭代器；若未找到则返回 e。
find_if(b, e, pred)：搜索首个满足谓词 pred 的元素。
find_end(b, e, sb, se)：查找子序列 [sb, se) 在容器中最后一次出现的位置。

std::vector<int> data = {2, 4, 6, 8, 10};
auto pos = std::find(data.begin(), data.end(), 6);
if (pos != data.end()) {
    // 输出 *pos == 6
}

auto first_gt7 = std::find_if(data.begin(), data.end(),
                              [](int v){ return v > 7; });
// first_gt7 指向 8

std::vector<int> pattern = {4, 6};
auto last_occ = std::find_end(data.begin(), data.end(),
                               pattern.begin(), pattern.end());
// last_occ 指向 4（唯一出现）

1.2 count 与 count_if

count(b, e, val)：统计等于 val 的元素数。
count_if(b, e, pred)：统计满足 pred 的元素数。

std::vector<int> vals = {5, 3, 5, 1, 5};
auto cnt5 = std::count(vals.begin(), vals.end(), 5);  // cnt5 = 3
auto odd_cnt = std::count_if(vals.begin(), vals.end(),
                              [](int x){ return x % 2 != 0; });
// odd_cnt = 4（3个5和1个1）

1.3 for_each

对范围内每一元素执行可调用对象。

std::vector<int> nums = {10, 20, 30};
std::for_each(nums.begin(), nums.end(), [](int& n){ n += 5; });
// nums 变为 {15, 25, 35}

1.4 equal 与 mismatch

equal(b1, e1, b2)：比较两个范围是否逐元素相等。
mismatch(b1, e1, b2)：返回一对迭代器指向首个不同元素的位置。

std::vector<int> lhs = {1,2,3};
std::vector<int> rhs = {1,2,4};
bool eq = std::equal(lhs.begin(), lhs.end(), rhs.begin()); // false

auto diff = std::mismatch(lhs.begin(), lhs.end(), rhs.begin());
if (diff.first != lhs.end()) {
    // *diff.first = 3, *diff.second = 4
}

1.5 all_of, any_of, none_of

分别检查是否全部/至少一个/没有元素满足条件。

std::vector<int> evens = {2,4,6,8};
bool all_even = std::all_of(evens.begin(), evens.end(),
                             [](int x){ return x%2==0; }); // true
bool has_odd = std::any_of(evens.begin(), evens.end(),
                            [](int x){ return x%2!=0; }); // false
bool none_neg = std::none_of(evens.begin(), evens.end(),
                              [](int x){ return x<0; }); // true

2. 修改序列算法

这些算法会改变容器内元素的值或顺序。

2.1 copy 与 copy_if

copy(b, e, out)：将 [b,e) 元素复制到 out 起始位置。
copy_if(b, e, out, pred)：仅复制满足 pred 的元素。

std::vector<int> src = {1,2,3,4,5};
std::vector<int> dst(5);
std::copy(src.begin(), src.end(), dst.begin()); // dst: {1,2,3,4,5}

std::vector<int> odds;
std::copy_if(src.begin(), src.end(),
             std::back_inserter(odds), [](int x){ return x%2!=0; });
// odds: {1,3,5} (使用 back_inserter 无需预分配)

2.2 transform

对元素施行变换并输出到目标范围，支持一元或二元操作。

std::vector<int> orig = {1,2,3};
std::vector<int> cubed(3);
std::transform(orig.begin(), orig.end(), cubed.begin(),
               [](int x){ return x*x*x; }); // cubed: {1,8,27}

std::vector<int> b = {4,5,6};
std::vector<int> sums(3);
std::transform(orig.begin(), orig.end(), b.begin(), sums.begin(),
               std::plus<int>());          // sums: {5,7,9}

2.3 replace, replace_if, replace_copy

replace(b,e,old,new)：原地替换所有 old 为 new。
replace_if(b,e,pred,new)：原地替换满足 pred 的元素。
replace_copy(b,e,out,old,new)：复制到新容器时执行替换，原容器不变。

std::vector<int> nums = {1,2,3,2,4};
std::replace(nums.begin(), nums.end(), 2, 99); // nums: {1,99,3,99,4}

std::replace_if(nums.begin(), nums.end(),
                [](int x){ return x>50; }, 0); // {1,0,3,0,4}

std::vector<int> result;
std::replace_copy(nums.begin(), nums.end(),
                  std::back_inserter(result), 3, 300);
// result: {1,0,300,0,4} , nums 不变

2.4 remove, remove_if 与 erase 惯用法

remove 将待删元素移到末尾并返回新逻辑结尾，不改变容器大小；必须配合 erase 完成物理删除。

std::vector<int> vals = {1,2,3,2,4};
auto it = std::remove(vals.begin(), vals.end(), 2);
vals.erase(it, vals.end()); // vals: {1,3,4}

// 删除所有偶数（remove_if 版）
vals = {1,2,3,4,5,6};
vals.erase(std::remove_if(vals.begin(), vals.end(),
                           [](int x){ return x%2==0; }),
           vals.end()); // vals: {1,3,5}

2.5 unique

移除连续重复元素，仅保留第一个实例。需搭配 erase 收缩容器。

std::vector<int> dup = {1,1,2,2,2,3,4,4};
auto last = std::unique(dup.begin(), dup.end());
dup.erase(last, dup.end()); // dup: {1,2,3,4}

2.6 reverse

反转范围内元素顺序。

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

2.7 rotate

将指定中间元素变成新的首元素。

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

2.8 shuffle

随机打乱序列（C++11 起）。

#include <random>
std::vector<int> data = {10,20,30,40,50};
std::random_device rd;
std::mt19937 gen(rd());
std::shuffle(data.begin(), data.end(), gen);

3. 排序与相关算法

3.1 sort, stable_sort, partial_sort

sort(b,e)：不稳定排序（内省排序），O(n log n)。
stable_sort(b,e)：稳定排序，保留相等元素相对顺序。
partial_sort(b,m,e)：将最小的 m-b 个元素排到前面并有序。

std::vector<int> unsorted = {7,2,5,1,3};
std::sort(unsorted.begin(), unsorted.end()); // {1,2,3,5,7}
std::sort(unsorted.begin(), unsorted.end(), std::greater<int>()); // {7,5,3,2,1}

// stable_sort 示例：按 pair.first 稳定排序
std::vector<std::pair<int,int>> ps = {{1,9},{2,8},{1,7}};
std::stable_sort(ps.begin(), ps.end(),
                 [](auto& a, auto& b){ return a.first < b.first; });
// 结果: (1,9),(1,7),(2,8)  — first=1 的元素保持原相对顺序

std::vector<int> big = {4,6,2,8,1,9};
std::partial_sort(big.begin(), big.begin()+3, big.end());
// 前3个元素为 {1,2,4}，剩余为 {8,6,9}

3.2 nth_element

将第 k 小元素放到正确位置，左侧元素 ≤ 它，右侧元素 ≥ 它。

std::vector<int> nums = {9,3,1,7,5};
std::nth_element(nums.begin(), nums.begin()+2, nums.end());
// nums[2] == 5，左元素 ≤5，右元素 ≥5

3.3 binary_search, lower_bound, upper_bound

前提：容器必须已排序。

binary_search(b,e,val)：返回 bool 表示是否存在。
lower_bound(b,e,val)：首个 >= val 的元素。
upper_bound(b,e,val)：首个 > val 的元素。

std::vector<int> sorted = {1,3,5,5,7};
bool ok = std::binary_search(sorted.begin(), sorted.end(), 5); // true
auto lb = std::lower_bound(sorted.begin(), sorted.end(), 5); // 索引2
auto ub = std::upper_bound(sorted.begin(), sorted.end(), 5); // 索引4

3.4 merge

合并两个有序序列到新容器（仍有序）。

std::vector<int> a = {1,4,7};
std::vector<int> b = {2,3,8};
std::vector<int> merged(6);
std::merge(a.begin(), a.end(), b.begin(), b.end(), merged.begin());
// merged: {1,2,3,4,7,8}

4. 堆操作

std::vector<int> heap = {2,4,1,3,5};
std::make_heap(heap.begin(), heap.end());           // 最大堆: {5,4,2,3,1}

heap.push_back(6);
std::push_heap(heap.begin(), heap.end());           // 加入6

std::pop_heap(heap.begin(), heap.end());            // 6移到末尾
int top = heap.back(); heap.pop_back();             // 取出最大元素

std::sort_heap(heap.begin(), heap.end());           // 堆排序后升序

5. 最小/最大值算法

int m = std::min(10, 5);           // 5
int M = std::max(10, 5);           // 10
auto small = std::min({8,3,5,2});  // 2

std::vector<int> sample = {4,9,2,7};
auto it_min = std::min_element(sample.begin(), sample.end()); // 指向2
auto it_max = std::max_element(sample.begin(), sample.end()); // 指向9

auto both = std::minmax_element(sample.begin(), sample.end());
// both.first → 2, both.second → 9

6. 数值算法（<numeric>）

6.1 accumulate

#include <numeric>
std::vector<int> v = {1,2,3,4};
int sum = std::accumulate(v.begin(), v.end(), 0);   // 10
int prod = std::accumulate(v.begin(), v.end(), 1,
                            std::multiplies<int>()); // 24

6.2 inner_product

std::vector<int> u = {1,2,3};
std::vector<int> w = {4,5,6};
int dot = std::inner_product(u.begin(), u.end(), w.begin(), 0); // 32

6.3 iota

std::vector<int> seq(5);
std::iota(seq.begin(), seq.end(), 100); // {100,101,102,103,104}

6.4 partial_sum

std::vector<int> inp = {1,2,3,4,5};
std::vector<int> out(5);
std::partial_sum(inp.begin(), inp.end(), out.begin()); // {1,3,6,10,15}

6.5 adjacent_difference

std::vector<int> src = {10,20,30,40};
std::vector<int> diff(4);
std::adjacent_difference(src.begin(), src.end(), diff.begin());
// {10, 10, 10, 10}（第一个元素被复制，后续为与前一个的差）

7. 其他常用算法

7.1 generate 与 generate_n

std::vector<int> buf(6);
int seed = 0;
std::generate(buf.begin(), buf.end(), [&seed](){ return seed += 2; });
// buf: {2,4,6,8,10,12}

std::vector<int> part(5);
std::generate_n(part.begin(), 3, [](){ static int n=0; return n++; });
// part: {0,1,2,0,0}（仅前3个被写）

7.2 includes

检查一个排序范围是否包含另一排序范围的全部。

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

7.3 集合运算（set_union, set_intersection, set_difference, set_symmetric_difference）

std::vector<int> A = {1,2,3,4,5};
std::vector<int> B = {3,4,5,6,7};
std::vector<int> res;

std::set_union(A.begin(), A.end(), B.begin(), B.end(),
               std::back_inserter(res)); // {1,2,3,4,5,6,7}

res.clear();
std::set_intersection(A.begin(), A.end(), B.begin(), B.end(),
                       std::back_inserter(res)); // {3,4,5}

res.clear();
std::set_difference(A.begin(), A.end(), B.begin(), B.end(),
                     std::back_inserter(res)); // {1,2}

res.clear();
std::set_symmetric_difference(A.begin(), A.end(), B.begin(), B.end(),
                               std::back_inserter(res)); // {1,2,6,7}

8. 常见问题与陷阱

sort vs stable_sort：sort 使用内省排序（不稳定），平均 O(n log n)；stable_sort 使用归并排序（稳定），O(n log n) 但需要额外内存。当相等元素相对顺序不重要时，优先用 sort。
为什么 remove 不直接删除元素？：remove 算法只做逻辑移动，不改变容器大小（它无法访问容器成员函数）。必须配合 erase(it, end()) 完成物理删除。这是 STL 算法与容器解耦的设计。
需要排序前置条件的算法：二分搜索系列（binary_search, lower_bound, upper_bound）、集合算法（set_union 等）、merge、includes 必须在有序范围上使用，否则结果未定义。

标签: C++STL

返回列表

上一篇：Flask与Vue构建社区运动场馆预约平台

下一篇：STM32平台NES模拟器实现方法

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...

老程序员博客