Searching for hints on how to implement immutable data structures in C++

Question

Hi everybody, I'm wondering how to implement immutable data structures in C++ (or C). I'm searching for a book or paper (or a relatively simple and documented implementation) on the subject and I haven't managed to find one for now so I decided to ask for hints. Thanks in advance for your answers.

Answer 1

const is your friend - objects with all data members const are hard to alter.

Answer 2

Have a look at the Phoenix Framework.

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

So it goes beyond simple immutable structures, but I assume that is the direction you're headed.

Answer 3

Hint: Declare a struct as follows:

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

This locks down the assignment operator. Now make sure the struct has no public or mutable member variables and that all 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 derive a less immutable type from yours anyway.

Answer 4

I think you may take an idea from another languages. For example in Java and C# immutability implemented following way. Instead of creating "mutators" (functions that "mutate" objects' state), we create functions that return 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 5

You can either declare objects as const like:

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

This is a common way of using the const keyword to make an object immutable.

If you know you have an object that you do not want to allow anything to be changed in and this should be part of the behavior of every instance of that object, you can make an object with all const 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 the values of const members within an initialization list. (which you should be using anyway as best practice)

Answer 6

Depends what you mean by "immutable data structure".

If you mean, a type where variables of that type can't be assigned to otherwise modified, then see the other answers here (removing access to assignment operator, using const, or simply having a reference or const data member).

If you mean, a type where values of that type can't be modified,e.g. like a Java or C# or Python string, but where variables of that type still can be assigned, then it's more tricky. Your best help there may be boost::intrusive_ptr to manage an internal mutable state. The reason for intrusive_ptr as opposed to e.g. shared_ptr is that intrusive_ptr allows more optimizations, one of which is crucial for e.g. "immutable strings", namely, constructing such a beast from a literal with no dynamic allocation at all.

I'm not aware of any general framework for doing the latter kind of "immutable data structure" in C++.

So, it seems that you've put up a good idea! :-)