std::map支持缓存吗？

Question

例如： 代码1：

if((iter = map.find(key)) != map.end()) {
    return iter->second;
}
return 0;

code2:

if(map.count(key) > 0) {
    return map.at(key);
}
return 0;

code2更简单，但是map.count()和map.at()都需要花费O(logn)的时间。是否std::map提供了缓存上次搜索结果并且使得同样的搜索更快的功能，还是只是在整个映射中进行第二次搜索？

- richselian

Answer 1

它通过整个地图进行搜索，没有进行缓存 - 或者说，标准没有强制要求任何缓存，我会说没有任何实现这样做，因为所有这样一个实现的客户端都必须为每次插入/删除更新缓存信息的可能不受欢迎的开销付费。

第一种方法是确定地图中是否包含键/值对的惯用方法（只需注意，应该使用operator->而不是operator.，因为从find()获取的是迭代器，并且对iter的赋值应该在if条件之外）：

auto iter = map.find(key);
if (iter != map.end()) {
    return iter->second;
}

- Andy Prowl

---

+1 虽然我认为将第一个示例中的条件拆分为两行会更清晰。 - dyp

第一种方法违反了我所见过的每个编码准则。在_if_的条件中，您绝不会更改状态。 - James Kanze

@JamesKanze：不确定你的意思。是谁在改变状态？ - Andy Prowl

@AndyProwl 在他的 if 语句中有一个赋值操作。 赋值操作会改变状态。 - James Kanze

@JamesKanze：哦，好的。是的，在我之前的回答中，我确实纠正了这个问题，但后来我又回滚了，并忘记提到它。我再次编辑了一下。 - Andy Prowl

Answer 2

据我所知，没有任何C++标准库实现使用缓存。C++11要求容器对多个读取器线程是线程安全的。为了达到这个目标，需要同步访问缓存，这将导致速度下降，即使您不需要。 C++的一个标准做法是，您不应该为任何您不明确需要或想要的内容付费。

- dalle

---

std::map是否根据标准保证多读取器（假设没有写入器）的线程安全性？否则，该参数毫无意义。 - Zarat

@Zarat：是的，根据C++11标准是这样的。 - dalle

因此结论是，由于标准要求在这种情况下具有线程安全性，缓存也需要具有线程安全性，这会使不想要/不需要它的调用者变慢。 - Zarat

@Zarat：我解释一下我的意思，“不适合多线程”。 - dalle

Answer 3

它可能会有这样的功能，但我所了解的没有。因此，惯用的解决方案是使用变量：

auto results = myMap.find( key );
return results == myMap.end()
    ? NULL
    : &results->second;

短小清晰易懂。(而且避免了多次换行，这样有助于推理程序的正确性。)

- James Kanze

Answer 4

有一点没有提到的是，虽然搜索过程中没有软件缓存，但在搜索路径上可能会有指针的硬件缓存（例如搜索树），因此在第一次搜索之后立即进行第二次搜索应该会快得多。

- Inbar Gera