Does the value of std :: map :: find depend on the size of the key?

Question

Let's say I have the following map definition:

 std::map<string,Storage> 

where the key is a string representation of an instance of the Storage class.
My question is that he stated that map :: find complexity is logarithmic in size, does string size affect performance?

The reason I have this map is because of quick access to an instance of the Storage class. However, if the string representation of the Storage classes is very large? Is there a maximum line size that, if exceeded, makes use of map redundant?

Notes

My intuition tells me that if the string representation of the Storage classes is very long, then comparing the classes themselves using operator== will also be expensive. Therefore, no matter how long the line is, I better use map

Answer 1

Yes, the card should do less than key comparison. This is a lexicographic comparison and linear WRT string size.

This does not affect the time complexity of the find method, which refers to the number of comparisons required. This affects the constant ratio.

Regardless of whether it matters or not in your application, it is empirically determined.

Answer 2

std::map uses lexicographic ordering for the key type. This means that the search operations on the map are determined by the general key prefix on the map and the key you are looking for. If you have many keys using a very long prefix, and you are looking for a key with this prefix, performance will decrease.

For example, it is expensive:

 aaaaaa <millions of a's> aaaa aaaaaa <millions of a's> aaab aaaaaa <millions of a's> aaac 

It is cheap:

 aaaaaa <millions of a's> aaaa baaaaa <millions of a's> aaaa caaaaa <millions of a's> aaaa 

Answer 3

The "complexity" of a map search is determined in units of comparisons. Thus, “logarithmic size” means that it will perform O(log(size())) comparison. For expensive key mappings, this does affect actual performance.

Answer 4

Yes, comparing two lines (with a long common prefix) is usually O (n).

If lines do not have a long prefix, this may take less time.

Typically, longer lines take longer to compare.

Perhaps you should consider unordered_map (hash_table) if the key is a string.