Iterating over objects of a specific class in a container of polymorphic base objects

Question

Let's suppose there is a base object class - let it be called Object - and a list<Object> container. There are many child classes of Object - Child1, Child2 etc.. They all are stored in the container.

I need a way to iterate over subsets of objects of some particular class. Say, over all Child1's or Child2's, while having them all together in one container so that they could be accessed in a polymorphic fashion.

Note should be taken that the container is dynamically resized now and then.

What are possible design solutions for that?

Currently I've come up with two:

introducing an iterator which runs on the container checking object type each time
keeping additional containers with all Child1 and all Child2 objects from the main container.

Honestly, I don't like either way: the first one, I'm afraid, is going to be slow because there will be really many objects, the second one is clumsy and requires observing each object addition and deletion.

I'm writing it in C++.

UPDATE

As a further development of the second solution, I've just thought of subclassing a list with methods that would return sublists of particular subclass types which could be kept cached and updated on each add/delete:

for(auto i: gameObjects.sublist<Child1>()) {
   ...

how many writes do you have to this container? i'm trying to understand if its holding some configuration data or some runtime data, if its mostly write or mostly read. — Tomer Ben David, Jun 01 '17 at 07:15
@TomerBenDavid It's a game with different objects. I can't assess actual numbers at the moment, perhaps a few hundreds or maybe more. Pair dozens writes/deletes per second. More being read than written. — olegst, Jun 01 '17 at 07:43
is there a different scenario where you do need to traverse them altogether? — Tomer Ben David, Jun 01 '17 at 09:57
Closely related, I do not think it is a duplicate: **[Is it a code smell to store generic objects in a container and then get object and downcast the objects from container?](https://softwareengineering.stackexchange.com/q/321805/)** — , Jun 01 '17 at 20:29

score 9 · Answer 1 · answered Jun 01 '17 at 08:23

When you have a polymorphic collection like your scenario, the problem you have is that the object itself knows what it is but nothing else does so anything outside of the container needs some extra knowledge to be able to identify what is what.

The direct solution would be to improve the container so that it distinguishes between objects itself. You could contain a map of containers for each object type, which are just pointers to the objects contained in the main list. Be careful, use shared pointers, pay attention to what is added and deleted. If you just keep references to the objects, memory shouldn't balloon up. You mentioned this already. I would not consider it clumsy, but dangerous.

That being said I feel like there may be a problem of design. If a list of objects is actually a list of many different objects, why are they together?

You mentioned in a comment that this is a game, so perhaps you have one generic 'game object' list, but many of those game objects are enemies and you are now trying to grab all enemies in one script. You are missing a step: all enemies are game objects, but not all game objects are enemies, thus you want some intermediary manager for all enemies. Perhaps have each enemy register itself with the manager, automate the system as much as possible. After all, what is spawning the enemies? You must already have something manipulating the game object list, expand on that.

This. Having a bunch of different things mashed up together in a list is usually a very good sign that someone, somewhere, is doing something wrong. +1, very good answer. — T. Sar, Jun 01 '17 at 19:49

score 4 · Answer 2 · answered Jun 01 '17 at 15:27

Polymorphic operations are traditionally handled by the visitor pattern. As @Erdrik Ironrose indicates, the object knows it’s type so let it do it’s work. The iteration is performed by calling a function on every object. This function then calls a type specific version of that function. Some objects may not support certain functions and will simply return.

There are many variations to the visitor pattern. What you are looking for is a double-dispatch concept. The abstract object is called with information that indicates that it should call some other function with it’s real type. At the time the object calls the type specific function, the right type will be known and the right function called.

I’ll ignore the problem that your list<Object> should be list<shared_ptr<Object>> (or something similar) as a list<Object> will slice each instance to the base class Object.

Yes, something like shared_ptr, I just overlooked it while was writing. — olegst, Jun 01 '17 at 17:03

score 3 · Answer 3 · answered Jun 01 '17 at 21:14

Elaborating on Erdrick's answer, I would strongly advocate that you scrap the "everything" container, and just have separate containers for all the Child1s, Child2s, etc.

If you need to occasionally iterate over Parents, just combine all of these (into a set or list as appropriate). This will add time, but you save tons of time when iterating over the ChildX types.

Only if iteration over Parent was common and iterating over ChildX was rare would I check object type.

Note, if speed is essential and memory is no problem you could maintain a separate collection of all Parents as well, though memory management will be slightly trickier.

R Sahu · Answer 4 · 2017-06-02T03:49:42.037

First of all, when you have a polymorphic object, you must not store a list of objects. That will result in object slicing. You must store a list of pointers, preferably a list of smart pointers.

Coming to the problem of iterating over the objects of a given derived type, you can use iteration in the manner used in a for loop, such as:

 for ( Object* ptr : container )
 {
    // If the pointer is of the right type, do something with it.
    // Otherwise, ignore it.
 }

or you iterate in the style of:

 iterator start = <some starting point>;
 iterator end = <some ending point>;
 for ( iterator iter = start; iter != end; ++iter )
 {
    Object* ptr = *iter;
    // If the pointer is of the right type, do something with it.
    // Otherwise, ignore it.
 }

The first case can be cleanly handled using an application specific for_each style function.

namespace MyApp
{
   template <typename ObjectType, typename Container, typename Functor>
   void for_each(Container const& container, Functor f)
   {
      for ( Object* ptr : container )
      {
         ObjectType* optr = dynamic_cast<ObjectType*>(ptr);
         if ( optr != nullptr )
         {
            f(optr);
         }
      }
   }
}

The second case can also be cleanly handled using another application specific for_each style function.

namespace MyApp
{
   template <typename ObjectType, typename iterator, typename Functor>
   void for_each(iterator start, iterator end, Functor f)
   {
      for ( iterator iter = start; iter != end; ++iter )
      {
         Object* ptr = *iter;
         ObjectType* optr = dynamic_cast<ObjectType*>(ptr);
         if ( optr != nullptr )
         {
            f(optr);
         }
      }
   }
}

You may also implement the first one using the second one.

namespace MyApp
{
   template <typename ObjectType, typename Container, typename Functor>
   void for_each(Container const& container, Functor f)
   {
      for_each<ObjectType>(container.begin(), container.end(), f);
   }
}

Your concern -- the first one, I'm afraid, is going to be slow because there will be really many objects -- is valid. However, I would worry about it only if it becomes a significant concern in typical runs. The simplicity of this approach is more attractive to me that other approaches.

Iterating over objects of a specific class in a container of polymorphic base objects

4 Answers4