struct vs. class containers (was: Re: dcollections 1.0 and 2.0a beta released)

[Steven Schveighoffer]

On Mon, 24 May 2010 12:18:02 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:

> On 05/24/2010 10:58 AM, Steven Schveighoffer wrote:
>> On Sun, 23 May 2010 17:36:52 -0400, Andrei Alexandrescu
>> <SeeWebsiteForEmail at erdani.org> wrote:
>>
>>> I've thought for a very long time about the class vs. struct choice in
>>> a container, and I came to a startling conclusion: it (almost) doesn't
>>> matter. Could be either, and the tradeoffs involved are nonessential.
>>> Here they are:
>>>
>>> 1. Using a class makes implementing members easier because there's no
>>> need to do work through an additional member. With a struct, you need
>>> a pimpl approach. For example:
>>>
>>> struct Array {
>>> struct Impl {
>>> ...
>>> }
>>> Impl * impl;
>>> ...
>>> @property length() const { return impl->length; }
>>> ...
>>> }
>>>
>>> 2. struct gives you more power in managing collection's own memory, as
>>> long as the collection doesn't escape item addresses or other
>>> addresses of internal handles. So all other things being equal, struct
>>> has a net advantage.
>>
>> Yes, but most containers are node-based, so as long as you use structs
>> for nodes, you are generally in control of the bulk of allocation
>> (dcollections does this).
>
> I'm saying, the net advantage of struct is that it can safely and  
> deterministically release memory in its destructor.

OK.

>
>>> 3. The creation syntaxes are different. For Phobos, I suggest adding a
>>> simple function make() to std.algorithm. make!T(a, b, c) returns a
>>> newly constructed object T by invoking the constructor with arguments
>>> a, b, and c. That way we can make client code virtually agnostic of
>>> the class/struct choice for a container.
>>>
>>
>> Classes have builtin object monitors. But you could handle that via a
>> struct as well. The language support wouldn't be there though.
>
> Oh, and the monitor isn't needed so that's an unused word there. I'd  
> forgotten about it.

Why isn't the monitor needed?  Will we no longer be able to use a globally  
shared container object?

>
>>> That's it. Otherwise, one could use either to build a container. Let
>>> me note that I have reached the conclusion that containers should be
>>> at best reference types, with a meta-constructor Value!(C) that takes
>>> a container C and makes it into a value type.
>>
>> The thing that classes really give you is the language support. Structs
>> need to be hand-crafted to support the same syntax. Classes are enforced
>> as always being reference types and always being on the heap.
>
> I'd agreed classes are more convenient because they make the  
> implementation straightforward.
>
>> The
>> Value!(C) is questionable because creating the head of a container on
>> the stack leads to easily escaped stack references.
>
> I don't understand this. Could you give an example?

For example, dcollections' TreeMap has an 'end' node that defines the end  
of the container.  It actually is the root of the RB tree and all the data  
is on the left child of the 'end' node.  This makes it always the last  
node iterated.

The end node is actually member of the class, it's not allocated  
separately on the heap for efficiency and a less complex constructor.  So  
let's say TreeMap could be on the stack, here's a situation where an  
escape would occur:

auto foo()
{
    TreeMap!(string, uint) tmap; // allocated on stack
    ... // fill up tmap;
    return tmap["hi"..tmap.end]; // oops! end is part of the range, and it  
was allocated on the stack.
}

In dcollections, all the classes have some sort of members that are  
associated with the entire container, not the elements.  These would  
disappear once a stack-based container exited scope, but there may be  
dangling references returned.

To get around this, you could ensure that all data was allocated on the  
heap, but then wouldn't Value!(C) be almost useless?  What data would be  
allocated on the stack that is part of the container that would never be  
referenced by the heap-based parts?

-Steve