Kinds of containers

[bitwise via Digitalmars-d]

On Thursday, 22 October 2015 at 05:09:38 UTC, deadalnix wrote:
> On Thursday, 22 October 2015 at 02:13:12 UTC, bitwise wrote:
>> I needed containers, so I implemented a few:
>> https://github.com/bitwise-github/d-collections
>>
>> Currently included:
>>
>> List(T) - contiguous list like std::vector
>> LinkedList(T) - doubly linked list like std::list
>> Queue(T) - double-ended queue/contiguous circular buffer
>> Stack(T) - contiguous fifo stack
>>
>
> You got such a good start with the first 2 ones, but somehow 
> missed on consistency. You should name the 2 other ones 
> QueueList and StackList.

Actually, I was thinking of calling them QueueSeq and StackSeq ;)


>> I initially had this reversed, where List(T) was a value type, 
>> and ListRef(T) was a reference type, but I flipped it the 
>> other way to avoid unneeded copying for naive usage. I'm still 
>> not sure this is the right direction though. Optimization is a 
>> job of it's own, and it's a job for a pro. I believe the 
>> amount of effort spent to idiot-proof(for lack of a better 
>> term) the containers should be limited. Especially with the 
>> power of D's ranges, I think containers should generally(and 
>> in my code, usually do) stay put. IMO, If someone wants to 
>> pass something around, they should pass a range, not the 
>> container itself. My solution, however, does support 
>> both(ref/value), if needed.
>>
>
> Reference types or COW are definitively the way to go for the 
> naive road. Think about it, 40% to 50% of chrome memory is 
> std::string . Eager copy is not a healthy default.

I can't ignore how many times I've heard people talking about 
eager-copy containers in C++ and how they're a pain. I believe 
the value-type option should be available though.

Maybe the idea of default-ref-type containers could be taken a 
step further to hide the value types from casual users:

struct List(T)
{
     struct Core { ... } // specified as a fully useable container 
on it's own
     RefCounted!Core core;
     alias core this;
}

List!int.Core list; // value type container

Unlike the current std.container.Array(T) though, the payload 
inside the container should be fully useable on it's own.

I don't understand exactly how a COW container would work. Is 
this what's done with D strings right now? I've got a bad feeling 
about this idea. Containers have been around a long time, and I 
don't think it would be prudent to stray to far from traditional 
approaches.

>> There is still work to do, of course.
>>
>
> The elephant in the room: make the template parameter's type 
> qualifier transitive with the collection's qualifier.

Not sure exactly what you mean by this. Currently, Ranges and 
Cursors are templated on the type of the container, so If the 
container is const, you get a const Range or Cursor. I haven't 
gone over the containers with a fine tooth comb yet, so if you 
can point anything out, it would be helpful.

     Bit