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/
