5 ms·
C++11 has hash backed containers now if you prefer them. std::unordered_set and std::unordered_map are identical to std::set and std::map except they use hash t
by 16s 14y ago
C++11 has hash backed containers now if you prefer them. std::unordered_set and std::unordered_map are identical to std::set and std::map except they use hash tables rather than red black trees.
- marshray 14y agoI've seen some huge (10-20x) performance gains simply by switching some of my sets and maps to unordered. Why did they wait so ridiculously long to add this to the standard?!
- malkia 14y agoIsn't that implementation specific?
- marshray 14y agoThe standard requires amortized O(1) insert and lookup operations, so it's in practice going to be a hashtable.
- aidenn0 14y agoAny Trie varient will have that as well though.
- marshray 14y agoReally? Looks to me like the lookup function is invoking recursion here: https://en.wikipedia.org/wiki/Trie#Algorithms https://en.wikipedia.org/wiki/Trie#Algorithms I would think the amortized cost would be O(log_b n), with b being something like the Shannon entropy of each symbol.
- aidenn0 14y agoWell in that case the cost of a hash-function is also not O(1) since the minimum length of a n distinct keys is log(n). Really both a trie and a hash-function boil down to O(m) where m is the length of the key.