Skip to main content

Chapter 17: Map and Set

std::map 和 std::set 解决的是同一个工程问题：在一组元素中维护一个持续有序的键空间，并用这个有序性支撑查找、插入、删除和范围查询。std::map 保存唯一键到值的关系，std::set 保存唯一键本身。标准接口层面可以从 std::map、std::set 和 Compare 的约束读出三条主线：键由比较器定义顺序，唯一性由比较器定义等价，常见实现使用平衡树形结构提供对数复杂度。

本章的主问题是：读到 map / set 代码时，怎样从 comparator、节点式存储、查找接口和修改接口推断对象关系、迭代器稳定性、异常边界和容器选型。读完后应能判断一段代码为什么按某个顺序遍历，为什么某个键插入失败，为什么 operator[] 可能构造新值，以及为什么相同查询需求有时应选择 ordered associative container，有时应选择 unordered associative container。

贯穿本章的材料是一段事件索引代码。它需要按用户名称稳定排序，同时记录每个用户的最近得分和活跃用户集合。代码很短，但包含本章要追踪的全部对象：键、比较器、节点、查找接口、插入接口和迭代器。

#include <map>
#include <set>
#include <string>
#include <string_view>

struct UserLess {
    bool operator()(const std::string& left, const std::string& right) const {
        return left < right;
    }
};

using ScoreTable = std::map<std::string, int, UserLess>;
using ActiveUsers = std::set<std::string, UserLess>;

void record_score(ScoreTable& scores, ActiveUsers& active,
                  std::string user, int score) {
    active.insert(user);
    scores[user] = score;
}

这段代码表面上只调用了 insert 和 operator[]。源码阅读时要把它还原成更具体的路径：user 进入比较器形成树搜索方向；树中不存在等价键时分配节点并构造元素；树结构通过旋转和颜色修复维持高度约束；迭代器指向节点；遍历顺序来自比较器定义的中序顺序。

17.1 key ordering、comparator 与 std::less​

map / set 的键空间由 comparator 决定。comparator 是一个二元可调用对象，输入两个键，输出第一个键是否排在第二个键之前。默认情况下，std::map<Key, T> 使用 std::less<Key>，std::set<Key> 也使用 std::less<Key>。当 Key 是字符串时，默认顺序通常表现为字典序；当 Key 是自定义结构时，排序含义完全取决于调用者提供的比较器。

这里的“有序”不是插入顺序。map / set 会把元素放进由 comparator 维护的有序键空间。下面的例子插入顺序是 "bob"、"alice"、"carol"，遍历输出仍按比较器顺序产生。

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> scores;
    scores.emplace("bob", 70);
    scores.emplace("alice", 90);
    scores.emplace("carol", 80);

    for (const auto& [name, score] : scores) {
        std::cout << name << ' ' << score << '\n';
    }
}

这段代码的关键现象是遍历顺序由 std::less<std::string> 定义。begin() 指向比较器意义下最小的键，++iterator 走向后继节点。接口没有保存“第几个插入”的信息，因此把 ordered associative container 当成插入日志会得到错误设计。

comparator 同时决定唯一性。两个键 a 和 b 等价的条件是 comp(a, b) 为 false 且 comp(b, a) 为 false。map 和 set 都保存唯一键，所以当新键与已有键等价时，insert 不会创建第二个等价元素。这个规则解释了为什么自定义比较器如果只比较用户 id，就会让同 id 的两个对象被容器视为同一个键。

#include <set>
#include <string>

struct UserKey {
    int id;
    std::string name;
};

struct CompareById {
    bool operator()(const UserKey& left, const UserKey& right) const {
        return left.id < right.id;
    }
};

void demo() {
    std::set<UserKey, CompareById> users;
    auto first = users.insert({42, "alice"});
    auto second = users.insert({42, "bob"});

    // first.second == true, second.second == false
}

第二次插入失败的原因不是 name 相同，也不是对象二进制内容相同。容器只通过 CompareById 判断等价。这个规则在源码形状中会落到树搜索路径：搜索过程中遇到一个既不小于新键、新键也不小于它的节点，唯一键容器就把这个节点当成等价节点。

