Design Pattern for caching different derived types without using RTTI

Question

Let's say I have a family of classes which all implement the same interface, perhaps for scheduling:

class Foo : public IScheduler {
public:
    Foo (Descriptor d) : IScheduler (d) {}
    /* methods */
};

class Bar : public IScheduler {
public:
    Bar (Descriptor d) : IScheduler (d) {}
    /* methods */
};

Now let's say I have a Scheduler class, which you can ask for an IScheduler-derived class to be started for a given descriptor. If it already exists, you'll be given a reference to it. If one doesn't exist, then it creates a new one.

One hypothetical invocation would be something like:

Foo & foo = scheduler->findOrCreate<Foo>(descriptor);

Implementing that would require a map whose keys were (descriptor, RTTI) mapped to base class pointers. Then you'd have to dynamic_cast. Something along these lines, I guess:

template<class ItemType>
ItemType & Scheduler::findOrCreate(Descriptor d)
{
    auto it = _map.find(SchedulerKey (d, typeid(ItemType)));
    if (it == _map.end()) {
        ItemType * newItem = new ItemType (d);
        _map[SchedulerKey (d, typeid(ItemType))] = newItem;
        return *newItem;
    }
    ItemType * existingItem = dynamic_cast<ItemType>(it->second);
    assert(existingItem != nullptr);
    return *existingItem;
}

Wondering if anyone has a way to achieve a similar result without leaning on RTTI like this. Perhaps a way that each scheduled item type could have its own map instance? A design pattern, or... ?

Answer 1

The address of a function, or class static member, is guaranteed to be unique (as far as < can see), so you could use such an address as key.

template <typename T>
struct Id { static void Addressed(); };

template <typename ItemType>
ItemType const& Scheduler::Get(Descriptor d) {
    using Identifier = std::pair<Descriptor, void(*)()>;

    Identifier const key = std::make_pair(d, &Id<ItemType>::Addressed);

    IScheduler*& s = _map[key];

    if (s == nullptr) { s = new ItemType{d}; }

    return static_cast<ItemType&>(*s);
}

Note the use of operator[] to avoid a double look-up and simplify the function body.

Answer 2

Here's one way.

Add a pure virtual method to IScheduler:

virtual const char *getId() const =0;

Then put every subclass to it's own .h or .cpp file, and define the function:

virtual const char *getId() const { return __FILE__; }

Additionally, for use from templates where you do have the exact type at compile time, in the same file define static method you can use without having class instance (AKA static polymorphism):

static const char *staticId() { return __FILE__; }

Then use this as cache map key. __FILE__ is in the C++ standard, so this is portable too.

Important note: use proper string compare instead of just comparing pointers. Perhaps return std::string instead of char* to avoid accidents. On the plus side, you can then compare with any string values, save them to file etc, you don't have to use only values returned by these methods.

If you want to compare pointers (like for efficiency), you need a bit more code to ensure you have exactly one pointer value per class (add private static member variable declaration in .h and definition+initialization with FILE in corresponding .cpp, and then return that), and only use the values returned by these methods.

---

Note about class hierarchy, if you have something like

• A inherits IScheduler, must override getId()
• A2 inherits A, compiler does not complain about forgetting getId()

Then if you want to make sure you don't accidentally forget to override getId(), you should instead have

• abstract Abase inherits IScheduler, without defining getId()
• final A inherits Abase, and must add getId()
• final A2 inherits Abase, and must add getId(), in addition to changes to A

(Note: final keyword identifier with special meaning is C++11 feature, for earlier versions just leave it out...)

Answer 3

If Scheduler is a singleton this would work.

template<typename T>
T& Scheduler::findOrCreate(Descriptor d) {
    static map<Descriptor, unique_ptr<T>> m;
    auto& p = m[d];
    if (!p) p = make_unique<T>(d);
    return *p;
}

If Scheduler is not a singleton you could have a central registry using the same technique but mapping a Scheduler* / Descriptor pair to the unique_ptr.

Answer 4

If you know all your different subtypes of IsScheduler, then yes absolutely. Check out Boost.Fusion, it let's you create a map whose key is really a type. Thus for your example, we might do something like:

typedef boost::fusion::map<
    boost::fusion::pair<Foo, std::map<Descriptor, Foo*>>,
    boost::fusion::pair<Bar, std::map<Descriptor, Bar*>>,
    ....
    > FullMap;

FullMap map_;

And we will use that map thuslly:

template <class ItemType>
ItemType& Scheduler::findOrCreate(Descriptor d)
{
    // first, we get the map based on ItemType
    std::map<Descriptor, ItemType*>& itemMap = boost::fusion::at_key<ItemType>(map_);

    // then, we look it up in there as normal
    ItemType*& item = itemMap[d];
    if (!item) item = new ItemType(d);
    return item;
}

If you try to findOrCreate an item that you didn't define in your FullMap, then at_key will fail to compile. So if you need something truly dynamic where you can ad hoc add new schedulers, this won't work. But if that's not a requirement, this works great.

Answer 5

static_cast the ItemType* to void* and store that in the map. Then, in findOrCreate, just get the void* and static_cast it back to ItemType*.

static_casting T* -> void* -> T* is guaranteed to get you back the original pointer. You already use typeid(ItemType) as part of your key, so it's guaranteed that the lookup will only succeed if the exact same type is requested. So that should be safe.

If you also need the IScheduler* in the scheduler map just store both pointers.