BitPacking

在编程面试或者编写生产代码时，你可能都遇到过这样一个问题：在 std::map 或 std::unordered_map 中查找值的正确方法是什么？简便起见，本文将这两种容器都称为映射。

我们来探讨一下不同的查找方式，以及它们的优缺点。

`operator[]`

使用 operator[] 是访问映射元素的过时方法 - 接受一个键，返回对应值的一个引用。对于 std::map，该方法的算法时间复杂度为；对于 std::unordered_map，平均时间复杂度为常数时间（最坏情况是线性时间/with worst-case linear）。

然而，这个方法存在一个比较大的限制。

如果键不在映射中，会发生什么？

与 vector - 对 operator[] 使用无效下标会导致未定义行为 - 不同，map 会插入一个给定键和默认构造值的新条目。这个副作用也即意味着 operator[] 在不期望插入的查找中是不安全的。

这也是不能在 const 映射上使用 operator[] 的原因：

#include <map>

int main() {
    const std::map<int, int> squares{ {1, 1}, {2, 4}, {3, 3} };
    return squares[2]; // ERROR: passing 'const std::map<int, int>' as 'this' argument discards qualifiers
}

可惜了。我们需要一个替代方案！

`at()`

at() 方法来救场了。与 operator[] 一样高效访问，但是它绝不会插入新元素。如果键不存在，它会抛出一个 std::out_of_range 异常。因此，它适合与 const 映射配合使用：

#include <map>

int main() {
    const std::map<int, int> squares{ {1, 1}, {2, 4}, {3, 3} };
    return squares.at(2);
}

若想安全地使用 at()，要么确保键存在，要么将查找操作包裹在 try-catch 块中。

看看如下这两个包装器：

#include <map>
#include <optional>
#include <stdexcept>

std::optional<int> lookupAtContains(const std::map<int, int> &map, int key) {
    if (map.contains(key)) {
        return map.at(key);
    }
    return std::nullopt;
} 

std::optional<int> lookupAtTryCatch(const std::map<int, int> &map, int key) {
    try {
        return map.at(key);
    } catch (const std::out_of_range& err) {
        return std::nullopt;
    }
}

两者使用起来都安全，但都有缺点。

第一个 - lookupAtContains - 不是线程安全的。如果在 contains 和 at 调用之间，键被移除了，怎么办？当然也许我们不需要考虑这样的场景。另一个问题是效率 - 键查找了两次。顺便说一句：这样的查找包装器也可以与 operator[] 一起使用。虽然使用 at() 要考虑这样的问题，不过未捕获的异常要好于未定义行为。

第二个，缺点是使用了异常。也许你不会允许在你的代码库中使用异常。也许你担心性能损失。也可能你会说异常如果没有被调用就是一种零成本抽象 - 这并不完全正确，运行时异常没有被调用的话确实没有开销，不过编译时，必须为生成处理异常所需的信息付出代价。此外，在映射中找不到键显然不是一种异常情况。

`std::find`

还有一个选择是使用 find() 方法。

int main() {
    const std::map<int, int> squares{ {1, 1}, {2, 4}, {3, 3} };
    auto maybe_entry = squares.find(2);
    return maybe_entry != squares.end() ? maybe_entry->second : -1;
}

在 const 容器上也能正常使用，不过代码丑了点。如果键存在，它会返回一个指向该键对应条目的迭代器；如果键不存在，则返回一个指向容器末尾之后位置的迭代器。我们对返回的迭代器做处理即可。

也可以配套使用一个包装器：

std::optional<int> lookupFind(const std::map<int, int> &map, int key) {
    auto maybe_entry = map.find(key);
    if (maybe_entry == map.end()) {
        return std::nullopt;
    }
    return maybe_entry->second;
}

这个方法仍然存在线程安全问题，不过对于单线程的适用场景，不存在这个问题。

优点是我们现在只需一次查找！如果想提高代码可读性，可以使用包装器。

双重查找真的是一个问题吗？

具体情况具体分析。

使用 contains 后跟 at() 的方式，确实会有性能损失。基准测试显示，当键存在时，lookupAtContains 的查找速度比 lookupFind 慢约 60%。

更糟糕的是，当键不存在时，lookupAtTryCatch 由于异常开销，速度慢了几个数量级。

话虽如此，双重查找的性能损耗自由在代码运行在热点路径上时才重要。大多数应用中，与其他瓶颈（如异常处理、I/O 等）相比，这点性能差异微乎其微。代码清晰度胜过过早优化 - 除非在性能关键领域。

结论

在 map 中查找值并不像看起来那么简单。如下对可选方案做个总结：

如果期望在键不存在时做插入，并且不是在操作不可变映射，可以使用 operator[]。
如果期望安全地不做插入地访问，特别时在操作不可变映射时，可以使用 at()，不过要注意异常。
使用 find()，可控性和性能都更好，代价是代码可能更冗长。如果你正在构建一个可重用组件，建议将 find() 包装在像 lookupFind() 这样的辅助函数中，可以在安全性、性能和代码清晰度之间取得最佳平衡。

最终，选择适合你当前情况的方法 - 可读性、性能和代码库规范都很重要。

你最常用哪种方法？为什么？