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... ?

Verdugo

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.

Terrazas

Not an overall "pattern" change, but an interesting avoidance of RTTI. Do you think in a modern C++11 compiler there's a big benefit to doing it this way? – Verdugo

@HostileFork: I do not think it brings much compared to using typeinfo... unless you happen to want to compile without RTTI support :) – Terrazas

That will stop to work if one uses e.g. Windows DLLs. I know the C++ standard still guarantees the address to be unique, but I know of no compiler that actually implements that behavior correctly with Windows DLLs. Using typeid still works though. – Polley

@PaulGroke: it is scary how broken C++ on Windows is :( – Terrazas

@MatthieuM. Eesh. Scary. typeinfo it is. – Verdugo

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...)

Marola

It does avoid the typeid... and I've done rickety things of this nature (even to the point of hashing a filename and line number together and hoping that it's unique :-/). But it appears @MatthieuM.'s technique is a more stable way of achieving the same goal, and doesn't dictate the file structure? – Verdugo

Yes, it's seems almost same as the version I describe with static private member variable, and probably better solution for this case. My string solution is better if you need to use the class id for many purposes, like save it to file or have other persistence. – Marola

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.

Sadie

Whilst quite clever, this is subject to data races in multi-threaded programs. This is also subject to the syndrom of the ever-growing cache. – Terrazas

All these answers (and the original code in the question) are subject to data races in multi-threaded programs, this could be easily synchronized if that was a requirement. – Sadie

+1 for direction I was looking for, although the scheduler needs access to iterate all the items... and it wouldn't necessarily be a singleton. :-/ I wonder what the tradeoff is? I'm not exactly sure what @MatthieuM. is referring to, but without getting too distracted I do recall several things to worry about with static members. – Verdugo

Prior to C++11 function local statics did not have thread-safe initialization. As of C++11 the standard says that they must have thread safe initialization but not all compilers implement this yet (it's not coming to Visual C++ until post VC 2013 according to this: herbsutter.com/2013/09/09/…). – Sadie

@HostileFork: I'll expand then :) 1. Thread safety: whilst in C++11 the creation is guaranteed to be thread-safe, afterwards it is your job to properly serialize access to m across threads (using locks, atomics, whatever). 2. Ever-growing cache: there is no way to remove items from m as it is defined, as a result it will only ever grow as the program runs. Depending on how many unique combinations of (Descriptor, T) you have, this might blow up your memory. A more tasteful design (which does not preclude static local variables) would include ways to control the size of this cache. – Terrazas

Answer 4

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.

Polley

Casting to void isn't very C++ish...I'm actually looking for a pattern within C++ to be "cleaner" than what I'm considering. But also, won't a static_cast work from an IScheduler* as well if you are certain the object is of the target type? I thought what wouldn't work would be IScheduler* ptr = &foo; Foo* fooPtr = (Foo*)((void*)ptr); – Verdugo

Yes, casting from IScheduler would work in your example. The point is that you don't need a dynamic_cast. And casting to void IMO is very much "C++ ish". Also I wouldn't consider it "unclean". Only that, as you correctly pointed out, it's unnecessary in your case. – Polley

Thanks for the idea here, but I did wind up going with the typeinfo...which has worked out well. – Verdugo

Answer 5

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.

Chalk

Missed this one. Interesting, hadn't heard of boost::fusion. Thanks. In my case, though, I don't know all the different IsScheduler types so I wound up resorting to the typeinfo solution. – Verdugo