2026-01-16

C++ STL 算法（Algorithms）详细指南

1. 功能说明

本指南基于 stl_algorithms.cpp 文件，详细介绍了 C++ 标准模板库（STL）中各种算法的使用方法和特性，包括：

排序算法：sort、partial_sort、stable_sort 等
查找算法：find、binary_search、lower_bound、upper_bound 等
修改算法：copy、fill、iota、reverse、random_shuffle 等
数值算法：accumulate、adjacent_difference 等
最值算法：minmax_element、min、max 等
计数算法：count、count_if 等
转换算法：transform 等
遍历算法：for_each 等
删除算法：remove、remove_if 等
去重算法：unique 等
合并算法：merge 等
分区算法：partition 等
逻辑算法：all_of、any_of、none_of 等
相等性算法：equal 等
包含算法：search 等

STL 算法是一组独立于容器的通用函数，它们通过迭代器操作容器中的元素，提供了丰富的操作功能，可以大大简化代码编写，提高开发效率。

2. 代码解析

2.1 排序算法

// 初始化一个整数向量
std::vector<int> nums = {5, 2, 8, 1, 9, 3, 7, 4, 6};

std::cout << "原始向量: ";
for (int x : nums) {
    std::cout << x << " ";
}
std::cout << std::endl;

std::cout << "\n=== 排序算法 ===" << std::endl;
// 升序排序
std::sort(nums.begin(), nums.end());
std::cout << "升序排序后: ";
for (int x : nums) {
    std::cout << x << " ";
}
std::cout << std::endl;

// 降序排序
std::sort(nums.begin(), nums.end(), std::greater<int>());
std::cout << "降序排序后: ";
for (int x : nums) {
    std::cout << x << " ";
}
std::cout << std::endl;

// 部分排序（前3个元素排序）
std::partial_sort(nums.begin(), nums.begin() + 3, nums.end());
std::cout << "部分排序（前3个元素）: ";
for (int x : nums) {
    std::cout << x << " ";
}
std::cout << std::endl;

解析：

std::sort：对指定范围内的元素进行排序，默认是升序排序
可以通过传入自定义比较函数来改变排序方式，如使用 std::greater<int>() 进行降序排序
std::partial_sort：对指定范围内的元素进行部分排序，只保证前 n 个元素是有序的
排序算法的时间复杂度通常为 O(n log n)

2.2 查找算法

std::cout << "\n=== 查找算法 ===" << std::endl;
// 先排序以便使用二分查找
std::sort(nums.begin(), nums.end());
// 线性查找
auto it = std::find(nums.begin(), nums.end(), 5);
if (it != nums.end()) {
    std::cout << "找到5，位置: " << (it - nums.begin()) << std::endl;
}

// 二分查找
bool exists = std::binary_search(nums.begin(), nums.end(), 7);
std::cout << "7 存在: " << (exists ? "是" : "否") << std::endl;

// 下界和上界
auto lower = std::lower_bound(nums.begin(), nums.end(), 5);
auto upper = std::upper_bound(nums.begin(), nums.end(), 5);
std::cout << "5的下界位置: " << (lower - nums.begin()) << std::endl;
std::cout << "5的上界位置: " << (upper - nums.begin()) << std::endl;

// 查找第一个满足条件的元素
auto firstEven = std::find_if(nums.begin(), nums.end(), 
                             [](int x) { return x % 2 == 0; });
if (firstEven != nums.end()) {
    std::cout << "第一个偶数: " << *firstEven << "，位置: " << (firstEven - nums.begin()) << std::endl;
}

解析：

std::find：线性查找指定值，返回第一个匹配元素的迭代器
std::binary_search：二分查找指定值，返回是否存在（要求容器已排序）
std::lower_bound：返回第一个不小于指定值的元素的迭代器（要求容器已排序）
std::upper_bound：返回第一个大于指定值的元素的迭代器（要求容器已排序）
std::find_if：查找第一个满足条件的元素，通过谓词函数指定条件

2.3 修改算法

std::cout << "\n=== 修改算法 ===" << std::endl;
std::vector<int> vec1 = {1, 2, 3, 4, 5};
std::vector<int> vec2(5);

// 复制元素
std::copy(vec1.begin(), vec1.end(), vec2.begin());
std::cout << "复制后的向量: ";
for (int x : vec2) {
    std::cout << x << " ";
}
std::cout << std::endl;

// 填充元素
std::fill(vec2.begin(), vec2.end(), 0);
std::cout << "填充0后: ";
for (int x : vec2) {
    std::cout << x << " ";
}
std::cout << std::endl;

