std :: map中find()的时间复杂度？

Question

std :: map类的find()函数效率如何？它是否遍历所有寻找密钥的元素,使其为O(n),或者是否在平衡树中,或者它是否使用哈希函数或什么？

Answer 1

Log(n)它基于红黑树.

编辑:n当然是地图中的成员数量.

是的,它是log(n).不正确它是基于红/黑树.该标准定义了具有最大复杂度log(n)的操作,并且实现此目的的最有效方式是使用红/黑树(尽管这不是必需的).因此,你在马前有你的车. (2认同)
@OrgnlDave:是的,它会的.标准保证.我不认为您理解复杂性是什么(您的陈述可能适用于绝对速度而非复杂性).在现代机器上100MB仍然很小,你不太可能真正衡量差异. (2认同)
@ std''OrgnlDave:我想你应该阅读[这个维基百科页面](https://en.wikipedia.org/wiki/Big_O_notation).`std :: map :: find`绝对是`log(n)`.您提到缓存和"现实世界约束"的事实告诉我们您对大O符号有误解.您认为`std :: map :: find`有多复杂？ (2认同)

Answer 2

std::map并std::set通过编译器厂商使用高度平衡的二叉搜索树(如红黑树,AVL树)来实现.

正如大卫正确指出的那样,find需要O(log n)时间,其中n是容器中元素的数量.

但是,这与基本数据类型,如int,long,char,double等,不是字符串.

如果std:string,将大小'm'用作键,则遍历平衡二叉搜索树的高度将需要将给定键与树的条目进行log n 比较.

何时std::string是std::map或的键std::set,find并且insert操作将花费O(m log n),其中m是需要找到的给定字符串的长度.