CODEWITHSUNDEEP
c++data-structuresimmutability
fokenrute
fokenrute

Reputation: 739

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 decided to ask for hints. Thanks in advance for your answers.

Upvotes: 4

Views: 1306

Answers (8)

Lihang Li
Lihang Li

Reputation: 361

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.

Upvotes: 0

sandover
sandover

Reputation: 7768

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

Upvotes: 0

Cheers and hth. - Alf
Cheers and hth. - Alf

Reputation: 145279

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

Upvotes: 0

Frédéric Hamidi
Frédéric Hamidi

Reputation: 262949

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.

Upvotes: 0

RC.
RC.

Reputation: 28217

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)

Upvotes: 2

Sergey Teplyakov
Sergey Teplyakov

Reputation: 11657

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

Upvotes: 3

Robert Harvey
Robert Harvey

Reputation: 180798

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.

Upvotes: 0

Steve Townsend
Steve Townsend

Reputation: 54158

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

Upvotes: 0

Related Questions