4 ms·

Having done the work of observing langugage users apparently want an ordered map, were there any steps taken to add such a facility, or did efforts stop at lett

Having done the work of observing langugage users apparently want an ordered map, were there any steps taken to add such a facility, or did efforts stop at letting developers know they were they were wrong by taking away a de facto feature?

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 ago
    C++ 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 ago
      Small 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 ago
  The 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.
fishywang 8y ago
If you really need an ordered map, implement one in Go isn't too difficult (but the usual no-generic caveat applies). You can just define a struct that wraps a map and a slice (or some other data structure) to record the order of the keys.
- lemoncucumber 8y ago
  If you want it to be performant, a linked list is better than a slice. Then in your map you store structs that have both the stores value and a pointer to the corresponding node in the linked list. That way random deletions are constant time since they don’t require copying the slice.

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 ago
  C++ 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 ago
    Small 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 ago
The 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.

fishywang 8y ago

If you really need an ordered map, implement one in Go isn't too difficult (but the usual no-generic caveat applies). You can just define a struct that wraps a map and a slice (or some other data structure) to record the order of the keys.

lemoncucumber 8y ago
If you want it to be performant, a linked list is better than a slice. Then in your map you store structs that have both the stores value and a pointer to the corresponding node in the linked list. That way random deletions are constant time since they don’t require copying the slice.