Does D have "structural sharing" of immutable collections?

Roman D. Boiko rb at d-coding.com
Wed May 23 11:51:31 PDT 2012


On Wednesday, 23 May 2012 at 18:39:02 UTC, Stewart Gordon wrote:
> On 23/05/2012 16:05, Roman D. Boiko wrote:
> <snip>
>> I need some immutable collections for my D Compiler Tools 
>> project, namely linked list,
>> red-black tree, and possibly some others.
> <snip>
>
> What's the point of an immutable red-black tree?
>
> The whole point of a red-black tree is to facilitate fast 
> dynamic addition, removal and lookup of elements.
>
> When the tree is immutable, only lookup speed is of any real 
> relevance, so you might as well create a perfectly balanced 
> binary tree.  Or even better, an array.
>
> Stewart.

Immutable collections in most cases have the same performance 
characteristics as mutable ones. Space consumption may be higher, 
but not necessarily.

Instead of mutating a collection, a new one is returned each time 
you add or remove an element. It shares most nodes with a 
previous one.


More information about the Digitalmars-d mailing list