Does D have "structural sharing" of immutable collections?

Roman D. Boiko rb at d-coding.com
Wed May 23 15:39:33 PDT 2012


On Wednesday, 23 May 2012 at 22:25:35 UTC, Steven Schveighoffer 
wrote:
> I looked up how it could be done, the one thing I was not sure 
> of was the parent node.  If you can have multiple references to 
> the same subtree, how do you keep track of the parents.  But if 
> you only are concerned about the ancestry of a single node, you 
> can dynamically determine the line in O(lgn) time, and use that 
> for the running of the redblack algorithm.
>
> I'm not sure how efficient it would be.
>
> -Steve

My problem is the following:

n elements in some given order, each has an associated value; I 
need to retrieve elements for which the sum of values associated 
with previous elements lies in a given ragne; this should work 
efficiently when elements are added or removed, and history 
should be preserved.

Storing elements as tree leafs and sums of children values in 
other nodes gives me this easily.

Lookup price is 0(log N) number comparisons, which should be very 
fast. Insert / delete / rotate are also logarithmic, but I don't 
know the constant factors.

No need to retrieve parents.

So far it seems like RBT is perfect for me (if cache friendly 
implementation will be possible. Hopefully it will, because nodes 
are small and I can preallocate memory for them).


More information about the Digitalmars-d mailing list