Bartosz Milewski has written the second article about immutable data structures in C++11, this time about Red-Black trees:
http://bartoszmilewski.com/2013/11/25/functional-data-structures-in-c-trees/

The C++11 code with few small changes (like using "enum class" instead of "enum"):
http://codepad.org/AEVVnfSc

D has GC and transitive immutability, so I have tried a D translation, a first draft:
http://dpaste.dzfl.pl/a48452af3

In the D code there are some problems with C++ lines as:
return RBTree(Color::R, RBTree(), x, RBTree());

And I don't know if this is public:
    Color rootColor() const {

Bye,
bearophile

On Tuesday, 26 November 2013 at 00:28:34 UTC, bearophile wrote:
> Bartosz Milewski has written the second article about immutable data structures in C++11, this time about Red-Black trees:
> http://bartoszmilewski.com/2013/11/25/functional-data-structures-in-c-trees/
>
> The C++11 code with few small changes (like using "enum class" instead of "enum"):
> http://codepad.org/AEVVnfSc
>
> D has GC and transitive immutability, so I have tried a D translation, a first draft:
> http://dpaste.dzfl.pl/a48452af3
>
> In the D code there are some problems with C++ lines as:
> return RBTree(Color::R, RBTree(), x, RBTree());
>
> And I don't know if this is public:
>     Color rootColor() const {
>
> Bye,
> bearophile

What do you mean by an 'immutable' data structure.  The linked article talks about Persistent data structures.  Are these the same thing?

When I saw "Immutable" I figured it didn't support insertion/deletion - which would sort eliminate the need for a Red-Black tree anyways.

On Tuesday, 26 November 2013 at 01:21:49 UTC, Craig Dillabaugh wrote:
> On Tuesday, 26 November 2013 at 00:28:34 UTC, bearophile wrote:
clip
>>
>> Bye,
>> bearophile
>
> What do you mean by an 'immutable' data structure.  The linked article talks about Persistent data structures.  Are these the same thing?
>
> When I saw "Immutable" I figured it didn't support insertion/deletion - which would sort eliminate the need for a Red-Black tree anyways.

While I am at it, I might as well ask another question.  How is it that your 'insert' function is const?  I thought I understood const, but apparently not!

Cheers

Craig Dillabaugh:

> What do you mean by an 'immutable' data structure.  The linked article talks about Persistent data structures.  Are these the same thing?
>
> When I saw "Immutable" I figured it didn't support insertion/deletion - which would sort eliminate the need for a Red-Black tree anyways.

In those articles Bartosz is implementing in C++11 the immutable data structures from the book by Okasaki. Immutable doesn't mean you can't change them :-) It means you can't modify the single data items, and you have referential transparency.

Bye,
bearophile

Craig Dillabaugh:

> While I am at it, I might as well ask another question.  How is it that your 'insert' function is const?  I thought I understood const, but apparently not!

The D code I have linked is not yet working, so don't read too much in it.
But you can add items to an immutable tree, if you use structural sharing.

Bye,
bearophile

On Tuesday, 26 November 2013 at 01:31:11 UTC, bearophile wrote:
> Craig Dillabaugh:
>
>> What do you mean by an 'immutable' data structure.  The linked article talks about Persistent data structures.  Are these the same thing?
>>
>> When I saw "Immutable" I figured it didn't support insertion/deletion - which would sort eliminate the need for a Red-Black tree anyways.
>
> In those articles Bartosz is implementing in C++11 the immutable data structures from the book by Okasaki. Immutable doesn't mean you can't change them :-) It means you can't modify the single data items, and you have referential transparency.
>
> Bye,
> bearophile

Ok, that make sense.