c++ - std::map 是否支持缓存？

Question

例如：

代码1：

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

代码2：

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

code2要简单得多，但两者都map.count()需要map.at()O(logn) 时间。是否std::map提供将最后一个搜索项存储在缓存中并使搜索相同项更快的功能，还是仅在整个地图中执行第二次搜索？

score 6 · Accepted Answer

它在整个地图中进行搜索，没有进行缓存 - 或者至少，标准没有强制要求，我会说没有实现这样做，因为这种实现的所有客户都必须为可能不希望的情况付费每次插入/删除后更新缓存信息的开销。

第一种方法是确定键/值对是否包含在映射中的惯用方法（请注意operator ->应该使用而不是的事实operator .，因为您从中获得的find()是迭代器，并且对的赋值iter应该在if条件之外):

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

score 4 · Accepted Answer

不，据我所知，没有一个 C++ 标准库实现使用缓存。C++11 要求容器对于多个阅读器是线程安全的。并且为了实现对缓存的访问需要同步。这将导致速度损失，即使您不想要它。C++ 的一个标准做法是，您不应该为您不明确需要或不想要的任何东西付费。

score 1 · Accepted Answer

可以，但据我所知没有一个。因此，惯用的解决方案是使用变量：

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

简短、干净且易于理解。（并且它避免了使推理程序正确性变得如此困难的多次返回。）

3 回答 3