digitalmars.D.learn - Is there a sorted map?

• stunaep (5/5) Mar 12 2016 Is there any sorted map in D? I need a map and I need to be able
• Jonathan M Davis via Digitalmars-d-learn (29/34) Mar 13 2016 The closest that we have in Phobos at the moment is RedBlackTree in
• stunaep (2/16) Mar 13 2016 Wow, thanks!
• cym13 (4/23) Mar 13 2016 Note that implementing an (admitedly not perfect) ordered
• Anonymouse (3/6) Mar 13 2016 Unsigned integer comparison with -1 in the remove function, by
• cym13 (2/8) Mar 13 2016 Nice catch, thanks ^^
• Steven Schveighoffer (11/39) Mar 15 2016 And in fact, the implementation of RBTree in dcollections should be
```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.
```
Mar 12 2016
Jonathan M Davis via Digitalmars-d-learn writes:
```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

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
```
Mar 13 2016
```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!
```
Mar 13 2016
cym13 <cpicard openmailbox.org> writes:
```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
```
Mar 13 2016
Anonymouse <asdf asdf.com> writes:
```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. :)
```
Mar 13 2016
cym13 <cpicard openmailbox.org> writes:
```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 ^^
```
Mar 13 2016
Steven Schveighoffer <schveiguy yahoo.com> writes:
```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

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
```
Mar 15 2016