// 生成递增序列
std::iota(vec2.begin(), vec2.end(), 1);
std::cout << "生成递增序列(1,2,3,4,5): ";
for (int x : vec2) {
    std::cout << x << " ";
}
std::cout << std::endl;

// 反转元素
std::vector<int> vec3 = {1, 2, 3, 4, 5};
std::reverse(vec3.begin(), vec3.end());
std::cout << "反转后: ";
for (int x : vec3) {
    std::cout << x << " ";
}
std::cout << std::endl;

// 随机打乱元素（C++11后推荐使用shuffle）
std::random_shuffle(vec3.begin(), vec3.end());
std::cout << "随机打乱后: ";
for (int x : vec3) {
    std::cout << x << " ";
}
std::cout << std::endl;

解析：

std::copy：将一个范围的元素复制到另一个范围
std::fill：将指定范围内的所有元素设置为给定值
std::iota：生成从给定值开始的递增序列
std::reverse：反转指定范围内的元素顺序
std::random_shuffle：随机打乱指定范围内的元素顺序（C++11后推荐使用 std::shuffle）

2.4 数值算法

std::cout << "\n=== 数值算法 ===" << std::endl;
std::vector<int> values = {1, 2, 3, 4, 5};
// 计算总和
int sum = std::accumulate(values.begin(), values.end(), 0);
std::cout << "总和: " << sum << std::endl;

// 计算乘积
int product = std::accumulate(values.begin(), values.end(), 1, std::multiplies<int>());
std::cout << "乘积: " << product << std::endl;

// 计算相邻元素的差
std::vector<int> diff(values.size() - 1);
std::adjacent_difference(values.begin(), values.end(), diff.begin());
std::cout << "相邻元素的差: ";
for (int x : diff) {
    std::cout << x << " ";
}
std::cout << std::endl;

解析：

std::accumulate：计算指定范围内元素的累加和，也可以通过自定义操作计算其他聚合值（如乘积）
std::adjacent_difference：计算指定范围内相邻元素的差值

2.5 最值算法

std::cout << "\n=== 最值算法 ===" << std::endl;
// 查找最小值和最大值
auto minMax = std::minmax_element(values.begin(), values.end());
std::cout << "最小值: " << *minMax.first << ", 最大值: " << *minMax.second << std::endl;

// 直接比较两个值
int a = 10, b = 20;
std::cout << "a和b的最小值: " << std::min(a, b) << std::endl;
std::cout << "a和b的最大值: " << std::max(a, b) << std::endl;

解析：

std::minmax_element：查找指定范围内的最小值和最大值，返回一个 pair 迭代器
std::min：返回两个值中的较小值
std::max：返回两个值中的较大值

2.6 计数算法

std::cout << "\n=== 计数算法 ===" << std::endl;
std::vector<int> countVec = {1, 2, 1, 3, 1, 4, 1};
// 计数元素出现次数
int count = std::count(countVec.begin(), countVec.end(), 1);
std::cout << "1出现的次数: " << count << std::endl;

// 计数满足条件的元素
int evenCount = std::count_if(countVec.begin(), countVec.end(),
                             [](int x) { return x % 2 == 0; });
std::cout << "偶数的个数: " << evenCount << std::endl;

解析：

std::count：计算指定值在范围内出现的次数
std::count_if：计算满足条件的元素在范围内出现的次数

2.7 转换算法

std::cout << "\n=== 转换算法 ===" << std::endl;
std::vector<int> original = {1, 2, 3, 4, 5};
std::vector<int> squared(5);
// 转换元素（计算平方）
std::transform(original.begin(), original.end(), squared.begin(),
               [](int x) { return x * x; });
std::cout << "平方值: ";
for (int x : squared) {
    std::cout << x << " ";
}
std::cout << std::endl;

// 两个序列的元素运算
std::vector<int> vecA = {1, 2, 3, 4, 5};
std::vector<int> vecB = {10, 20, 30, 40, 50};
std::vector<int> result(5);
std::transform(vecA.begin(), vecA.end(), vecB.begin(), result.begin(),
               [](int a, int b) { return a + b; });
std::cout << "两个向量的和: ";
for (int x : result) {
    std::cout << x << " ";
}
std::cout << std::endl;

解析：

std::transform：将指定范围内的元素转换后存储到另一个范围
可以处理单个序列的转换，也可以处理两个序列的元素级运算

2.8 遍历算法

std::cout << "\n=== 遍历算法 ===" << std::endl;
std::vector<int> forEachVec = {1, 2, 3, 4, 5};
// 遍历并修改元素
std::for_each(forEachVec.begin(), forEachVec.end(),
              [](int& x) { x *= 2; });
