Type to instance map

Question

I needed a class where I could store an instance of any type. The goal was an interface as follows:

class TypeMap {
    template<typename T>
    T& get();
};

Such that:

• Iff &m1 == &m2 then &m1.get<T>() == &m2.get<T>().
• The first call to m.get<T> for all m, T combinations returns a reference to a default-constructed T.
• A TypeMap going out of scope deallocates all memory that was accessible through it.

Here is my solution:

#pragma once

// Note to CR.SO: Provides the ASSERT macro.
#include "assert.hpp"
#include <boost/utility.hpp>
#include <set>

//! A map of types to values.
//!
//! Associative container which allows mapping of types to values of that
//! type.
class TypeMap : boost::noncopyable {
    template<typename T>
    class TypeMapDetail {
        struct Node : boost::noncopyable {
            Node(void* key, Node* parent) : key(key), lhs(), rhs(), parent(parent), data() {}
            void* key;
            Node* lhs;
            Node* rhs;
            Node* parent;
            T data;
        };
        Node* root;

        typedef void (*destruct_func)(void*);
        static void destroy_impl(void* p) {
            delete static_cast<Node*>(p);
        }
        destruct_func destroy;

        // No member data past this point.

        Node*& get_parent_to_this(Node* current) {
            if (!current->parent)
                return root;
            if (current->parent->lhs == current)
                return current->parent->lhs;
            else
                return current->parent->rhs;
        }

        void remove_specific(Node* current) {
            Node*& parent_to_this = get_parent_to_this(current);
            if (!current->lhs && !current->rhs) {
                parent_to_this = nullptr;
                return;
            }
            if (!current->lhs) {
                parent_to_this = current->rhs;
                current->rhs->parent = current->parent;
                return;
            }
            if (!current->rhs) {
                parent_to_this = current->lhs;
                current->lhs->parent = current->parent;
                return;
            }
            Node* replacement = current->lhs;
            while (replacement->rhs)
                replacement = replacement->rhs;
            replacement->parent->rhs = replacement->lhs;
            replacement->lhs->parent = replacement->parent;

            parent_to_this = replacement;
            current->lhs->parent = replacement;
            current->rhs->parent = replacement;
            replacement->lhs = current->lhs;
            replacement->rhs = current->rhs;
            replacement->parent = current->parent;
        }

      public:
        static TypeMapDetail map_;

        TypeMapDetail() : destroy(destroy_impl), root() {}

        // Will construct if not found.
        Node* retrieve(void* key) {
            if (!root)
                return root = new Node(key, nullptr);
            Node* current = root;
            while (true) {
                if (key < current->key) {
                    if (current->lhs)
                        current = current->lhs;
                    else
                        return current->lhs = new Node(key, current);
                } else if (key > current->key) {
                    if (current->rhs)
                        current = current->rhs;
                    else
                        return current->rhs = new Node(key, current);
                } else {
                    return current;
                }
            }
            ASSERT(!"Unreachable code.");
        }

        static T& get(TypeMap* p) {
            return map_.retrieve(p)->data;
        }

        void remove(void* key) {
            Node* current = root;
            while (current) {
                if (key < current->key) {
                    current = current->lhs;
                } else if (key > current->key) {
                    current = current->rhs;
                } else {
                    remove_specific(current);
                    destroy(current);
                    return;
                }
            }
            ASSERT(!"Tried to remove a non-existent node.");
        }

        // Kept for debugging.
        void print(Node* p) const {
            if (!p)
                return;
            std::cerr << "(";
            print(p->lhs);
            std::cerr << " " << p->data << " ";
            print(p->rhs);
            std::cerr << ")";
        }

        void print() const {
            print(root);
            std::cerr << '\n';
        }
    };

    std::set<void*> members_;
  public:
    //! Retrieve the data associated with the given type.
    template<typename T>
    T& get() {
        members_.insert(&TypeMapDetail<T>::map_);
        return TypeMapDetail<T>::get(this);
    }

    ~TypeMap() {
        struct DummyForCleaningPurposes {};
        for (auto m : members_) {
            auto map = static_cast<TypeMapDetail<DummyForCleaningPurposes>*>(m);
            map->remove(this);
        }
    }

    template<typename T>
    static void print() {
        TypeMapDetail<T>::map_.print();
    }
};

template<typename T>
TypeMap::TypeMapDetail<T> TypeMap::TypeMapDetail<T>::map_;

I know I am currently using a simple algorithm for the binary search tree which will not auto-balance the tree. I'll take a look at fixing it once I'm sure this way will work. I'll also be splitting out the functions so that they class definition is easier to read.

I'm also aware that I should add a const getter of some sort, but I have no need for it and don't want to complicate the code any further.

Questions:

• Does what I wrote satisfy the requirements? It seems to work so far, but I'd really like to know about any issues.
• What are some non-obvious cases of undefined behaviour here, and are they likely to cause issues in practice? I can see that treating Node<T>*s as Node<DummyForCleaningPurposes>* may break aliasing (could optimisations do anything nasty?), but perhaps there's more issues. (Layout of Node<T> that would make the four pointers in it fail?)
• Any stylistic issues that could be improved? Stuff that should be commented on?

Answer 1

I don't see why you use void* as a key, when that pointer is always a TypeMap*.

You could use a std::map<TypeMap*, T*> as TypeMapDetail<T>'s member. (Yes, std::less<X*> is a safe total ordering, even though operator<(X*, X*) is undefined behavior unless within a common complete object.)

Or if C++11 features and libraries are available, std::map<NodeMap*, std::unique_ptr<T>> is even easier.

I think I would approach the cleanup more like:

class TypeMap : boost::noncopyable {
    typedef void cleanup_func(TypeMap*);
    template<typename T>
    class TypeMapDetail : boost::noncopyable {
        static std::map<TypeMap*, std::unique_ptr<T> > objects;
    public:
        static T& get(TypeMap*);
        static void cleanup(TypeMap* tm) { objects.erase(tm); }
    };

    typedef std::map<std::type_index, cleanup_func> cleanup_map_type;
    cleanup_map_type cleanup_actions;

public:
    TypeMap() : cleanup_actions() {}
    ~TypeMap() {
        for (cleanup_map_type::iterator iter = cleanup_actions.begin();
             iter != cleanup_actions.end();
             ++iter) {
            iter->second(this);
        }
    }
    template <typename T>
    T& get() {
        cleanup_actions.insert(std::make_pair(
            std::cref(typeid(T)), &TypeMapDetail<T>::cleanup));
        return TypeMapDetail<T>::get(this);
    }
};

... which doesn't involve any of that static_cast undefined behavior at all. If C++11 is out, struct type_index is fairly easy to implement.