Maps:to_list/1 element order.

Jesper Louis Andersen jesper.louis.andersen@REDACTED
Fri Feb 28 10:56:14 CET 2020


No, and it is subtle:

L1 = [{X, X} || X <- lists:seq(1,32)].
L1 == maps:to_list(maps:from_list(L1)).
true

L2 = [{X, X} || X <- lists:seq(1,33)].
L2 == maps:to_list(maps:from_list(L2)).
false

At 32+ elements, Maps change their representation order to a hash array
mapped trie. These are not generally ordered, but provide very fast
lookups. In practice you are O(1) bound with a couple of memory reads. In
theory you are O(lg n) bound width a branch factor of 32.

If you need the order, you need to use a representation which maintains the
order.

On Fri, Feb 28, 2020 at 10:45 AM Valentin Micic <v@REDACTED> wrote:

> Hi
>
> Even though documentation indicates that:
>
> to_list(Map) -> [{Key, Value}]
> Types
> Map = map()
> Key = Value = term()
>
>
> Returns a list of pairs representing the key-value associations of Map,
> where the pairs [{K1,V1}, ..., {Kn,Vn}] *are returned in arbitrary order.*
> It appears that the list returned has been sorted in ascending order,
> using value of the key as a criterion for sorting.
> I did some testing using a bit modified example offered in documentation:
>
>
> (x@REDACTED)47> f(Map), Map = #{42 => value_three,1337 => "value
> two","a" => 1, 1 => "Last entered"},maps:to_list(Map).
> [{1,"Last entered"},
>  {42,value_three},
>  {1337,"value two"},
>  {"a",1}]
>
>
>
> When I changed 1337 to -1337, I get the result that indicates that the
> list of pairs is *not* returned in arbitrary order, but actually sorted:
>
>
> (x@REDACTED)48>
> (x@REDACTED)48> f(Map), Map = #{42 => value_three, -1337 => "value
> two","a" => 1, 1 => "Last entered"},maps:to_list(Map).
> [{-1337,"value two"},
>  {1,"Last entered"},
>  {42,value_three},
>  {"a",1}]
>
>
> Could one relay on this always being the case?
> A I need this list to be sorted, I would hate to attempt sorting the
> already sorted list.
>
> Thanks in advance
>
> V/
>
>

-- 
J.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20200228/a82f4f5a/attachment.htm>


More information about the erlang-questions mailing list