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!
