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

[Mark Isaacson via Digitalmars-d-learn]

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!