Immutable "functional" data structure in C++11

Question

I was trying to write down some implementations for a couple of data structures that I'm interested in for a multithreaded / concurrent scenario.

A lot of functional languages, pretty much all that I know of, design their own data structures in such a way that they are immutable, so this means that if you are going to add value to an instance t1 of T, you really get a new instance of T that packs t1 + value.

 container t;
 container s = t; //t and s refer to the same container.
 t.add(value); //this makes a copy of t, and t is the copy

I can't find the appropriate keywords to do this in C++11; there are keywords, semantics and functions from the standard library that are clearly oriented to the functional approach, in particular I found that:

• mutable it's not for runtime, it's more likely to be an hint for the compiler, but this keyword doesn't really help you in designing a new data structure or use a data structure in an immutable way
• swap doesn't works on temporaries, and this is a big downside in my case

I also don't know how much the other keywords / functions can help with such design, swap was one of them really close to something good, so I could at least start to write something, but apparently it's limited to lvalues .

So I'm asking: it's possible to design immutable data structure in C++11 with a functional approach ?

Answer 1

You simply declare a class with private member variables and you don't provide any methods to change the value of these private members. That's it. You initialize the members only from the constructors of the class. Noone will be able to change the data of the class this way. The tool of C++ to create immutable objects is the private visibility of the members.

mutable: This is one of the biggest hacks in C++. I've seen at most 2 places in my whole life where its usage was reasonable and this keyword is pretty much the opposite of what you are searching for. If you would search for a keyword in C++ that helps you at compile time to mark data members then you are searching for the const keyword. If you mark a class member as const then you can initialize it only from the INITIALIZER LIST of constructors and you can no longer modify them throughout the lifetime of the instance. And this is not C++11, it is pure C++. There are no magic language features to provide immutability, you can do that only by programming smartly.

Answer 2

In c++ "immutability" is granted by the const keyword. Sure - you still can change a const variable, but you have to do it on purpose (like here). In normal cases, the compiler won't let you do that. Since your biggest concern seems to be doing it in a functional style, and you want a structure, you can define it yourself like this:

class Immutable{
   Immutable& operator=(const Immutable& b){} // This is private, so it can't be called from outside
   const int myHiddenValue;
public:
   operator const int(){return myHiddenValue;}
   Immutable(int valueGivenUponCreation): myHiddenValue(valueGivenUponCreation){}
};

If you define a class like that, even if you try to change myHiddenValue with const_cast, it won't actually do anything, since the value will be copied during the call to operator const int.

Note: there's no real reason to do this, but hey - it's your wish.

Also note: since pointers exist in C++, you still can change the value with some kind of pointer magic (get the address of the object, calc the offset, etc), but you can't really help that. You wouldn't be able to prevent that even when using an functional language, if it had pointers.

And on a side note - why are you trying to force yourself in using C++ in a functional manner? I can understand it's simpler for you, and you're used to it, but functional programming isn't often used because of its downfalls. Note that whenever you create a new object, you have to allocate space. It's slower for the end-user.

Answer 3

Bartoz Milewski has implemented Okasaki's functional data structures in C++. He gives a very thorough treatise on why functional data structures are important for concurrency. In that treatise, he explains the need in concurrency to construct an object and then afterwards make it immutable:

Here’s what needs to happen: A thread has to somehow construct the data that it destined to be immutable. Depending on the structure of that data, this could be a very simple or a very complex process. Then the state of that data has to be frozen — no more changes are allowed.

As others have said, when you want to expose data in C++ and have it not be available for changing, you make your function signature look like this:

class MutableButExposesImmutably
{
    private:
        std::string member;
    public:
        void complicatedProcess() { member = "something else"; } // mutates
        const std::string & immutableAccessToMember() const {
            return member;
        }
};

This is an example of a data structure that is mutable, but you can't mutate it directly.

I think what you are looking for is something like java's final keyword: This keyword allows you to construct an object, but thereafter the object remains immutable.

You can do this in C++. The following code sample compiles. Note that in the class Immutable, the object member is literally immutable, (unlike what it was in the previous example): You can construct it, but once constructed, it is immutable.

#include <iostream>
#include <string>
using namespace std;

class Immutable
{
    private:
        const std::string member;
    public:
        Immutable(std::string a) : member(a) {}
        const std::string & immutable_member_view() const { return member; }
};


int main() {
    Immutable foo("bar");
    // your code goes here
    return 0;
}

Answer 4

Re. your code example with s and t. You can do this in C++, but "immutability" has nothing to do with that question, if I understand your requirements correctly!

I have used containers in vendor libraries that do operate the way you describe; i.e. when they are copied they share their internal data, and they don't make a copy of the internal data until it's time to change one of them.

Note that in your code example, there is a requirement that if s changes then t must not change. So s has to contain some sort of flag or reference count to indicate that t is currently sharing its data, so when s has its data changed, it needs to split off a copy instead of just updating its data.

So, as a very broad outline of what your container will look like: it will consist of a handle (e.g. a pointer) to some data, plus a reference count; and your functions that update the data all need to check the refcount to decide whether to reallocate the data or not; and your copy-constructor and copy-assignment operator need to increment the refcount.