CODEWITHSUNDEEP
c++dictionaryfindtime-complexity
idanshmu
idanshmu

Reputation: 5271

Does std::map::find performance depend on the key size?

Say I have the the following map definition:

std::map<string,Storage>

where the key is the string representation of a Storage class instance.
My question is, even though it stated that map::find complexity is logarithmic in size, does the string size has any influence on the performance?

The reason I have this map is to enable fast access to Storage class instance. However, what if the string representation of Storage classes is very long? Is there a max string size that if exceeded makes the use of map redundant?

Notes

My intuition tells me that if the string representation of Storage classes is very long then comparing the classes themselves using operator== would be expensive as well. So no matter how long the string is, I'm better of using map

Upvotes: 6

Views: 2505

Answers (4)

wacky6
wacky6

Reputation: 145

Yes, comparing two strings(with a long shared prefix) are generally O(n) complexity.

if strings do not share a long prefix, it may take less time.

Generally, longer strings take longer time to compare.

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

Upvotes: 1

orlp
orlp

Reputation: 117791

std::map uses lexicographical ordering for the key type. This means that performance of search operations on the map is determined by the shared prefix of keys in the map and the key you are looking for. If you have many keys sharing a very long prefix, and you search for a key with that prefix, performance will dwindle.

For example, this is expensive:

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

This is cheap:

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

Upvotes: 3

juanchopanza
juanchopanza

Reputation: 227548

Yes, the map has to perform a less-than comparison of the keys. This is a lexicographical comparison and is linear WRT the string size.

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

Whether that matters or not in your application should be determined empirically.

Upvotes: 3

Angew is no longer proud of SO
Angew is no longer proud of SO

Reputation: 171167

The "complexity" of a map lookup is defined in units of comparisons. So "logarithmic in size" means it will perform O(log(size())) key comparisons. For expensive key comparisons, this indeed affects actual performance.

Upvotes: 2

Related Questions