Design pattern to allow the efficient deletion of an element from multiple containers in C++

Question

Say for example, an element is referenced from multiple maps, e.g. a map name to element, a map address to element and a map age to element. Now one looks up the element for example via name, and now wishes to delete it from all three maps?

Several solutions come to mind:

1) The most straight forward. Look up the element in the name to element map, then search both other maps to find the element in those, then remove the element entry in all three.

2) Store weak pointers in all three maps. Store a shared pointer somewhere, at best maybe even in the element itself. After finding the element in one map, delete the element. When trying to access the element from the other maps and realizing the weak pointers can't be converted to shared pointers, remove the entry.

3) Use intrusive maps. This has the advantage that one does not need to search the remaining maps to find the element in those. However, as the object is stored in several maps, the element itself can't be made intrusive - rather the element might need to have a member implementing the hooks.

4) Others?

Is there a very clean nice solution to this? I have been bumping into this problem a few times...

A few thoughts. Solution 1 is typically the one that ends up being implemented naturally as a project grows. If the element itself has the key information of the other maps, and other containers are maps, this is probably quite acceptable. However, if the keys are missing, or if the container is e.g. a list, it can become very slow. Solution 2 depends on the implementation of weak pointers, and might also end up being quite slow. Solution 3 seems best, but maybe somewhat complicated?

Answer 1

Never found anything to replace solution 1. I ended up with shared_pointers and delete flags in a delete function (e.g. DeleteFromMaps(bool map1, bool map2, bool map3)) in the object. The call from eg map2 then becomes e.g.

it->DeleteFromMaps(true,false,true);
erase(it);

Answer 2

boost::multi_index is designed specially for such case.

Answer 3

Sounds like you haven't decided what is managing the lifetime of the object - that comes first. Once you know that then use the observer pattern. When the object is to be destroyed, the objected magaing its lifetime notifies all the objects that wrap the maps holding the pointers, then destroys the object.

The observers can either implement a common interface like this:

class ObjectLifetimeMgr
{
public:
    CauseObjDeletion()
    {
        /.. notify all observers ../
    }
private:
    list<IObserver*> observers;
};

class IObserver
{
public:
    virtual void ObjectDestroyed( Obj* );
};

class ConcreteObserver
{
public:
    void ObjectDestroyed( Obj* )
    {
        /.. delete Obj from map ../
    }
};

Or to do a really lovely job you could implement a c++ delegate, this frees the observers from a common base class and simply allows them to register a callback using a member method