1. 非修改序列操作

此类算法仅对容器进行读取或查找，不会改变其原有内容。

1.1 查找算法：find, find_if, find_end

• find：定位首个匹配指定值的元素。
• find_if：根据自定义谓词查找第一个满足条件的元素。
• find_end：在序列中搜索最后一次出现的子序列。

std::vector<int> data = {10, 25, 40, 55, 70, 40, 55};

// 寻找数值 40
auto pos = std::find(data.begin(), data.end(), 40);
if (pos != data.end()) {
    std::cout << "Found: " << *pos << std::endl;
}

// 寻找第一个超过 50 的数
auto high_val = std::find_if(data.begin(), data.end(), [](int v) {
    return v > 50;
});

// 查找子序列最后出现的位置
std::vector<int> sub = {40, 55};
auto last_sub = std::find_end(data.begin(), data.end(), sub.begin(), sub.end());

1.2 计数算法：count, count_if

std::vector<int> scores = {1, 2, 2, 3, 2, 4};
// 统计 2 出现的次数
int num_twos = std::count(scores.begin(), scores.end(), 2); 
// 统计偶数数量
int evens = std::count_if(scores.begin(), scores.end(), [](int s) { 
    return s % 2 == 0; 
});

1.3 逻辑检查：all_of, any_of, none_of

std::vector<int> vals = {2, 4, 6, 8};
bool is_all_even = std::all_of(vals.begin(), vals.end(), [](int n) { return n % 2 == 0; });
bool has_negative = std::any_of(vals.begin(), vals.end(), [](int n) { return n < 0; });

2. 修改序列操作

此类算法会重排、替换或修改容器中的元素值。

2.1 复制与转换：copy, transform

std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> target;

// 复制满足条件的元素
std::copy_if(source.begin(), source.end(), std::back_inserter(target), [](int x) {
    return x > 2;
});

// 元素映射（变换）
std::vector<int> cubes;
std::transform(source.begin(), source.end(), std::back_inserter(cubes), [](int x) {
    return x * x * x;
});

2.2 替换与移除

注意：remove 并不真正减小容器大小，需配合 erase 使用。

std::vector<int> items = {1, 9, 3, 9, 5};

// 替换数值
std::replace(items.begin(), items.end(), 9, 0); 

// Erase-Remove 惯用法移除所有 0
items.erase(std::remove(items.begin(), items.end(), 0), items.end());

// 移除相邻重复项
auto it = std::unique(items.begin(), items.end());
items.erase(it, items.end());

2.3 重排操作：reverse, rotate, shuffle

std::vector<int> sequence = {1, 2, 3, 4, 5};
// 反转
std::reverse(sequence.begin(), sequence.end());
// 旋转（将第二个元素移到首位）
std::rotate(sequence.begin(), sequence.begin() + 1, sequence.end());

// 随机打乱
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(sequence.begin(), sequence.end(), g);

3. 排序及相关检索

排序算法是 STL 的核心部分，大多数检索算法要求区间有序。

3.1 排序：sort, partial_sort

std::vector<int> unsorted = {9, 1, 5, 2, 7};
// 全排序
std::sort(unsorted.begin(), unsorted.end());
// 稳定排序（保持相等元素的相对顺序）
std::stable_sort(unsorted.begin(), unsorted.end());
// 寻找前 3 个最小元素并排序
std::partial_sort(unsorted.begin(), unsorted.begin() + 3, unsorted.end());

3.2 二分查找：lower_bound, upper_bound

std::vector<int> sorted_data = {10, 20, 20, 30, 40};
// 查找第一个不小于 20 的位置
auto lb = std::lower_bound(sorted_data.begin(), sorted_data.end(), 20); 
// 查找第一个大于 20 的位置
auto ub = std::upper_bound(sorted_data.begin(), sorted_data.end(), 20);

4. 数值处理算法

这些算法通常定义在 <numeric> 头文件中。

#include <numeric>

std::vector<int> nums = {1, 2, 3, 4, 5};
// 累加求和
int total = std::accumulate(nums.begin(), nums.end(), 0);
// 填充序列（10, 11, 12...）
std::iota(nums.begin(), nums.end(), 10);
// 计算相邻差值
std::vector<int> diffs(nums.size());
std::adjacent_difference(nums.begin(), nums.end(), diffs.begin());

5. 堆操作算法

利用现有容器（如 vector）构建和管理最大堆。

std::vector<int> heap_data = {5, 1, 9, 3};
std::make_heap(heap_data.begin(), heap_data.end()); // 建立堆

heap_data.push_back(10);
std::push_heap(heap_data.begin(), heap_data.end()); // 插入后重构

std::pop_heap(heap_data.begin(), heap_data.end()); // 弹出最大值到末尾
heap_data.pop_back();

6. 常见技术问答

问：为何 std::remove 之后必须接 erase？
答：std::remove 采用元素移动覆盖的逻辑，它将不被删除的元素移到容器前端，并返回指向第一个"废弃"位置的迭代器。容器本身的逻辑大小并没有改变，物理内存中该位置之后的旧数据依然存在。只有调用 container.erase 才能真正缩减容器长度。

问：std::sort 和 std::stable_sort 选哪个？
答：sort 通常速度更快，但在排序具有相同权重的对象时，它可能改变它们的原始相对位置。如果业务逻辑依赖于这种相对位置（例如先按时间排序，再按类别排序），则必须使用 stable_sort。

问：使用二分查找算法的前提是什么？
答：区间必须是有序的。binary_search、lower_bound 等算法依赖有序性来实现对数时间复杂度 $O(\log n)$。如果在无序容器上使用，结果将是未定义的。