In different forums, I have found the statement that in C++::stl, insert and find for unordered_map have guaranteed amortized time complexity O(1). This puzzles me, and I would like to see the official document (perhaps ISO) to see exactly what is being demanded. Could someone provide me with the link?Here is why I think that guaranteed time complexity amortized O(1) may not be possible. Please correct me if I say something wrong, as I am not an experienced programmer. The best way to implement an unordered map is through the use of a hash table. It seems reasonable towant to use keys that are strings of length at most 1000. Let's assume that the alphabet has size 26. Then we are possibly dealing with more than 26^1000 different strings. Any hash function would need to give an array index ranging over 2^64 possible indices. However, any hash function from a set of size 26^1000 to a set of size 2^64 must result in at least one array index having more than exp(600) strings that  all hash to that same array index. So, unless there is some special information about the special nature of the strings to be hashed, one cannot choose a hash function that is guaranteed to work for a chained hash table. For an open hash table, with probes, my argument is not complete, but it seems to be enough to make one worry about guarantees.Given a specific hashing scheme (not necessarily one found in a textbook), is it possible to choose a sequence of strings (all of length 1000) such that the time to insert increases linearly with the number of strings?
Link to ISO doc? Complexity of unordered_map operations in C++::stl
c++;algorithms;stl