比较器必须形成严格弱序（strict weak ordering）。工程上可以按三个检查点阅读：同一个键与自身比较必须为 false；如果 a 排在 b 前面，b 不能再排在 a 前面；如果 a 排在 b 前面且 b 排在 c 前面，a 也要排在 c 前面。下面的比较器使用 <=，它会让 comp(x, x) 返回 true，树搜索中的“等价”关系会被破坏。

struct BadLessEqual {
    bool operator()(int left, int right) const {
        return left <= right;
    }
};

错误比较器的后果通常不是立刻编译失败。它会让树结构依赖的顺序前提失效，进而让查找、插入位置和遍历结果失去可靠语义。源码阅读时看到 key_comp()、value_comp()、_Compare、__comp_ 这类成员，要先把它们视为容器不变量的一部分，而不只是一个可替换的排序函数。

std::less 的默认行为适合键类型已经有稳定小于关系的场景。自定义 comparator 适合业务排序与类型默认排序不同的场景，例如按 id、按时间戳、按多字段组合排序。设计比较器时要把“排序字段”和“唯一性字段”一起确定，因为 ordered unique container 用同一套 comparator 同时回答“谁在前面”和“两个键是否等价”。

17.2 底层红黑树、节点结构与 iterator 实现​

map / set 的标准语义要求排序、唯一键和对数复杂度，具体实现结构由标准库实现决定。常见 libstdc++ / libc++ / MSVC STL 这类实现会使用红黑树或等价的自平衡二叉搜索树形状。标准保证的是接口语义和复杂度承诺，源码中的颜色位、哨兵节点、父指针命名和旋转函数名称属于实现细节。

节点式有序容器的最小形状可以理解为三层：容器对象保存根节点、大小、比较器和 allocator；树节点保存父指针、左右孩子、颜色以及元素对象；iterator 保存某个节点的位置，并通过 successor / predecessor 规则前进或后退。这个形状解释了两个接口现象：遍历是有序遍历，插入通常不搬移已有元素对象。

// 教学简化形状，不代表某个标准库源码。
template<class Value>
struct tree_node {
    tree_node* parent;
    tree_node* left;
    tree_node* right;
    bool red;
    Value value;
};

template<class Node>
class tree_iterator {
    Node* current_;
public:
    // operator++ 会从 current_ 走到中序后继节点。
};

set 节点的 Value 就是 Key。map 节点的 Value 是 std::pair<const Key, T>。const Key 不是装饰性写法，它表达了一个树不变量：节点进入树之后，键值参与定位，容器必须阻止通过普通 iterator 原地改键。mapped value 可以修改，因为它不参与树顺序。

#include <map>
#include <string>

void update_value(std::map<std::string, int>& scores) {
    auto it = scores.find("alice");
    if (it != scores.end()) {
        it->second = 100;      // mapped value 可以修改
        // it->first = "bob"; // key 是 const，普通路径不允许改
    }
}

这个限制来自树结构本身。节点的位置由键决定。若节点留在原位置而键被改成另一个排序位置，左子树都小于当前键、右子树都大于当前键的搜索前提会失效。C++17 的 node handle 提供了受控出口：可以先 extract 把节点移出容器，在容器外修改键，再插回容器。节点不在树中时，键修改不会破坏当前树的不变量。

iterator 稳定性也来自节点式结构。插入新键时，容器分配一个新节点并把它链接到树中，已有节点对象的地址通常保持不变；旋转只改变节点之间的父子关系，不移动元素对象本身。因此，对 map / set 而言，插入不会让已有元素的 iterator 和 reference 失效；删除只让被删除元素对应的 iterator 和 reference 失效。clear 删除所有元素，所以所有元素位置都随之结束生命周期。

读源码时不要把 iterator 想成数组下标。vector iterator 常见形状接近指针，随机访问可以通过地址算术完成；map / set iterator 指向树节点，++it 需要找后继节点，--it 需要找前驱节点。它满足 bidirectional iterator 能力，支持前进和后退，不提供常数时间随机跳转。

这也解释了为什么 std::map / std::set 没有 operator[] 式下标随机访问。第 100 个元素在树中没有连续地址可算，定位它需要按遍历顺序走过节点，接口层面直接暴露这种访问会让复杂度模型含混。ordered associative container 的核心访问方式是按键查找和按顺序遍历。

17.3 lower_bound、upper_bound、equal_range 与 find​

