Finding hints on how to implement immutable data structures in C ++

Question

I am wondering how to implement immutable data structures in C ++ (or C). I am looking for a book or document (or a relatively simple and documented implementation) on this issue, and I have not been able to find it yet, so I decided to ask for tips. Thank you in advance for your answers.

Answer 1

I think you can take the idea from other languages. For example, in Java and C # immutability is implemented as follows. Instead of creating "mutators" (functions that "mutate" the state of objects), we create functions that return a new "changed" instance:

class Foo { public: Foo(int i) : i_(i) {} int GetI() const {return i_;} Foo SetI(int i) const {return Foo(i);} private: const int i_; }; 

Answer 2

You can declare objects as const:

const std::string x("My Const String");

This is the usual way to use the const keyword to make an object immutable.

If you know that you have an object that you do not want to allow something to be changed, and this should be part of the behavior of each instance of this object, you can create an object with all constant members.

 class Immutable { public: Immutable() :z(10), y(20) { } Immutable(int zVal, int yVal) : z(zVal), y(yVal) { } int getZ() const; int getY() const; private: const int z; const int y; }; 

Note that you must set member constants in the initialization list. (which you should use as best practice anyway)

Answer 3

const is your friend - objects with all const data elements are hard to change.

Answer 4

Check out the Phoenix Framework.

Phoenix extends FP concepts to C ++ much further. In short, the framework opens up FP methods such as Lambda (unnamed functions) and Currying (evaluation of partial functions).

Thus, it goes beyond simple immutable structures, but I assume this is the direction you are heading.

Answer 5

Hint: declare a struct as follows:

 struct Immutable { private: Immutable& operator =(const Immutable& other); }; 

This blocks the assignment operator. Now make sure that the structure does not have member variables public or mutable and that all of its public methods are const :

 public: int get_quux() const; void foo(int bar) const; 

And you have something very close to an immutable type. Of course, the lack of sealed / final in C ++ means that someone can get a less immutable type from you.

Answer 6

Depends on what you mean by "immutable data structure."

If you mean a type in which variables of this type cannot be assigned otherwise, then see the other answers here (removing access to the assignment operator using const or just having a reference or const data element).

If you mean a type in which values ​​of this type cannot be changed, for example. like a Java or C # or Python string, but where variables of this type can still be assigned, it is more complicated. Your best help might be boost::intrusive_ptr for managing internal volatile state. The reason for intrusive_ptr , unlike, for example, shared_ptr is that intrusive_ptr allows more optimizations, one of which is crucial for, for example, "immutable strings", namely, building such a beast from a literal without any dynamic allocation at all.

I am not aware of any general structure for executing the latter type of “immutable data structure” in C ++.

So it seems that you have created a good idea! :-)

Answer 7

I found a Github project called gorgone that contains a C ++ implementation for PersistentVector (based on Rich Hickey Java implementation in Clojure) and RRBVector (based on a later work by Phil Bagwell).

The originator of this project is no longer pursuing him, but I am. See my fork here: https://github.com/sandover/gorgone

Answer 8

I can't help but recommend this article The C ++ Immutable Stack - the thoughts and performance , the code review and the answer are really awesome!

Also, to get started with persistent data structures or functional data structures in C ++, read this post Functional Data Structures in C ++: Lists .