std::cout << "遍历后（乘以2）: ";
for (int x : forEachVec) {
    std::cout << x << " ";
}
std::cout << std::endl;

解析：

std::for_each：遍历指定范围内的所有元素，并对每个元素执行指定操作
可以通过引用修改元素的值

2.9 删除算法

std::cout << "\n=== 删除算法 ===" << std::endl;
std::vector<int> removeVec = {1, 2, 3, 2, 4, 2, 5};
// 移除元素（返回新的结束迭代器）
auto newEnd = std::remove(removeVec.begin(), removeVec.end(), 2);
// 擦除从新结束迭代器到原结束迭代器的元素
removeVec.erase(newEnd, removeVec.end());
std::cout << "移除2后: ";
for (int x : removeVec) {
    std::cout << x << " ";
}
std::cout << std::endl;

// 条件删除
std::vector<int> removeIfVec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
auto newEndIf = std::remove_if(removeIfVec.begin(), removeIfVec.end(),
                              [](int x) { return x % 2 == 0; });
removeIfVec.erase(newEndIf, removeIfVec.end());
std::cout << "移除偶数后: ";
for (int x : removeIfVec) {
    std::cout << x << " ";
}
std::cout << std::endl;

解析：

std::remove：移除指定值的元素，返回新的结束迭代器
std::remove_if：移除满足条件的元素，返回新的结束迭代器
注意：这些算法只是将需要移除的元素移到了范围的末尾，并没有真正删除它们，需要配合 erase 函数使用

2.10 去重算法

std::cout << "\n=== 去重算法 ===" << std::endl;
std::vector<int> uniqueVec = {1, 1, 2, 2, 3, 3, 4, 4};
// 先排序
std::sort(uniqueVec.begin(), uniqueVec.end());
// 去重
auto uniqueEnd = std::unique(uniqueVec.begin(), uniqueVec.end());
// 擦除重复元素
uniqueVec.erase(uniqueEnd, uniqueVec.end());
std::cout << "去重后: ";
for (int x : uniqueVec) {
    std::cout << x << " ";
}
std::cout << std::endl;

解析：

std::unique：移除相邻的重复元素，返回新的结束迭代器
通常需要先对元素进行排序，以确保所有重复元素都相邻

2.11 合并算法

std::cout << "\n=== 合并算法 ===" << std::endl;
// 两个已排序的向量
std::vector<int> v1 = {1, 3, 5, 7, 9};
std::vector<int> v2 = {2, 4, 6, 8, 10};
std::vector<int> merged(10);
// 合并两个已排序的向量
std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), merged.begin());
std::cout << "合并后: ";
for (int x : merged) {
    std::cout << x << " ";
}
std::cout << std::endl;

解析：

std::merge：合并两个已排序的范围，结果也会保持排序状态

2.12 分区算法

std::cout << "\n=== 分区算法 ===" << std::endl;
std::vector<int> partitionVec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
// 分区（偶数在前，奇数在后）
auto partitionPoint = std::partition(partitionVec.begin(), partitionVec.end(),
                                     [](int x) { return x % 2 == 0; });
std::cout << "分区后（偶数在前）: ";
for (int x : partitionVec) {
    std::cout << x << " ";
}
std::cout << std::endl;
std::cout << "分区点位置: " << (partitionPoint - partitionVec.begin()) << std::endl;

解析：

std::partition：根据条件将范围分为两部分，满足条件的元素在前，不满足的在后
返回分区点，即第一个不满足条件的元素的迭代器

2.13 逻辑算法

std::cout << "\n=== 逻辑算法 ===" << std::endl;
std::vector<int> checkVec = {2, 4, 6, 8, 10};
// 检查所有元素是否满足条件
bool allEven = std::all_of(checkVec.begin(), checkVec.end(),
                           [](int x) { return x % 2 == 0; });
// 检查是否有元素满足条件
bool anyOdd = std::any_of(checkVec.begin(), checkVec.end(),
                          [](int x) { return x % 2 != 0; });
// 检查是否没有元素满足条件
bool noneNegative = std::none_of(checkVec.begin(), checkVec.end(),
                                 [](int x) { return x < 0; });
std::cout << "所有元素都是偶数: " << (allEven ? "是" : "否") << std::endl;
std::cout << "存在奇数: " << (anyOdd ? "是" : "否") << std::endl;
std::cout << "没有负数: " << (noneNegative ? "是" : "否") << std::endl;

解析：

std::all_of：检查范围内的所有元素是否都满足条件
std::any_of：检查范围内是否有元素满足条件
std::none_of：检查范围内是否没有元素满足条件

2.14 相等性算法

