STL算法库讲解1

1. 迭代算法：for_each

核心特性

• 最基础的遍历算法，对区间[first, last)中的每个元素执行指定操作
• 是非修改性算法（除非操作函数显式修改元素）
• 支持自定义操作（函数指针、函数对象、Lambda 表达式）
• 返回值：C++11 后返回传入的操作函数对象

函数原型

template<class InputIt, class UnaryFunction> UnaryFunction for_each(InputIt first, InputIt last, UnaryFunction f);

用法示例

#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> vec = {1, 2, 3, 4, 5}; // 1. 普通函数作为操作 auto print = [](int x) { std::cout << x << " "; }; std::for_each(vec.begin(), vec.end(), print); // 输出：1 2 3 4 5 std::cout << std::endl; // 2. 修改元素（通过引用捕获） std::for_each(vec.begin(), vec.end(), [](int& x) { x *= 2; }); // 现在vec：{2, 4, 6, 8, 10} // 3. 捕获外部变量 int sum = 0; std::for_each(vec.begin(), vec.end(), [&sum](int x) { sum += x; }); std::cout << "总和：" << sum << std::endl; // 输出：30 return 0; }

注意事项

• 与 C++11 范围 for 循环的区别：for_each可以返回操作函数对象，适合需要累积状态的场景
• 操作函数的参数如果是值传递，无法修改原元素；必须使用引用传递int& x
• 时间复杂度：O (n)，遍历一次区间

2. 查找算法

核心特性

• 在区间中查找单个元素或满足条件的元素
• 返回值：找到则返回指向该元素的迭代器；未找到则返回last迭代器
• 适用于无序区间（有序区间优先使用二分查找，效率更高）

常用函数

用法示例

#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> vec = {1, 3, 5, 3, 7, 9, 3}; // 1. 查找指定值 auto it1 = std::find(vec.begin(), vec.end(), 3); if (it1 != vec.end()) { std::cout << "找到3，位置：" << it1 - vec.begin() << std::endl; // 输出：1 } // 2. 查找第一个大于5的元素 auto it2 = std::find_if(vec.begin(), vec.end(), [](int x) { return x > 5; }); std::cout << "第一个大于5的元素：" << *it2 << std::endl; // 输出：7 // 3. 查找第一对相邻相等的元素 std::vector<int> vec2 = {1, 2, 2, 3, 3, 3}; auto it3 = std::adjacent_find(vec2.begin(), vec2.end()); std::cout << "第一对相邻相等的元素：" << *it3 << std::endl; // 输出：2 return 0; }

3. 搜索算法

核心特性

• 在区间中查找子序列或连续重复元素
• 与查找算法的区别：查找单个元素 vs 查找多个元素组成的序列
• 返回值：找到则返回子序列起始位置的迭代器；未找到则返回last

常用函数

用法示例

#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> text = {1, 2, 3, 4, 2, 3, 4, 5}; std::vector<int> pattern = {2, 3, 4}; // 1. 查找第一个子序列 auto it1 = std::search(text.begin(), text.end(), pattern.begin(), pattern.end()); if (it1 != text.end()) { std::cout << "第一个子序列起始位置：" << it1 - text.begin() << std::endl; // 输出：1 } // 2. 查找最后一个子序列 auto it2 = std::find_end(text.begin(), text.end(), pattern.begin(), pattern.end()); std::cout << "最后一个子序列起始位置：" << it2 - text.begin() << std::endl; // 输出：4 // 3. 查找连续3个5 std::vector<int> vec = {1, 5, 5, 5, 2, 5}; auto it3 = std::search_n(vec.begin(), vec.end(), 3, 5); if (it3 != vec.end()) { std::cout << "找到连续3个5，起始位置：" << it3 - vec.begin() << std::endl; // 输出：1 } return 0; }

4. 统计算法

核心特性

• 统计区间中满足条件的元素个数或进行数值累积
• 分为两类：计数类（<algorithm>）和数值累积类（<numeric>）

常用函数

用法示例

