3 ms·
Yeah, most (all?) implementations of unordered_set are really slow. My understanding is that the iterator invalidation behavior specified by the standard force
by panic 10y ago
Yeah, most (all?) implementations of unordered_set are really slow. My understanding is that the iterator invalidation behavior specified by the standard forces implementations to use chaining, which means allocating constantly on insertions and chasing pointers on every lookup.
- amelius 10y agoYes, I guess the designers of the standard library envisioned that programmers can easily make mistakes with the lifetime of iterators, and this is their best way to safeguard against it. Rust enforces the constraints on iterator usage, so this is a clear example where Rust would be a superior language.
- gpderetta 10y agoMy guess is that the hash_map of the original STL had that iterator guarantees. While hash_map wasn't standardized, it was de-facto available on many standard libraries. When the committee standardized unordered_map, they tried to make it as much of a drop-in replacement for hash_map as they could and subtly different invalidation rules would have been extremely hard to catch.
- Ono-Sendai 10y agoI've heard it was due to std::unordered_map trying to be a drop-in replacement for std::map.