Is there something like std::map?

So I feel like this is a stupid question, but is there something in the standard library (or at least some high quality third-party library) that would replace std::map? Dictionaries seem to be hash tables, OrderedDictionary isn't sorted and requires keys to be hashable.

there are no balanced trees in the standard library.

what is special about your key type that implementing Comparable would be easier than implementing Hashable?

1 Like

Well I am writing a utility library and requiring Hashable makes the contract ugly.

But ignoring that, I don't think OrderedDictionary is the right data structure for what I need. OrderedDictionary preserves insert-order, but I need a sorted dictionary. In addition I need the ability to find all kv-pairs within a range.

I obviously could make this work by calling sort after each insert, but at that point it doesn't seem like OrderedDictionary is giving me any benefit over an Array (except for faster de-duplication).

Looks like SortedDictionary should be good for you.

Yes, but it doesn't seem I can use it yet :frowning:

The following additional data structures are currently under development on but they aren't stable enough to preview yet.

Well I guess I see whether a sorted array is fast enough for what I need and if it isn't I guess I'll have to implement my own balanced tree.

Maybe it (SortedDictionary) is stable enough for your needs, unless of course you want to make your own implementation (I totally appreciate the desire). Last commit to that repo was done in August 2021, BTW, so development wise it seems to be on hold at the moment.