Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

std::unordered_map isn't particularly good. Its strength is that it can handle nearly all workloads without having abysmal performance. The price paid for that is that it's never actually all that good. If you know your workload, a "specialised" hash table can easily be 2x faster (e.g. Google's dense_hash_map).

This is because the standard makes some very specific complexity guarantees on operations and iterator validity. This practically forces standard-compliant implementations to use hashing with chaining, and not in the most efficient way. That's why it's universally bad and not just a bad implementation in any particular standard library. I don't remember the exact details, though.



But we are talking about a standard hash table here. I.e., one that should have consistent performance for general problems, and no surprising behavior whatsoever.

Imho, if the user wants better performance for special use cases, then they can search for better algorithms.


Despite the downvotes, I think you're absolutely right. "No surprises, okay performance" is what a standard library data structure or algorithm should strive for. Sometimes that works out really well for both criteria (libstdc++'s std::sort), but other times performance suffers as "no surprises" is more important (std::unordered_map).




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: