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

高性能网络协议栈

访客技术 2026年5月24日 3

1、非修改序列算法

此类算法不改变输入容器的元素内容。

1.1 查找操作

find(first, last, value)：在指定范围内查找首个与目标值匹配的元素，返回其迭代器（未找到则返回尾迭代器）。
find_if(first, last, pred)：定位第一个满足条件的元素。
find_end(first, last, sub_first, sub_last)：在主序列中寻找子序列最后一次出现的位置。

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'; // 输出: 5
}

// 找出第一个大于6的数
auto first_gt_six = std::find_if(data.begin(), data.end(), [](int x) {
    return x > 6;
});
std::cout << "First >6: " << *first_gt_six << '\n'; // 输出: 7

// 查找子序列[3,5]的起始位置
std::vector<int> pattern = {3, 5};
auto match_pos = std::find_end(data.begin(), data.end(), pattern.begin(), pattern.end());
if (match_pos != data.end()) {
    std::cout << "Pattern starts at index: " << (match_pos - data.begin()) << '\n'; // 输出: 1
}

1.2 统计函数

count(first, last, value)：统计等于特定值的元素数量。
count_if(first, last, pred)：计算满足谓词条件的元素个数。

std::vector<int> nums = {1, 2, 3, 2, 4, 2};
int count_two = std::count(nums.begin(), nums.end(), 2); // 3
int even_count = std::count_if(nums.begin(), nums.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& x) {
    x *= 2; // 每个元素翻倍
});
// 值变为: [2, 4, 6, 8, 10]

1.4 比较范围

equal(first1, last1, first2)：判断两个等长范围是否完全一致。
mismatch(first1, last1, first2)：返回第一个不匹配的位置对。

std::vector<int> a = {1, 2, 3};
std::vector<int> b = {1, 2, 4};
std::vector<int> c = {1, 2, 3, 4};

bool is_equal = std::equal(a.begin(), a.end(), b.begin()); // false
auto mismatch_pair = std::mismatch(a.begin(), a.end(), c.begin());
if (mismatch_pair.first != a.end()) {
    std::cout << "Mismatch: " << *mismatch_pair.first << " vs " << *mismatch_pair.second << '\n';
}

1.5 条件验证

检查所有、任意或无元素满足某条件

std::vector<int> numbers = {2, 4, 6, 8};
bool all_even = std::all_of(numbers.begin(), numbers.end(), [](int x) {
    return x % 2 == 0;
}); // true

bool has_odd = std::any_of(numbers.begin(), numbers.end(), [](int x) {
    return x % 2 != 0;
}); // false

bool no_negative = std::none_of(numbers.begin(), numbers.end(), [](int x) {
    return x < 0;
}); // true

2、修改序列算法

这些函数会直接更改原容器中的数据。

2.1 复制与筛选复制

copy(first, last, dest)：将源范围复制到目标位置。
copy_if(first, last, dest, pred)：仅复制满足条件的元素。

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

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

// 仅复制偶数
std::vector<int> evens;
std::copy_if(source.begin(), source.end(), std::back_inserter(evens), [](int x) {
    return x % 2 == 0;
}); // evens: [2,4]

提示：std::back_inserter 可自动扩容，无需预分配空间。

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;
}); // squares: [1,4,9]

// 双参数变换：两向量对应项相加
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;
}); // sum: [5,7,9]

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> data = {1, 2, 3, 2, 5};

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

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

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

2.4 删除逻辑处理

remove(first, last, value)：将匹配项"移至末尾"，返回新逻辑结尾。
remove_if(first, last, pred)：移动满足条件的元素到末尾。

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

// 移除所有2（逻辑删除）
auto new_end = std::remove(list.begin(), list.end(), 2); // list: [1,3,4,2,2]
list.erase(new_end, list.end()); // 物理清除尾部冗余元素

// 使用lambda删除偶数
list = {1, 2, 3, 4, 5};
list.erase(std::remove_if(list.begin(), list.end(), [](int x) {
    return x % 2 == 0;
}), list.end()); // list: [1,3,5]

2.5 去重

移除连续重复元素，需配合 erase 实现物理去重

std::vector<int> raw = {1, 1, 2, 2, 3, 3, 3, 4, 5};
auto end_iter = std::unique(raw.begin(), raw.end());
raw.erase(end_iter, raw.end()); // 去重后: [1,2,3,4,5]

2.6 反转顺序

反转范围内元素的排列

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

2.7 旋转操作

以指定位置为轴心旋转元素

std::vector<int> arr = {1, 2, 3, 4, 5};
std::rotate(arr.begin(), arr.begin() + 2, arr.end()); // 从第3个元素开始旋转 → [3,4,5,1,2]

2.8 随机打乱

随机重新排列元素顺序（需支持C++11及以上）

#include <random>
#include <algorithm>

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

3、排序相关算法

3.1 排序方式

sort(first, last)：快速排序（不稳定），平均时间复杂度 $O(n \log n)$。
stable_sort(first, last)：归并排序，保持相等元素原始顺序。
partial_sort(first, mid, last)：仅保证前半部分为最小的元素且已排序。

