dmd 1.066 and 2.051 release

[Jonathan M Davis]

On Friday 24 December 2010 17:48:46 Ali Çehreli wrote:
> 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.

Yes, the C++ standard has performance requirements that pretty much restrict 
each container type to a particular implementation but leave it open to other 
implementations if they can meet the performance requirements. However, sets in 
general do not have to have any particular implementation. The same goes for 
maps. In Java, you HashSet and TreeSet, both of which implement the Set 
interface. So, if you use Set, you don't know what the implementation is.

Andrei chose to have Phobos select particular data structures for containers 
rather than their concepts. So, you have a red-black tree and you can use it for 
whatever makes sense to use a red-black tree for. If that's a set, then it's a 
set. But each container is defined as a particular data structure rather than 
what it's going to be used for.

Whether that is the best decision is obviously debatable, since other languages 
have taken other approaches. But that's what we're doing in D. Personally, I 
think that it makes good sense. In particular, I do _not_ like Java's approach 
where you have interfaces with implementations with very different performance 
characteristics. With std.container, the performance characteristics will be 
clear.

- Jonathan M Davis