put different class in hierarchy in one container in C++

Some times we have to put different objects in the same hierarchy in one container. I read some article saying there are some tricks and traps. However, I have no big picture about this question. Actually, t开发者_开发技巧his happens a lot in the real word.

For example, a parking lot has to contain different types of cars; a zoo has to contain different types of animals; a book store has to contain different types of books.

I remember that one article saying neither of the following is a good design, but I forgot where it is.

vector<vehicle> parking_lot;
vector<*vehicle> parking_lot;

Can anybody offer some basic rules for this kind of question?

I learnt a lot writing my reply to a similar question by the same author, so I couldn't resist to do the same here. In short, I've written a benchmark to compare the following approaches to the problem of storing heterogeneous elements in a standard container:

1. Make a class for each type of element and have them all inherit from a common base and store polymorphic base pointers in a std::vector<boost::shared_ptr<Base> >. This is probably the more general and flexible solution:

   struct Shape {
       ...
   };
   struct Point : public Shape { 
       ...
   };
   struct Circle : public Shape { 
       ...
   };
   std::vector<boost::shared_ptr<Shape> > shapes;    
   shapes.push_back(new Point(...));
   shapes.push_back(new Circle(...));
   shapes.front()->draw(); // virtual call
   

2. Same as (1) but store the polymorphic pointers in a boost::ptr_vector<Base>. This is a bit less general because the elements are owned exclusively by the vector, but it should suffice most of the times. One advantage of boost::ptr_vector is that it has the interface of a std::vector<Base> (without the *), so its simpler to use.

    boost::ptr_vector<Shape> shapes;    
    shapes.push_back(new Point(...));
    shapes.push_back(new Circle(...));
    shapes.front().draw(); // virtual call
   

