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
