c++ - 使用静态字符串值访问 std::map 时，访问时间是否仍然为 O(log n)？

Question

std::map<string, int> dict;
for(int i = 0; i < 300; ++i)
{
    dict["afsfgsdg"] = i*i;
    dict["5t3rfb"] = i;
    dict["fddss"] = i-1;
    dict["u4ffd"] = i/3;
    dict["vgfd3"] = i%3;
}

由于字符串值在编译时已知，编译器会在编译时对它们进行哈希处理，而不是在运行时对这些字符串进行哈希处理吗？

Answer 1

std::map 不会散列任何内容。它使用比较来查找元素，其 O(lg n) 界限是映射中有 n 键时所需的比较次数。它没有表达任何关于比较本身的成本。

即该程序可能会使用一些短路字符串比较，首先进行指针比较，但在最坏的情况下比较次数将保持对数(当项目位于树中的叶子之一时，对于典型的红黑树实现)。