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.

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

On Sunday, 13 March 2016 at 08:33:43 UTC, Jonathan M Davis wrote:
> On Sunday, March 13, 2016 02:35:27 stunaep via Digitalmars-d-learn wrote:
>> [...]
>
> 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.
>
> [...]

Wow, thanks!

On Sunday, 13 March 2016 at 10:06:24 UTC, stunaep wrote:
> On Sunday, 13 March 2016 at 08:33:43 UTC, Jonathan M Davis wrote:
>> On Sunday, March 13, 2016 02:35:27 stunaep via Digitalmars-d-learn wrote:
>>> [...]
>>
>> 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.
>>
>> [...]
>
> Wow, thanks!

Note that implementing an (admitedly not perfect) ordered associative array yourself really isn't much work: https://github.com/cym13/miscD/blob/master/ordered_aa.d

On Sunday, 13 March 2016 at 13:44:35 UTC, cym13 wrote:
> Note that implementing an (admitedly not perfect) ordered associative array yourself really isn't much work: https://github.com/cym13/miscD/blob/master/ordered_aa.d

Unsigned integer comparison with -1 in the remove function, by the way. :)

On Sunday, 13 March 2016 at 14:11:14 UTC, Anonymouse wrote:
> On Sunday, 13 March 2016 at 13:44:35 UTC, cym13 wrote:
>> Note that implementing an (admitedly not perfect) ordered associative array yourself really isn't much work: https://github.com/cym13/miscD/blob/master/ordered_aa.d
>
> Unsigned integer comparison with -1 in the remove function, by the way. :)

Nice catch, thanks ^^

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