C++ / a working model

91 / 163   ·   C++11   ·   约 13 分钟

同名 find，不同身份：先定义键的等价关系

先记住这句话

有序集合成员 find 使用比较器定义的等价关系，通用 std::find 使用相等比较。以分桶编号为例，观察两种查找为何可以给出不同结果，并建立不会破坏容器要求的严格弱序。

本篇内容
  1. 先写清楚集合认为什么相同
  2. 成员查找与线性查找回答不同问题
  3. 严格性只是起点，不是全部要求
  4. 运行示例
  5. 动手练习
READING EVIDENCE / 已读完整正文

Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library

已读完222页中文扫描本的全部实质内容：引言、Items1–50、参考书目、附录A/B（印刷页1–208，PDF15–222）。PDF1–99读取远程OCR全文，另直接核对21、38、70–71页图示；服务限流后不再请求OCR，PDF100–222逐页直接读图，包括全部代码、表格和插图。版权页核实2006年4月中文第1版第1次印刷。另读英文出版社Items1–4、16、21、44；不把中文全书通读说成英文全书通读。

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

先写清楚集合认为什么相同

出版社 Item 44 的成员算法对照，提醒我们不要只看函数名。本例限定编号为非负整数，以十位分桶：12 和18属于同一桶。比较器仅比较除以10的结果，于是集合认为二者等价，即两个方向的比较都为假。集合只为每个等价类保存一个代表，并不自动把代表转换成查询值。

这种建模适合每组仅保留一个代表的业务。如果实际需要每条记录都存在，就不能用这个 set 假装做普通去重；应改用 multiset，或直接用 map 把桶编号映射到记录集合。数据结构选择必须服从真实身份定义。

成员查找与线性查找回答不同问题

向集合插入12后，成员 find(18) 可以返回保存着12的节点，因为它询问是否存在与18等价的键。std::find 遍历元素并执行整数相等比较，因而不会认为12等于18。两者结果不同完全合法，不是某个算法漏找了元素。

有序集合成员查找还可以利用内部结构，复杂度为对数级；通用 find 是线性查找。本课只断言可观察的结果，不断言红黑树形状或精确比较次数，那些是实现细节。若业务需要精确相等，就应该明确表达，不能为了速度擅自改变查询含义。

严格性只是起点，不是全部要求

Item 21 强调相等值的比较结果必须是假，因此 <= 不能作为这里的排序关系。反向顺序应比较后一个键是否小于前一个键，而不是把原比较结果取反。取反会把相同值也判成先后关系，破坏契约。

严格弱序还要求传递性，以及不可比较关系形成一致的等价类。本例通过整数桶编号上的普通 < 自然满足这些条件。不要从若干断言推导任意比较器已经正确；有限例子用于观察，完整保证来自定义。现代 ranges 算法也不会自动替你证明这些语义性质。

常见误区

  • 比较器把不同对象视为等价时，set 会拒绝第二个等价键；这与 operator== 是否成立无关。
  • 不要在键仍处于容器中时改变比较器所依赖的外部状态，否则原有顺序可能失效。

运行一个例子

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

#include <algorithm>
#include <cassert>
#include <set>

struct ByBucket {
    bool operator()(int left, int right) const noexcept {
        return left / 10 < right / 10;
    }
};

int main() {
    std::set<int, ByBucket> representatives{12, 31};
    const auto equivalent = representatives.find(18);
    assert(equivalent != representatives.end());
    assert(*equivalent == 12);
    assert(std::find(representatives.begin(), representatives.end(), 18)
           == representatives.end());
    const auto inserted = representatives.insert(19);
    assert(!inserted.second);
    assert(representatives.size() == 2);
    assert(!ByBucket{}(12, 12));
    assert(!ByBucket{}(12, 18));
    assert(!ByBucket{}(18, 12));
}

在本地编译

g++ -std=c++11 -Wall -Wextra -Wpedantic -pthread books-effective-stl.cpp -o example && ./example

预期结果

预期：正常退出、无输出；所有 assert 通过。

CHECK YOUR UNDERSTANDING

合上答案，试着解释。

需要按桶降序排列，同时维持桶内等价，比较器应如何修改？

查看参考答案

把返回表达式改成 right / 10 < left / 10。对于同桶的12和18，两个方向依旧都为假；对不同桶，先后方向反转。不能写 !(left / 10 < right / 10)，因为同桶时它返回真。

继续查证

标准草案与官方章节会更新；版本标记只说明示例最低要求。

回到目录