Kinds of containers

[Rikki Cattermole via Digitalmars-d]

On 22/10/15 12:05 AM, Andrei Alexandrescu wrote:
> I'm finally getting the cycles to get to thinking about Design by
> Introspection containers. First off, there are several general
> categories of containers. I think D should support all properly. One
> question is which we go for in the standard library.
>
> 1. Functional containers.
>
> These are immutable; once created, neither their topology nor their
> elements may be observably changed. Manipulating a container entails
> creating an entire new container, often based on an existing container
> (e.g. append takes a container and an element and creates a whole new
> container).
>
> Internally, functional containers take advantage of common substructure
> and immutability to share actual data. The classic resource for defining
> and implementing functional containers is
> http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504.
>
>
> 2. Reference containers.
>
> These have classic reference semantics (à la Java). Internally, they may
> be implemented either as class objects or as reference counted structs.
>
> They're by default mutable. Qualifiers should apply to them gracefully.
>
> 3. Eager value containers.
>
> These are STL-style. Somewhat surprisingly I think these are the worst
> of the pack; they expensively duplicate at the drop of a hat and need to
> be carefully passed around by reference lest performance silently drops.
> Nevertheless, when used as members inside other data structures value
> semantics might be the appropriate choice. Also, thinking of them as
> values often makes code simpler.
>
> By default eager value containers are mutable. They should support
> immutable and const meaningfully.
>
> 4. Copy-on-write containers.
>
> These combine the advantages of value and reference containers: you get
> to think of them as values, yet they're not expensive to copy. Copying
> only occurs by necessity upon the first attempt to change them.
>
> The disadvantage is implementations get somewhat complicated. Also, they
> are shunned in C++ because there is no proper support for COW; for
> example, COW strings have been banned starting with C++11 which is quite
> the bummer.
>
> Together with Scott Meyers, Walter figured out a way to change D to
> support COW properly. The language change consists of two attributes.
>
> =======
>
> I'll attempt to implement a few versions of each and see what they look
> like. The question here is what containers are of interest for D's
> standard library.
>
>
> Andrei

I've got a list and a map implementation using allocators. They are 
pretty primitive but they may lead to insight so links provided.

https://github.com/rikkimax/alphaPhobos/blob/master/source/std/experimental/internal/containers/list.d
https://github.com/rikkimax/alphaPhobos/blob/master/source/std/experimental/internal/containers/map.d