C++ STL 算法深度解析：从基础到 C++20 Ranges

三、修改序列操作算法

3.1 拷贝与移动算法

// 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}

3.2 变换与替换算法

// 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

3.3 删除与去重算法

// 重要：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"}

四、排序与相关算法

4.1 排序算法详解

// 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

4.2 堆算法

// 堆操作（基于 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}

4.3 集合算法

// 前提：两个输入序列必须已排序 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 中

五、数值算法

5.1 累加与内积

// 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

5.2 部分和与相邻差

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); }); // 绝对差

六、C++20 Ranges 算法（现代 C++）

6.1 Ranges 视图管道

#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; });

6.2 范围适配器组合

// 复杂的管道操作示例 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 }

七、性能优化与最佳实践

7.1 算法选择指南

// 根据需求选择合适的算法 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());  // 找中位数

}

7.2 避免常见陷阱

// 陷阱 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); // 正确

7.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"}

希望以上内容对你有帮助。