有序查找接口复用同一条树搜索路径。find(key) 回答是否存在等价键；lower_bound(key) 返回第一个不小于 key 的位置；upper_bound(key) 返回第一个大于 key 的位置；equal_range(key) 返回 [lower_bound(key), upper_bound(key))。对唯一键的 map / set 来说，这个范围最多包含一个元素，但范围接口仍然有意义，因为它统一了插入点、区间查询和后续 multi 容器语义。

看下面的分数表。键按整数排序，值是用户名。我们要找第一个分数不低于 80 的记录、分数 80 的记录范围，以及 75 是否存在。

#include <iostream>
#include <map>
#include <string>

void query_scores() {
    std::map<int, std::string> rank {
        {60, "devon"},
        {80, "alice"},
        {90, "carol"}
    };

    auto first_pass = rank.lower_bound(80);
    auto after_pass = rank.upper_bound(80);
    auto exact = rank.find(75);

    if (first_pass != rank.end()) {
        std::cout << first_pass->first << ' ' << first_pass->second << '\n';
    }
    if (after_pass != rank.end()) {
        std::cout << after_pass->first << ' ' << after_pass->second << '\n';
    }
    if (exact == rank.end()) {
        std::cout << "75 missing\n";
    }
}

lower_bound(80) 会返回键 80 的节点；upper_bound(80) 会返回键 90 的节点；find(75) 会返回 end()。这三个结果来自同一套 comparator 判断。容器在搜索时比较当前节点键和目标键，并根据结果进入左子树或右子树，同时记录可能成为答案的候选节点。

lower_bound 的最小搜索逻辑可以写成教学伪代码。它说明“第一个不小于目标”的含义怎样落到树路径上。

// 教学伪代码：展示候选节点更新规则。
Node* lower_bound(Node* root, const Key& key, Compare comp) {
    Node* answer = nullptr;
    Node* current = root;

    while (current != nullptr) {
        if (!comp(current->key, key)) {
            answer = current;
            current = current->left;
        } else {
            current = current->right;
        }
    }
    return answer;
}

当 current->key 排在 key 前面时，当前节点以及它的左子树都不足以成为“不小于 key”的候选，搜索进入右子树。当当前节点没有排在 key 前面时，它是一个候选答案，但左子树里可能还有更靠前的候选，所以搜索继续向左收缩。这个过程依赖树高为对数级，红黑树这类平衡结构正是为了限制最坏路径长度。

upper_bound 的候选规则与 lower_bound 对称。它要找第一个“大于 key”的节点，因此当 key 排在 current->key 前面时，当前节点成为候选并继续查左侧；否则查右侧。equal_range 可以理解为同时求出这两个边界。对唯一键容器，lower_bound 结果等于 end() 或者不等价于目标键时，find 就返回 end()。

范围查询是 ordered associative container 相对 unordered container 的主要接口收益。比如要遍历 ["alice", "mike") 之间的用户，map / set 可以直接使用两个边界 iterator。

#include <iostream>
#include <map>
#include <string>

void print_name_range(const std::map<std::string, int>& scores) {
    auto first = scores.lower_bound("alice");
    auto last = scores.lower_bound("mike");

    for (auto it = first; it != last; ++it) {
        std::cout << it->first << ' ' << it->second << '\n';
    }
}

这段代码的成本由一次下界查询、一次上界查询和区间长度共同决定。若需求经常是“从某个键开始顺序扫描”“取某个区间”“找前驱后继”，map / set 的顺序结构直接服务需求。若需求只是用完整键做存在性查询，哈希容器通常有更低平均查找成本，但它不提供按 comparator 定义的全局顺序。

17.4 insert、erase、operator[] 与 at​

修改接口要按“搜索位置 → 构造或访问节点 → 修复结构 → 返回结果”阅读。insert 先查找等价键。等价键已存在时，唯一键容器保留旧元素并通过返回值告诉调用者插入失败；等价键不存在时，容器分配节点、构造元素、挂接节点并修复平衡树不变量。

#include <map>
#include <string>

void insert_once(std::map<std::string, int>& scores) {
    auto [it, inserted] = scores.insert({"alice", 90});
    if (inserted) {
        it->second += 1;
    }
}

返回值中的 iterator 指向容器里的元素。inserted 为 true 时，它指向新元素；inserted 为 false 时，它指向已经存在的等价键元素。这个设计让调用者能够在一次操作后继续处理目标节点，同时区分“新建节点”和“复用旧节点”。对 set，返回 iterator 指向键本身；对 map，返回 iterator 指向 pair<const Key, T>。