#include <iostream> #include <vector> #include <algorithm> #include <numeric> int main() { std::vector<int> vec = {1, 2, 3, 4, 5, 3, 3}; // 1. 统计等于3的元素个数 int cnt1 = std::count(vec.begin(), vec.end(), 3); std::cout << "3的个数：" << cnt1 << std::endl; // 输出：3 // 2. 统计偶数个数 int cnt2 = std::count_if(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; }); std::cout << "偶数个数：" << cnt2 << std::endl; // 输出：2 // 3. 计算总和 int sum = std::accumulate(vec.begin(), vec.end(), 0); std::cout << "总和：" << sum << std::endl; // 输出：21 // 4. 计算乘积 int product = std::accumulate(vec.begin(), vec.end(), 1, std::multiplies<int>()); std::cout << "乘积：" << product << std::endl; // 输出：540 return 0; }

5. 复制或变换算法

核心特性

• 将源区间的元素复制或变换后复制到目标区间
• 要求目标区间有足够的空间，否则使用back_inserter等插入迭代器
• 变换算法可以对每个元素执行自定义操作

常用函数

用法示例

#include <iostream> #include <vector> #include <algorithm> #include <iterator> // 用于back_inserter int main() { std::vector<int> src = {1, 2, 3, 4, 5}; std::vector<int> dest; // 1. 复制所有元素（使用back_inserter自动扩容） std::copy(src.begin(), src.end(), std::back_inserter(dest)); // dest：{1, 2, 3, 4, 5} // 2. 复制偶数元素 std::vector<int> even; std::copy_if(src.begin(), src.end(), std::back_inserter(even), [](int x) { return x % 2 == 0; }); // even：{2, 4} // 3. 元素平方变换 std::vector<int> squared; std::transform(src.begin(), src.end(), std::back_inserter(squared), [](int x) { return x * x; }); // squared：{1, 4, 9, 16, 25} // 4. 两个区间元素相加 std::vector<int> a = {1, 2, 3}; std::vector<int> b = {4, 5, 6}; std::vector<int> c; std::transform(a.begin(), a.end(), b.begin(), std::back_inserter(c), std::plus<int>()); // c：{5, 7, 9} return 0; }

6. 填充算法

核心特性

• 用指定值或生成的值填充区间
• 分为两类：固定值填充和生成值填充

常用函数

用法示例

#include <iostream> #include <vector> #include <algorithm> #include <random> int main() { std::vector<int> vec(5); // 1. 填充固定值 std::fill(vec.begin(), vec.end(), 10); // vec：{10, 10, 10, 10, 10} // 2. 填充前3个元素为0 std::fill_n(vec.begin(), 3, 0); // vec：{0, 0, 0, 10, 10} // 3. 生成随机数填充 std::random_device rd; std::mt19937 gen(rd()); std::uniform_int_distribution<> dis(1, 100); std::generate(vec.begin(), vec.end(), [&]() { return dis(gen); }); // 示例输出：{42, 17, 89, 3, 56} return 0; }

7. 删除算法

⚠️ 核心注意事项

STL 删除算法不会真正删除容器元素，只是将需要保留的元素移到区间前部，返回新的尾迭代器。必须配合容器的erase方法才能真正释放内存。

常用函数

用法示例

#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> vec = {1, 3, 2, 3, 4, 3, 5}; // 1. 删除所有等于3的元素 auto new_end1 = std::remove(vec.begin(), vec.end(), 3); // 此时vec：{1, 2, 4, 5, ?, ?, ?}（?为未定义值） vec.erase(new_end1, vec.end()); // 真正删除 // vec：{1, 2, 4, 5} // 2. 删除所有偶数 std::vector<int> vec2 = {1, 2, 3, 4, 5, 6}; auto new_end2 = std::remove_if(vec2.begin(), vec2.end(), [](int x) { return x % 2 == 0; }); vec2.erase(new_end2, vec2.end()); // vec2：{1, 3, 5} // 3. 去重（必须先排序） std::vector<int> vec3 = {1, 2, 2, 3, 3, 3, 4}; std::sort(vec3.begin(), vec3.end()); // 先排序 auto new_end3 = std::unique(vec3.begin(), vec3.end()); vec3.erase(new_end3, vec3.end()); // vec3：{1, 2, 3, 4} return 0; }

8. 排序算法

核心特性

