I'm looking for a means to associate a key with a value and iterate over said container in-order. My natural choice in C++ would be std::map. When I look in std.container, I see that there is a RedBlackTree implementation, however this does not associate a key with a value (it is the equivalent of std::set).

My question is essentially what the best/most idiomatic way to represent this is in D?


I've contemplated several solutions:

1) Have 2 containers, a RedBlackTree of keys and a D associative array of keys to values. The downside to this approach is that I incur the cost of both key lookups when I iterate (the tree's and the array's). Furthermore, separate containers likely incurs a cache performance hit.

2) Create a wrapper struct that contains key and value and whose comparison operator is defined only on the key. This would essentially be doing what the C++ implementation does.

3) Use an associative array and sort the keys each time I intend to iterate. This is an indue performance cost. I could probably cache the sorted keys in this particular instance reasonably successfully, but this doesn't seem like a general solution.


I suppose the reason I'm reluctant to take the 2nd option is that I feel like if this was the correct move there would be a mechanism for this somewhere in phobos (ideally with a better abstraction than C++'s std::map's decision to use std::pair everywhere).

Have I missed something? Is the idiomatic solution to just do one of the above depending on the performance tradeoffs?


Thanks in advance!

Mark Isaacson:

> 2) Create a wrapper struct that contains key and value and whose comparison operator is defined only on the key. This would essentially be doing what the C++ implementation does.

Until we have a tree-based associative map, use a tuple for the key-value and define a "less" template argument like q{a.key < b.key} or q{a[0] < b[0]}.

Bye,
bearophile

On Sunday, 4 May 2014 at 21:40:04 UTC, bearophile wrote:
> Mark Isaacson:
>
>> 2) Create a wrapper struct that contains key and value and whose comparison operator is defined only on the key. This would essentially be doing what the C++ implementation does.
>
> Until we have a tree-based associative map, use a tuple for the key-value and define a "less" template argument like q{a.key < b.key} or q{a[0] < b[0]}.
>
> Bye,
> bearophile

Got it, no native support. Most unfortunate. I've always been vehemently against losing self-documentation via the std::pair/tuple based solution to the problem. I ended up rolling my own solution that lets you give meaningful names to the wrapper struct's data members: http://pastebin.com/cKLccqFn

Thanks.

Mark Isaacson:

> Got it, no native support. Most unfortunate.

What native support are you talking about?


> I've always been vehemently against losing self-documentation via the std::pair/tuple based solution to the problem.

What self documentation are you losing in D?


> I ended up rolling my own solution that lets you give meaningful names to the wrapper struct's data members: http://pastebin.com/cKLccqFn

What's bad about this?

void main() {
    import std.stdio, std.container, std.typecons;

    alias Two = Tuple!(string,"str", int, "bob");
    alias MyTree = RedBlackTree!(Two, q{a.str < b.str}, false);

    auto map = new MyTree(Two("hello", 5), Two("zbd", 3), Two("abc", 9));

    map[].writeln;
    auto rng = map[];
    assert(rng.front == map.Elem("abc", 9));
    assert(rng.front.str == "abc");
    assert(rng.front.bob == 9);
}


Bye,
bearophile

On Sunday, 4 May 2014 at 21:40:04 UTC, bearophile wrote:
> Mark Isaacson:
>
>> 2) Create a wrapper struct that contains key and value and whose comparison operator is defined only on the key. This would essentially be doing what the C++ implementation does.
>
> Until we have a tree-based associative map, use a tuple for the key-value and define a "less" template argument like q{a.key < b.key} or q{a[0] < b[0]}.
>
> Bye,
> bearophile

What benefits this gives over definining distinct struct? Sounds like unnecessary complication for me.

Dicebot:

> What benefits this gives over definining distinct struct? Sounds like unnecessary complication for me.

See the code in my precedent post, what do you think about it?

Bye,
bearophile

On Sunday, 4 May 2014 at 22:25:36 UTC, bearophile wrote:
> Dicebot:
>
>> What benefits this gives over definining distinct struct? Sounds like unnecessary complication for me.
>
> See the code in my precedent post, what do you think about it?
>
> Bye,
> bearophile

Change

    alias Two = Tuple!(string,"str", int, "bob");

to

    struct Two
    {
        string str;
        int bob;
    }

and it will become much more readable while staying semantically equivalent

Interesting. I clearly have more to learn about Tuple. I think I concur with Dicebot's alterations for self-documentation.

Thanks for all of your suggestions gentlemen.

On 5/4/14, 6:04 PM, Mark Isaacson wrote:
>
> I'm looking for a means to associate a key with a value and iterate over
> said container in-order. My natural choice in C++ would be std::map.
> When I look in std.container, I see that there is a RedBlackTree
> implementation, however this does not associate a key with a value (it
> is the equivalent of std::set).
>
> My question is essentially what the best/most idiomatic way to represent
> this is in D?

I don't think there's an idiomatic way to do it in D.

You'll probably have to create a class for it (and I think it would be good if D included such class in the standard library so nobody does this job twice).

You can copy what Ruby (and Crystal :-P) does: a hash table where each entry has reference to the previous and next entries, in the way they were inserted. That way the entries form a doubly-linked list. You get in-order iteration cost and also amortized O(1) insertion/lookup. When you need to delete a key you'd repoint the previous/next pointers (that's why you need the "previous" pointer).

Here's some code you can copy from: https://github.com/manastech/crystal/blob/master/src/hash.cr

And here an article about how they added this notion of order to Ruby hashes from 1.8 to 1.9: http://www.igvita.com/2009/02/04/ruby-19-internals-ordered-hash/