On 10/21/2015 01:05 PM, 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.
...
I still think those should be mutable by default in order to have
painless interchangeability with other value type containers. Why should
corresponding ephemeral and persistent containers have different interfaces?
I assume you envision code using those to look as follows?
FunSet!int a;
a=a.with_(1);
auto b=a;
a=a.with_(2);
a=a.with_(3);
// b = {1}, a={1,2,3};
I think this should be allowed too:
FunSet!int a;
a.insert(1);
auto b=a;
a.insert(2);
a.insert(3);
// b = {1}, a={1,2,3};
One of the two versions should be automatically implemented via UFCS.
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.
...
IMO "1." ought to combine the advantages of value and reference
containers as well, just without any expensive copying at all, even when
updates happen.
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.
...
List:
- forward iteration
- bidirectional iteration
Stack:
- basic stack
- ordered stack [0]
Queue:
- basic queue
- heap
Set:
- hash set
- ordered set
- accumulating set [1]
- trie/radix tree
+ multiset versions
Map:
- hash map
- ordered map
- accumulating map [1]
- accumulating map with range update [2]
- trie/radix tree
- accumulating trie [1]
- accumulating trie with range update [2]
+ multimap versions
- array
- accumulating array [1]
- accumulating array with range update [2]
+ O(1) reset versions [3]
- rope
- accumulating rope [1]
- accumulating rope with range update [2]
[0] ordered stack: Push operations automatically pop the minimal number
of elements off the stack prior to pushing, such as to guarantee that
the elements on the stack remain ordered. The stack should expose a
sorted range in order to support binary search.
[1] accumulation: The (ordered!) data structure allows fast queries for
the result of some binary associative operations on the elements in a
certain range. (the allowed operations are determined in advance and
some intermediate results are automatically maintained). (for map, the
operation would be just on the values, not on the keys.) This is usually
quite easy support, but very useful.
[2] range update: here, the idea is that the data structure allows all
elements in a certain range to be updated. the updates are performed
lazily and have to be compatible with the associative operations (if any).
[3] fast reset: here the idea is that the map allows fast reset of its
values at the cost of some small additional overhead per lookup.
(destructors are called lazily.)
