Can I have polymorphic containers with value semantics in C++?

Question

As a general rule, I prefer using value rather than pointer semantics in C++ (ie using vector<Class> instead of vector<Class*>). Usually the slight loss in performance is more than made up for by not having to remember to delete dynamically allocated objects.

Unfortunately, value collections don't work when you want to store a variety of object types that all derive from a common base. See the example below.

#include <iostream>

using namespace std;

class Parent
{
    public:
     Parent() : parent_mem(1) {}
     virtual void write() { cout << "Parent: " << parent_mem << endl; }
     int parent_mem;
};

class Child : public Parent
{
    public:
     Child() : child_mem(2) { parent_mem = 2; }
     void write() { cout << "Child: " << parent_mem << ", " << child_mem << endl; }

     int child_mem;
};

int main(int, char**)
{
    // I can have a polymorphic container with pointer semantics
    vector<Parent*> pointerVec;

    pointerVec.push_back(new Parent());
    pointerVec.push_back(new Child());

    pointerVec[0]->write(); 
    pointerVec[1]->write(); 

    // Output:
    //
    // Parent: 1
    // Child: 2, 2

    // But I can't do it with value semantics

    vector<Parent> valueVec;

    valueVec.push_back(Parent());
    valueVec.push_back(Child()); // gets turned into a Parent object :(

    valueVec[0].write(); 
    valueVec[1].write(); 

    // Output:
    // 
    // Parent: 1
    // Parent: 2

}

My question is: Can I have have my cake (value semantics) and eat it too (polymorphic containers)? Or do I have to use pointers?

Answer 1

Since the objects of different classes will have different sizes, you would end up running into the slicing problem if you store them as values.

One reasonable solution is to store container safe smart pointers. I normally use boost::shared_ptr which is safe to store in a container. Note that std::auto_ptr is not.

vector<shared_ptr<Parent>> vec;
vec.push_back(shared_ptr<Parent>(new Child()));

shared_ptr uses reference counting so it will not delete the underlying instance until all references are removed.

Answer 2

Take a look at *static_cast* and *reinterpret_cast*
In C++ Programming Language, 3rd ed, Bjarne Stroustrup describes it on page 130. There's a whole section on this in Chapter 6.
You can recast your Parent class to Child class. This requires you to know when each one is which. In the book, Dr. Stroustrup talks about different techniques to avoid this situation.

Do not do this. This negates the polymorphism that you're trying to achieve in the first place!

Answer 3

@Misha: I think I can see where you are going with reinterpret_cast and static_ cast, and although it might be safe in the specific example given above, I do not think it could be a good programming practice in general to do that. What happens if the Child class includes non-POD data types (such as strings) that have destructors? When the vector is destroyed, it would go through calling destructors on objects that aren't really there. Your method is too fragile.

Answer 4

You might also consider boost::any. I've used it for heterogeneous containers. When reading the value back, you need to perform an any_cast. It will throw a bad_any_cast if it fails. If that happens, you can catch and move on to the next type.

I believe it will throw a bad_any_cast if you try to any_cast a derived class to its base. I tried it:

  // But you sort of can do it with boost::any.

  vector<any> valueVec;

  valueVec.push_back(any(Parent()));
  valueVec.push_back(any(Child()));        // remains a Child, wrapped in an Any.

  Parent p = any_cast<Parent>(valueVec[0]);
  Child c = any_cast<Child>(valueVec[1]);
  p.write();
  c.write();

  // Output:
  //
  // Parent: 1
  // Child: 2, 2

  // Now try casting the child as a parent.
  try {
   Parent p2 = any_cast<Parent>(valueVec[1]);
   p2.write();
  }
  catch (const boost::bad_any_cast &e)
  {
      cout << e.what() << endl;
  }

  // Output:
  // boost::bad_any_cast: failed conversion using boost::any_cast

All that being said, I would also go the shared_ptr route first! Just thought this might be of some interest.

Answer 5

Most container types want to abstract the particular storage strategy, be it linked list, vector, tree-based or what have you. For this reason, you're going to have trouble with both possessing and consuming the aforementioned cake (i.e., the cake is lie (NB: someone had to make this joke)).

So what to do? Well there are a few cute options, but most will reduce to variants on one of a few themes or combinations of them: picking or inventing a suitable smart pointer, playing with templates or template templates in some clever way, using a common interface for containees that provides a hook for implementing per-containee double-dispatch.

There's basic tension between your two stated goals, so you should decide what you want, then try to design something that gets you basically what you want. It is possible to do some nice and unexpected tricks to get pointers to look like values with clever enough reference counting and clever enough implementations of a factory. The basic idea is to use reference counting and copy-on-demand and constness and (for the factor) a combination of the preprocessor, templates, and C++'s static initialization rules to get something that is as smart as possible about automating pointer conversions.

I have, in the past, spent some time trying to envision how to use Virtual Proxy / Envelope-Letter / that cute trick with reference counted pointers to accomplish something like a basis for value semantic programming in C++.

And I think it could be done, but you'd have to provide a fairly closed, C#-managed-code-like world within C++ (though one from which you could break through to underlying C++ when needed). So I have a lot of sympathy for your line of thought.

Answer 6

Just to add one thing to all 1800 INFORMATION already said.

You might want to take a look at "More Effective C++" by Scott Mayers "Item 3: Never treat arrays polymorphically" in order to better understand this issue.

Answer 7

Yes, you can.

The boost.ptr_container library provides polymorphic value semantic versions of the standard containers. You only have to pass in a pointer to a heap-allocated object, and the container will take ownership and all further operations will provide value semantics , except for reclaiming ownership, which gives you almost all the benefits of value semantics by using a smart pointer.

Answer 8

I just wanted to point out that vector<Foo> is usually more efficient than vector<Foo*>. In a vector<Foo>, all the Foos will be adjacent to each other in memory. Assuming a cold TLB and cache, the first read will add the page to the TLB and pull a chunk of the vector into the L# caches; subsequent reads will use the warm cache and loaded TLB, with occasional cache misses and less frequent TLB faults.

Contrast this with a vector<Foo*>: As you fill the vector, you obtain Foo*'s from your memory allocator. Assuming your allocator is not extremely smart, (tcmalloc?) or you fill the vector slowly over time, the location of each Foo is likely to be far apart from the other Foos: maybe just by hundreds of bytes, maybe megabytes apart.

In the worst case, as you scan through a vector<Foo*> and dereferencing each pointer you will incur a TLB fault and cache miss -- this will end up being a lot slower than if you had a vector<Foo>. (Well, in the really worst case, each Foo has been paged out to disk, and every read incurs a disk seek() and read() to move the page back into RAM.)

So, keep on using vector<Foo> whenever appropriate. :-)

Answer 9

I'm using my own templated collection class with exposed value type semantics, but internally it stores pointers. It's using a custom iterator class that when dereferenced gets a value reference instead of a pointer. Copying the collection makes deep item copies, instead of duplicated pointers, and this is where most overhead lies (a really minor issue, considered what I get instead).

That's an idea that could suit your needs.