C++ 练习册第 8 章 STL 算法

📝 本章练习：10 题（A 识别 / B 理解 / C 改错 / D 写程序）。先自己做完再看答案——A、B 档不翻书做，C、D 档必须真的编译运行。

8.1 排序与 lambda

A1识别判断题：std::sort 需要随机访问迭代器，所以不能直接给 std::list 排序。

答：______________

✅ 查看答案与解析

答案　对

解析：list 只有双向迭代器，要排序用它的成员函数 l.sort()。

A2识别判断题：lambda 里 [&] 表示按引用捕获外部变量。

答：______________

✅ 查看答案与解析

答案　对

解析：[&] 引用捕获，[=] 值捕获，[x] 只捕获 x，[] 不捕获。引用捕获能修改外部变量。

B1理解选择题：写排序比较器时，相等元素必须返回什么？

true

false

随便

抛出异常

答：______________

✅ 查看答案与解析

答案　B

解析：严格弱序要求相等时返回 false。写成 a.score >= b.score 会让 sort 行为未定义。

C1应用改错题：下面的比较器破坏了严格弱序。

std::sort(v.begin(), v.end(),
          [](const Student& a, const Student& b) {
              return a.score >= b.score;   // 相等时返回 true，破坏严格弱序
          });

✅ 查看答案与解析

答案　return a.score > b.score; // 相等时返回 false

解析：严格弱序：相等必须 false。>= 会导致 sort 段错误或元素丢失。

D1创造写程序：定义 Student（name、score），用 lambda 按分数降序、分数相同按名字升序排序，输出结果。

提示：lambda 里先比 score，相等再比 name。

✅ 查看答案与解析

答案　参考答案：

解析：比较器必须是严格弱序；lambda 就近写比较规则比具名函数省事。

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct Student { std::string name; int score; };
int main() {
    std::vector<Student> v{{"Ann", 90}, {"Bob", 95}, {"Cid", 90}};
    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;
}
// 输出：Bob 95 / Ann 90 / Cid 90

8.2 erase-remove 与二分查找

A1识别判断题：std::remove 并不会真正删除元素，只是把要保留的元素往前挪，并返回新的逻辑结尾。

答：______________

✅ 查看答案与解析

答案　对

解析：std::remove 名字有误导性：真正删除要靠 v.erase(remove(...), v.end()) 组合。

B1理解选择题：std::lower_bound(v.begin(), v.end(), x)（v 已有序）返回什么？

第一个 > x 的位置

第一个 >= x 的位置

x 出现的次数

最后一个 x 的位置

答：______________

✅ 查看答案与解析

答案　B

解析：lower_bound 找第一个不小于 x（左边界）；upper_bound 找第一个大于 x（右边界后一位）。

B2理解选择题：upper_bound - lower_bound 得到什么？

x 在数组中出现的次数

数组长度

x 的下标

x 的平方

答：______________

✅ 查看答案与解析

答案　A

解析：两个迭代器相减就是 x 的出现次数。

C1应用改错题：只调了 std::remove，元素没有被真正删掉。

std::vector<int> v{1, 2, 3, 2, 4};
std::remove(v.begin(), v.end(), 2);   // 只是挪动元素，size 没变

✅ 查看答案与解析

答案　v.erase(std::remove(v.begin(), v.end(), 2), v.end());

解析：erase-remove 惯用法：remove 把保留元素前移并返回新逻辑结尾，erase 从那里删到真正末尾。

D1创造写程序：先读 n 个数存 vector，删除所有偶数（用 erase-remove），再排序，最后用 lower_bound 输出第一个 >= 3 的元素下标（没有则输出 -1）。

提示：删除用 v.erase(std::remove_if(...), v.end())。

✅ 查看答案与解析

答案　参考答案：

解析：remove_if 按条件前移；迭代器相减得下标。

#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_if(v.begin(), v.end(),
                           [](int x) { return x % 2 == 0; }), v.end());
    std::sort(v.begin(), v.end());
    auto it = std::lower_bound(v.begin(), v.end(), 3);
    if (it == v.end()) { std::cout << -1 << '\n'; }
    else { std::cout << (it - v.begin()) << '\n'; }
    return 0;
}

📚 相关概念：编译与链接 · STL · map / set · 迭代器

← 第 7 章第 9 章 →