std::cout << "\n=== 相等性算法 ===" << std::endl;
std::vector<int> eqVec1 = {1, 2, 3, 4, 5};
std::vector<int> eqVec2 = {1, 2, 3, 4, 5};
std::vector<int> eqVec3 = {1, 2, 3, 4, 6};
// 检查两个序列是否相等
bool equal1 = std::equal(eqVec1.begin(), eqVec1.end(), eqVec2.begin());
bool equal2 = std::equal(eqVec1.begin(), eqVec1.end(), eqVec3.begin());
std::cout << "eqVec1 和 eqVec2 相等: " << (equal1 ? "是" : "否") << std::endl;
std::cout << "eqVec1 和 eqVec3 相等: " << (equal2 ? "是" : "否") << std::endl;

解析：

std::equal：检查两个范围是否相等，即对应位置的元素是否都相等

2.15 包含算法

std::cout << "\n=== 包含算法 ===" << std::endl;
std::vector<int> haystack = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::vector<int> needle = {3, 4, 5};
// 检查一个序列是否是另一个序列的子序列
bool contains = std::search(haystack.begin(), haystack.end(), 
                           needle.begin(), needle.end()) != haystack.end();
std::cout << "haystack 包含 needle: " << (contains ? "是" : "否") << std::endl;

解析：

std::search：在一个范围中搜索另一个范围，返回第一次出现的位置

3. 编译和运行说明

3.1 编译命令

使用以下命令编译 stl_algorithms.cpp 文件：

1	g++ -std=c++11 -fexec-charset=GBK -o stl_algorithms stl_algorithms.cpp

参数说明：

-std=c++11：使用 C++11 标准
-fexec-charset=GBK：确保输出的中文字符正确显示
-o stl_algorithms：指定输出可执行文件名为 stl_algorithms

3.2 运行命令

编译成功后，使用以下命令运行程序：

1 2	./stl_algorithms # Linux/macOS .\stl_algorithms.exe # Windows

3.3 预期输出

运行程序后，您将看到类似以下的输出：

原始向量: 5 2 8 1 9 3 7 4 6 

=== 排序算法 ===
升序排序后: 1 2 3 4 5 6 7 8 9
降序排序后: 9 8 7 6 5 4 3 2 1
部分排序（前3个元素）: 1 2 3 9 8 7 6 5 4

=== 查找算法 ===
找到5，位置: 4
7 存在: 是
5的下界位置: 4
5的上界位置: 5
第一个偶数: 2，位置: 1

=== 修改算法 ===
复制后的向量: 1 2 3 4 5
填充0后: 0 0 0 0 0 
生成递增序列(1,2,3,4,5): 1 2 3 4 5
反转后: 5 4 3 2 1
随机打乱后: 1 4 2 3 5

=== 数值算法 ===
总和: 15
乘积: 120
相邻元素的差: 1 1 1 1

=== 最值算法 ===
最小值: 1, 最大值: 5
a和b的最小值: 10
a和b的最大值: 20

=== 计数算法 ===
1出现的次数: 4
偶数的个数: 2

=== 转换算法 ===
平方值: 1 4 9 16 25
两个向量的和: 11 22 33 44 55

=== 遍历算法 ===
遍历后（乘以2）: 2 4 6 8 10

=== 删除算法 ===
移除2后: 1 3 4 5
移除偶数后: 1 3 5 7 9 

=== 去重算法 ===
去重后: 1 2 3 4

合并后: 1 2 3 4 5 6 7 8 9 10

=== 分区算法 ===
分区后（偶数在前）: 10 2 8 4 6 5 7 3 9 1
分区点位置: 5

=== 逻辑算法 ===
所有元素都是偶数: 是
存在奇数: 否
没有负数: 是

=== 相等性算法 ===
eqVec1 和 eqVec2 相等: 是
eqVec1 和 eqVec3 相等: 否

=== 包含算法 ===
haystack 包含 needle: 是

4. 技术要点

4.1 迭代器的重要性

迭代器：是 STL 算法的核心，它们提供了一种统一的方式来访问容器中的元素，无论容器的具体实现如何
迭代器类别：
- InputIterator：只读，只能单向移动
- OutputIterator：只写，只能单向移动
- ForwardIterator：可读可写，只能单向移动
- BidirectionalIterator：可读可写，可双向移动
- RandomAccessIterator：可读可写，可随机访问
算法对迭代器的要求：不同的算法对迭代器有不同的要求，例如 sort 需要随机访问迭代器，而 find 只需要输入迭代器

4.2 谓词函数

谓词函数：是返回布尔值的函数，用于判断元素是否满足特定条件
一元谓词：接受一个参数的谓词函数，如 std::count_if 使用的谓词
二元谓词：接受两个参数的谓词函数，如 std::sort 使用的比较函数
Lambda 表达式：C++11 引入的 lambda 表达式是定义谓词函数的便捷方式

