Re:Mapping Strings in C++
by utopcell on Wednesday April 12, 2017 @04:47PM
(#14101591)
The performance gap between unordered_map<> and the custom implementations seems to be less than 2X. This will quickly evaporate if one uses an efficient hash such as dense_hash_map<>.
[ Parent
| on HN ]
For the trie, things would be a lot better if the words got longer. All the 'inefficiencies' of a trie lie in the pointer chasing. The great thing is that you can process a string 'on-line'.
If things start getting really big, there are some tricks with LCP-arrays and constant time RMQ (range minimal query) that have great theoretical performance. I haven't seen that stuff in practice though.