Time complexity of finding a string in an unordered set of strings

Question

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

The time complexity of find in an unordered_set has been given to be constant on average for an unordered_set. If I have an unordered_set of strings, then what will be the time complexity of finding a string in that set? Will it be constant or O(length of the string)?

Augmentation

This is a better resource – Nazar

The point is that cppreference.com is the more accurate and reputable source than the one you linked to. – Nazar

Will it be constant or O(length of the string)? -- The hash of the string you're searching for has to be computed. Look at the std::hash<std::string> implementation. – Nazar

Answer 1

std::unordered_set is implemented as a hash table. Its find method has an average-case complexity of O(1) and a worst-case complexity of O(set.size()) key comparisons as specified by [tab:container.hash.req].

---

By default, std::unordered_set<std::string> uses operator== to compare keys, so each key comparison runs in O(str.size()) as specified in [string.view.ops] (operator==(const std::string&, const std::string&) is defined to be equivalent to std::string_view(str1) == std::string_view(str2), which is defined to be equivalent to std::string_view(str1).compare(std::string_view(str2) == 0).

For an std::unordered_set<std::string>, the container must calculate a hash of the string to find. By default it uses std::hash<std::string> for this. The standard doesn't specify any complexity requirements for std::hash<std::string>, but it's most likely O(str.size()).

Uralic