Is there a sorted map?

[Jonathan M Davis via Digitalmars-d-learn]

On Sunday, March 13, 2016 02:35:27 stunaep via Digitalmars-d-learn wrote:
> Is there any sorted map in D? I need a map and I need to be able
> to get the highest key in the map. In java I would use a TreeMap
> and use map.lastKey(), but since associative arrays are not
> sorted that would be O(n). I know about RedBlackTree, but that's
> a set and it must be a map.

The closest that we have in Phobos at the moment is RedBlackTree in
std.container. Its API is geared towards sets, not maps, but you can get it
to work as a map if you define the comparison functions appropriately.
Red-black trees are typically used for both sets and maps, so using
RedBlackTree in that manner is pretty normal from an implementation
perspective, but there's no question that what we really need is a wrapper
around it that provides a map API, since it's not terribly user-friendly to
use the set API for a map, much as it works.

But unfortunately, the container situation in Phobos has been stalled for a
while. It was decided that it would get a major overhaul once allocators
were added to the standard library, so they didn't get much love for quite a
while, and now that we finally have std.experimental.allocator, Andrei is
working on a major redesign of our container solution that's supposed to
replace what we have now, but in the interim, we're stuck with what we've
had for a while.

An alternative would be dcollections: 
https://github.com/schveiguy/dcollections

It does have a HashMap, but it doesn't look like it's been updated in a
while, so I don't know quite what its state is. It was solid, and as long as
it still compiles, it should be fine, but it looks like Steven hasn't made
any updates to it in a while (though it's my understanding that he intends
to).

Another alternative would be EMSI's containers:
http://code.dlang.org/packages/emsi_containers

They also appear to have a TreeMap, and that code should be up-to-date.  In
addition, since that library is up on code.dlang.org, it's easy to pull into
your project and use it if you're building your project with D.

- Jonathan M Davis