Best Practice For List of Polymorphic Objects in C++

Question

What is a common practice for the storage of a list of base class pointers each of which can describe a polymorphic derived class?

To elaborate and in the interest of a simple example lets assume that I have a set of classes with the following goals:

1. An abstract base class whose purpose is to enforce a common functionality on its derived classes.
2. A set of derived classes which: can perform a common functionality, are inherently copyable (this is important), and are serializable.

Now alongside this required functionality I want to address the following key points:

1. I want the use of this system to be safe; I don't want a user to have undefined errors when he/she erroneously casts a base class pointer to the wrong derived type.
2. Additionally I want as much as possible the work for copying/serializing this list to be taken care of automatically. The reason for this is, as a new derived type is added I don't want to have to search through many source files and make sure everything will be compatible.

The following code demonstrates a simple case of this, and my proposed (again I am looking for a common well thought out method of doing this, mine may not be so good) solution.

class Shape {
public:
    virtual void draw() const = 0;
    virtual void serialize();
protected:
    int shapeType;
};

class Square : public Shape
{
public:
    void draw const; // draw code here.
    void serialize(); // serialization here.
private:
    // square member variables.
};

class Circle : public Shape
{
public:
    void draw const; // draw code here.
    void serialize(); // serialization here.
private:
    // circle member variables.
};

// The proposed solution: rather than store list<shape*>, store a generic shape type which
// takes care of copying, saving, loading and throws errors when erroneous casting is done.
class GenericShape
{
public:
    GenericShape( const Square& shape );
    GenericShape( const Circle& shape );
    ~GenericShape();
    operator const Square& (); // Throw error here if a circle tries to get a square!
    operator const Circle& (); // Throw error here if a square tries to get a circle!
private:
    Shape* copyShape( const Shape* otherShape );
    Shape* m_pShape; // The internally stored pointer to a base type.
};

The above code is certainly missing some items, firstly the base class would have a single constructor requiring the type, the derived classes would internally call this during their construction. Additionally in the GenericShape class, copy/assignment constructor/operator would be present.

Sorry for the long post, trying to explain my intents fully. On that note, and to re-iterate: above is my solution, but this likely has some serious flaws and I would be happy to hear about them, and the other solutions out there!

Thank you

Answer 1

You could avoid lots of repetition in GenericShape by using templates (for the constructors and converters), but the key bit that's missing is having it inherit from Shape and implement its virtuals -- without it it's unusable, with it it's a pretty normal variant on envelope/implementation idioms.

You may want to use auto_ptr (or somewhat-smarter pointers) rather than a bare pointer to Shape, too;-).

Answer 2

What is the problem of a std::list< shape* > (or a std::list< boost::shared_ptr > thereof)?

That would be the idiomatic way of implementing a list of shapes with polymorphic behavior.

1. I want the use of this system to be safe; I don't want a user to have undefined errors when he/she erroneously casts a base class pointer to the wrong derived type.

Users should not downcast, but rather use the polymorphism and the base (shape) operations provided. Consider why they would be interested in downcasting, if you find a reason to do so, go back to drawing board and redesign so that your base provides all needed operations.

Then if the user wants to downcast, they should use dynamic_cast, and they will get the same behavior you are trying to provide in your wrapper (either a null pointer if downcasting pointers or a std::bad_cast exception for reference downcasting).

Your solution adds a level of indirection and (with the provided interface) require the user to try guessing the type of shape before use. You offer two conversion operators to each of the derived classes, but the user must call them before trying to use the methods (that are no longer polymorphic).

1. Additionally I want as much as possible the work for copying/serializing this list to be taken care of automatically. The reason for this is, as a new derived type is added I don't want to have to search through many source files and make sure everything will be compatible.

Without dealing with deserialization (I will come back later), your solution, as compared to storing (smart) pointers in the list, requires revisiting the adapter to add new code for each and every other class that is added to the hierarchy.

Now the deserialization problem.

The proposed solution is using a plain std::list< boost::shared_ptr >, once you have the list built, drawing and serialization can be performed right out of the box:

class shape
{
public:
   virtual void draw() = 0;
   virtual void serialize( std::ostream& s ) = 0;
};
typedef std::list< boost::shared_ptr<shape> > shape_list;
void drawall( shape_list const & l )
{
   std::for_each( l.begin(), l.end(), boost::bind( &shape::draw, _1 ));
}
void serialize( std::ostream& s, shape_list const & l )
{
   std::for_each( l.begin(), l.end(), boost::bind( &shape::serialize, _1, s ) );
}

Where I have used boost::bind to reduce code bloat instead of iterating manually. The problem is that you cannot virtualize construction as before the object has been constructed you cannot know what type it actually is. After the problem of deserializing one element of a known hierarchy is solved, deserializing the list is trivial.

Solutions to this problem are never as clean and simple as the code above.

