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