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
