Map with ordered keys

Have you considered using this library?

There is an Erlang gb_tree that is built in. For ordered iteration, there is an iterator/1, and to_list/1 can be used with Enum I think. gb_sets is also available.

Sadly it’s interface isn’t compatible with Elixir pipes, because the data structure is the last argument but an Elixir wrapper shouldn’t be too hard.

If you need custom ordering, consider AVLTree

I’m not sure from the project docs it’s doing what I need.

Had a look. I’ll throw in a couple of examples now and maybe benchmark later.

Create new :

:gb_trees.empty

Populate with 10 elements :
gb = 1..10 |> Enum.reduce(:gb_trees.empty, fn x,acc -> :gb_trees.insert(x,x,acc) end)

Iterating elements :
{k,v,next} = :gb_trees.next(iter)

I will mention I started looking at native code to solve my issue (need high performance). Here’s what I also considered.. After some investigation, I came across klib library (pure C, license X11/MIT) and it’s KBtree ordered map implementation. Considering wrapping it with a NIF.

If you need the high performance, you could still leverage ets for direct access and use a separate data structure just for iteration of the keys, but that does get cumbersome.

Nifs are tricky you can take a look at this (very similar) nif I write to wrap a C data structure (also a single header lib). If you need to load a huge amount of items into that tree consider using a dirty nif as not to block the whole VM while it scans the tree. That also comes with overhead of it’s own though.

This probably calls for a generic Rustler-based Elixir library that bridges various Rust data structures to Elixir code. In your case that’d be Rust’s BTreeMap.

Discord have a sorted set library with bindings to Rust – not a map but still, in case you need this one as well. You can also just take a look at Discord’s libraries in general, they are quite excellent.

Yeah everyone speaks well of Rust for native code - I haven’t taken the time to learn it so worried about the cognitive load but I do know C/C++ . Should probably watch Scroggin’s talk again but I’m spending so much time on beam/infrastructure I’ve not much chance to learn a new language. Excuses. Excuses.

Thanks @mpope some good points there. exor_filter/c_src/xor_filter_nif.c at master · mpope9/exor_filter · GitHub yeah good example of resource allocation/deallocation - at least it’s reasonably straightforward in BEAM compared to say for example writing a Java native extension. Good point about the dirty NIF.

Can you share the use case for an ordered map? I super curious!