5 ms·

Any algorithm you pick is going to have edge cases, and the C++ STL only defines the interfaces for interacting with them. This means that there is no "typical"

• Fede_V 10y ago
  I might be wrong but I thought the STL design docs also had restrictions on algorithm speed? As in - you are free to choose any design you want, as long as it has a given API and has O(1) access.
  • KMag 10y ago
    It's been a while, so my memory could be playing tricks on me. However, I believe the specified std::unordered_map iterator invalidation behavior rules out efficient use of open addressing unless someone comes up with some timsort-level novel implementation ideas.
• amelius 10y ago
  I know some of the core algorithms used by GNU's implementation (libstdc++). But what the Rust team could do is compare the performance of different implementations, and pick the best one for each data structure.
  • KMag 10y ago
    ... which they have done, for some definition of "best". They've chosen an implementation with good cache locality and lower memory overhead (and presumably better average-case speed) than the chaining implementation usually used for std::unordered_map. The downside is that its worst-case speed is pretty bad. On the other hand, I believe they use Siphash by default, which means it's very difficult to even intentionally trigger worst-case behavior without being able to inspect the process's memory for the random Siphash key.