3 ms·
Can I just settle for O(log n) lookup and forget about the theoretical O(1) and constant struggle to find the "best" hash function and data structure?
by phkahler 4y ago
Can I just settle for O(log n) lookup and forget about the theoretical O(1) and constant struggle to find the "best" hash function and data structure?
- adrianN 4y agoIf you don't care about performance at all you can of course do that. For many real world applications however asymptotic runtimes are not enough, you need to care about constant factors too.
- merijnv 4y agostd::map (as opposed to std::unordered_map) uses a balanced binary search tree approach and thus guarantees O(log n) lookup for anything that has a well-defined total order (i.e. comparison function), without worrying about hash functions, etc. So, yes you can ;)
- Sharlin 4y agoSure, just use a tree-based map such as `std::map`. (Which, as the name implies, was the OG associative container in C++.)