4.3 算法的时间复杂度

算法类别	算法名称	时间复杂度	空间复杂度
排序算法	sort	O(n log n)	O(log n)
	partial_sort	O(n log k)	O(log k)
	stable_sort	O(n log n)	O(n)
查找算法	find	O(n)	O(1)
	binary_search	O(log n)	O(1)
	lower_bound	O(log n)	O(1)
	upper_bound	O(log n)	O(1)
修改算法	copy	O(n)	O(1)
	fill	O(n)	O(1)
	reverse	O(n)	O(1)
	random_shuffle	O(n)	O(1)
数值算法	accumulate	O(n)	O(1)
	adjacent_difference	O(n)	O(1)
最值算法	minmax_element	O(n)	O(1)
计数算法	count	O(n)	O(1)
	count_if	O(n)	O(1)
转换算法	transform	O(n)	O(1)
遍历算法	for_each	O(n)	O(1)
删除算法	remove	O(n)	O(1)
	remove_if	O(n)	O(1)
去重算法	unique	O(n)	O(1)
合并算法	merge	O(n)	O(n)
分区算法	partition	O(n)	O(1)
逻辑算法	all_of	O(n)	O(1)
	any_of	O(n)	O(1)
	none_of	O(n)	O(1)
相等性算法	equal	O(n)	O(1)
包含算法	search	O(n*m)	O(1)

4.4 算法的使用技巧

选择合适的算法：根据具体需求选择最适合的算法，例如需要排序时使用 sort，需要查找时使用 find 或 binary_search
注意算法的前提条件：例如 binary_search 要求容器已排序，unique 要求重复元素相邻
使用 lambda 表达式：lambda 表达式是定义谓词函数的便捷方式，使代码更简洁
注意算法的返回值：例如 remove 返回新的结束迭代器，需要配合 erase 使用
考虑算法的性能：不同算法的时间复杂度不同，对于大型数据集，选择高效的算法非常重要

4.5 算法与容器的配合

容器提供迭代器：所有 STL 容器都提供了迭代器，使算法能够操作它们
容器的成员函数：有些容器提供了与算法同名的成员函数，例如 list::sort，这些成员函数通常针对容器的特性进行了优化
算法的通用性：算法通过迭代器操作元素，与具体的容器实现无关，这使得算法可以用于任何提供适当迭代器的容器

5. 常见问题解答

5.1 如何选择合适的排序算法？

解答：

需要完全排序：使用 std::sort
需要保持相等元素的相对顺序：使用 std::stable_sort
只需要部分元素排序：使用 std::partial_sort
只需要找到前 k 个最小元素：使用 std::nth_element
对于链表：使用 list::sort 成员函数，因为链表不支持随机访问迭代器

5.2 为什么 `std::remove` 没有真正删除元素？

解答：

std::remove 的设计理念是”算法不修改容器的大小”，它只是将需要保留的元素移到容器的前面，将需要删除的元素移到容器的后面
这样设计的原因是为了保持算法的通用性，因为并不是所有容器都支持高效的删除操作
使用 std::remove 后，需要配合 erase 函数来真正删除元素，例如：
1
vec.erase(std::remove(vec.begin(), vec.end(), value), vec.end());

5.3 如何在自定义类型上使用 STL 算法？

解答：

对于排序算法：需要为自定义类型定义 < 运算符，或者提供自定义比较函数
对于查找算法：需要为自定义类型定义 == 运算符，或者提供自定义相等性函数
对于其他算法：根据算法的要求，可能需要定义相应的操作符或函数

5.4 如何使用 STL 算法处理多个容器？

解答：

使用 std::transform：可以处理两个容器的元素级运算
使用 std::merge：可以合并两个已排序的容器
使用 std::set_union、std::set_intersection 等：可以处理集合操作
使用迭代器：可以手动控制多个容器的迭代器，实现复杂的操作

5.5 如何提高 STL 算法的性能？

解答：

选择合适的算法：根据具体需求选择时间复杂度最低的算法
选择合适的容器：不同的容器对不同算法的支持效率不同
减少不必要的拷贝：使用移动语义和引用传递
预分配内存：对于需要输出结果的算法，预分配足够的内存
使用并行算法：C++17 引入了并行算法，可以利用多核处理器提高性能

5.6 如何使用 STL 算法处理自定义数据结构？

解答：

实现迭代器：为自定义数据结构实现适当的迭代器
使用适配器：使用 std::reference_wrapper 等适配器来包装元素
使用 lambda 表达式：使用 lambda 表达式来处理自定义数据结构的元素
继承现有容器：如果可能，继承现有容器并扩展其功能