3. Use a C union that can contain all possible elements and then use a std::vector<UnionType>. This is not very flexible as we need to know all element types in advance (they are hard-coded into the union) and also unions are well known for not interacting nicely with other C++ constructs (for example, the stored types can't have constructors).

   struct Point { 
       ...
   };
   struct Circle { 
       ...    
   };
   struct Shape {
       enum Type { PointShape, CircleShape };
       Type type;
       union {
           Point p;
           Circle c;
       } data;
   };
   std::vector<Shape> shapes;
   Point p = { 1, 2 };
   shapes.push_back(p);
   if(shapes.front().type == Shape::PointShape)
       draw_point(shapes.front());
   

4. Use a boost::variant that can contain all possible elements and then use a std::vector<Variant>. This is not very flexible like the union but the code to deal with it is much more elegant.

   struct Point { 
       ...
   };
   struct Circle { 
       ...
   };
   typedef boost::variant<Point, Circle> Shape;
   std::vector<Shape> shapes;
   shapes.push_back(Point(1,2));
   draw_visitor(shapes.front());   // use boost::static_visitor
   

5. Use boost::any (which can contain anything) and then a std::vector<boost::any>. That is very flexible but the interface is a little clumsy and error prone.

   struct Point { 
       ...
   };
   struct Circle { 
       ...
   };
   typedef boost::any Shape;
   std::vector<Shape> shapes;
   shapes.push_back(Point(1,2));
   if(shapes.front().type() == typeid(Point))    
       draw_point(shapes.front());   
   

This is the code of the full benchmark program (doesn't run on codepad for some reason). And here are my performance results:

time with hierarchy and boost::shared_ptr: 0.491 microseconds

time with hierarchy and boost::ptr_vector: 0.249 microseconds

time with union: 0.043 microseconds

time with boost::variant: 0.043 microseconds

time with boost::any: 0.322 microseconds

My conclusions:

• Use vector<shared_ptr<Base> > only if you need the flexibility provided by runtime polymorphism and if you need shared ownership. Otherwise you'll have significant overhead.

• Use boost::ptr_vector<Base> if you need runtime polymorphism but don't care about shared ownership. It will be significantly faster than the shared_ptr counterpart and the interface will be more friendly (stored elements not presented like pointers).

• Use boost::variant<A, B, C> if you don't need much flexibility (i.e. you have a small set of types which will not grow). It will be lighting fast and the code will be elegant.

• Use boost::any if you need total flexibility (you want to store anything).

• Don't use unions. If you really need speed then boost::variant is as fast.

Before I finish I want to mention that a vector of std::unique_ptr will be a good option when it becomes widely available (I think it's already in VS2010)

The problem with vector<vehicle> is that the object only holds vehicles. The problem with vector<vehicle*> is that you need to allocate and, more importantly, free the pointers appropriately.

This might be acceptable, depending on your project, etc...

However, one usually uses some kind of smart-ptr in the vector (vector<boost::shared_ptr<vehicle>> or Qt-something, or one of your own) that handles deallocation, but still permits storing different types objects in the same container.

Update

Some people have, in other answers/comments, also mentioned boost::ptr_vector. That works well as a container-of-ptr's too, and solves the memory deallocation problem by owning all the contained elements. I prefer vector<shared_ptr<T>> as I can then store objects all over the place, and move them using in and out of containers w/o issues. It's a more generic usage model that I've found is easier for me and others to grasp, and applies better to a larger set of problems.

The problems are:

1. You cannot place polymorphic objects into a container since they may differ in size --i.e., you must use a pointer.
2. Because of how containers work a normal pointer / auto pointer is not suitable.

The solution is :

1. Create a class hierarchy, and use at least one virtual function in your base class (if you can't think of any function to virtualize, virtualize the destructor -- which as Neil pointed out is generally a must).
2. Use a boost::shared_pointer (this will be in the next c++ standard) -- shared_ptr handles being copied around ad hoc, and containers may do this.
3. Build a class hierarchy and allocate your objects on the heap --i.e., by using new. The pointer to the base class must be encapsulated by a shared_ptr.
4. place the base class shared_pointer into your container of choice.

Once you understand the "whys and hows" of the points above look at the boost ptr_containers -- thanks to Manual for the tip.

Say vehicle is a base class, that has certain properties, then, inheriting from it you have say a car, and a truck. Then you can just do something like:

std::vector<vehicle *> parking_lot;
parking_lot.push_back(new car(x, y));
parking_lot.push_back(new truck(x1, y1));

This would be perfectly valid, and in fact very useful sometimes. The only requirement for this type of object handling is sane hierarchy of objects.

Other popular type of objects that can be used like that are e.g. people :) you see that in almost every programming book.

EDIT:
Of course that vector can be packed with boost::shared_ptr or std::tr1::shared_ptr instead of raw pointers for ease of memory management. And in fact that's something I would recommend to do by all means possible.

EDIT2:
I removed a not very relevant example, here's a new one:

Say you are to implement some kind of AV scanning functionality, and you have multiple scanning engines. So you implement some kind of engine management class, say scan_manager which can call bool scan(...) function of those. Then you make an engine interface, say engine. It would have a virtual bool scan(...) = 0; Then you make a few engines like my_super_engine and my_other_uber_engine, which both inherit from engine and implement scan(...). Then your engine manager would somewhere during initialization fill that std::vector<engine *> with instances of my_super_engine and my_other_uber_engine and use them by calling bool scan(...) on them either sequentially, or based on whatever types of scanning you'd like to perform. Obviously what those engines do in scan(...) remains unknown, the only interesting bit is that bool, so the manager can use them all in the same way without any modification.

Same can be applied to various game units, like scary_enemies and those would be orks, drunks and other unpleasant creatures. They all implement void attack_good_guys(...) and your evil_master would make many of them and call that method.

This is indeed a common practice, and I would hardly call it bad design for as long as all those types actually are related.

You can refer to this Stroustrup's answer to the question Why can't I assign a vector< Apple*> to a vector< Fruit*>?.