C++ 算法库 algorithm

下面对 C++ 标准库中 <algorithm> 头文件所提供的算法做一个系统、详细的梳理与讲解，内容包含常见的算法分类、典型算法、使用示例及其时间复杂度等。

---

一、概述

• <algorithm> 是 C++ 标准库中最核心的头文件之一，提供了对序列（通常是容器、原始数组或迭代器区间）进行各类操作的通用算法。
• 所有算法都以迭代器（Iterator）作为输入和输出参数，可以与标准容器 (vector, list, deque 等) 和原始数组无缝协作。
• 算法一般分为不修改序列（non‐modifying）、修改序列（modifying）、排序与相关（sorting）、数值算法（numeric）、堆算法（heap）和集合算法（set）等几大类。

---

二、按功能分类详解

1. 不修改序列算法（Non‐Modifying Sequence）

这些算法不会改变原序列元素，但可进行查找、计数、比较和判断等操作。

函数	功能	典型时间复杂度
std::for_each	对区间内每个元素依次执行指定操作	O(N)
std::find	查找第一个等于给定值的元素	O(N)
std::find_if	查找第一个满足谓词的元素	O(N)
std::count	统计等于给定值的元素个数	O(N)
std::all_of、any_of、none_of	判断区间内所有/任一/无元素满足谓词	O(N)
std::equal	判断两区间元素是否依次相等	O(N)

示例：查找并统计

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v{1, 3, 5, 3, 7, 3};
    // 查找第一个值为3的元素
    auto it = std::find(v.begin(), v.end(), 3);
    if (it != v.end()) {
        std::cout << "Found 3 at index " << (it - v.begin()) << "\n";
    }
    // 统计值为3的元素个数
    int cnt = std::count(v.begin(), v.end(), 3);
    std::cout << "Number of 3's: " << cnt << "\n";
    return 0;
}

---

2. 修改序列算法（Modifying Sequence）

这些算法会对序列本身进行插入、删除、替换、填充或重新排列等操作。

函数	功能	典型时间复杂度
std::copy	复制区间到另一序列	O(N)
std::move	将元素移动（非复制）	O(N)
std::fill / fill_n	用指定值填充区间	O(N)
std::transform	对元素应用一元/二元操作并写入目标区间	O(N)
std::replace	将区间中等于特定值的元素替换为新值	O(N)
std::remove / remove_if	删除值或满足谓词的元素（不改变大小）	O(N)
std::unique	删除连续重复元素	O(N)

示例：删除与填充

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v{1, 2, 2, 3, 4, 2, 5};
    // remove+erase 习惯用法：删除所有值为2的元素
    v.erase(std::remove(v.begin(), v.end(), 2), v.end());
    // 用0填充前3个元素
    std::fill_n(v.begin(), 3, 0);
    for (int x : v) std::cout << x << ' ';  // 输出: 0 0 0 3 4 5
    return 0;
}

---

3. 排序与相关算法（Sorting and Related）

函数	功能	典型时间复杂度
std::sort	对区间进行快速排序	平均 O(Nlog⁡N)
std::stable_sort	对区间进行稳定排序	O(Nlog⁡2N) 或改进版 O(Nlog⁡N)
std::partial_sort	部分排序，前 K 小元素有序	O(Nlog⁡K)
std::nth_element	将第 N 小元素放到正确位置	平均 O(N)
std::binary_search、lower_bound、upper_bound	二分查找及范围定位	O(log⁡N)

示例：排序与二分查找

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v{5,1,4,2,3};
    std::sort(v.begin(), v.end());  // 升序排序
    // 查找元素3
    bool found = std::binary_search(v.begin(), v.end(), 3);
    std::cout << (found ? "Exists\n" : "Not found\n");
    return 0;
}

---

4. 数值算法（Numeric）

提供对区间元素进行累加、内积、差分等操作。

函数	功能	典型时间复杂度
std::accumulate	累加区间内所有元素	O(N)
std::inner_product	计算两个区间内元素的内积	O(N)
std::iota	生成等差序列	O(N)
std::adjacent_difference	邻接差分	O(N)

示例：累加与序列生成

#include <algorithm>
#include <numeric>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v(5);
    std::iota(v.begin(), v.end(), 1);  // v = {1,2,3,4,5}
    int sum = std::accumulate(v.begin(), v.end(), 0);
    std::cout << "Sum = " << sum << "\n";  // 输出 Sum = 15
    return 0;
}

---

5. 堆算法（Heap）

可以将区间视为二叉堆，进行堆的构造、插入、删除等操作。

函数	功能	典型时间复杂度
std::make_heap	将区间构造为最大堆	O(N)
std::push_heap	在已有堆中插入新元素	O(log⁡N)
std::pop_heap	弹出堆顶元素（仅重排，不缩容）	O(log⁡N)
std::sort_heap	将堆排序为升序区间	O(Nlog⁡N)

示例：堆的使用

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v{3,1,4,1,5,9};
    std::make_heap(v.begin(), v.end());
    std::cout << "Max: " << v.front() << "\n";  // 堆顶最大值
    // 插入元素 6
    v.push_back(6);
    std::push_heap(v.begin(), v.end());
    std::cout << "New Max: " << v.front() << "\n";
    return 0;
}

---

6. 集合算法（Set Operations）

针对已排序区间，求交集、并集、差集等。

函数	功能	典型时间复杂度
std::set_union	并集	O(N+M)
std::set_intersection	交集	O(N+M)
std::set_difference	差集	O(N+M)
std::set_symmetric_difference	对称差集	O(N+M)

注意：参与集合运算的两个序列必须先进行排序。

std::vector<int> a{1,2,4,5}, b{2,3,5,6}, c;
std::sort(a.begin(), a.end());
std::sort(b.begin(), b.end());
std::set_union(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(c));
// c = {1,2,3,4,5,6}

---

三、实践建议

1. 选择合适的算法
   • 当仅需判断元素存在与否，优先 std::find；需频繁查找、统计时考虑用哈希或排序 + 二分。
   • 大规模排序请用 std::sort；需保证稳定性时用 std::stable_sort。
2. 避免不必要的拷贝或内存分配
   • 对于大对象，优先使用 std::move 或就地修改算法，如 std::remove_if + erase。
3. 利用标准迭代器适配器
   • 如 std::back_inserter, std::front_inserter 等，与算法结合可简化输出过程。
4. 关注复杂度
   • 不同算法对同一问题的时间/空间复杂度差异较大，选择前要对序列长度特征有初步预估。

---

四、常见面试题示例

1. 判断区间是否为回文bool is_palindrome(auto first, auto last) { return std::equal(first, last, std::reverse_iterator<decltype(last)>(last)); }
2. 滑动窗口最大值
   • 可用堆、双端队列配合 std::make_heap、pop_heap 实现。
3. 合并 K 个已排序链表
   • 可借助 std::priority_queue（底层即堆算法）实现最小堆。

---

通过对 <algorithm> 中各类算法的分类梳理与示例，能够帮助你在实际开发与面试中快速定位所需工具，并且写出高效、可读性强的代码。祝学习愉快！