Kinds of containers

Zz via Digitalmars-d digitalmars-d at puremagic.com
Wed Oct 21 11:18:54 PDT 2015


On Wednesday, 21 October 2015 at 11:05:12 UTC, 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

While looking at containers take a look at Jiri Soukup's work 
some good ideas could come from there.

http://www.amazon.ca/Serialization-Persistent-Objects-Structures-Efficient/dp/3642393225/ref=sr_1_1?ie=UTF8&qid=1386946808&sr=8-1&keywords=SERIALIZATION+AND+PERSISTENT+OBJECTS#productPromotions%22%20target=%22_blank

Intrusive Data Structures.
http://www.codefarms.com/home
http://www.codefarms.com/dol
http://www.codefarms.com/ppf
http://www.codefarms.com/ptl

Zz


More information about the Digitalmars-d mailing list