C++ std::map 中 find() 的时间复杂度？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/9961742/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Time complexity of find() in std::map?
提问by Avi
How efficient is the find() function on the std::map class? Does it iterate through all the elements looking for the key such that it's O(n), or is it in a balanced tree, or does it use a hash function or what?
std::map 类上的 find() 函数的效率如何？它是否遍历所有元素以查找键，使其为 O(n)，或者它是否在平衡树中，或者它是否使用哈希函数或什么？
回答by David D
回答by Arif Ali Saiyed
std::mapand std::setare implemented by compiler vendors using highly balanced binary search trees (e.g. red-black tree, AVL tree).
std::map并且std::set由编译器供应商使用高度平衡的二叉搜索树（例如红黑树、AVL 树）实现。
As correctly pointed out by David, findwould take O(log n) time, where n is the number of elements in the container.
正如大卫正确指出的那样，find将花费 O(log n) 时间，其中 n 是容器中的元素数。
But that's with primitive data types like int, long, char, doubleetc., not with strings.
但是，与原始数据类型，例如int，long，char，double等，不与字符串。
If std:string, lets say of size 'm', is used as key, traversing the height of the balanced binary search tree will require log n comparisonsof the given key with an entry of the tree.
如果std:string，比如说大小为“m”的 用作键，则遍历平衡二叉搜索树的高度将需要对给定键与树的条目进行 log n 次比较。
When std::stringis the key of the std::mapor std::set, findand insertoperations will cost O(m log n), where m is the length of given string that needs to be found.
当std::string是的关键std::map或std::set，find和insert操作将花费O（米日志n），其中m为给定的字符串的长度被发现的需求。
回答by fbafelipe
It does not iterate all elements, it does a binary search (which is O(log(n))). It use operator< or a comparator to do the search.
它不会迭代所有元素，而是进行二分查找（O(log(n))）。它使用 operator< 或比较器来进行搜索。
If you want a hash map, you can use a std::unordered_map (added on C++-0x), which use a hash function and on average (depending on the hash function and data you provide) find() will be O(1).
如果你想要一个哈希映射，你可以使用 std::unordered_map（在 C++-0x 上添加），它使用一个哈希函数，平均而言（取决于你提供的哈希函数和数据） find() 将是 O(1 ）。
