操作数据，而非容器
一、概述
泛型算法（Generic Algorithm） 是 C++ Standard Template Library (STL) 的核心组成部分，其本质是与容器类型无关的通用操作逻辑。通过模板和迭代器机制，泛型算法能够对任意满足迭代器接口的容器（如 vector、list、map）进行操作，实现代码复用和高度灵活性。
核心特征：
- 容器无关性：不依赖具体容器类型，只要求容器提供迭代器。
- 类型安全：通过模板参数推导类型，编译期检查错误。
- 高性能：针对不同容器底层数据结构优化（如
vector的连续内存访问、list的链表节点操作）。
STL 泛型算法可分为以下几类
| 类别 | 典型算法 | 功能描述 |
|---|---|---|
| 非修改序列算法 | for_each, count | 遍历或统计元素，不修改容器 |
| 修改序列算法 | copy, transform | 生成新序列或就地修改元素 |
| 排序与划分算法 | sort, partition | 重排元素顺序 |
| 二分搜索算法 | lower_bound, binary_search | 在有序序列中高效查找 |
| 集合算法 | set_union, includes | 对有序集合进行交、并、差操作 |
| 堆操作算法 | make_heap, push_heap | 实现堆数据结构操作 |
| 数值算法 | accumulate, inner_product | 数学运算（求和、内积等） |
二、泛型算法的原理
1、泛型算法的核心原则
-
算法与容器解耦
泛型算法不直接操作容器，而是通过迭代器（Iterator） 间接访问容器元素。迭代器作为中间层，屏蔽了不同容器的底层实现差异（如vector的连续内存、list的链表节点），使算法能统一处理所有支持迭代器的容器。 -
不改变容器结构
算法永远不会直接添加或删除容器元素，因此不会改变容器的大小（size）或容量（capacity）。这一设计保证了算法的通用性和安全性。std::vector<int> v = {3, 1, 4, 1, 5}; auto it = std::find(v.begin(), v.end(), 1); // 查找元素，但不修改容器
2、算法对元素的操作限制
| 允许的操作 | 禁止的操作 |
|---|---|
| 修改元素的值（如赋值） | 添加或删除元素 |
| 移动元素的位置 | 改变容器的容量或大小 |
-
允许：修改元素值
算法可以通过迭代器修改元素的值，例如std::replace替换指定值：std::replace(v.begin(), v.end(), 1, 9); // 将所有1替换为9 -
允许：移动元素位置
算法可以重新排列元素顺序，例如std::sort排序：std::sort(v.begin(), v.end()); // 元素按升序排列 -
禁止：改变容器大小
算法无法直接调用容器的insert()或erase()方法。之前有举过std::remove仅标记要删除的元素，需结合erase()完成实际删除的例子：auto new_end = std::remove(v.begin(), v.end(), 3); // 移动元素，不改变大小 v.erase(new_end, v.end()); // 真正删除元素
3、插入器（Inserter）的桥梁作用（算法不会直接不改变容器结构，只会借助其他工具）
-
插入器的功能
插入器是一种特殊迭代器，允许算法间接向容器添加元素。当对插入器赋值时，它会在底层容器上执行插入操作（如push_back、insert）。 -
插入器类型
插入器类型 底层操作 示例 std::back_inserter调用 push_back()适用于 vector、deque、liststd::front_inserter调用 push_front()适用于 deque、liststd::inserter调用 insert()指定位置通用型插入器 -
示例：使用插入器实现元素添加
#include <vector> #include <iterator> #include <algorithm>int main() {std::vector<int> src = {1, 2, 3};std::vector<int> dest;// 通过back_inserter间接添加元素std::copy(src.begin(), src.end(), std::back_inserter(dest));// dest变为{1, 2, 3}return 0; }
4、泛型算法的工作流程
-
输入阶段
算法接受一对迭代器（begin,end）定义操作范围，以及可能的辅助参数（如比较函数、插入器等）。 -
执行阶段
通过迭代器遍历元素，按需修改值或移动位置，但不改变容器结构。 -
输出阶段
返回结果可能是一个迭代器（如find返回找到的位置）或通过插入器间接操作容器。
流程图：
5、为什么禁止算法直接操作容器？
- 通用性：避免算法依赖具体容器的接口（如
vector::push_back和list::push_front不同）。 - 安全性：防止误操作导致容器状态不一致（如迭代器失效）。
- 性能：允许编译器优化迭代器操作（如连续内存的指针算术）。
5、泛型算法的核心特性
| 特性 | 说明 |
|---|---|
| 容器无关性 | 通过迭代器抽象，适配所有支持迭代器的容器 |
| 元素操作可控 | 可修改值或移动元素，但不改变容器大小 |
| 插入器的间接扩展 | 通过特殊迭代器间接添加元素，保持算法逻辑简洁 |
| 编译时类型安全 | 模板机制确保操作的类型匹配，避免运行时错误 |
三、基本泛型算法
理解算法的最基本的方法就是了解它们是否读取元素、改变元素或是重排元素顺序。
(1)总纲
1、泛型算法基本架构
-
输入范围机制
- 双迭代器界定：所有算法通过
[begin, end)半开区间操作元素sort(vec.begin(), vec.end()); // 对整个vector排序 find(lst.begin(), lst.end(), 42); // 在list中查找元素 - 容器无关性：算法不直接操作容器，仅通过迭代器间接访问
- 尾后迭代器：
end()指向最后一个元素的后一位，确保空范围安全
- 双迭代器界定：所有算法通过
-
参数通用模式
algorithm(first_iter, last_iter, [predicate/op]); // 示例：统计大于5的元素 count_if(v.begin(), v.end(), [](int x){return x > 5;});
2、算法行为分类
| 类型 | 特点 | 典型算法 |
|---|---|---|
| 观察型 | 不修改元素，仅读取 | find, count, accumulate |
| 修改型 | 直接修改元素值 | replace, fill, copy |
| 重排型 | 改变元素顺序但不修改值 | sort, reverse, shuffle |
// 观察型：查找元素位置
auto pos = find(v.begin(), v.end(), target);// 修改型：将所有负数替换为0
replace_if(v.begin(), v.end(), [](int x){return x < 0;}, 0);// 重排型：按自定义规则排序
sort(v.begin(), v.end(), [](int a, int b){return a%10 < b%10;});-
可组合性
// 组合排序与查找 sort(v.begin(), v.end()); auto it = lower_bound(v.begin(), v.end(), 42);
4、一些建议
-
掌握共性规律
- 所有算法都遵循
操作范围->处理元素->返回结果的流程 - 70%算法可归入"读/改/排"三大类
- 所有算法都遵循
-
关注关键参数
- 前两个参数必为输入范围
- 可选参数包括：谓词（判断条件）、输出位置、自定义操作函数
-
实践建议
// 从简单算法入手理解模式 vector<int> data {5,3,7,2};// 1. 使用find_if查找首个偶数 auto it = find_if(data.begin(), data.end(), [](int x){return x%2==0;});// 2. 用transform转换元素 transform(data.begin(), data.end(), data.begin(), [](int x){return x*2;});// 3. 结合sort和unique去重 sort(data.begin(), data.end()); auto last = unique(data.begin(), data.end()); data.erase(last, data.end());
(2)基本泛型算法
2.1观察型算法（只读）
核心定义
本质：仅读取输入范围内的元素，不修改容器内容或元素顺序的算法类型
设计目标：通过统一接口实现数据的安全观察与计算
核心特征
-
无副作用性
- 算法执行后保证原始数据完全不变
- 适用于需要保留原始数据场景（如统计分析、条件检测）
-
输入范围依赖
- 通过
[begin, end)迭代器对操作数据范围 - 典型参数结构：
result_type algorithm(first_iter, last_iter, [predicate]);
- 通过
-
谓词扩展性
- 支持通过谓词（Predicate）自定义读取逻辑
// 统计字符串长度大于5的元素 count_if(vec.begin(), vec.end(), [](const string& s){return s.size() >5;});
- 支持通过谓词（Predicate）自定义读取逻辑
常见算法分类
| 算法类型 | 典型代表 | 返回值类型 |
|---|---|---|
| 查找型 | find, search, adjacent_find | 迭代器（指向目标位置） |
| 计数型 | count, count_if | 整型数值（统计结果） |
| 比较型 | equal, mismatch | bool或差异位置对 |
| 累积型 | accumulate, inner_product | 计算值（如求和/内积） |
| 遍历型 | for_each | 可选的函数对象返回值 |
关键使用模式
// 示例1：查找首个满足条件的元素
vector<int> data {7, 4, 9, 2};
auto it = find_if(data.begin(), data.end(), [](int x){return x%3 ==0;}); // 返回指向9的迭代器// 示例2：跨容器元素比较
list<string> names {"Alice", "Bob"};
vector<string> tmp {"Alice", "Charlie"};
bool match_front = equal(names.begin(), names.end(), tmp.begin()); // 返回false// 示例3：数值计算
int sum = accumulate(data.begin(), data.end(), 0); // 7+4+9+2=22设计原则体现
-
统一性
所有只读算法遵循相同的迭代器接口规范，例如：// 所有查找类算法返回迭代器 auto pos1 = find(...); // 值查找 auto pos2 = search(...); // 子序列查找 -
泛型扩展
通过模板支持任意元素类型：// 对自定义类型有效 struct Person { string name; int age; }; vector<Person> people; auto elder = find_if(people.begin(), people.end(),[](const Person& p){return p.age >60;}); -
安全保证
即使操作无效范围也不会导致数据破坏：vector<int> empty_vec; // 安全操作：返回empty_vec.end() auto result = find(empty_vec.begin(), empty_vec.end(), 42);
应用场景建议
-
数据质量检查
// 验证容器中是否存在非法值 bool has_negative = any_of(data.begin(), data.end(),[](int x){return x <0;}); -
元数据分析
// 计算文本行平均长度 vector<string> lines = read_file(); int total = accumulate(lines.begin(), lines.end(), 0,[](int sum, const string& s){return sum + s.size();}); double avg = static_cast<double>(total)/lines.size(); -
预处理验证
// 排序前检查是否已有序 if(!is_sorted(data.begin(), data.end())) {sort(data.begin(), data.end()); }
注意事项
-
迭代器有效性
确保输入的迭代器范围[begin, end)构成有效区间 -
谓词纯度
谓词函数应当是无副作用的纯函数（不修改外部状态） -
性能选择
对已排序数据优先使用binary_search等优化算法：// 比线性查找更高效 bool exists = binary_search(sorted_data.begin(), sorted_data.end(), target);
2.2修改型算法 （算法不检查写操作）
核心概念
-
定义
通过迭代器修改容器元素值或结构的算法，属于修改型算法- 直接修改：在原容器上改变元素值（如
fill） - 输出写入：将结果写入另一个容器（如
transform）
- 直接修改：在原容器上改变元素值（如
-
统一接口特征
// 典型参数结构 algorithm(input_begin, input_end, [output_iter], [operation]);
常见算法分类
| 算法类型 | 典型代表 | 修改方式 | 关键特性 |
|---|---|---|---|
| 原位修改型 | fill, replace, generate | 直接修改输入范围内的元素 | 无需额外存储空间 |
| 拷贝输出型 | copy, transform | 将结果写入另一个容器 | 需要预分配输出空间 |
| 条件修改型 | replace_if, remove_if | 根据谓词选择性修改元素 | 常配合lambda使用 |
| 结构变更型 | remove, unique | 逻辑删除后需配合erase | 实际修改容器物理结构 |
详细解释
1. 填充与赋值
| 算法 | 功能 | 示例 |
|---|---|---|
std::fill | 将区间填充为指定值 | fill(v.begin(), v.end(), 0) |
std::generate | 通过函数生成值填充区间 | generate(v.begin(), v.end(), rand) |
std::iota | 填充递增序列（C++11 起） | iota(v.begin(), v.end(), 1) |
2. 元素转换
| 算法 | 功能 | 示例 |
|---|---|---|
std::transform | 对每个元素应用函数并写入目标位置 | transform(src.begin(), src.end(), dest.begin(), toupper) |
std::replace | 替换区间内的特定值 | replace(v.begin(), v.end(), 3, 10) |
std::replace_if | 按条件替换元素 | replace_if(v.begin(), v.end(), is_odd, 0) |
3. 删除与去重
| 算法 | 功能 | 示例 |
|---|---|---|
std::remove | 移除指定值（需配合 erase） | v.erase(remove(v.begin(), v.end(), 42), v.end()) |
std::remove_if | 按条件移除元素 | v.erase(remove_if(v.begin(), v.end(), is_negative), v.end()) |
std::unique | 移除相邻重复元素（需先排序） | v.erase(unique(v.begin(), v.end()), v.end()) |
4. 重新排列
| 算法 | 功能 | 示例 |
|---|---|---|
std::reverse | 反转区间元素顺序 | reverse(v.begin(), v.end()) |
std::rotate | 循环移动区间元素 | rotate(v.begin(), v.begin()+2, v.end()) |
std::shuffle | 随机打乱元素顺序（需随机引擎） | shuffle(v.begin(), v.end(), rand_gen) |
5. 复制与移动
| 算法 | 功能 | 示例 |
|---|---|---|
std::copy | 复制源区间到目标位置 | copy(src.begin(), src.end(), dest.begin()) |
std::move | 移动元素到目标位置（C++11 起） | move(src.begin(), src.end(), dest.begin()) |
使用场景
-
初始化容器
使用fill、generate或iota填充初始值。 -
数据清洗
通过remove、remove_if或unique删除无效或冗余数据。 -
数据转换
使用transform或replace修改元素格式或内容。 -
算法优化
通过reverse、rotate或shuffle调整数据顺序以满足特定需求。 -
数据迁移
使用copy或move将数据转移到其他容器。
核心写入方式
1. 原位直接修改
vector<int> vec(5);
fill(vec.begin(), vec.end(), 10); // 所有元素变为10
replace(vec.begin(), vec.end(), 10, 20); // 10替换为202. 输出到其他容器
vector<int> src {1,2,3}, dest;
// 需要确保dest有足够空间（或使用插入迭代器）
copy(src.begin(), src.end(), back_inserter(dest)); // 转换+写入模式
transform(src.begin(), src.end(), back_inserter(dest),[](int x){return x*2;}); // dest得到[2,4,6]3. 条件性修改
vector<int> data {5,-3,7,-2};
replace_if(data.begin(), data.end(), [](int x){return x <0;}, 0); // 负数替换为0auto new_end = remove_if(data.begin(), data.end(),[](int x){return x%2 ==0;}); // 逻辑删除偶数
data.erase(new_end, data.end()); // 物理删除关键注意事项
-
空间预分配
// 错误：未预分配空间 vector<int> dest; copy(src.begin(), src.end(), dest.begin()); // 崩溃！// 正确：使用插入迭代器 copy(src.begin(), src.end(), back_inserter(dest)); -
迭代器失效
vector<int> data {1,2,3,4}; auto it = data.begin(); fill(data.begin(), data.end(), 0); // 安全操作 data.push_back(5); // 使it可能失效 -
谓词副作用
// 错误示例：带副作用的谓词 int counter = 0; replace_if(data.begin(), data.end(),[&](int x){return ++counter >2;}, 0); // 结果不可预测
典型应用模式
// 数据清洗管道
vector<int> process_data(vector<int>& raw) {vector<int> result;// 1. 去除非正数remove_copy_if(raw.begin(), raw.end(), back_inserter(result),[](int x){return x <=0;});// 2. 数值规范化transform(result.begin(), result.end(), result.begin(),[](int x){return x*100;});// 3. 去重处理sort(result.begin(), result.end());auto last = unique(result.begin(), result.end());result.erase(last, result.end());return result;
}（3）重排型容器算法
1、重排型算法概述
重排型算法通过重新排列容器内元素的顺序实现特定目标，不改变元素值。这些算法定义在头文件 <algorithm> 中，部分需要 <random> 支持。核心特点如下：
- 不改变容器大小（除非配合
erase） - 依赖迭代器范围，支持不同容器
- 时间复杂度各异，需根据场景选择
| 类别 | 算法列表 | 用法说明 |
|---|---|---|
| 排序（Sorting） | sort, stable_sort, partial_sort | - sort(first, last)：对迭代器范围 [first, last) 内的元素进行排序。- stable_sort(first, last)：稳定排序，相同元素相对顺序不变。- partial_sort(first, middle, last)：部分排序，使 [first, middle) 有序，剩余元素无序。 |
| 反转（Reversing） | reverse | reverse(first, last)：反转迭代器范围 [first, last) 内元素的顺序。 |
| 旋转（Rotating） | rotate, rotate_copy | - rotate(first, middle, last)：将 [middle, last) 区间的元素移到 [first, last) 最前方。- rotate_copy(first, middle, last, dest)：旋转复制，结果存入 dest 开始的位置。 |
| 随机重排（Shuffling） | shuffle | shuffle(first, last, rng)：利用随机数生成器 rng（如 default_random_engine）对 [first, last) 内元素随机重排。 |
| 排列生成（Permutation） | next_permutation, prev_permutation | - next_permutation(first, last)：求下一个字典序排列，成功返回 true，否则 false。- prev_permutation(first, last)：求上一个字典序排列，成功返回 true，否则 false。 |
| 分区（Partitioning） | partition, stable_partition | - partition(first, last, pred)：按谓词 pred 分区，不保证元素相对顺序。- stable_partition(first, last, pred)：稳定分区，保留元素相对顺序。 |
2.关键算法详解
1. 排序算法
-
std::sort-
功能：对范围内的元素进行升序排序（默认）或自定义排序。
-
实现原理：通常为IntroSort（快速排序 + 堆排序的混合）。
-
时间复杂度：平均
O(n log n)，最坏O(n²)。 -
示例：
#include <vector> #include <algorithm>std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6}; std::sort(vec.begin(), vec.end()); // 默认升序 std::sort(vec.begin(), vec.end(), std::greater<int>()); // 降序
-
-
std::stable_sort - 示例：
struct Item { int id; int value; }; std::vector<Item> items = {{1,3}, {2,3}, {3,1}}; std::stable_sort(items.begin(), items.end(), [](const Item& a, const Item& b) {return a.value < b.value; // 按 value 排序，相同值保持插入顺序 }); // 结果顺序：{3,1}, {1,3}, {2,3} - 注意：时间复杂度 O(n log n)，内存占用较高。
- 特点：保持相等元素的原始相对顺序。
- 适用场景：需要稳定排序时（如按多字段排序）。
std::partial_sort
- 用途：部分排序（仅排序前 N 个元素）
- 示例：
std::vector<int> v = {9, 5, 2, 7, 4}; // 仅排序前3个元素，其余不保证顺序 std::partial_sort(v.begin(), v.begin() + 3, v.end()); // 结果：2,4,5,9,7（前3位有序，后两位无序） - 注意：时间复杂度 O(n log k)（k 为排序部分大小）。
2. 反转算法
-
std::reverse-
功能：反转容器中元素的顺序。
-
实现原理：交换首尾对称位置的元素。
-
时间复杂度：
O(n)。 -
示例：
std::vector<int> vec = {1, 2, 3, 4, 5}; std::reverse(vec.begin(), vec.end()); // 结果为 {5, 4, 3, 2, 1}
-
3. 旋转算法
-
std::rotate-
功能：将
[first, middle, last)范围内的元素左旋，使middle成为新的第一个元素。 -
时间复杂度：
O(n)。 -
示例：
std::vector<int> vec = {1, 2, 3, 4, 5}; auto mid = vec.begin() + 2; // 指向元素3 std::rotate(vec.begin(), mid, vec.end()); // 结果 {3, 4, 5, 1, 2}
-
std::rotate_copy
- 用途：旋转并拷贝到新容器，不修改原数据
- 示例：
std::vector<int> src = {1,2,3,4,5}; std::vector<int> dest(src.size()); std::rotate_copy(src.begin(), src.begin()+2, src.end(), dest.begin()); // dest: 3,4,5,1,2（原容器不变）
4. 随机重排算法
-
std::shuffle-
功能：随机打乱元素顺序。
-
依赖：需提供随机数生成器（如
std::mt19937）。 -
示例：
#include <random> std::vector<int> vec = {1, 2, 3, 4, 5}; std::random_device rd; std::mt19937 rng(rd()); std::shuffle(vec.begin(), vec.end(), rng);
-
- 注意：使用高质量随机数生成器（如
mt19937）。
5. 排列生成算法
-
std::next_permutation-
功能：按字典序生成下一个更大的排列。
-
返回值：
bool（若存在更小排列则返回false）。 -
示例：
#include <algorithm> #include <vector> #include <iostream> int main() {std::vector<int> v = {1,2,3}; do {// 依次输出：123, 132, 213, 231, 312, 321for (auto i : v) {std::cout << i;}std:: cout<<std::endl; } while (std::next_permutation(v.begin(), v.end())); }
-
std::prev_permutation
- 用途：生成下一个字典序更小的排列
- 示例：
#include <algorithm> #include <vector> #include <iostream> int main() {std::vector<int> v = {1,2,3}; do {// 依次输出：123, 132, 213, 231, 312, 321for (auto i : v) {std::cout << i;}std:: cout<<std::endl; } while (std::next_permutation(v.begin(), v.end()));std::vector<int> v1 = {3,2,1}; do {// 依次输出：321, 312, 231, 213, 132, 123for(auto i : v1) {std::cout << i;}std::cout << std::endl; } while (std::prev_permutation(v1.begin(), v1.end()));return 0; }
6. 分区算法
-
std::partition-
功能：根据谓词条件将元素分为满足条件和不满足条件的两组，并将满足条件的元素移到前端。
-
不保证稳定性（相等元素可能交换顺序）。
-
示例：
std::vector<int> vec = {1, 2, 3, 4, 5}; auto it = std::partition(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; }); // 偶数在前，奇数在后，如 {4, 2, 3, 1, 5}std::stable_partition - 用途：分区并保持元素相对顺序
- 示例：
#include <iostream> #include <vector> #include <algorithm>int main() {std::vector<int> v = {1,2,3,4,1,5};auto it = std::stable_partition(v.begin(), v.end(), [](int x) { return x < 3; });// 结果：1,2,1,3,4,5 → 1,2 保持顺序，剩余元素保持顺序for (auto i : v) {std::cout << i << " ";}return 0; } - 注意：时间复杂度 O(n)，但可能使用额外内存。
-
3.总结与选择建议
| 算法类型 | 典型场景 | 性能与特点 |
|---|---|---|
sort | 需要快速排序，不关心相等元素顺序 | O(n log n)，非稳定 |
stable_sort | 需保持相等元素原始顺序（如多字段排序） | O(n log n)，内存占用较高 |
partial_sort | 仅需前 N 个元素有序（如排行榜前10名） | O(n log k)，k 为部分排序大小 |
rotate | 循环移动元素（如缓冲区处理） | O(n) |
shuffle | 随机化数据（如游戏洗牌） | O(n)，依赖随机数生成器质量 |
next_permutation | 遍历所有排列（如密码破解、组合优化） | O(n) 单次调用 |
stable_partition | 分区且需保持元素顺序（如日志按级别分类） | O(n)，可能使用额外内存 |
四、如何去“定制”自己的算法呢？
1. 默认比较与自定义操作的必要性
C++标准库算法如sort默认使用<运算符比较元素。但在以下情况需自定义比较逻辑：
- 默认排序规则不适用：如按字符串长度而非字典序排序。
- 元素类型未定义
<运算符：如自定义结构体需按特定成员排序。
2. 向算法传递函数：以sort为例
sort的重载版本允许传入谓词（Predicate），自定义排序规则。
示例1：按字符串长度排序
#include <vector>
#include <algorithm>
#include <string>
#include <iostream>
#include <string_view>/*** @brief 比较两个字符串视图的长度，判断第一个字符串是否比第二个字符串短。* * @param first 第一个要比较的字符串视图。* @param second 第二个要比较的字符串视图。* @return true 如果 first 的长度小于 second 的长度。* @return false 如果 first 的长度大于或等于 second 的长度。*/
// 自定义比较函数（二元谓词）
bool isShorter(const std::string_view first, const std::string_view second) {return first.size() < second.size();
}int main() {std::vector<std::string> vec = {"apple", "banana", "cherry", "date"};std::sort(vec.begin(), vec.end(), isShorter); // 按长度升序排列for (const auto &str : vec) {std::cout << str << " (" << str.size() << "), ";}// 结果：date (4), apple (5), banana (6), cherry (6)return 0;
}3. 谓词的定义与分类
- 谓词：返回
bool的可调用对象（函数、函数对象、Lambda）。- 一元谓词：接受一个参数，如
find_if的条件判断。 - 二元谓词：接受两个参数，如
sort的比较操作。
- 一元谓词：接受一个参数，如
示例2：自定义结构体排序
struct Person {std::string name;int age;
};// 按年龄升序的二元谓词
/*** @brief 比较两个 Person 对象的年龄，判断第一个对象的年龄是否小于第二个对象的年龄。* * @param a 第一个要比较的 Person 对象的常量引用。* @param b 第二个要比较的 Person 对象的常量引用。* @return true 如果 a 的年龄小于 b 的年龄。* @return false 如果 a 的年龄大于或等于 b 的年龄。*/
#include <cassert>bool compareByAge(const Person &a, const Person &b, bool ascending = true) {if (ascending) {return a.age < b.age;}return a.age > b.age;
}int main() {std::vector<Person> people = {{"Alice", 30}, {"Bob", 25}, {"Charlie", 20}};// 升序排序std::sort(people.begin(), people.end(), [](const Person &a, const Person &b) {return compareByAge(a, b, true);});// 降序排序std::sort(people.begin(), people.end(), [](const Person &a, const Person &b) {return compareByAge(a, b, false);});return 0;
}4. 严格弱序条件
自定义二元谓词必须满足严格弱序，确保排序逻辑合理：
- 非自反性：
comp(a, a) == false。 - 不对称性：若
comp(a, b) == true，则comp(b, a) == false。 - 传递性：若
comp(a, b) && comp(b, c)，则comp(a, c)。 - 等价传递性：若
a与b等价，b与c等价，则a与c等价。
错误示例：使用<=破坏严格弱序
// 错误：违反非自反性和不对称性
bool badCompare(int a, int b) {return a <= b; // 若a == b，返回true，导致未定义行为
}5. 使用Lambda简化谓词
对于简单逻辑，Lambda表达式更便捷。
示例3：Lambda按结构体成员排序
struct Point { int x, y; };int main() {std::vector<Point> points = {{3, 5}, {1, 2}, {2, 4}};// 按 x 坐标升序排序std::sort(points.begin(), points.end(), [](const Point &a, const Point &b) { // 比较两个点的 x 坐标return a.x < b.x; });// 结果：{1,2}, {2,4}, {3,5}return 0;
}6.小结
- 自定义排序：通过传递二元谓词，覆盖
sort的默认<比较。 - 严格弱序：确保谓词满足条件，避免未定义行为。
- 灵活选择：函数、Lambda、函数对象均可作为谓词，按需使用。
再见咯