5.7 如何调试 STL 算法？

解答：

使用调试器：使用 GDB 或 Visual Studio 调试器来跟踪算法的执行
添加日志：在谓词函数中添加日志，查看算法的执行过程
简化问题：使用小型数据集来测试算法，以便更容易理解其行为
查看文档：仔细阅读算法的文档，了解其行为和限制

6. 代码优化建议

6.1 算法选择优化

根据数据规模选择算法：对于小型数据集，简单算法可能比复杂算法更快；对于大型数据集，应选择时间复杂度低的算法
根据数据特性选择算法：例如，对于几乎有序的数据，插入排序可能比快速排序更快
考虑空间复杂度：对于内存受限的环境，应选择空间复杂度低的算法

6.2 迭代器使用优化

使用正确的迭代器类型：根据算法的要求选择合适的迭代器类型
避免不必要的迭代器操作：例如，在循环中避免重复计算迭代器的位置
使用 std::begin 和 std::end：这些函数可以统一处理容器和数组

6.3 谓词函数优化

使用 inline 函数：对于简单的谓词函数，使用 inline 可以提高性能
使用 lambda 表达式：lambda 表达式可以捕获上下文，使代码更简洁
避免复杂的谓词函数：复杂的谓词函数会增加算法的执行时间

6.4 内存使用优化

预分配内存：对于需要输出结果的算法，使用 reserve 预分配足够的内存
使用移动语义：对于大对象，使用移动语义减少拷贝开销
避免不必要的临时对象：尽可能使用引用传递，避免创建临时对象

6.5 并行计算

使用 C++17 并行算法：C++17 引入了并行算法，可以利用多核处理器提高性能
使用 OpenMP：对于不支持 C++17 的环境，可以使用 OpenMP 进行并行计算
考虑数据依赖性：并行计算需要考虑数据依赖性，避免竞态条件

7. 总结

C++ STL 算法是一组功能强大的通用函数，它们通过迭代器操作容器中的元素，提供了丰富的操作功能。正确使用这些算法可以大大简化代码编写，提高开发效率和代码质量。

7.1 算法分类总结

排序算法：用于对元素进行排序
查找算法：用于在容器中查找元素
修改算法：用于修改容器中的元素
数值算法：用于数值计算
最值算法：用于查找最大值和最小值
计数算法：用于计数元素
转换算法：用于转换元素
遍历算法：用于遍历元素
删除算法：用于删除元素
去重算法：用于去除重复元素
合并算法：用于合并容器
分区算法：用于分区容器
逻辑算法：用于逻辑判断
相等性算法：用于比较容器
包含算法：用于检查容器是否包含子序列

7.2 最佳实践

了解算法的功能和限制：仔细阅读算法的文档，了解其功能、时间复杂度和限制
选择合适的算法：根据具体需求选择最适合的算法
使用正确的迭代器：根据算法的要求选择合适的迭代器类型
使用 lambda 表达式：lambda 表达式是定义谓词函数的便捷方式
注意算法的返回值：例如 remove 返回新的结束迭代器，需要配合 erase 使用
考虑性能：对于大型数据集，选择高效的算法和容器
编写清晰的代码：使用有意义的变量名和注释，使代码易于理解
测试算法：在关键场景下测试算法的性能和正确性

通过合理选择和使用 STL 算法，可以显著提高 C++ 程序的性能和可维护性。希望本指南能够帮助您更好地理解和使用 C++ STL 算法。

stl_algorithms.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <string>
#include <list>
#include <functional>

