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.
