C++ / a working model

93 / 103   ·   C++20   ·   约 12 分钟

谓词表达值条件,不表达第几次调用

先记住这句话

算法可以复制谓词,调用次数也不等于容器中的位置。将稳定的阈值配置与位置操作分开,用 C++20 erase_if 删除满足值条件的元素,再安全执行一次明确的按位置删除。

本篇内容
  1. 有成员数据,不等于依赖历史
  2. 删除值与删除位置用不同接口
  3. 算法结果之后重新理解位置
  4. 运行示例
  5. 动手练习
READING EVIDENCE / 已读部分正文

More Exceptional C++: 40 New Engineering Puzzles, Programming Problems, and Solutions

读完出版社Item2(独立PDF5页)与Item3(9页)。Item1(6页)和Item4(14页)的全部公开文字也已读,但文件最后分别止于“Good sepa-”及“foreordained base class”,无法保证结尾完整,按可见节选计。Items5–40及附录A/B未读;未获得整本全文,GotW原版不替代书本。

查看版本、实际阅读范围与原文入口 →

有成员数据,不等于依赖历史

Item 3 区分了两类常被混称为有状态的函数对象。阈值在创建后固定,判断只依赖当前元素的谓词,可以任意复制而不改变答案。相反,内部每调用一次就加一、到第三次返回真的对象,依赖自己的历史;算法若复制它,计数就分叉了。

因此不能把 remove_if 的谓词当作隐含的循环游标。即使某个库版本恰好按预想方式调用,也不能把这种观察升级为可移植契约。共享一个计数器只解决副本间的数据一致性,并不能补上算法没有给出的次序保证。

删除值与删除位置用不同接口

本例先按稳定阈值删除低分记录,lambda按值捕获固定的阈值,每个副本得到相同判断。C++20 的 std::erase_if 接受整个 vector,完成压缩与实际擦除,并返回删除数。它不同于仅接受迭代器范围的 remove_if,后者不会自动缩小容器。

第二个需求是删掉当前序列的第三个元素,这是位置语义。代码先检查大小,再由 begin()+2取得有效位置,直接调用成员 erase。这样代码没有依赖谓词调用次数,边界条件也写在使用位置旁边;空容器和不足三个元素都不会越界。

算法结果之后重新理解位置

按值过滤会压缩序列,所以后面的第三个元素是过滤后的第三个,不是原输入的第三个。这是两个不同业务要求,不能在优化过程中悄悄互换。若需要按原始位置删除,应先按原位置操作,或者在输入记录中保存显式原始编号。

示例只在操作完成后检查最终值,没有观察 remove_if 尾部的未指定值,也没有继续使用擦除前的迭代器。原书使用 C++98 的函数对象适配器;现代代码可以用 lambda 取代样板声明,但不能因此省略对谓词语义与迭代器失效的分析。

容易答错的地方

  • remove/remove_if 的返回位置到旧 end 之间仍有对象,但它们的值不能被当作已删除元素清单。
  • 捕获引用让副本共享状态不代表依赖调用次序的谓词就正确;并行算法下还可能引入数据竞争。

运行一个例子

最低标准 C++20 · 完整程序 · 下载 .cpp

#include <cassert>
#include <vector>

int main() {
    std::vector<int> scores{8, 2, 9, 4, 7, 6};
    const int minimum = 6;
    const auto removed = std::erase_if(scores, [minimum](int score) {
        return score < minimum;
    });
    assert(removed == 2);
    assert((scores == std::vector<int>{8, 9, 7, 6}));
    if (scores.size() >= 3) {
        scores.erase(scores.begin() + 2);
    }
    assert((scores == std::vector<int>{8, 9, 6}));
}

在本地编译

g++ -std=c++20 -Wall -Wextra -Wpedantic -pthread books-more-exceptional-cpp.cpp -o example && ./example

预期结果

预期:正常退出、无输出;所有 assert 通过。

CHECK YOUR UNDERSTANDING

合上答案,试着解释。

如果需求是删除原输入的第三项,再删除低于6的值,结果是什么?

查看参考答案

先对原序列执行 erase(begin()+2),删掉9,得到8、2、4、7、6;再执行同一个 erase_if,删掉2和4,最终为8、7、6。与示例结果不同,说明位置删除和条件过滤不能任意交换次序。

继续查证

标准草案链接会随工作草案更新;本文版本标记对应示例最低要求,不表示草案中的所有新规则都适用于旧标准。

回到目录