The idea of a type map is quite simple. It's similar to a hash table, except its keys are types. It has two basic operations - associate a value with the given type and retrieve the value associated with the given type. So, how would one go about implementing something like this in C++? Let's find out.
Compile-Time Solution
The most simple and straightforward way of associating a value with a type is simply introducing a static member variable into your class. It's not very flexible, though. You can get a bit more fancy. For example, if you want to be able to provide a string annotation for arbitrary types, you can do it with the help of template specializations:
template <typename T>struct StringAnnotationTypeMap { static const std::string annotation; };template <typename T>const std::string StringAnnotationTypeMap<T>::annotation = "default value";template <>const std::string StringAnnotationTypeMap<int>::annotation = "annotation for int";//etc...The idea here is that you simply specialize the template for any types you want to put in your typemap.
You can then use the type map like this:
std::cout << StringAnnotationTypeMap<int>::annotation << "\n";Runtime Typemaps
The above solution works, but I happen to think that initializing the type map in this way is a pain. More importantly, it's fundamentally impossible to use if you require multiple instances of type maps that can be created and destroyed arbitrarily at runtime. What we have above, one could say, is a "static" or "compile time" type map: your program can't create and populate a new typemaps when it's running. But why would we want to do that anyway? Let's consider the following example.
A Motivating Example
In game development, there is a pattern called "Entity Component System". In a nutshell, the idea of ECS is that all the entities in the game (such as enemies, power-ups, projectiles, etc.) are modelled as being composed of various "components" rather than being members of a giant class hierarchy. Various "systems" (such as AI system, graphics system, etc.) then read or manipulate the state of components to achieve the desired effects.
For example, in a 2D side scrolling game, the player's character might be an entity that has (among others) a sprite component (for displaying the animation of the player on screen) and a physics component (for detecting collisions). On the other hand, something like a butterfly that just flies around for decoration, might have a sprite component, but no physics component (since it doesn't collide with anything). The graphics system can use the sprite component to draw a graphical representation of an entity on the screen. On the other hand, the AI system may change the sprite component of a computer-controlled character's entity in order to display a different image depending on whether the character is walking or standing still. Note how this approach is different from, say, having an entity class that extends the "PhysicsEntity" and "Drawable" classes.
Entity Component System is an interesting pattern, but a complete discussion on it is not within the scope of this post (read this if you want to know more about ECS). For now, we'll focus on just one aspect: simplifying the process of adding new component types.
Let's say you just created a new type of component called HitPointComponent, which has the amount of hit points, or "health" that a character has left:
class HitPointComponent : public AbstractComponent {public: void takeHitFrom(const Entity *other_entity); void add(int hp); void setCurrentCap(int c); private: int m_hitPoints; // amount of hitpoints, can't be greater than m_currentCap int m_currentCap; // maximum amount of hitpoints}; It would be nice to be able say: "hey, entity e1, give me your HitPointComponent" without having to write any additional code. You can achieve that by simply having Entity contain a hash table that maps strings (component names) to AbstractComponent pointers:
class Entity {public:// ... AbstractComponent* get (const std::string &component_name) { auto it = m_components.find(component_name); assert(it != m_components.end()); return it->second.get(); }private: std::unordered_map<std::string, std::unique_ptr<AbstractComponent>> m_components;//...};It's simple to implement, but also not very safe: there are no guarantees that the component obtained using e->get("HitPointComponent"); is actually a HitPointComponent. Also, every time you want to do something with a component, you have to deal with this awkward cast: dynamic_cast<HitPointComponent>(player->get("HitPointComponent"))->takeHitFrom(projectile).
We can use dynamic type maps for a safer and more convenient solution. It will be possible to write code like this:
auto e = std::make_unique<Entity>();e->provideComponent<HitPointComponent>(std::make_unique<HitPointComponent>());//...e->get<HitPointComponent>()->takeHitFrom(projectile);Mapping Types To Integers
First, we need an efficient way to obtain a unique identifier (that can be used at runtime) for a given type. Of course, typeid comes to mind. typeid(HitPointComponent) refers to a object of type const std::type_info. Conveniently, const std::type_info has a method called hash_code, which appears to be doing what we want - it returns an integer corresponding to our type!
So then, we're done, right? Well, not quite. Unfortunately, the C++ standard does not strictly require that method to return different values for different types. It merely suggests that the compiler developers should try to implement hash_code in a way that returns different values for different types. However, it is not a strict requirement. The only strict requirement is returning same values for same types.
In practice, most implementations of std::type_info::hash_code probably do return different values for different types. But maybe you don't like to put too much trust into that (or maybe you just don't want to use RTTI). You can use the following trick:
// In a header file:#include <atomic>extern std::atomic_int TypeIdCounter;template <typename T>int getTypeId() { static int id = ++TypeIdCounter; return id;}// In a *.cpp file:std::atomic_int TypeIdCounter(0);A call to getTypeId will return a unique integer for your type. The trick relies on the fact that getTypeId and getTypeId are considered two completely different functions (even though they are instantiated from the same function template), and therefore they will have completely different static variables id initialized to different values. The concrete values will depend on what the value of the global TypeIdCounter was at the time of the function call. TypeIdCounter is made atomic just in case getTypeId is called from different threads, but you can get away with just a plaint int if you program is single-threaded.
Implementing Our Type Map
Using the above technique, it's quite easy to implement a type map by first converting the type to the corresponding integer and then using that integer as a key into a hash map. We'll write a class template, TypeMap, with a single template parameter, ValueType. It will map arbitrary types to objects of type ValueType.
#include <unordered_map>#include <atomic>template <class ValueType>class TypeMap { // Internally, we'll use a hash table to store mapping from type // IDs to the values. typedef std::unordered_map<int, ValueType> InternalMap;public: typedef typename InternalMap::iterator iterator; typedef typename InternalMap::const_iterator const_iterator; typedef typename InternalMap::value_type value_type; const_iterator begin() const { return m_map.begin(); } const_iterator end() const { return m_map.end(); } iterator begin() { return m_map.begin(); } iterator end() { return m_map.end(); } // Finds the value associated with the type "Key" in the type map. template <class Key> iterator find() { return m_map.find(getTypeId<Key>()); } // Same as above, const version template <class Key> const_iterator find() const { return m_map.find(getTypeId<Key>()); } // Associates a value with the type "Key" template <class Key> void put(ValueType &&value) { m_map[getTypeId<Key>()] = std::forward<ValueType>(value); } private: template <class Key> inline static int getTypeId() { static const int id = LastTypeId++; return id; } static std::atomic_int LastTypeId; InternalMap m_map;};template <class ValueType>std::atomic_int TypeMap<ValueType>::LastTypeId(0);With this, we can do stuff like:
TypeMap<std::string> tmap;tmap.put<int>("integers!");tmap.put<double>("doubles!");std::cout << tmap.find<int>()->second << "\n";Using Our Type Map
The following demonstrates how to use the TypeMap class template in our Entity class:
class Entity {public:// ... template <typename Component> Component* get() { auto it = m_components.find<Component>(); assert(it != m_components.end()); return static_cast<Component*>(it->second.get()); } template <typename Component> void provideComponent(std::unique_ptr<Component> &&c) { m_components.put<Component>(std::forward<std::unique_ptr<Component>>(c)); }private: TypeMap<std::unique_ptr<AbstractComponent>> m_components;//...};Conclusion
You won't have to use this technique often (if at all), but I thought it was pretty neat and worth sharing.
Like this post? Follow this blog on Twitter for more!
