Functional data structures in C++

Question

Does anyone know of a C++ data structure library providing functional (a.k.a. immutable, or "persistent" in the FP sense) equivalents of the familiar STL structures?

By "functional" I mean that the objects themselves are immutable, while modifications to those objects return new objects sharing the same internals as the parent object where appropriate.

Ideally, such a library would resemble STL, and would work well with Boost.Phoenix (caveat- I haven't actually used Phoenix, but as far as I can tell it provides many algorithms but no data structures, unless a lazily-computed change to an existing data structure counts - does it?)

Answer 1

I would look and see whether FC++ developed by Yannis Smaragdakis includes any data structures. Certainly this project more than any other is about supporting a functional style in C++.

Answer 2

This is more of a heads up than a detailed answer, but Bartosz Milewski appears to have done a lot of work on this. See, for example:

http://bartoszmilewski.com/2013/11/13/functional-data-structures-in-c-lists/

Looks like he's implemented a lot of algorithms from Okasiki's book Purely Functional Data Structures here:

https://github.com/BartoszMilewski/Okasaki

N.B. I haven't tried these yet, but they're the first C++ persistent data structures I've seen outside of FC++.

Hopefully, I'll get to trying them soon.