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

[Ary Borenszweig via Digitalmars-d-learn]

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/