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