erase 的关键边界是生命周期。按 iterator 删除时，被删节点中的元素会析构，节点内存由 allocator 释放或回收到实现内部策略；其它节点的 iterator 和 reference 保持有效。按 key 删除时，容器先查找等价键，再执行删除路径。删除树节点可能需要用后继节点替换、旋转和变色修复黑高，但这些修复仍然围绕节点链接进行。

#include <map>
#include <string>

void remove_inactive(std::map<std::string, int>& scores) {
    for (auto it = scores.begin(); it != scores.end(); ) {
        if (it->second == 0) {
            it = scores.erase(it);
        } else {
            ++it;
        }
    }
}

这个循环把 erase(it) 的返回值作为下一轮位置。被删 iterator 的生命周期已经结束，继续对旧 iterator 执行 ++it 没有合法意义。返回后继位置可以让遍历和删除形成一条连续路径。这个写法同样体现了节点式容器的稳定性：删除一个节点不会让其它节点位置整体重排。

operator[] 是 map 专属接口，set 没有 mapped value，因此没有这个接口。scores[user] = score 的读取部分先按 key 查找；若 key 存在，返回 mapped value 的引用；若 key 不存在，容器插入一个新节点，key 来自传入参数，mapped value 进行值初始化，然后返回新 mapped value 的引用。对 int，值初始化得到 0；对类类型，会调用默认构造。

#include <map>
#include <string>

void count_word(std::map<std::string, int>& counts, const std::string& word) {
    ++counts[word];
}

这段计数代码成立，依赖 operator[] 对缺失键插入默认值的语义。它适合“缺失即默认值”的累加场景。若 mapped type 没有合适的默认构造，或者缺失键不应改变容器状态，应改用 find、contains、at、try_emplace 或 insert_or_assign 这类更明确的接口。

at 也是 map 专属访问接口。它查找 key，存在时返回 mapped value 引用，缺失时抛出 std::out_of_range。at 不插入新元素，适合把缺失键当成错误路径处理。operator[] 和 at 的工程差异不在语法长短，而在缺失键的状态变化：前者可能修改容器，后者保持容器元素集合不变。

#include <map>
#include <stdexcept>
#include <string>

int read_score(const std::map<std::string, int>& scores,
               const std::string& user) {
    return scores.at(user);
}

异常安全要沿节点构造路径看。插入新节点时可能发生 key / value 构造异常、比较器调用异常、allocator 分配异常或节点链接后的修复异常。标准库实现通常把“分配并构造节点”和“把节点提交进树”分成阶段：提交前失败要销毁已构造对象并释放节点；提交后容器必须维持有效状态。用户编写的 comparator 如果会抛异常，会把查找和插入路径都变成可能失败路径。

17.5 allocator、iterator 稳定性与 unordered 容器对比​

map / set 是 allocator-aware container。每个元素通常位于独立节点中，节点内除了元素对象，还需要父指针、左右指针、颜色或等价状态字段。allocator 决定节点原始存储从哪里来，容器负责在节点存储上构造元素、销毁元素并释放节点存储。这个模型的收益是节点位置稳定，代价是每个元素都有额外指针开销和分配开销。

相比 vector，节点式容器不会因为扩容搬移整段元素。相比 unordered_map / unordered_set，ordered container 插入时没有 rehash 阶段，已有节点 iterator 的稳定性更容易推断。cppreference 的容器失效表把 associative containers 归为插入后 iterator / reference 保持有效、删除后只有被删元素失效；unordered associative containers 在 rehash 时 iterator 会失效，reference 通常仍指向元素对象。

这个差异对工程代码有直接影响。下面的函数先保存一个指向 scores 中元素的 iterator，再插入其它元素。对 std::map，这个 iterator 在插入后仍然可用。

#include <map>
#include <string>

void keep_iterator(std::map<std::string, int>& scores) {
    auto alice = scores.find("alice");
    scores.emplace("carol", 80);
    scores.emplace("devon", 70);

    if (alice != scores.end()) {
        alice->second += 5;
    }
}

