3 ms·
Somewhat interestingly, C++ STL unordered_map is so much slower than it needs to be: https://www.youtube.com/watch?v=fHNmRkzxHWs&t=47m13s https://www.youtube.co
by chillee 8y ago
Somewhat interestingly, C++ STL unordered_map is so much slower than it needs to be: https://www.youtube.com/watch?v=fHNmRkzxHWs&t=47m13s https://www.youtube.com/watch?v=fHNmRkzxHWs&t=47m13s
Using one of the policy-based data structures instantly gets you about an order magnitude of speedup (for accesses).
- asdfasgasdgasdg 8y agoKinda makes you wonder why those decisions (to provide bucket iteration, bucket iterators) were made. It's hard to picture a use for such a feature that makes it worthy of adding constraints to a standard container. I would love it if someone could provide some insight into the decision process that led to this state of affairs.
- yoklov 8y agoIIRC boost::unordered_map/set offered those, and I'm pretty sure the API was taken more or less verbatim from that. I suspect some desire of compatibility was to blame, but don't know. Hopefully in the future mistakes of these sort will be avoided, but that might be asking for too much (certainly std::optional opted to break compat with boost's (`std::optional<T&>` is disallowed) so there's some hope).
- mehrdadn 8y agoOn the other hand it makes you think twice about using hashtables, which IMHO is a good thing... :-)
- fulafel 8y agoAnyone have a text link or tl;dr about the issue?
- Ono-Sendai 8y agoIt's something to do with requiring that values stored in buckets are not relocated. This requires link-list storage in buckets, and rules out open-addressing. Something like that at least :)
- iainmerrick 8y agoNo need to apologize, that’s a good summary!