std::vector<int> data = {5, 3, 1, 4, 2};
std::sort(data.begin(), data.end()); // 升序: [1,2,3,4,5]
std::sort(data.begin(), data.end(), std::greater<int>()); // 降序: [5,4,3,2,1]

std::vector<std::pair<int, int>> pairs = {{1,2}, {2,1}, {1,1}, {2,2}};
std::stable_sort(pairs.begin(), pairs.end(), [](const auto& a, const auto& b) {
    return a.first < b.first;
});

std::vector<int> nums = {5, 3, 1, 4, 2, 6};
std::partial_sort(nums.begin(), nums.begin() + 3, nums.end()); // 前3小元素排好序

3.2 第k小元素

使指定位置的元素成为排序后的第k个元素，左右两侧分别小于等于和大于等于它

std::vector<int> vals = {5, 3, 1, 4, 2, 6};
std::nth_element(vals.begin(), vals.begin() + 2, vals.end()); // 索引2处是第3小的数（值为3）

3.3 二分查找系列

要求输入范围必须有序

binary_search(first, last, value)：判断是否存在该值。
lower_bound(first, last, value)：返回第一个不小于目标值的位置。
upper_bound(first, last, value)：返回第一个大于目标值的位置。

std::vector<int> sorted = {1, 3, 3, 5, 7};

bool found = std::binary_search(sorted.begin(), sorted.end(), 3); // true
auto lb = std::lower_bound(sorted.begin(), sorted.end(), 3); // 指向第一个3
auto ub = std::upper_bound(sorted.begin(), sorted.end(), 3); // 指向5

3.4 合并有序序列

合并两个已排序范围成一个新有序序列

std::vector<int> left = {1, 3, 5};
std::vector<int> right = {2, 4, 6};
std::vector<int> merged(left.size() + right.size());

std::merge(left.begin(), left.end(), right.begin(), right.end(), merged.begin());
// merged: [1,2,3,4,5,6]

4、堆操作算法

提供基于堆结构的操作接口

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 = heap_data.back(); // 取出最大值
heap_data.pop_back();

std::sort_heap(heap_data.begin(), heap_data.end()); // 排序为升序

5、极值查找算法

5.1 最大/最小值比较

min(a, b) / max(a, b)：返回两个值中的极值。
min({...}) / max({...})：支持初始化列表。

int a = 5, b = 3;
int min_val = std::min(a, b); // 3
auto max_from_list = std::max({4, 2, 8, 5, 1}); // 8

5.2 迭代器级极值

min_element(first, last)：返回最小值的迭代器。
max_element(first, last)：返回最大值的迭代器。

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

5.3 同时获取最值

返回最小和最大元素的迭代器对

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

6、数值计算算法（来自 `<numeric>`）

6.1 累加求和

计算范围内的总和或自定义运算

#include <numeric>

std::vector<int> nums = {1, 2, 3, 4, 5};
int total = std::accumulate(nums.begin(), nums.end(), 0); // 15
int prod = std::accumulate(nums.begin(), nums.end(), 1, std::multiplies<int>()); // 120

6.2 内积计算

计算两个序列对应项乘积之和

std::vector<int> a = {1, 2, 3};
std::vector<int> 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_sum(src.size());
std::partial_sum(src.begin(), src.end(), partial_sum.begin()); // [1,3,6,10,15]

6.5 相邻差值

计算相邻元素之间的差值

std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> diff(src.size());
std::adjacent_difference(src.begin(), src.end(), diff.begin()); // [1,1,1,1,1]

7、其他实用工具

7.1 生成填充

使用函数对象填充范围

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

7.2 有限生成

仅填充前n个元素

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

7.3 包含性检查

判断一个有序范围是否包含另一个

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

7.4 集合运算

执行标准集合操作

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_union(set_a.begin(), set_a.end(), set_b.begin(), set_b.end(), std::back_inserter(result));

// 交集
result.clear();
std::set_intersection(set_a.begin(), set_a.end(), set_b.begin(), set_b.end(), std::back_inserter(result));

// 差集（a - b）
result.clear();
std::set_difference(set_a.begin(), set_a.end(), set_b.begin(), set_b.end(), std::back_inserter(result));

// 对称差集（(a ∪ b) - (a ∩ b)）
result.clear();
std::set_symmetric_difference(set_a.begin(), set_a.end(), set_b.begin(), set_b.end(), std::back_inserter(result));

8、常见问题解析

sort 和 stable_sort 的区别？

sort 使用 introsort（快排+堆排混合），性能高，但不保证相等元素顺序。
stable_sort 使用归并排序，稳定，但额外占用内存。

为何 remove 要搭配 erase？ remove 只将要删的元素"移"到末尾，不改变容器大小。真正的删除需调用 erase 清除尾部冗余部分。
哪些算法依赖有序性？二分查找类（binary_search, lower_bound, upper_bound）、集合运算（set_intersection 等）、merge 等均要求输入已排序，否则结果不可靠。

标签: STL C++算法容器序列操作

返回列表

上一篇：STM32F103C8T6与DM9051以太网接口实现方案

下一篇：OpenAI Java SDK 企业级应用架构实践：三种核心模式与性能优化

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

老程序员博客