c++ - 在 unordered_map 中查找的性能

Question

我知道这可能是个愚蠢的问题，但我想确定一下，但无法轻易找到此信息。

find() 在无序映射中的性能特点是什么？它和普通查找一样快/几乎一样快吗？

即

std::string defaultrow = sprite.attribute("defaultrow").value();
auto rclassIt = Rows::NameRowMap.find(defaultrow);
if (rclassIt != Rows::NameRowMap.end())
    defRow = rclassIt->second;

对比

std::string defaultrow = sprite.attribute("defaultrow").value();
defRow = Rows::NameRowMap[defaultrow];

其中 Rows::NameRowMap 是一个将字符串索引映射到 int 的无序映射。

在我的例子中，我不确定 key 是否会事先存在，所以第一个解决方案对我来说似乎更安全，但如果我能保证存在，第二种情况是否更快(忽略额外的检查我'我在做什么)？如果是这样，为什么？如果重要的话，我正在使用 1.46 boost 实现

Answer 1

无序容器上的

find 和 operator[] 平均为 O(1)，最坏情况为 O(n) —— 这取决于哈希的质量功能。