← C++ 教材目录（共 13 章）

第 8 章　STL 算法与常用编程范式

red wenzi · 2026-09-15 · 编程语言 · C++ · 📖 预计阅读 22 分钟 · 共 5 道练习
🎯 本章你会学到：sort 与 lambda、erase-remove、二分函数。建议边读边敲代码，每节的练习先自己做，再展开答案对照。

算法库统一以“迭代器区间 [first, last)”为参数——左闭右开，last 指向最后一个元素的下一个位置。理解了这一点，所有算法的参数形式就都好记了。

8.1 排序与 lambda

std::sort 是你在算法题里用得最多的函数。配合 lambda，任何排序规则都能写。

sort + lambda：多条件排序

lambda 的语法是 [捕获](参数) { 函数体 }，就地写一个匿名函数。排序规则里先比分数降序、相同再比名字升序，一个 lambda 搞定。

示例代码
std::sort(v.begin(), v.end(), [](const Student& a, const Student& b) {
    if (a.score != b.score) { return a.score > b.score; }
    return a.name < b.name;
});
⚠️ 易错点　比较器必须是严格弱序：相等时返回 false。写 return a.score >= b.score; 会让 sort 走进未定义行为，典型症状是段错误或元素丢失。

lambda 的捕获

[capture] 控制 lambda 怎么访问外部变量：[x] 按值捕获、[&x] 按引用捕获、[&] 全部按引用、[=] 全部按值。std::count_if(v.begin(), v.end(), [lowest](int x){ return x >= lowest; }) 能就近读取上下文变量。

⚠️ 易错点　按引用捕获的变量在 lambda 存活期间必须还在（别捕获局部变量的引用然后带出去用）。

✍️ 本节练习

8.1.1必做分数排序

读入 n 个学生（名字、分数），用 std::sort + lambda 按分数从高到低排序，分数相同按名字字典序升序，输出排序结果。

输入　第一行 n；接下来 n 行“名字 分数”。

输出　排序后每行“名字 分数”。

样例输入
3
Ann 90
Bob 95
Cid 90
样例输出
Bob 95
Ann 90
Cid 90

💡 提示　lambda 里先比 score 降序，相等再比 name 升序。

✅ 查看参考答案与解析 
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct Student { std::string name; int score; };
int main() {
    int n;
    std::cin >> n;
    std::vector<Student> v(n);
    for (int i = 0; i < n; ++i) { std::cin >> v[i].name >> v[i].score; }
    std::sort(v.begin(), v.end(), [](const Student& a, const Student& b) {
        if (a.score != b.score) { return a.score > b.score; }
        return a.name < b.name;
    });
    for (const auto& s : v) { std::cout << s.name << ' ' << s.score << '\n'; }
    return 0;
}

解析　比较器必须是严格弱序：相等返回 false。lambda 就近定义规则，最省事。

8.1.2挑战按绝对值排序

读入 n 个整数（可正可负），按绝对值从小到大排序；绝对值相同则负数在前。输出排序结果。

输入　第一行 n；第二行 n 个整数。

输出　排序后的序列。

样例输入
5
-2 3 -1 2 1
样例输出
-1 1 -2 2 3

💡 提示　std::abs 在 <cstdlib>；lambda 里比 abs(a) 和 abs(b)，相等时负数优先（a < b）。

✅ 查看参考答案与解析 
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <vector>
int main() {
    int n;
    std::cin >> n;
    std::vector<int> v(n);
    for (int i = 0; i < n; ++i) { std::cin >> v[i]; }
    std::sort(v.begin(), v.end(), [](int a, int b) {
        if (std::abs(a) != std::abs(b)) { return std::abs(a) < std::abs(b); }
        return a < b;   // 绝对值相同，负数在前
    });
    for (size_t i = 0; i < v.size(); ++i) {
        std::cout << v[i] << (i + 1 == v.size() ? '\n' : ' ');
    }
    return 0;
}

解析　自定义比较器可以随意定义规则，只要满足严格弱序。

8.2 erase-remove 与二分查找

std::remove 这个名字有误导性：它不删除元素，只是把要保留的元素往前挪并返回新的逻辑结尾。真正删除要靠容器的 erase。

erase-remove 惯用法

v.erase(std::remove(v.begin(), v.end(), 2), v.end()); 删除所有等于 2 的元素。为什么拆两步？因为算法只拿到迭代器，不知道背后是 vector 还是数组，无法真正改变容器大小。按条件删用 remove_if + lambda。去重用 sort + unique + erase。

示例代码
v.erase(std::remove(v.begin(), v.end(), 2), v.end());
v.erase(std::remove_if(v.begin(), v.end(),
                       [](int x) { return x % 2 == 0; }), v.end());
⚠️ 易错点　忘记 v.erase(...) 只写 std::remove(...) 的话，元素其实没被删除（只是被移到后面）。

三个二分函数的明确分工

