Vectors and polymorphism in C++

Question

I have a tricky situation. Its simplified form is something like this

class Instruction
{
public:
    virtual void execute() {  }
};

class Add: public Instruction
{
private:
    int a;
    int b;
    int c;
public:
    Add(int x, int y, int z) {a=x;b=y;c=z;}
    void execute() { a = b + c;  }
};

And then in one class I do something like...

void some_method()
{
    vector<Instruction> v;
    Instruction* i = new Add(1,2,3)
    v.push_back(*i);
}

And in yet another class...

void some_other_method()
{
    Instruction ins = v.back();
    ins.execute();
}

And they share this Instruction vector somehow. My concern is the part where I do "execute" function. Will it work? Will it retain its Add type?

Solution 1

No, it won't.

vector<Instruction> ins;

stores values, not references. This means that no matter how you but that Instruction object in there, it'll be copied at some point in the future.

Furthermore, since you're allocating with new, the above code leaks that object. If you want to do this properly, you'll have to do

vector<Instruction*> ins

Or, better yet:

vector< std::reference_wrapper<Instruction> > ins

I like this this blog post to explain reference_wrapper

This behavior is called object slicing.

Solution 2

So you will need some kind of pointer. A std::shared_ptr works well:

typedef shared_ptr<Instruction> PInstruction;

vector<PInstruction> v;
v.emplace_back(make_shared<Add>());

PInstruction i = v[0];

Keep in mind that PInstruction is reference-counted, so that the copy constructor of PInstruction will create a new "reference" to the same object.

If you want to make a copy of the referenced object you will have to implement a clone method:

struct Instruction
{

   virtual PInstruction clone() = 0;
   ...
}

struct Add
{
    PInstruction clone() { return make_shared<Add>(*this); }
    ...
}

PInstruction x = ...;
PInstruction y = x->clone();

If performance is an issue than you can look at std::unique_ptr, this is a little trickier to manage as move semantics are always required, but it avoids the cost of some atomic operations.

You can also use raw pointers and manage the memory manually with some sort of memory pool architecture.

The underlying problem is that to have a polymorphic type the compiler doesn't know how big the subclasses are going to be, so you can't just have a vector of the base type, as it won't have the extra space needed by subclasses. For this reason you will need to use pass-by-reference semantics as described above. This stores a pointer to the object in the vector and then stores the object on the heap in blocks of different sizes depending on what the subclass needs.

Solution 3

No, that will not work; you are "slicing" the Add object, and only inserting its Instruction part into the array. I would recommend that you make the base class abstract (e.g. by making execute pure virtual), so that slicing gives a compile error rather than unexpected behaviour.

To get polymorphic behaviour, the vector needs to contain pointers to the base class.

You will then need to be careful how you manage the objects themselves, since they are no longer contained in the vector. Smart pointers may be useful for this; and since you're likely to be dynamically allocating these objects, you should also give the base class a virtual destructor to make sure you can delete them correctly.

Comments

[Mike Seymour]

@user44273: Then use the shared_ptr implementation in Boost or TR1.

[WhozCraig]

@user44273 Do you understand why pushing objects by-value doesn't work though? That is the most important point of this answer.

[user44273]

Not completely. Can you enlighten me?

[WhozCraig]

@user44273 Read the linked Q&A on object-slicing. It spells out precisely what is wrong with how you're approaching this, and this answer (and several others) envelope mechanics for addressing it. It will explain it far better than a comment-alone can here.

[user44273]

Well... thanks a lot! I am glad I didn't went on to implement this and banging my head on the wall several hours later.

[user44273]

I apologize for memory leaks. It was a hastily written code. And unfortunately, I wouldn't know the type. There are Sub, Mul, Div and more besides Add that's given here.

[The Floating Brain]

@user44273 No need for apologies, I was just being hypothetical with the dynamic_cast.

[zennehoy]

Be very very careful with vector<std::reference_wrapper<Instruction>>! You have to be absolutely certain that whatever you add to the vector has a lifetime longer than the vector, and that what you add does get deleted at some point. Much better to use a vector<std::unique_ptr<Instruction>> instead.