I will assume that you have defined unique shape type values for all shapes, and that your serialization starts by printing out that id. That is, the first element of serialization is the type id.

const int CIRCLE = ...;
class circle : public shape
{
   // ...
public:
   static circle* deserialize( std::istream & );
};
shape* shape_deserialize( std::istream & input )
{
   int type;
   input >> type;
   switch ( type ) {
   case CIRCLE:
      return circle::deserialize( input );
      break;
   //...
   default:
      // manage error: unrecognized type
   };
}

You can further alleviate the need to work on the deserializer function if you convert it into an abstract factory where upon creation of a new class the class itself registers it's deserialization method.

typedef shape* (*deserialization_method)( std::istream& );
typedef std::map< int, deserialization_method > deserializer_map;
class shape_deserializator
{
public:
   void register_deserializator( int shape_type, deserialization_method method );
   shape* deserialize( std::istream& );
private:
   deserializer_map deserializers_;
};

shape* shape_deserializator::deserialize( std::istream & input )
{
   int shape_type;
   input >> shape_type;
   deserializer_map::const_iterator s = deserializers_.find( shape_type );
   if ( s == deserializers_.end() ) {
      // input error: don't know how to deserialize the class
   }
   return *(s->second)( input ); // call the deserializer method
}

In real life, I would have used boost::function<> instead of the function pointers, making the code cleaner and clearer, but adding yet another dependency to the example code. This solution requires that during initialization (or at least before trying to deserialize) all classes register their respective methods in the *shape_deserializator* object.

Answer 3

I would propose boost::shared_pointer<Shape> in an STL container. Then use dynamic_cast to downcast guarantee type correctness. If you want to provide helper functions to toss exceptions instead of returning NULL, then follow Alex's suggestion and define a template helper function like:

template <typename T, typename U>
T* downcast_to(U *inPtr) {
    T* outPtr = dynamic_cast<T*>(inPtr);
    if (outPtr == NULL) {
        throw std::bad_cast("inappropriate cast");
    }
    return outPtr;
}

and use it like:

void some_function(Shape *shp) {
    Circle *circ = downcast_to<Circle>(shp);
    // ...
}

Using a separate class like GenericShape is just too strongly coupled with every class that descends from Shape. I wonder if this would be considered a code smell or not...

Answer 4

I want the use of this system to be safe; I don't want a user to have undefined errors when he/she erroneously casts a base class pointer to the wrong derived type.

Why would you get undefined errors? The behavior of dynamic_cast is perfectly well-defined and catches the error if you cast a base class pointer to the wrong derived type. This really seems like reinventing the wheel.

Additionally I want as much as possible the work for copying/serializing this list to be taken care of automatically. The reason for this is, as a new derived type is added I don't want to have to search through many source files and make sure everything will be compatible.

I'm not sure what the problem is here. If all the derived classes are serializable and copyable, isn't that good enough? What more do you need?

I'm also not sure what to make of the first two requirements. What do you mean, the ABC should "enforce a common functionality"? And what is the point in having derived classes, if their role is only to perform that same common functionality, be copyable and serializable?

Why not just make one non-abstract class serializable and copyable then?

I'm probably missing something vital here, but I don't really think you've explained what it is you're trying to achieve.

Answer 5

Hey, first off thanks for the responses. Sorry that I am writing a new 'answer' not sure if this is the convention at SO, regardless though since I'm not allowed to post comments yet this is the only way to give/receive additional feedback.

I really like the answer from dribeas above, and if he/she comes back to look I have some follow up questions. First off in response to your comment:

Users should not downcast, but rather use the polymorphism and the base (shape) operations provided. Consider why they would be interested in downcasting, if you find a reason to do so, go back to drawing board and redesign so that your base provides all needed operations.

So in this particular case, I might want to downcast because: I load (deserialize) a list of shapes and then at some point I want to edit the information contained within the shape (ie. for a circle perhaps I will redefine its radius). Is there a way to set derived class specific members via a base class pointer? It seems to me that I would need to use the ever so useful (and thanks for this, I didn't realize dynamic_cast worked this way) dynamic_cast.

So my next question is in regards to foregoing copying of my shapes and instead using a shared_pointer. Perhaps I don't fully understand the use of a shared_pointer but given the nature of pointers I would imagine that this is essentially a safe shallow copy. Now in my case I do want to be able to 'deep' copy the shape object. I suppose one solution would be similar to your deserialization method, instead returning an auto_pointer to a shape. Any other suggestions in this area (deep copying that is).

Again thank you for the response, you are all clearly more enlightened in the use of higher level OOP concepts!

PS: In response to your last comment jalf, and I suppose I didn't make it particularily clear. What I meant by common functionality was more in the sense of a common goal (ie. drawing a shape) however the actual drawing might vary significantly based on the specific shape.