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
?
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
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.