C++算法
C++ STL 算法深度解析：从基础到 C++20 Ranges
本文深入解析 C++ STL 算法体系，涵盖非修改、修改序列操作、排序及数值算法。介绍 STL 设计哲学与迭代器抽象，演示查找、计数、拷贝、变换等核心用法。重点讲解 C++20 Ranges 新特性，包括视图管道与范围适配器组合。最后提供性能优化指南与常见陷阱规避建议，帮助开发者编写高效、现代的 C++ 代码。
本文深入解析 C++ STL 算法体系，涵盖非修改、修改序列操作、排序及数值算法。介绍 STL 设计哲学与迭代器抽象，演示查找、计数、拷贝、变换等核心用法。重点讲解 C++20 Ranges 新特性，包括视图管道与范围适配器组合。最后提供性能优化指南与常见陷阱规避建议，帮助开发者编写高效、现代的 C++ 代码。
非修改序列操作 (25 个) ← 只读遍历，不改变容器 ↓ find, count, for_each, search, equal, mismatch 修改序列操作 (27 个) ← 改变元素值或顺序 ↓ copy, move, transform, replace, fill, reverse, rotate 排序与相关操作 (15 个) ← 排序、二分查找、集合运算 ↓ sort, stable_sort, partial_sort, nth_element, binary_search 数值算法 (5 个) ← 数学计算 ↓ accumulate, inner_product, partial_sum, adjacent_difference
// 通用性：通过迭代器抽象，适用于任何容器 template<typename InputIt, typename UnaryFunction> UnaryFunction for_each(InputIt first, InputIt last, UnaryFunction f) { for (; first != last; ++first) { f(*first); // 对每个元素应用函数 } return f; // 返回函数对象，可携带状态 }
// 组合性：算法可以链式组合 auto result = std::views::numbers | std::views::filter(is_prime) | std::views::transform(square) | std::views::take(10);
// 1. find 系列：线性查找 std::vector vec = {1, 2, 3, 4, 5, 6, 7, 8, 9};
// 基本查找 auto it = std::find(vec.begin(), vec.end(), 5); if (it != vec.end()) { std::cout << "找到 5，位置：" << std::distance(vec.begin(), it) << std::endl; }
// 条件查找 auto even_it = std::find_if(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; });
// 查找连续重复元素 std::vector nums = {1, 2, 2, 2, 3, 4, 4, 5}; auto adj_it = std::adjacent_find(nums.begin(), nums.end()); // 返回第一个重复对 {2, 2} 的迭代器
// 2. search 系列：子序列查找 std::string text = "the quick brown fox jumps over the lazy dog"; std::string pattern = "fox"; auto pos = std::search(text.begin(), text.end(), pattern.begin(), pattern.end());
// 3. 二分查找（要求有序） std::sort(vec.begin(), vec.end()); bool found = std::binary_search(vec.begin(), vec.end(), 5); auto lower = std::lower_bound(vec.begin(), vec.end(), 5); // 第一个≥5 的位置 auto upper = std::upper_bound(vec.begin(), vec.end(), 5); // 第一个＞5 的位置
// 1. 计数算法 std::vector data = {1, 2, 3, 2, 4, 2, 5, 2, 6}; int count_2 = std::count(data.begin(), data.end(), 2); // 4 int count_even = std::count_if(data.begin(), data.end(), [](int x) { return x % 2 == 0; }); // 5
// 2. 比较算法 std::vector a = {1, 2, 3, 4, 5}; std::vector b = {1, 2, 3, 4, 5}; std::vector c = {1, 2, 3, 4, 6};
bool equal_ab = std::equal(a.begin(), a.end(), b.begin()); // true bool equal_ac = std::equal(a.begin(), a.end(), c.begin()); // false
// 3. 不匹配查找（找第一个不同点） auto mismatch_pair = std::mismatch(a.begin(), a.end(), c.begin()); if (mismatch_pair.first != a.end()) { std::cout << "第一个不同点：a=" << *mismatch_pair.first << ", c=" << *mismatch_pair.second << std::endl; }
// 1. 拷贝算法 std::vector src = {1, 2, 3, 4, 5}; std::vector dst(5);
// 基本拷贝 std::copy(src.begin(), src.end(), dst.begin());
// 条件拷贝 std::vector evens; std::copy_if(src.begin(), src.end(), std::back_inserter(evens), [](int x) { return x % 2 == 0; }); // {2, 4}
// 反向拷贝 std::vector reversed(5); std::copy(src.rbegin(), src.rend(), reversed.begin()); // {5, 4, 3, 2, 1}
// 2. 移动算法（C++11） std::vector<std::unique_ptr> src_ptrs; for (int i = 0; i < 5; ++i) { src_ptrs.push_back(std::make_unique(i)); }
std::vector<std::unique_ptr> dst_ptrs(5); std::move(src_ptrs.begin(), src_ptrs.end(), dst_ptrs.begin()); // src_ptrs 现在包含空 unique_ptr
// 3. 安全拷贝算法（防止重叠） std::vector overlapping = {1, 2, 3, 4, 5, 6, 7, 8, 9}; // 将前 5 个元素向后移动 3 位 std::copy_backward(overlapping.begin(), overlapping.begin() + 5, overlapping.begin() + 8); // 结果：{1, 2, 3, 1, 2, 3, 4, 5, 9}
// 1. transform：元素转换 std::vector numbers = {1, 2, 3, 4, 5}; std::vector squares(numbers.size());
// 一元变换 std::transform(numbers.begin(), numbers.end(), squares.begin(), [](int x) { return x * x; }); // {1, 4, 9, 16, 25}
// 二元变换（合并两个序列） std::vector a = {1, 2, 3, 4, 5}; std::vector b = {10, 20, 30, 40, 50}; std::vector sums(a.size());
std::transform(a.begin(), a.end(), b.begin(), sums.begin(), std::plus()); // {11, 22, 33, 44, 55}
// 2. replace 系列 std::vector data = {1, 2, 3, 2, 4, 2, 5};
// 替换所有等于 2 的元素为 99 std::replace(data.begin(), data.end(), 2, 99); // {1, 99, 3, 99, 4, 99, 5}
// 条件替换 std::replace_if(data.begin(), data.end(), [](int x) { return x > 3; }, 0); // {1, 0, 3, 0, 0, 0, 0}
// 3. fill 算法 std::vector vec(10); std::fill(vec.begin(), vec.end(), 42); // 全部填充为 42
std::fill_n(vec.begin() + 2, 5, 99); // 从第 3 个元素开始，填充 5 个 99
// 重要：remove 算法并不真正删除元素，而是移动元素 std::vector numbers = {1, 2, 3, 2, 4, 2, 5, 2};
// 1. remove：移动要删除的元素到末尾，返回新的逻辑结尾 auto new_end = std::remove(numbers.begin(), numbers.end(), 2); // numbers 现在可能是：{1, 3, 4, 5, ?, ?, ?, ?}，?表示未指定值
// 真正删除需要结合 erase numbers.erase(new_end, numbers.end()); // {1, 3, 4, 5}
// 2. remove_if：条件删除 std::vector data = {1, 2, 3, 4, 5, 6, 7, 8, 9}; auto it = std::remove_if(data.begin(), data.end(), [](int x) { return x % 2 == 0; }); // 删除偶数 data.erase(it, data.end()); // {1, 3, 5, 7, 9}
// 3. unique：去除连续重复 std::vector dupes = {1, 1, 2, 2, 2, 3, 4, 4, 5}; auto unique_end = std::unique(dupes.begin(), dupes.end()); dupes.erase(unique_end, dupes.end()); // {1, 2, 3, 4, 5}
// 自定义比较的 unique std::vectorstd::string words = {"hello", "Hello", "HELLO", "world", "World"}; auto word_end = std::unique(words.begin(), words.end(), [](const std::string& a, const std::string& b) { std::string a_lower = a; std::string b_lower = b; std::transform(a_lower.begin(), a_lower.end(), a_lower.begin(), ::tolower); std::transform(b_lower.begin(), b_lower.end(), b_lower.begin(), ::tolower); return a_lower == b_lower; }); words.erase(word_end, words.end()); // {"hello", "world"}
// 1. 基本排序 std::vector numbers = {5, 2, 8, 1, 9, 3, 7, 4, 6};
// 快速排序（不稳定） std::sort(numbers.begin(), numbers.end()); // 升序 std::sort(numbers.begin(), numbers.end(), std::greater()); // 降序
// 稳定排序（保持相等元素的原始顺序） struct Student { std::string name; int score; };
std::vector students = { {"Alice", 85}, {"Bob", 85}, {"Charlie", 90}, {"David", 80} };
std::stable_sort(students.begin(), students.end(), [](const Student& a, const Student& b) { return a.score > b.score; // 按分数降序 });
// 2. 部分排序 std::vector data = {9, 8, 7, 6, 5, 4, 3, 2, 1};
// 部分排序：保证前 5 个是最小的，但不保证顺序 std::partial_sort(data.begin(), data.begin() + 5, data.end()); // 结果：前 5 个是{1, 2, 3, 4, 5}，后 4 个未定义
// 3. 第 n 个元素（快速选择） std::vector nums = {9, 3, 6, 2, 7, 1, 8, 5, 4}; auto middle = nums.begin() + nums.size() / 2;
// 使得第 n 个元素就位，左边都≤它，右边都≥它 std::nth_element(nums.begin(), middle, nums.end()); std::cout << "中位数：" << *middle << std::endl; // 5
// 堆操作（基于 vector 的优先队列） std::vector heap = {3, 1, 4, 1, 5, 9, 2, 6};
// 1. 建立最大堆 std::make_heap(heap.begin(), heap.end()); // {9, 5, 6, 1, 1, 4, 2, 3}
// 2. 添加元素 heap.push_back(7); std::push_heap(heap.begin(), heap.end()); // 重新调整堆
// 3. 弹出堆顶 std::pop_heap(heap.begin(), heap.end()); // 最大元素移动到末尾 heap.pop_back(); // 移除最大元素
// 4. 堆排序 std::vector data = {3, 1, 4, 1, 5, 9, 2, 6}; std::make_heap(data.begin(), data.end()); std::sort_heap(data.begin(), data.end()); // {1, 1, 2, 3, 4, 5, 6, 9}
// 前提：两个输入序列必须已排序 std::vector set1 = {1, 2, 3, 4, 5}; std::vector set2 = {3, 4, 5, 6, 7}; std::vector result;
// 1. 并集 std::set_union(set1.begin(), set1.end(), set2.begin(), set2.end(), std::back_inserter(result)); // {1, 2, 3, 4, 5, 6, 7}
// 2. 交集 result.clear(); std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), std::back_inserter(result)); // {3, 4, 5}
// 3. 差集（set1 - set2） result.clear(); std::set_difference(set1.begin(), set1.end(), set2.begin(), set2.end(), std::back_inserter(result)); // {1, 2}
// 4. 对称差集（只在其中一个集合中） result.clear(); std::set_symmetric_difference(set1.begin(), set1.end(), set2.begin(), set2.end(), std::back_inserter(result)); // {1, 2, 6, 7}
// 5. 包含判断 bool includes = std::includes(set1.begin(), set1.end(), set2.begin(), set2.begin() + 3); // 检查{3,4,5}是否在 set1 中
// 1. accumulate：累加/累乘 std::vector nums = {1, 2, 3, 4, 5};
// 基本累加 int sum = std::accumulate(nums.begin(), nums.end(), 0); // 15
// 累乘 int product = std::accumulate(nums.begin(), nums.end(), 1, std::multiplies()); // 120
// 字符串连接 std::vectorstd::string words = {"Hello", " ", "World", "!"}; std::string sentence = std::accumulate(words.begin(), words.end(), std::string()); // "Hello World!"
// 2. inner_product：内积（点积） std::vector a = {1, 2, 3}; std::vector b = {4, 5, 6};
int dot_product = std::inner_product(a.begin(), a.end(), b.begin(), 0); // 计算：14 + 25 + 3*6 = 32
// 自定义操作的内积 int custom_product = std::inner_product(a.begin(), a.end(), b.begin(), 0, std::plus(), // 累加操作 [](int x, int y) { return (x - y) * (x - y); }); // 差值的平方 // 计算：(1-4)² + (2-5)² + (3-6)² = 27
std::vector nums = {1, 2, 3, 4, 5}; std::vector result(nums.size());
// 1. partial_sum：部分和（前缀和） std::partial_sum(nums.begin(), nums.end(), result.begin()); // result = {1, 3, 6, 10, 15}
// 自定义操作的部分和 std::partial_sum(nums.begin(), nums.end(), result.begin(), std::multiplies()); // 部分积 // result = {1, 2, 6, 24, 120}
// 2. adjacent_difference：相邻差 std::adjacent_difference(nums.begin(), nums.end(), result.begin()); // result = {1, 1, 1, 1, 1} (第一个元素保持原值)
// 自定义操作的相邻差 std::adjacent_difference(nums.begin(), nums.end(), result.begin(), [](int a, int b) { return std::abs(a - b); }); // 绝对差
#include #include
namespace rv = std::views;
std::vector numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
// 1. 链式操作（惰性求值） auto result = numbers | rv::filter([](int x) { return x % 2 == 0; }) // 取偶数 | rv::transform([](int x) { return x * x; }) // 平方 | rv::take(3); // 取前 3 个
// 转换为容器 std::vector squares(std::ranges::begin(result), std::ranges::end(result)); // {4, 16, 36}
// 2. 直接使用 ranges 算法 bool all_even = std::ranges::all_of(numbers, [](int x) { return x % 2 == 0; }); // false
// 3. 投影（Projection） struct Person { std::string name; int age; };
std::vector people = { {"Alice", 25}, {"Bob", 30}, {"Charlie", 20}, {"David", 35} };
// 按年龄排序，使用投影 std::ranges::sort(people, {}, &Person::age); // 等价于：std::ranges::sort(people, [](const Person& a, const Person& b) { return a.age < b.age; });
// 复杂的管道操作示例 std::vector data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
auto processed = data | rv::drop(2) // 跳过前 2 个：{3,4,5,6,7,8,9,10} | rv::take(6) // 取 6 个：{3,4,5,6,7,8} | rv::filter([](int x) { return x % 2 == 1; // 取奇数：{3,5,7} }) | rv::transform([](int x) { return x * 10; // 乘以 10：{30,50,70} }) | rv::reverse(); // 反转：{70,50,30}
// 惰性求值：直到迭代时才计算 for (int x : processed) { std::cout << x << " "; // 输出：70 50 30 }
// 根据需求选择合适的算法 void process_data(const std::vector& data) { // 1. 只需要检查是否存在 → find bool has_negative = std::find_if(data.begin(), data.end(), [](int x) { return x < 0; }) != data.end();
// 2. 需要计数 → count
int negative_count = std::count_if(data.begin(), data.end(),
[](int x) { return x < 0; });
// 3. 需要检查所有/任意元素满足条件 → all_of/any_of
bool all_positive = std::all_of(data.begin(), data.end(),
[](int x) { return x > 0; });
// 4. 需要排序 → 根据稳定性选择
std::vector<int> sorted = data;
if (need_stable_sort) {
std::stable_sort(sorted.begin(), sorted.end());
} else {
std::sort(sorted.begin(), sorted.end());
}
// 5. 需要部分排序 → nth_element 或 partial_sort
std::vector<int> copy = data;
auto mid = copy.begin() + copy.size() / 2;
std::nth_element(copy.begin(), mid, copy.end()); // 找中位数
}
// 陷阱 1：迭代器失效 std::vector vec = {1, 2, 3, 4, 5}; auto it = std::find(vec.begin(), vec.end(), 3);
// 错误：在修改容器后使用旧迭代器 vec.erase(it); // it 现在可能失效
// 正确：立即使用或重新获取 it = vec.erase(it); // erase 返回新的有效迭代器
// 陷阱 2：错误使用 remove std::vector numbers = {1, 2, 3, 2, 4, 2, 5};
// 错误：以为 remove 会删除元素 std::remove(numbers.begin(), numbers.end(), 2); // numbers 大小不变！只是移动了元素
// 正确：erase-remove 惯用法 numbers.erase( std::remove(numbers.begin(), numbers.end(), 2), numbers.end() );
// 陷阱 3：未排序就使用二分查找 std::vector unsorted = {5, 3, 1, 4, 2};
// 错误：对未排序序列使用 binary_search bool found = std::binary_search(unsorted.begin(), unsorted.end(), 3); // 未定义行为
// 正确：先排序 std::sort(unsorted.begin(), unsorted.end()); found = std::binary_search(unsorted.begin(), unsorted.end(), 3); // 正确
// 实现自己的算法（遵循 STL 风格） template<typename ForwardIt, typename BinaryPredicate> ForwardIt unique_erase(ForwardIt first, ForwardIt last, BinaryPredicate p) { if (first == last) return last;
ForwardIt result = first;
while (++first != last) {
if (!p(*result, *first) && ++result != first) {
*result = std::move(*first);
}
}
return ++result;
}
// 使用示例 std::vectorstd::string words = {"apple", "Apple", "APPLE", "banana", "Banana"}; auto new_end = unique_erase(words.begin(), words.end(), [](const std::string& a, const std::string& b) { std::string a_lower, b_lower; std::transform(a.begin(), a.end(), std::back_inserter(a_lower), ::tolower); std::transform(b.begin(), b.end(), std::back_inserter(b_lower), ::tolower); return a_lower == b_lower; }); words.erase(new_end, words.end()); // {"apple", "banana"}
希望以上内容对你有帮助。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online