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

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 dec开发者_StackOverflow社区ided to ask for hints. Thanks in advance for your answers.

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_;
};

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)

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

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.

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.

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! :-)

I found a project on Github called gorgone, which contains a C++ implementation of PersistentVector (based on Rich Hickey's Java implementation in Clojure) and RRBVector (based on more recent work by Phil Bagwell).

The maintainer of that project is no longer pursuing it, but I am. See my fork here: https://github.com/sandover/gorgone

I can't help to recommend this article Immutable C++ stack - thoughts and performance, the code review and answer is really awesome!

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