lower_bound 找第一个 >= x（左边界）；upper_bound 找第一个 > x（右边界之后）；两者相减 = x 出现的次数。binary_search 只回答“在不在”，需要位置信息时别用它。

示例代码
auto lo = std::lower_bound(v.begin(), v.end(), 3);  // 第一个 >= 3
auto up = std::upper_bound(v.begin(), v.end(), 3);  // 第一个 > 3
std::cout << (up - lo);   // 3 的个数
⚠️ 易错点　对 set/map 用成员函数 s.lower_bound(x)（沿树走 O(log n)）；用 std::lower_bound 会退化成 O(n)。

✍️ 本节练习

8.2.1必做删除所有 2

读入 n 个整数存入 vector，用 erase-remove 惯用法删除所有等于 2 的元素，输出剩余元素。

输入　第一行 n；第二行 n 个整数。

输出　删除 2 后剩下的数，空格分隔。

样例输入
7
1 2 3 2 4 2 5
样例输出
1 3 4 5

💡 提示　v.erase(std::remove(v.begin(), v.end(), 2), v.end());

✅ 查看参考答案与解析 
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
    int n;
    std::cin >> n;
    std::vector<int> v(n);
    for (int i = 0; i < n; ++i) { std::cin >> v[i]; }
    v.erase(std::remove(v.begin(), v.end(), 2), v.end());
    for (size_t i = 0; i < v.size(); ++i) {
        std::cout << v[i] << (i + 1 == v.size() ? '\n' : ' ');
    }
    return 0;
}

解析　std::remove 只把保留的元素前移，返回新逻辑结尾；erase 负责真正改变 size。

8.2.2挑战统计 >= x 的个数

读入 n 个整数排序，再读入一个 x，用 lower_bound 统计有多少个数 >= x。

输入　第一行 n；第二行 n 个整数；第三行 x。

输出　>= x 的个数。

样例输入
6
1 3 3 5 7 9
3
样例输出
5

💡 提示　lower_bound 找第一个 >= x 的位置 it，个数 = v.end() - it。

✅ 查看参考答案与解析 
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
    int n;
    std::cin >> n;
    std::vector<int> v(n);
    for (int i = 0; i < n; ++i) { std::cin >> v[i]; }
    std::sort(v.begin(), v.end());
    int x;
    std::cin >> x;
    auto it = std::lower_bound(v.begin(), v.end(), x);
    std::cout << (v.end() - it) << '\n';
    return 0;
}

解析　lower_bound 返回第一个 >= x 的位置；它到末尾的距离就是 >= x 的个数。

本章小结

🧩 本章综合练习

这几道题把本章多个知识点串起来，建议合上资料独立完成，再展开答案对照。

8.A综合成绩表：sort + lambda + count_if + lower_bound

读入 n 个学生（名字 分数），按分数降序、同分按名字升序输出；用 std::count_if 统计及格人数；把分数单独排序后用 std::lower_bound 统计 90 分及以上人数。

输入　第一行整数 n；接下来 n 行，每行「名字 分数」。

输出　先输出排序后的 n 行「名字 分数」；再输出 pass=、ge90=。

样例输入
5
Ann 90
Bob 59
Cid 90
Dan 72
Eve 100
样例输出
Eve 100
Ann 90
Cid 90
Dan 72
Bob 59
pass=4
ge90=3

💡 提示　比较器必须严格弱序：相等时返回 false；lower_bound 要求区间已升序。

✅ 查看参考答案与解析 
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>

struct Student {
    std::string name;
    int score{};
};

int main() {
    int n{};
    std::cin >> n;
    std::vector<Student> v(n);
    std::vector<int> scores;
    scores.reserve(static_cast<std::size_t>(n));
    for (int i = 0; i < n; ++i) {
        std::cin >> v[i].name >> v[i].score;
        scores.push_back(v[i].score);
    }

    std::sort(v.begin(), v.end(), [](const Student& a, const Student& b) {
        if (a.score != b.score) { return a.score > b.score; }   // 分数降序
        return a.name < b.name;                                 // 同分名字升序
    });
    for (const auto& s : v) { std::cout << s.name << ' ' << s.score << '\n'; }

    int pass = static_cast<int>(std::count_if(
        v.begin(), v.end(), [](const Student& s) { return s.score >= 60; }));
    std::cout << "pass=" << pass << '\n';

    std::sort(scores.begin(), scores.end());                    // 升序才能二分
    auto first90 = std::lower_bound(scores.begin(), scores.end(), 90);
    std::cout << "ge90=" << std::distance(first90, scores.end()) << '\n';
    return 0;
}

解析　count_if 用一个返回 bool 的 lambda 统计；lower_bound 返回第一个不小于 90 的位置，用 distance 算数量。

📚 本文概念都在知识大全：

STL 算法 · lambda 表达式 · 二分查找

← 上一章：第 7 章 STL 容器与迭代器下一章：第 9 章 现代 C++ 特性 →