dmd 1.066 and 2.051 release

Ali Çehreli acehreli at yahoo.com
Fri Dec 24 17:48:46 PST 2010


Jonathan M Davis wrote:
 > On Friday 24 December 2010 00:02:06 Caligo wrote:
 >> Why are they calling it RedBlackTree? why not Set?  C++ std::set is a
 >> red-black tree as far as I know, but they named it set.
 >
 > Andrei decided that the containers in Phobos will named after what 
they actually
 > are instead of what they're used for. A prime example of this is a 
red-black
 > tree. It can be used as a set. Depending on the implementation (I 
haven't look
 > at the Phobos one yet), it can also be used as a map (it's used for 
both set and
 > map in C++'s STL). But a set could be implemented in many different 
ways. A red-
 > black tree is only one of them. It could be implemented with a hash 
instead. But
 > that would give it very different performance characteristics.

Yes, having different performance characteristics, hash table does not 
satisfy the requirements of the standard though: std::set is an ordered 
container.

Table 99 in "23.2.4 Associative containers" of the standard lists the 
requirements for associative containers. Here is a link to the draft:

   http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3126.pdf

I guess an implementation could maintain a hash table as well, for 
better-than-required access.

 > Phobos is taking the approach that a container is labeled for the 
data structure
 > that it is rather than what it's used for. That way it's very clear 
what it's
 > performance characteristics are. If you want to use the term Set in 
your code,
 > then simply alias RedBlackTree to Set.
 >
 > - Jonathan M Davis

Ali


More information about the Digitalmars-d-announce mailing list