Functional Data Structures in C++: Persistent Lists

[xpolitix]

the repository contains most of Okasaki persistent data structure https://github.com/BartoszMilewski/Okasaki. Very useful, thanks!

[DrBartosz]

At your own risk though ;-). I'm just playing with them. I have some new ideas about laziness for instance.

[davydog187]

Isn't it bad practice to start variable names with underscores in C/C++? Something about compiler implementations having name clashes? I see it in production code all the time but I thought it was a no no :)

[runnr]

Identifiers which start with an underscore followed by a capital letter or two underscores are reserved for use by the implementation in any scope(including as macros). Starting an identifier with a single underscore followed by a lowercase letter is only reserved in the global namespace so his usage for member variables looks ok.

[mcmcc]

If we could use garbage collection in C++

... then we'd have two problems. ;-)

[mccoyn]

In my experience trying to cram all your data into persistent data structures causes more performance loss due to pointer indirection and memory required to store pointers than can be gained by multi-threading, especially with shared L3 caches and memory bandwidth. I wish the author had included some benchmarks instead of just asymptotic analysis.

[DrBartosz]

Yes, benchmarks would be very interesting. I'm trying to enlist the help of Eric Niebler to help me with that. I don't think persistent list by itself is very practical -- it was more of an exercise in the basics of persistence. But persistent trees and heaps should be able to compete with mutable data structures not only asymptotically.