• STL 提供了多种排序算法，适用于不同场景
• 默认使用<运算符比较，支持自定义比较函数
• 时间复杂度：O (n log n)（主流排序算法）

常用函数

用法示例

#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> vec = {5, 2, 9, 1, 5, 6}; // 1. 默认升序排序 std::sort(vec.begin(), vec.end()); // vec：{1, 2, 5, 5, 6, 9} // 2. 自定义降序排序 std::sort(vec.begin(), vec.end(), std::greater<int>()); // vec：{9, 6, 5, 5, 2, 1} // 3. 部分排序（前3个元素有序） std::vector<int> vec2 = {5, 2, 9, 1, 5, 6}; std::partial_sort(vec2.begin(), vec2.begin() + 3, vec2.end()); // vec2：{1, 2, 5, 9, 5, 6}（前3个最小的元素有序） // 4. 找第3小的元素（索引从0开始） std::vector<int> vec3 = {5, 2, 9, 1, 5, 6}; std::nth_element(vec3.begin(), vec3.begin() + 2, vec3.end()); std::cout << "第3小的元素：" << vec3[2] << std::endl; // 输出：5 return 0; }

9. 堆操作

核心特性

• STL 实现了大顶堆（默认），即堆顶元素是最大值
• 堆是一种完全二叉树，存储在数组中
• 所有堆操作的时间复杂度均为 O (log n)

常用函数

用法示例

#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> heap = {3, 1, 4, 1, 5, 9, 2, 6}; // 1. 构建大顶堆 std::make_heap(heap.begin(), heap.end()); // 堆顶元素是最大值：9 std::cout << "堆顶元素：" << heap.front() << std::endl; // 输出：9 // 2. 插入元素 heap.push_back(7); // 先加到末尾 std::push_heap(heap.begin(), heap.end()); // 调整为堆 // 现在堆顶还是9 // 3. 删除堆顶元素 std::pop_heap(heap.begin(), heap.end()); // 堆顶移到末尾 heap.pop_back(); // 真正删除 // 新堆顶：7 // 4. 堆排序（升序） std::sort_heap(heap.begin(), heap.end()); // heap：{1, 1, 2, 3, 4, 5, 6, 7} return 0; }

10. 二分查找算法

核心特性

• 要求区间必须是有序的（默认升序）
• 时间复杂度：O (log n)，远快于线性查找的 O (n)
• 适用于大规模有序数据的查找

常用函数

用法示例

#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> vec = {1, 2, 3, 4, 4, 4, 5, 6}; // 1. 判断元素是否存在 bool exists = std::binary_search(vec.begin(), vec.end(), 4); std::cout << "4是否存在：" << std::boolalpha << exists << std::endl; // 输出：true // 2. 查找第一个大于等于4的元素 auto it_low = std::lower_bound(vec.begin(), vec.end(), 4); std::cout << "第一个>=4的元素位置：" << it_low - vec.begin() << std::endl; // 输出：3 // 3. 查找第一个大于4的元素 auto it_high = std::upper_bound(vec.begin(), vec.end(), 4); std::cout << "第一个>4的元素位置：" << it_high - vec.begin() << std::endl; // 输出：6 // 4. 统计等于4的元素个数 int cnt = it_high - it_low; std::cout << "4的个数：" << cnt << std::endl; // 输出：3 return 0; }

11. 交换算法

核心特性

• 交换两个元素或两个区间的元素
• 是 STL 中最基础的算法之一，被其他算法广泛调用

常用函数

用法示例

#include <iostream> #include <vector> #include <algorithm> int main() { // 1. 交换两个变量 int a = 10, b = 20; std::swap(a, b); std::cout << "a=" << a << ", b=" << b << std::endl; // 输出：a=20, b=10 // 2. 交换两个迭代器指向的元素 std::vector<int> vec = {1, 2, 3, 4}; std::iter_swap(vec.begin(), vec.end() - 1); // vec：{4, 2, 3, 1} // 3. 交换两个区间的元素 std::vector<int> vec1 = {1, 2, 3}; std::vector<int> vec2 = {4, 5, 6}; std::swap_ranges(vec1.begin(), vec1.end(), vec2.begin()); // vec1：{4, 5, 6}, vec2：{1, 2, 3} return 0; }