跳转到内容
VitaLogos
新建笔记

C++ 算法：范围前提、排序查询与删除惯用法

知识概念更新于 编辑本文

标准库算法通过迭代器操作范围，并不自动理解容器的全部规则。使用前要确认范围有效、迭代器能力足够、输出空间存在，以及比较器和排序前提成立。本页使用C++17，合并了原 random_shuffle升级故障笔记。

1. 范围、头文件和比较器

跳转到“1. 范围、头文件和比较器”

大多数算法接收半开范围 [first, last)：包含first指向的元素，不包含last。空范围可以是 first == last，但不能解引用它的末端。

  • <algorithm>提供排序、查找、复制等多数算法。
  • <numeric>提供 accumulate、inner_product、partial_sum、iota、adjacent_difference，不能依赖其他头文件恰好间接包含它。
  • <iterator>提供插入迭代器；<random>提供随机引擎。

排序比较器必须构成严格弱序。例如升序用 a < b，不能用 a <= b，后者会让 comp(x,x)为true。涉及NaN等特殊值时，应先定义数据策略，不能随意假设普通浮点 <满足所需关系。stable_sort保留的是比较器认为等价元素的原有相对顺序。

2. 常用算法与前提

跳转到“2. 常用算法与前提”
算法做什么关键条件/结果
sort / stable_sort排序；后者稳定。需要随机访问迭代器；list使用成员 sort()。
partial_sort把选出的最小若干项排到前段并排序。后段不保证整体排序。
nth_element把第n位置分隔到完整排序时应处的一侧关系。两侧均不保证排好序。
reverse / rotate反转/把指定中间位置旋到开头。按各算法要求提供双向或前向等迭代器能力。
shuffle用显式随机引擎打乱。随机访问范围，结果是原元素的置换。
find / count找首个相等元素/计数。find失败返回last；计数类型不宜固定写成int。
equal / mismatch比较序列/找到首个不匹配位置。优先使用给出两段末端的重载，避免第二段过短。
for_each对每项调用函数。形参按值只改副本；要改元素使用合适的引用。
transform把转换结果写入输出范围。输出必须已存在或使用插入迭代器；不要任意重叠输入输出。
copy / fill复制/给已有范围赋值。不会自动为普通输出迭代器扩容。
replace将范围内匹配值替换。容器大小不变。
remove / remove_if把保留项移到前段，返回逻辑末端。不改变容器的物理size。
unique把连续等价项压成一项。只处理相邻重复，也不改变size。
lower_bound / upper_bound返回下界/上界。范围需按相应比较关系分区；按同一比较器排序是常用充分条件。
equal_range返回等价元素范围。返回 pair<iterator,iterator>，一般用auto接收。
min_element / max_element找最小/最大位置。空范围返回last，先检查再解引用。
swap / iter_swap交换对象/迭代器所指元素。迭代器本身交换与所指元素交换不是一回事。

3. 排序、求和与边界查询

跳转到“3. 排序、求和与边界查询”
#include <algorithm>
#include <cassert>
#include <iterator>
#include <numeric>
#include <vector>


int main()
{
    std::vector<int> values{3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    std::sort(values.begin(), values.end());
    const auto sum = std::accumulate(values.begin(), values.end(), 0LL);
    assert(sum == 39);
    const auto minimum = std::min_element(values.begin(), values.end());
    const auto maximum = std::max_element(values.begin(), values.end());
    assert(minimum != values.end() && *minimum == 1);
    assert(maximum != values.end() && *maximum == 9);


    const auto range = std::equal_range(values.begin(), values.end(), 5);
    assert(std::distance(range.first, range.second) == 2);
    assert(range.first == std::lower_bound(values.begin(), values.end(), 5));
    assert(range.second == std::upper_bound(values.begin(), values.end(), 5));
    assert(std::find(values.begin(), values.end(), 99) == values.end());
    std::vector<int> empty;
    assert(std::max_element(empty.begin(), empty.end()) == empty.end());
}

累加初值决定 accumulate的累加类型。这里的 0LL选择 long long，但仍需确认实际数据总和不会溢出；换大类型不等于无限精度。原来的 std::pair<it,it>把变量当作类型，不能编译，使用返回类型推导即可。

4. erase-remove与相邻去重

跳转到“4. erase-remove与相邻去重”
#include <algorithm>
#include <cassert>
#include <iterator>
#include <vector>


int main()
{
    std::vector<int> values{1, 2, 2, 3, 1};
    auto logicalEnd = std::unique(values.begin(), values.end());
    assert(values.size() == 5); // 算法尚未删除容器元素。
    values.erase(logicalEnd, values.end());
    assert((values == std::vector<int>{1, 2, 3, 1}));


    values.erase(std::remove(values.begin(), values.end(), 1), values.end());
    assert((values == std::vector<int>{2, 3}));


    std::vector<int> doubled;
    std::transform(values.begin(), values.end(), std::back_inserter(doubled),
                   [](int value) { return value * 2; });
    assert((doubled == std::vector<int>{4, 6}));
}

逻辑末端之后仍是容器中的对象，其值不应当作被删除值的可靠清单。如果想对所有重复值去重，常见办法是排序后 unique再 erase，但排序会改变顺序；要保留原有顺序，需要另外设计“已见集合”等策略。list也有自己的 remove/unique成员，它们能实际移除节点，不能与通用算法混淆。

5. 数值算法

跳转到“5. 数值算法”
算法例子含义
accumulate把初值与一段序列依次折叠，例如求和。
inner_product两段序列逐项组合再累加，第二段必须足够长。
partial_sum输出每个前缀的累计结果。
iota从起始值递增填入已存在的范围。
adjacent_difference首项原样输出，其余输出与前项的差。
#include <cassert>
#include <numeric>
#include <vector>


int main()
{
    std::vector<int> values(4);
    std::iota(values.begin(), values.end(), 1);
    std::vector<int> sums(4), differences(4);
    std::partial_sum(values.begin(), values.end(), sums.begin());
    std::adjacent_difference(sums.begin(), sums.end(), differences.begin());
    assert((sums == std::vector<int>{1, 3, 6, 10}));
    assert(differences == values);
    assert(std::inner_product(values.begin(), values.end(), values.begin(), 0) == 30);
}

6. 升级后random_shuffle不可用

跳转到“6. 升级后random_shuffle不可用”

std::random_shuffle在C++14弃用、C++17移除。替代的 std::shuffle从C++11就已提供，需要显式传入符合要求的均匀随机位生成器。

#include <algorithm>
#include <cassert>
#include <random>
#include <vector>


int main()
{
    const std::vector<int> original{1, 2, 3, 4, 5};
    auto values = original;
    std::mt19937 engine(2026); // 固定种子便于本环境复现。
    std::shuffle(values.begin(), values.end(), engine);
    auto sorted = values;
    std::sort(sorted.begin(), sorted.end());
    assert(sorted == original);
}

若需要非固定种子，可按应用要求使用 std::random_device初始化引擎，但它的熵来源和行为依赖实现。固定引擎/种子也不保证不同标准库的 shuffle产生完全相同排列，因此测试检查置换关系。mt19937适合一般仿真和随机抽样，不应用于密码、访问令牌等安全用途。

依据

跳转到“依据”