map 与 set：有序关联和比较器契约

标准承诺有序，不承诺某种树

set 保存键，map 保存键和值，普通版本只允许每个等价键出现一次，multi 版本允许重复。迭代顺序服从比较器；查找和一般单元素插入为对数复杂度，按迭代器删除具有摊还常数复杂度，按键删除还包含查找与删除数量的成本。

红黑树是常见实现，不是标准指定的数据结构。复杂度也没有把一次字符串比较自动变成常数成本：共同前缀很长时，比较本身可能很昂贵。需要区间查询、顺序遍历或明确的对数查找上界时，有序关联容器比依赖平均常数查找的哈希表更匹配。

比较等价与业务相等必须对齐

键 a、b 等价的定义是 !comp(a,b) && !comp(b,a)，即双方都不排在对方前面，不必满足 a == b。示例只比较 Record 的 id，因此同 id、不同标签的第二次插入仍失败。若业务要求同 id 不同标签可以并存，就必须把标签加入排序键，或选择允许等价键的容器。

比较器必须形成严格弱序：自身不小于自身，先后关系具有传递性，比较等价性也具有传递性。<= 不是合法替代品。比较器依赖的外部配置不能在元素存放期间改变排序关系；同理，键的排序字段不能绕过 const 或借助可变间接对象偷偷改变。

查找不该意外插入

map::operator[] 在键缺失时插入一个值初始化的映射值，因此读取存在性应使用 find；需要不存在时报错可用 at。map 的元素类型是 pair<const Key,T>，可以修改 second，不能原地修改 first；set 的迭代器同样不允许修改键。

插入保持已有迭代器和引用有效，删除只使被删元素的句柄失效。边界查询优先使用成员 lower_bound，它能利用容器结构进行对数查找；通用 std::lower_bound 虽然比较次数对数，但在这些双向迭代器上可能有线性步进成本。区间结果仍须先检查是否为 end 再解引用。

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

#include <cassert>
#include <iostream>
#include <map>
#include <set>
#include <string>

struct Record { int id; std::string label; };
struct ById {
    bool operator()(const Record& a, const Record& b) const {
        return a.id < b.id;
    }
};

int main() {
    std::set<Record, ById> records;
    auto first = records.insert(Record{7, "original"});
    auto duplicate = records.insert(Record{7, "replacement"});
    assert(first.second && !duplicate.second);
    assert(duplicate.first->label == "original");

    std::map<int, std::string> names{{10, "ten"}, {30, "thirty"}};
    auto saved = names.find(10);
    names.emplace(20, "twenty");
    assert(saved->second == "ten");
    auto boundary = names.lower_bound(15);
    assert(boundary != names.end() && boundary->first == 20);
    auto missing = names.find(99);
    assert(missing == names.end() && names.size() == 3);
    std::cout << duplicate.first->label << ' ' << boundary->second << '\n';
}

在本地编译

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

预期结果

original twenty

CHECK YOUR UNDERSTANDING

合上答案，试着解释。

map<int,int> 中需要统计所有键位于 [20,40) 的值之和，应该如何定位并遍历？说明复杂度。

继续查证

• 标准草案 [associative.reqmts]：比较等价、有序查找与稳定性
• 标准草案 [alg.binary.search]：比较次数与步进次数

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