把容器换成 std::unordered_map 后，这段写法要重新审查。插入可能触发 rehash，桶数组重建会让 iterator 失效。reference 和 pointer 的规则又不同，具体要看被保留的是 iterator、reference 还是 pointer。源码阅读时应先识别“位置对象”类型，再查容器修改操作是否会改变它的有效性。

ordered 和 unordered 的选型要用同一组维度比较。第一维是顺序需求：需要按键遍历、范围查询、前驱后继时，map / set 更直接。第二维是查找成本：只做完整键等值查询时，unordered_map / unordered_set 通常提供平均常数复杂度，但最坏情况和哈希质量有关。第三维是稳定性：有大量长期保存 iterator 的代码时，map / set 的插入稳定性更容易使用。第四维是内存和局部性：两类容器都可能使用节点；哈希容器还维护桶数组，有序树节点维护父子关系和颜色。

#include <map>
#include <string>
#include <unordered_map>

struct UserRecord {
    int score;
    bool active;
};

using OrderedUsers = std::map<std::string, UserRecord>;
using HashedUsers = std::unordered_map<std::string, UserRecord>;

如果需求是“按用户名区间导出报表”，OrderedUsers 可以用 lower_bound 定位边界并顺序输出。如果需求是“请求路径上按完整用户名查一个记录”，HashedUsers 往往更贴合。若调用方还要保存位置并在后续插入后继续使用，OrderedUsers 的 iterator 规则更稳；若只保存指向 mapped value 的引用，还要分别审查容器的 erase、rehash 和对象生命周期。

allocator 参与还影响异常边界和性能模型。节点分配失败会让插入失败；mapped value 构造失败会触发已分配节点清理；频繁插入大量小节点会产生大量分配调用。读性能代码时，map / set 的瓶颈经常来自指针追踪、缓存不连续、比较器成本和分配次数，而不仅是 $O(\log n)$ 这个复杂度表达。

17.6 Comparator Correctness, Key Stability, and Container Selection​

这一节把前面规则收束成一个源码阅读和工程选型顺序。读到 std::map 或 std::set，先确定键类型和 comparator。键类型回答“容器按什么对象定位”；comparator 回答“什么叫排在前面”和“什么叫等价”。如果 comparator 只比较部分字段，唯一性也只由这些字段决定。

第二步检查键稳定性。set 的元素整体承担键的角色，普通 iterator 暴露的元素应按只读键处理。map 的 value_type 是 pair<const Key, T>，key 受保护，mapped value 可以更新。需要改键时，优先把动作表达成删除旧键再插入新键；C++17 之后可以考虑 node handle 的 extract / insert 路径，但要把节点离开容器和重新进入容器两个阶段分开审查。

第三步检查访问接口。find 和 contains 表达存在性查询；lower_bound、upper_bound 和 equal_range 表达有序边界；operator[] 表达“缺失则插入默认 mapped value”；at 表达“缺失是错误路径”。同一个 key 查询需求，接口选择会决定容器是否被修改、是否抛异常、是否要求 mapped type 可默认构造。

第四步检查位置对象。保存 iterator 时，要问后续是否有 insert、erase、clear、swap、extract、merge 等操作。对 map / set，普通 insert 不会让已有元素位置失效；erase 结束被删元素生命周期；clear 删除全部元素；extract 让被提取节点离开容器。位置稳定性不是“容器永远安全”，它始终受元素生命周期和具体修改操作约束。

第五步检查复杂度和内存路径。map / set 的查找、插入、删除是对数复杂度，常见树实现还需要多次比较、指针跳转和少量旋转修复。比较器很重时，比较成本会进入热路径；键很大时，节点构造和比较都可能昂贵；节点分配频繁时，allocator 策略会影响延迟分布。

第六步做容器选择。可以用下面的判断顺序：需要全局有序遍历或范围查询，优先考虑 map / set；只需要等值查询且哈希质量可控，考虑 unordered_map / unordered_set；需要重复键，进入 multimap / multiset 或 unordered multi 容器；需要按优先级反复取极值，考虑 priority_queue 或堆算法；需要连续内存和下标访问，回到 vector 或 array。

下面的代码片段把比较器错误、键稳定性和接口选择集中在一起。它适合作为审查 checklist 的触发材料。

#include <map>
#include <string>

struct CaseInsensitiveLess {
    bool operator()(const std::string& left,
                    const std::string& right) const;
};

std::map<std::string, int, CaseInsensitiveLess> visits;

