[erlang-questions] map elements in defined order

[Sverker Eriksson]

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 
> Manual:
>
> «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 
> order".
>
> 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.



/Sverker