int main() {
    // 初始化一个整数向量
    std::vector<int> nums = {5, 2, 8, 1, 9, 3, 7, 4, 6};

    std::cout << "原始向量: ";
    for (int x : nums) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    std::cout << "\n=== 排序算法 ===" << std::endl;
    // 升序排序
    std::sort(nums.begin(), nums.end());
    std::cout << "升序排序后: ";
    for (int x : nums) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // 降序排序
    std::sort(nums.begin(), nums.end(), std::greater<int>());
    std::cout << "降序排序后: ";
    for (int x : nums) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // 部分排序（前3个元素排序）
    std::partial_sort(nums.begin(), nums.begin() + 3, nums.end());
    std::cout << "部分排序（前3个元素）: ";
    for (int x : nums) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    std::cout << "\n=== 查找算法 ===" << std::endl;
    // 先排序以便使用二分查找
    std::sort(nums.begin(), nums.end());
    // 线性查找
    auto it = std::find(nums.begin(), nums.end(), 5);
    if (it != nums.end()) {
        std::cout << "找到5，位置: " << (it - nums.begin()) << std::endl;
    }

    // 二分查找
    bool exists = std::binary_search(nums.begin(), nums.end(), 7);
    std::cout << "7 存在: " << (exists ? "是" : "否") << std::endl;

    // 下界和上界
    auto lower = std::lower_bound(nums.begin(), nums.end(), 5);
    auto upper = std::upper_bound(nums.begin(), nums.end(), 5);
    std::cout << "5的下界位置: " << (lower - nums.begin()) << std::endl;
    std::cout << "5的上界位置: " << (upper - nums.begin()) << std::endl;

    // 查找第一个满足条件的元素
    auto firstEven = std::find_if(nums.begin(), nums.end(), 
                                 [](int x) { return x % 2 == 0; });
    if (firstEven != nums.end()) {
        std::cout << "第一个偶数: " << *firstEven << "，位置: " << (firstEven - nums.begin()) << std::endl;
    }

    std::cout << "\n=== 修改算法 ===" << std::endl;
    std::vector<int> vec1 = {1, 2, 3, 4, 5};
    std::vector<int> vec2(5);
    
    // 复制元素
    std::copy(vec1.begin(), vec1.end(), vec2.begin());
    std::cout << "复制后的向量: ";
    for (int x : vec2) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // 填充元素
    std::fill(vec2.begin(), vec2.end(), 0);
    std::cout << "填充0后: ";
    for (int x : vec2) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // 生成递增序列
    std::iota(vec2.begin(), vec2.end(), 1);
    std::cout << "生成递增序列(1,2,3,4,5): ";
    for (int x : vec2) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // 反转元素
    std::vector<int> vec3 = {1, 2, 3, 4, 5};
    std::reverse(vec3.begin(), vec3.end());
    std::cout << "反转后: ";
    for (int x : vec3) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // 随机打乱元素（C++11后推荐使用shuffle）
    std::random_shuffle(vec3.begin(), vec3.end());
    std::cout << "随机打乱后: ";
    for (int x : vec3) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    std::cout << "\n=== 数值算法 ===" << std::endl;
    std::vector<int> values = {1, 2, 3, 4, 5};
    // 计算总和
    int sum = std::accumulate(values.begin(), values.end(), 0);
    std::cout << "总和: " << sum << std::endl;

    // 计算乘积
    int product = std::accumulate(values.begin(), values.end(), 1, std::multiplies<int>());
    std::cout << "乘积: " << product << std::endl;

    // 计算相邻元素的差
    std::vector<int> diff(values.size() - 1);
    std::adjacent_difference(values.begin(), values.end(), diff.begin());
    std::cout << "相邻元素的差: ";
    for (int x : diff) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    std::cout << "\n=== 最值算法 ===" << std::endl;
    // 查找最小值和最大值
    auto minMax = std::minmax_element(values.begin(), values.end());
    std::cout << "最小值: " << *minMax.first << ", 最大值: " << *minMax.second << std::endl;

    // 直接比较两个值
    int a = 10, b = 20;
    std::cout << "a和b的最小值: " << std::min(a, b) << std::endl;
    std::cout << "a和b的最大值: " << std::max(a, b) << std::endl;

    std::cout << "\n=== 计数算法 ===" << std::endl;
    std::vector<int> countVec = {1, 2, 1, 3, 1, 4, 1};
    // 计数元素出现次数
    int count = std::count(countVec.begin(), countVec.end(), 1);
    std::cout << "1出现的次数: " << count << std::endl;

    // 计数满足条件的元素
    int evenCount = std::count_if(countVec.begin(), countVec.end(),
                                 [](int x) { return x % 2 == 0; });
    std::cout << "偶数的个数: " << evenCount << std::endl;

    std::cout << "\n=== 转换算法 ===" << std::endl;
    std::vector<int> original = {1, 2, 3, 4, 5};
    std::vector<int> squared(5);
    // 转换元素（计算平方）
    std::transform(original.begin(), original.end(), squared.begin(),
                   [](int x) { return x * x; });
    std::cout << "平方值: ";
    for (int x : squared) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // 两个序列的元素运算
    std::vector<int> vecA = {1, 2, 3, 4, 5};
    std::vector<int> vecB = {10, 20, 30, 40, 50};
    std::vector<int> result(5);
    std::transform(vecA.begin(), vecA.end(), vecB.begin(), result.begin(),
                   [](int a, int b) { return a + b; });
    std::cout << "两个向量的和: ";
    for (int x : result) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    std::cout << "\n=== 遍历算法 ===" << std::endl;
    std::vector<int> forEachVec = {1, 2, 3, 4, 5};
    // 遍历并修改元素
    std::for_each(forEachVec.begin(), forEachVec.end(),
                  [](int& x) { x *= 2; });
    std::cout << "遍历后（乘以2）: ";
    for (int x : forEachVec) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    std::cout << "\n=== 删除算法 ===" << std::endl;
    std::vector<int> removeVec = {1, 2, 3, 2, 4, 2, 5};
    // 移除元素（返回新的结束迭代器）
    auto newEnd = std::remove(removeVec.begin(), removeVec.end(), 2);
    // 擦除从新结束迭代器到原结束迭代器的元素
    removeVec.erase(newEnd, removeVec.end());
    std::cout << "移除2后: ";
    for (int x : removeVec) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // 条件删除
    std::vector<int> removeIfVec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    auto newEndIf = std::remove_if(removeIfVec.begin(), removeIfVec.end(),
                                  [](int x) { return x % 2 == 0; });
    removeIfVec.erase(newEndIf, removeIfVec.end());
    std::cout << "移除偶数后: ";
    for (int x : removeIfVec) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    std::cout << "\n=== 去重算法 ===" << std::endl;
    std::vector<int> uniqueVec = {1, 1, 2, 2, 3, 3, 4, 4};
    // 先排序
    std::sort(uniqueVec.begin(), uniqueVec.end());
    // 去重
    auto uniqueEnd = std::unique(uniqueVec.begin(), uniqueVec.end());
    // 擦除重复元素
    uniqueVec.erase(uniqueEnd, uniqueVec.end());
    std::cout << "去重后: ";
    for (int x : uniqueVec) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    std::cout << "\n=== 合并算法 ===" << std::endl;
    // 两个已排序的向量
    std::vector<int> v1 = {1, 3, 5, 7, 9};
    std::vector<int> v2 = {2, 4, 6, 8, 10};
    std::vector<int> merged(10);
    // 合并两个已排序的向量
    std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), merged.begin());
    std::cout << "合并后: ";
    for (int x : merged) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    std::cout << "\n=== 分区算法 ===" << std::endl;
    std::vector<int> partitionVec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    // 分区（偶数在前，奇数在后）
    auto partitionPoint = std::partition(partitionVec.begin(), partitionVec.end(),
                                         [](int x) { return x % 2 == 0; });
    std::cout << "分区后（偶数在前）: ";
    for (int x : partitionVec) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    std::cout << "分区点位置: " << (partitionPoint - partitionVec.begin()) << std::endl;

    std::cout << "\n=== 逻辑算法 ===" << std::endl;
    std::vector<int> checkVec = {2, 4, 6, 8, 10};
    // 检查所有元素是否满足条件
    bool allEven = std::all_of(checkVec.begin(), checkVec.end(),
                               [](int x) { return x % 2 == 0; });
    // 检查是否有元素满足条件
    bool anyOdd = std::any_of(checkVec.begin(), checkVec.end(),
                              [](int x) { return x % 2 != 0; });
    // 检查是否没有元素满足条件
    bool noneNegative = std::none_of(checkVec.begin(), checkVec.end(),
                                     [](int x) { return x < 0; });
    std::cout << "所有元素都是偶数: " << (allEven ? "是" : "否") << std::endl;
    std::cout << "存在奇数: " << (anyOdd ? "是" : "否") << std::endl;
    std::cout << "没有负数: " << (noneNegative ? "是" : "否") << std::endl;

    std::cout << "\n=== 相等性算法 ===" << std::endl;
    std::vector<int> eqVec1 = {1, 2, 3, 4, 5};
    std::vector<int> eqVec2 = {1, 2, 3, 4, 5};
    std::vector<int> eqVec3 = {1, 2, 3, 4, 6};
    // 检查两个序列是否相等
    bool equal1 = std::equal(eqVec1.begin(), eqVec1.end(), eqVec2.begin());
    bool equal2 = std::equal(eqVec1.begin(), eqVec1.end(), eqVec3.begin());
    std::cout << "eqVec1 和 eqVec2 相等: " << (equal1 ? "是" : "否") << std::endl;
    std::cout << "eqVec1 和 eqVec3 相等: " << (equal2 ? "是" : "否") << std::endl;

    std::cout << "\n=== 包含算法 ===" << std::endl;
    std::vector<int> haystack = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::vector<int> needle = {3, 4, 5};
    // 检查一个序列是否是另一个序列的子序列
    bool contains = std::search(haystack.begin(), haystack.end(), 
                               needle.begin(), needle.end()) != haystack.end();
    std::cout << "haystack 包含 needle: " << (contains ? "是" : "否") << std::endl;

    return 0;
}