当使用静态字符串值访问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个键时所需的比较次数.它没有表达比较本身的成本.

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