Deque impl.

[Robert burner Schadek]

On 01/31/2013 04:11 PM, Andrei Alexandrescu wrote:
> On 1/31/13 3:46 AM, monarch_dodra wrote:
>> Quite frankly, I'm bringing more and more into question the fact that
>> everything in phobos are structs, especially considering the "no default
>> constructor" problem.
>>
>> The containers in std.container pretty much emulate final classes via
>> pointers to payloads anyways. Not doing it via classes only brings
>> problems.
>>
>> And even if you succeed in coding the damn thing correctly (Objects like
>> DList had so many bugs I consider it virtually unusable). The end result
>> is subtle user bugs when passing containers, if they have not been
>> initialized yet. It creates an ambiguity in behavior if or if not the
>> container is initialized (modification to the container inside the
>> function may or may not modify the outside container).
>>
>> The only argument I see in favor of structs, is the possibility of
>> having a deterministic memory model (std.container.Array). I don't think
>> D's *generic* containers should do that though, IMO. It also brings lots
>> of problems, just for a specific use case.
>>
>> Long story short, I'd say that unless you have a damn good reason to
>> stay with structs, use classes. It has easier user semantics and much
>> less room for implementation bugs.
>
> We should use structs.
>
> Many people who need containers have efficiency as a primary concern. 
> It makes sense for the standard library to make containers as good as 
> possible.
>
> The intended semantics of containers in stdlib is reference counted 
> with reference semantics. Yes, there are disadvantages for that. After 
> much deliberation it seemed to me this is the best approach to 
> containers in a language that cares for efficiency.
>
> Reference counting and adding allocators later rule out final classes.
>
>
> Andrei
So just to check if I get you.

struct Deque(T) {
     struct Payload {
         T* array;
         size_t head, size;
         size_t ref;
     }

     Payload* load;

     ~this() {
         if(load !is null && load.ref-1 == 0) {
             free(load);
     }
}