[erlang-questions] map elements in defined order
Thu Oct 26 19:10:34 CEST 2017
On 10/26/2017 05:30 PM, Ulf Wiger wrote:
> Looking at the maps API, I see no function that can present the
> contents of a map in the defined order.
> Because there IS a defined order, described in the Erlang Reference
> «Maps are ordered by size, two maps with the same size are compared by
> keys in ascending term order and then by values in key order. In maps
> key order integers types are considered less than floats types.»
> Note that the key ordering described above doesn't follow normal
> Erlang term ordering, so lists:sort(maps:to_list(Map)) will produce
> something will a well-defined order, but comparing the sorted lists of
> two maps is not guaranteed to have the same outcome as comparing the
> maps themselves.
> I can solve this by using lists:sort/2, but this seems contrived.
> To clarify, e.g. msgpack:pack(Map) will perform a maps:to_list(Map).
> This is not guaranteed to produce the same result across Erlang
> versions, since maps:to_list/1 says pairs "are returned in arbitrary
> Yet there is no alternative API function that will return pairs in the
> defined sort order, although presumably there is an efficient internal
> implementation for producing it.
There is an efficient internal implementation to compare two terms in
map-key order (undocumented erts_internal:cmp_term/2).
But there is no efficient implementation to produce a map-key-value
ordered list. That would require N*log(N) sorting.
'==' for hashmaps (> 32 keys) does a one pass iteration in key hash
order over both trees (HAMTs) and keeps track of the minimal key or
value seen so far.
More information about the erlang-questions