Does anyone know how C++ STL map works internally for keys like string? I tried googling, but didn't find much. Does it hash the string for matching or does it match character by character?
30441799 In this code of problem D of last contest (434), he used a map with string as key, it got TLE.
30461043 In this code, he just turned the map into unordered_map, and AC with 2276ms.
Why map and unordered_map differs that much ?
mapuses the string as a key for a red-black tree. Everything is done character by character.unordered_mapuses hashes for its operations.So,
mapactually takes O(|s| * log(n)).Yes.
unordered_mapshould also take at least O(|s|) when checking if a string actually exists in the hash-table (assuming there is at least one entry with the same hash code).Ok. Thanks. :D
since we are talking maps here , can someone tell me why this code doesn't work , the vectors don't get sorted .
Use 'auto &d'. Otherwise it is just copied to variable d and change isn't reflected in actual vector.
Try auto &d