Is there a sorted map?

[Steven Schveighoffer via Digitalmars-d-learn]

On 3/13/16 4:33 AM, Jonathan M Davis via Digitalmars-d-learn wrote:
> 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

And in fact, the implementation of RBTree in dcollections should be 
nearly identical to that in std.container.RedBlackTree (as the latter is 
based on the former).

I use the same implementation for both TreeMap and TreeSet, proving 
Jonathan's point (all you need is a proper wrapper).

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

I haven't compiled it in a long time, or even thought about how I would 
update it recently. I do want to freshen it up, and I did have some 
ideas to make the library more modular and composable. But free time is 
always limited ;)

-Steve