Kinds of containers
Andrei Alexandrescu via Digitalmars-d
digitalmars-d at puremagic.com
Wed Oct 21 04:05:12 PDT 2015
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
More information about the Digitalmars-d
mailing list