Containers

[bitwise via Digitalmars-d]

On Friday, 4 September 2015 at 13:26:27 UTC, wobbles wrote:
> On Friday, 4 September 2015 at 10:25:24 UTC, Russel Winder 
> wrote:
>> On Thu, 2015-09-03 at 21:11 +0000, bitwise via Digitalmars-d 
>> wrote:
>>> On Thursday, 3 September 2015 at 19:45:48 UTC, bitwise wrote:
>>> 
>>> > I'm not sure how the container's I've built would be 
>>> > integrated
>>> 
>>> I suppose what I'm suggesting would be to integrate my new 
>>> containers and modify the spec to explain the new value type 
>>> containers, and start deprecating the old containers as 
>>> better versions become available...starting with Array(T)...
>>> 
>>> Or I could stop trying to make tangible contributions to D 
>>> and just go bikeshed about =+
>>
>> Isn't the best route here to make a trivially accessible 
>> library (via the Dub repository?) that people can choose to 
>> use instead of the bits of Phobos that these data structures 
>> replace? This will then allow the momentum of usage to apply 
>> pressure for the Phobos ones to be deprecated and your new 
>> ones to be absorbed into Phobos…
>
> I do think this is the best option for all new libraries that 
> are to be potentially merged into phobos.
>
> It's how the python/Java world works too and I think they've 
> done pretty well out of it.

What I meant by that comment, is how the process would go of 
differentiating between the new and the old containers, allowing 
them to coexist until the old ones were removed. I've since put 
my containers into a package called "collections" which would 
differentiate them from the current "containers". They could then 
have their own documentation without being subject to the current 
container spec.

The current container spec has several problems.

It specifies containers as reference types, but then goes on to 
explain how that's only half true, and tries to explain explain 
the quirks involved, and recommend using "make" to reconcile the 
problem. This is confusing, inconsistent, and inflexible. 
Containers should all be either real reference types(classes) or 
real value types(structs).

Given the above two choices, I would choose structs. With 
structs, your options extend all the way down to primitive value 
types. You can house the struct in your own class or a 
RefCounted(T) with no unnecessary cost or hassle. With classes, 
there are only two choices, which are as-is classes(which use GC 
and have to be new'ed), or RefCounted classes(which incur cost of 
ref counting and the additional allocation for payload). The only 
benefit I see of using classes would be to allow containers to 
inherit common interfaces, which I don't think is all that useful.

This is another problem:
   "Containers do not form a class hierarchy, instead they 
implement a common set of primitives (see table below). These 
primitives each guarantee a specific worst case complexity and 
thus allow generic code to be written independently of the 
container implementation."

I believe this is wrong, in that the point of abstraction should 
be the Ranges you get from the containers, not the containers 
themselves. I think it's a little silly for an Array(T) to have a 
"removeAny()" method.

Then, there is the idea of range validity. I strongly disagree 
with the way this idea is presented by the current spec.

For example, Array(T) has "stableRemoveBack". This is misleading, 
because although your program _may_ not crash by using a range to 
a modified container, the range may be pointing at the wrong 
elements. Or worse, the program could still crash. Array(T) has 
stableRemoveBack(), but if you call it and then access a range 
that was pointing to the last element in the container, you get 
an out of range exception.

I believe a better definition of range validity would be that the 
range pointed to the exact same elements after modification of 
the container. With a linked list, people would have to 
understand that ranges were a pair of iterators, and that 
removing either end point of the range from the container would 
invalidate it.


On Friday, 4 September 2015 at 11:11:03 UTC, BBasile wrote:
> On Thursday, 3 September 2015 at 19:45:48 UTC, bitwise wrote:
>>[...]
>
> I think that std.allocators is a prerequisite to implement the 
> some new std containers.

agreed, it's on the todo list.

> New containers without std.mallocators would be an error. In 
> this sense, EMSI allocators are a bit more compliant (they 
> already use them, not exactly as required but   templates have 
> an optional param to indicate if the structures are GC-free or 
> not).

I looked at this, and I think this point should be abstracted 
away. I believe the allocators should expose the necessary 
information/traits to allow containers to know how to use them... 
possibly something like iterator tags in C++.