3 ms·
Ordered maps require other tradeoffs. For example, c++ has both: std::map and std::unordered_map. std::map is a treemap, and so has logn access/insertion times.
by likpok 8y ago
Ordered maps require other tradeoffs. For example, c++ has both: std::map and std::unordered_map. std::map is a treemap, and so has logn access/insertion times. It also does a ton of small allocations, and scatters your data across memory, leading to poor cache performance at scale.
But it has ordered output, and doesn't invalidate iterators on insertion (hashmaps might, because they sometimes need to rehash).
Generally, the suggestion that I've heard is to avoid using std::map unless you really really what it specifically provides, because it's expensive and it's hard to know if you can safely relax those constraints.
- masklinn 8y ago> Ordered maps require other tradeoffs. Ordered maps don't require trees, and don't have that high a tradeoff: https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html https://morepypy.blogspot.com/2015/01/faster-more-memory-eff... https://github.com/rust-lang/rust/pull/45282#issuecomment-336700260 https://github.com/rust-lang/rust/pull/45282#issuecomment-33...
- fanf2 8y agoC++ ordered maps are in sorted order whereas php-style hashes are in insertion order (recent versions of Ruby and Python have adopted the php semantics; in JS maps are php style but JS objects are unordered)
- demurgos 8y agoSmall note, the JS objects are in fact ordered. The lack of determinism caused issues between browsers so the spec now defines the following order: 1. Integer indexes (string keys) in ascending numeric order 2. Other string keys (non-integer indexes) in insertion order 3. Symbols in insertion order https://www.ecma-international.org/ecma-262/#sec-ordinary-object-internal-methods-and-internal-slots-ownpropertykeys https://www.ecma-international.org/ecma-262/#sec-ordinary-ob...
- int_19h 8y agoThe biggest advantage of trees is deterministic complexity. There's a bunch of DoS attacks that exploit hashtables, because they can be O(n) in the worst case - and if you control the input, you can deliberately make it worst case. Most "secure C++" guidelines recommend defaulting to std::set and std::map for this reason alone.