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