在无序字符串集中查找字符串的时间复杂度

Question

http://www.cplusplus.com/reference/unordered_set/unordered_set/find/

在 unordered_set 中查找的时间复杂度对于 unordered_set 来说平均是恒定的。如果我有一个 unordered_set 字符串，那么在该集合中查找字符串的时间复杂度是多少？它是常量还是 O(字符串长度)？

Answer 1

std::unordered_set被实现为哈希表。其find方法的平均情况复杂度O(1)和键比较的最坏情况复杂度由[tab:container.hash.req]O(set.size())指定。

默认情况下，std::unordered_set<std::string>用于operator==比较键，因此每个键比较都按照[string.view.ops]O(str.size())中指定的方式运行（定义为等效于，定义为等效于）。operator==(const std::string&, const std::string&)std::string_view(str1) == std::string_view(str2)std::string_view(str1).compare(std::string_view(str2) == 0

对于std::unordered_set<std::string>，容器必须计算要查找的字符串的哈希值。默认情况下它用于std::hash<std::string>此目的。该标准没有指定 的任何复杂性要求std::hash<std::string>，但很可能是O(str.size())。