www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - C++ std::map equivalent? (An in-order iterable associative container)

reply "Mark Isaacson" <turck11 hotmail.com> writes:
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!
May 04 2014
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
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
May 04 2014
next sibling parent reply "Mark Isaacson" <turck11 hotmail.com> writes:
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.
May 04 2014
parent "bearophile" <bearophileHUGS lycos.com> writes:
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
May 04 2014
prev sibling parent reply "Dicebot" <public dicebot.lv> writes:
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.
May 04 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
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
May 04 2014
parent reply "Dicebot" <public dicebot.lv> writes:
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
May 04 2014
parent "Mark Isaacson" <turck11 hotmail.com> writes:
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.
May 04 2014
prev sibling parent Ary Borenszweig <ary esperanto.org.ar> writes:
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/
May 04 2014