前言
“非变易算法”这个说法来自早期 SGI STL 的文档分类，指的是不修改容器中元素、不改变元素顺序的一组算法，例如查找、计数、比较、遍历。C++ 标准里对应的章节标题是“不修改序列的操作”（non-modifying sequence operations），两者大体对应，但用词并不完全一致。阅读标准或 cppreference 时，按英文术语查更准确。
这里有一个容易误解的地方：std::for_each被归入非变易算法，但它传入的函数对象完全可以通过引用修改元素。分类的依据是算法本身不改变序列的结构与长度，而不是“保证元素只读”。真正保证只读的，是你传进去的仿函数是否接收const引用。
另一个常见误解是把std::lower_bound、std::binary_search也当成普通查找随便用。它们要求区间已经按同一比较规则有序（或至少相对目标值 partitioned），对无序区间使用是逻辑错误；标准不会替你检查，结果也没有意义。
本文按“查找、计数与比较、有序区间上的二分、遍历与谓词”四组介绍这些算法，说明各自的前置条件与复杂度，给出一个完整示例，并列出最容易踩的坑。
一、查找类算法
查找类算法都返回迭代器，找不到时返回区间的end()。判断结果必须与end()比较，不能与nullptr比较，也不能假定“找不到返回最后一个元素”。
| 算法 | 作用 | 复杂度 |
|---|
std::find(first, last, value) | 查找第一个等于 value 的元素 | 至多 N 次比较 |
std::find_if(first, last, pred) | 查找第一个满足谓词的元素 | 至多 N 次谓词调用 |
std::find_if_not(first, last, pred) | 查找第一个不满足谓词的元素 | 至多 N 次谓词调用 |
std::find_end(first, last, s_first, s_last) | 查找子序列最后一次出现的位置 | 最坏为 N×M 次比较 |
std::find_first_of(first, last, s_first, s_last) | 查找第一个属于给定集合的元素 | 最坏为 N×M 次比较 |
std::adjacent_find(first, last) | 查找第一对相邻且相等的元素 | 至多 N-1 次比较 |
std::search(first, last, s_first, s_last) | 查找子序列第一次出现的位置 | 最坏为 N×M 次比较 |
std::search_n(first, last, count, value) | 查找连续 count 个等于 value 的位置 | 至多 N 次比较 |
find_end与search的区别值得记清：前者找子序列的最后一次出现，后者找第一次。二者都返回子序列起始位置的迭代器，找不到返回外层区间的last。
std::search在 C++17 增加了接受“搜索器”（searcher）的重载，标准库提供了std::default_searcher、std::boyer_moore_searcher、std::boyer_moore_horspool_searcher（定义在<functional>）。后两者在长文本上通常更快，但需要目标类型支持哈希，且构造搜索器本身有开销；是否需要取决于数据规模，应当测量而不是想当然。
关联容器（std::map、std::set、std::unordered_map）有自己的成员find，复杂度是对数或平均常数。对它们调用std::find会退化成线性扫描，应当优先使用成员函数。
二、计数、比较与遍历
std::count与std::count_if返回满足条件的元素个数，类型是迭代器的difference_type，通常是std::ptrdiff_t，不是int，也不是size_t。把结果直接与无符号数比较可能触发符号转换警告。
std::equal比较两个区间是否逐元素相等。三参数版本只接收第二个区间的起始迭代器，它假定第二个区间至少与第一个区间一样长；如果实际更短，会读越界，属于未定义行为。C++14 起有四参数版本，可以同时给出第二个区间的末尾，安全地处理长度不同的情况。C++20 的std::ranges::equal可以直接接收两个范围。
std::mismatch返回一对迭代器，分别指向两个区间中第一对不相等的元素。它适合“找出从哪里开始不同”，比equal提供更多信息。
std::for_each对区间内每个元素调用一次函数对象，返回该函数对象的副本（C++11 起返回std::move(f)）。如果函数对象内部累计了状态，可以通过返回值取出；但要注意算法内部操作的是函数对象的副本，直接读取传入的那个对象是拿不到累计结果的。
std::for_each_n是 C++17 新增的版本，接收起始迭代器与元素个数，适合只知道长度、不方便取得尾迭代器的场景。
这些算法都可能接受执行策略（C++17 的并行算法重载），例如std::execution::par。使用前要确认标准库实现了并行后端，并注意并行版本对谓词的要求更严格：谓词不能修改共享状态，否则会引入数据竞争。
三、有序区间上的二分算法
std::binary_search、std::lower_bound、std::upper_bound、std::equal_range都要求区间相对于给定比较规则有序。它们的复杂度是对数级，但前提是数据已经排好序；对无序数据使用，结果没有定义意义上的正确性可言。
| 算法 | 返回值 | 含义 |
|---|
binary_search | bool | 是否存在等价元素 |
lower_bound | 迭代器 | 第一个不小于给定值的元素 |
upper_bound | 迭代器 | 第一个大于给定值的元素 |
equal_range | pair<iterator, iterator> | 等价元素构成的半开区间 |
lower_bound与upper_bound配合可以数出等价元素的个数：二者相减。对std::multiset、std::multimap这类允许重复的容器，成员函数equal_range是更直接的写法。
比较规则必须一致。如果排序用std::less<>，查找却传了一个自定义的“按绝对值比较”，二分的前提就被破坏，结果不可预期。自定义类型要么重载operator<，要么在排序和查找时传同一个比较器。
std::binary_search只回答“在不在”，不告诉你位置。需要位置时用lower_bound；需要判断找到的元素是否真的等价时，还要检查it != end && !(value < *it) && !(*it < value)，或者直接比较*it == value（若类型支持相等比较）。
四、完整示例
下面的示例在一组传感器读数上演示查找、相邻重复检测、计数、全称判断、变换与二分查找。
// 适用于 C++17
#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>
struct Reading {
std::string sensor;
double value;
};
int main() {
std::vector<Reading> data = {
{"t1", 20.5}, {"t1", 21.0}, {"t2", 19.8},
{"t2", 19.8}, {"t3", 25.1}
};
const double limit = 24.0;
auto over = std::find_if(
data.begin(), data.end(),
[limit](const Reading& r) { return r.value > limit; });
if (over != data.end()) {
std::cout << over->sensor << ' ' << over->value << '\n';
}
auto repeated = std::adjacent_find(
data.begin(), data.end(),
[](const Reading& a, const Reading& b) {
return a.sensor == b.sensor && a.value == b.value;
});
if (repeated != data.end()) {
std::cout << "repeat: " << repeated->sensor << '\n';
}
auto high = std::count_if(
data.begin(), data.end(),
[](const Reading& r) { return r.value >= 21.0; });
std::cout << "high count: " << high << '\n';
bool all_positive = std::all_of(
data.begin(), data.end(),
[](const Reading& r) { return r.value > 0.0; });
std::cout << std::boolalpha << all_positive << '\n';
std::vector<double> values;
values.reserve(data.size());
std::transform(
data.begin(), data.end(), std::back_inserter(values),
[](const Reading& r) { return r.value; });
std::sort(values.begin(), values.end());
auto lb = std::lower_bound(values.begin(), values.end(), 21.0);
std::cout << "first >= 21.0 at index "
<< (lb - values.begin()) << '\n';
std::vector<double> prefix = {19.8, 19.8, 20.5};
bool same = std::equal(prefix.begin(), prefix.end(), values.begin());
std::cout << same << '\n';
return 0;
}按标准语义推演：find_if找到第一个大于 24.0 的读数，即t3的 25.1；adjacent_find用自定义谓词找到t2的两条重复记录；count_if数出大于等于 21.0 的读数有 2 条；all_of判断全部为正，结果为 true。values排序后是 19.8、19.8、20.5、21.0、25.1，lower_bound(21.0)指向下标 3。std::equal比较三个元素，前缀恰好是排序后的前三个，结果为 true。
示例中std::equal的三参数版本是安全的，因为values至少有 3 个元素。真实代码里如果无法保证长度，应改用四参数版本，先比较两个区间的距离。
常见坑点
- ❌ 对无序的
std::vector直接调用std::lower_bound。
✅ 先用同一比较器排序，或改用std::find做线性查找。
- ❌ 把
std::find的结果与nullptr比较。
✅ 与容器的end()比较：if (it != c.end())。
- ❌ 在
std::for_each的仿函数里累加计数，然后读取传入的那个仿函数对象。
✅ 接收for_each的返回值，因为算法操作的是函数对象的副本。
- ❌ 用三参数
std::equal比较两个长度未知的区间。
✅ 用四参数版本同时给出第二个区间的末尾，或先比较std::distance。
- ❌ 把
std::count的返回值存入int，在大容器上溢出。
✅ 用auto或迭代器的difference_type接收。
- ❌ 对
std::map使用std::find(m.begin(), m.end(), key)。
✅ 用成员函数m.find(key)，复杂度从线性降为对数。
- ❌ 谓词里修改元素或修改外部共享变量，尤其是在并行算法中。
✅ 谓词保持无副作用；需要修改时用std::transform或显式循环，并自行处理同步。
- ❌ 认为
std::search与std::find_first_of等价。
✅ 前者找完整子序列，后者找“任意一个属于集合的元素”，语义完全不同。
总结
| 类别 | 代表算法 | 前置条件 |
|---|
| 线性查找 | find、find_if、adjacent_find、search | 无，O(N) |
| 计数与比较 | count、count_if、equal、mismatch | 无，O(N) |
| 全称判断 | all_of、any_of、none_of | 无，O(N) |
| 遍历 | for_each、for_each_n | 无，O(N) |
| 二分查找 | lower_bound、upper_bound、equal_range、binary_search | 区间有序，O(log N) |
“非变易”描述的是算法不改变序列结构，而不是元素绝对只读。使用这批算法时，先确认数据是否有序，再确认谓词是否无副作用，最后确认返回值的类型与比较对象。把这三件事做对，绝大多数查找和统计代码都能写得既短又可靠。