void touch(const std::string& name) {
    ++visits[name];
}

审查这段代码时，先确认 CaseInsensitiveLess 是否形成严格弱序。若它把大小写不同的拼写视为等价，"Alice" 和 "alice" 会落到同一个唯一键位置，容器保存哪一个原始拼写取决于首次进入容器的那个键。然后检查 operator[]：缺失键会插入新节点，mapped value 从 0 开始累加。最后检查需求：如果后续要按大小写无关顺序导出用户，map 的顺序有价值；如果只是在请求路径上计数，且不需要顺序，哈希容器加一致的 hash / equality 规则可能更合适。

本章最终建立的判断是：map / set 不是“带排序的字典”这么粗略的标签，而是一组由 comparator 驱动的节点式有序容器。它们的顺序、唯一性、查找边界、键不可变性、iterator 稳定性和选型结论都能从这条主线推出。

最小自检任务​

阅读下面代码，回答四个问题：遍历顺序由什么决定；第二次插入是否成功；scores["Bob"] 会不会改变容器；把 scores 改成 std::unordered_map<std::string, int> 后，保存的 iterator 在插入后还能不能按同样规则使用。

#include <iostream>
#include <map>
#include <string>

struct LengthThenLexicographical {
    bool operator()(const std::string& left,
                    const std::string& right) const {
        if (left.size() != right.size()) {
            return left.size() < right.size();
        }
        return left < right;
    }
};

int main() {
    std::map<std::string, int, LengthThenLexicographical> scores;
    scores.insert({"Amy", 90});
    scores.insert({"Bob", 80});
    scores.insert({"Chris", 70});

    auto saved = scores.find("Amy");
    auto result = scores.insert({"Bob", 100});
    int value = scores["Bob"];
    scores.insert({"Dan", 60});

    for (const auto& [name, score] : scores) {
        std::cout << name << ' ' << score << '\n';
    }
}

答案要点​

遍历顺序由 LengthThenLexicographical 决定：先按字符串长度升序，再按字典序升序。同长度的 "Amy"、"Bob"、"Dan" 会按字典序排列，"Chris" 长度更大，会排在它们之后。

第二次插入 {"Bob", 100} 不会成功，因为已有键 "Bob" 与新键在 comparator 下等价。result.second 为 false，result.first 指向旧的 "Bob" 节点，旧 mapped value 仍是 80。

scores["Bob"] 会查找已有键并返回 mapped value 引用；因为键已经存在，这一次不会插入新节点。若访问的是缺失键，operator[] 会插入新节点，并把 mapped value 值初始化。

saved 指向 "Amy" 的节点。对 std::map，后续普通 insert 不会让它失效；若容器改成 std::unordered_map<std::string, int>，插入可能触发 rehash，iterator 稳定性要按 unordered container 的 rehash 规则重新审查。

本章知识点总结​

  • 键空间：map / set 用 comparator 建立有序键空间，遍历顺序来自 comparator 定义的顺序。
  • 唯一性：唯一键判断依赖 comparator 定义的等价关系，两个对象互相都不排在对方面前时被视为等价。
  • 默认比较：std::less<Key> 适合已有稳定小于关系的键类型，自定义 comparator 会同时改变排序和唯一性。
  • 严格弱序：比较器要满足自反排除、反对称和传递等约束，错误比较器会破坏树搜索前提。
  • 节点结构：常见实现用自平衡树节点保存元素、父子链接和颜色状态，标准承诺语义和复杂度。
  • 键不可变：map 的 key 是 const Key，set 的元素承担键角色，普通路径下原地改键会破坏树不变量。
  • 查找边界：lower_bound、upper_bound 和 equal_range 把树搜索结果表达成有序边界，适合范围查询。
  • 修改路径：insert 先查找等价键再决定构造节点，erase 结束被删元素生命周期并修复树结构。
  • 访问差异：operator[] 会在缺失键时插入默认 mapped value，at 在缺失键时走异常路径并保持元素集合不变。
  • 迭代稳定：map / set 普通插入保持已有元素 iterator 和 reference 有效，删除只结束被删元素位置。
  • 分配成本：节点式存储提高位置稳定性，同时引入指针、分配、缓存不连续和比较器调用成本。
  • 容器选型：需要顺序、范围和前驱后继时优先考虑 ordered container，只做等值查询时再评估 unordered container。