Menu
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?
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
688
The map solution results in "Time Limit Exceeded on Test 3", whereas the set solution results in "Time Limit Exceeded on Test 2", which means that Test 2 is such that the map solution works faster on it than the set solution.
The unordered_map is the fastest in most of the cases in C++. The map however is faster in some of the cases.
C++ maps are efficient data structures even for insertion just because the underlying data structure (a red black tree) 'balances' itself after every operation if required.
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.
132
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
