Take the 2-minute tour ×

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.

share|improve this question
Maybe you're looking for Persistent data structures (en.wikipedia.org/wiki/Persistent_data_structure)? If so, you can take a look at immutable collections in .net for some other hints as well (blogs.msdn.com/b/bclteam/archive/2012/12/18/…) –  Sergey Teplyakov May 12 '13 at 19:43

8 Answers 8

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
  Foo(int i)
   : i_(i)

   int GetI() const {return i_;}
   Foo SetI(int i) const {return Foo(i);}
   const int i_;
share|improve this answer
That exactly what I meant by "immutable", but what I'm searching for hints on how to efficiently implement immutable collections (eg: Clojure collections), particularly how to share part of the structure to avoid unnecessary copying. –  fokenrute Oct 13 '10 at 21:16
@fokenrute I think that is the real question, sharing the part of the immutable structure. In garbage collected languages that is quite straightforward. –  Ghita May 12 '13 at 6:36

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
   Immutable() :z(10), y(20) 


   Immutable(int zVal, int yVal) : z(zVal), y(yVal) 


   int getZ() const;
   int getY() const;

   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)

share|improve this answer

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

share|improve this answer

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.

share|improve this answer
Does it also allow structure sharing? –  CMCDragonkai Dec 18 at 4:00

Hint: Declare a struct as follows:

struct Immutable
    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:

    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.

share|improve this answer
Immutable doesn't mean non-copyable. You don't have to worry about the object being copied. –  RC. Oct 13 '10 at 18:15
You're absolutely right, one only has to worry about the object being assigned to. Answer updated accordingly. Thanks for the heads-up. –  Frédéric Hamidi Oct 13 '10 at 18:20

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Your Answer


