Ordered Collection

The Problem

During my parental leave last year I looked for an Erlang functionality that didn’t have a well known Elixir implementation in order to get some practice building with Elixir and to get to know some of the underlying data structures.

What I built

I developed an Elixir library to fill the gap in the standard library by providing sorted data structures with an idiomatic Elixir API. Elixir’s built-in Map and MapSet do not maintain ordering. Erlang offers balanced binary trees (:gb_trees and :gb_sets) that do, but their APIs are not idiomatic in Elixir. OrderedCollections encapsulates these structures in two modules, SortedMap and SortedSet, which integrate seamlessly with Elixir code.

SortedMap maintains key-value pairs in sorted key order and supports efficient lookups, insertions, updates, deletions, and range queries over keys. SortedSet stores unique elements in sorted order, enabling fast membership checks, range queries, and standard set operations such as union, intersection, and difference. Both structures can be converted to standard Map, MapSet, or list representations.

Their native integration is achieved through protocol support. Both structures implement Enumerable, enabling direct use of the Enum and Stream toolkits; Collectable, allowing data to be piped in with Enum.into/2; Inspect, for readable output in IEx; and the JSON protocol introduced in Elixir 1.18, which facilitates direct serialization.

The library is available on Hex as ordered_collections, with documentation provided on HexDocs.