Andrei:

> Apologies for that. This is a major addition! Walter, I just updated the changelog, would you mind updating the website? Thanks, and many thanks to Steve who contributed the most complex container yet to std.container!

I suggest to add a RedBlackTree example usage (a little program) in the docs.

Bye,
bearophile

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.

On Fri, Dec 24, 2010 at 1:25 AM, bearophile <bearophileHUGS@lycos.com>wrote:

> Andrei:
>
> > Apologies for that. This is a major addition! Walter, I just updated the changelog, would you mind updating the website? Thanks, and many thanks to Steve who contributed the most complex container yet to std.container!
>
> I suggest to add a RedBlackTree example usage (a little program) in the
> docs.
>
> Bye,
> bearophile
>

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.

std::set uses a red-black tree in most (all?) C++ standard library implementations; so does std::map.

Neither "is a" red-black tree. They use red-black trees in their implementations. They could very well be implemented as a simple binary tree as well. The C++ standard spells out algorithmic complexities of operations on standard containers, but not actual implementations.

Ali

>
> On Fri, Dec 24, 2010 at 1:25 AM, bearophile <bearophileHUGS@lycos.com>wrote:
>
>> Andrei:
>>
>>> Apologies for that. This is a major addition! Walter, I just updated the
>>> changelog, would you mind updating the website? Thanks, and many thanks
>>> to Steve who contributed the most complex container yet to std.container!
>> I suggest to add a RedBlackTree example usage (a little program) in the
>> docs.
>>
>> Bye,
>> bearophile
>>
>

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.

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

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

So what does one use in D if something like std::unordered_set is needed? RedBlackTree is ordered as far as I can tell.

On Fri, Dec 24, 2010 at 6:08 PM, Jonathan M Davis <jmdavisProg@gmx.com>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.
>
> 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
>

Caligo wrote:
> So what does one use in D if something like std::unordered_set is needed?

Like std::unordered_sets, D's associative arrays are hash tables.

A table of doubles indexed with string keys:

    double[string] my_table;

Ali

> RedBlackTree is ordered as far as I can tell.
> 
> On Fri, Dec 24, 2010 at 6:08 PM, Jonathan M Davis <jmdavisProg@gmx.com>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.
>>
>> 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
>>
> 

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

Am 2010-12-21 09:38, schrieb Walter Bright:
> This is another bug fix release.
>
> http://www.digitalmars.com/d/1.0/changelog.html
> http://ftp.digitalmars.com/dmd.1.066.zip
>
> http://www.digitalmars.com/d/2.0/changelog.html
> http://ftp.digitalmars.com/dmd.2.051.zip

Is it possible that someone creates tags for every release in the svn repos for dmd, phobos and druntime?

It should be common use.