Does D have "structural sharing" of immutable collections?

Roman D. Boiko rb at d-coding.com
Thu May 24 06:25:35 PDT 2012


On Thursday, 24 May 2012 at 13:15:30 UTC, Craig Dillabaugh wrote:
> I am not sure if I entirely understand your problem, but would a
> persistent search tree work? See:
>
> http://www.sciencedirect.com/science/article/pii/0022000089900342
>
> I have a small write up on them from a course I took years ago:
>
> http://cg.scs.carleton.ca/~cdillaba/comp5008/sarnak.html
Yes, it would. Actually, what I described is how to use RBT as
search tree. RBT is selected because it bounds number of levels
to the optimum, and thus gives log N worst case for all
operations.

I'll take a look at the links, thanks!


More information about the Digitalmars-d mailing list