www.digitalmars.com         C & C++   DMDScript  

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

reply stunaep <admin pea2nuts.com> writes:
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
parent reply 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
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
Mar 13 2016
next sibling parent reply stunaep <admin pea2nuts.com> writes:
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
parent reply 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
parent reply 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
parent 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
prev sibling parent 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
 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
Mar 15 2016