How to break this circular typedef?

Question

I want to declare a couple of types (internal to the class template K and V and providing some caching behavior):

 typedef std::map< long long, typename key_to_value_type::iterator // Ooops... not declared yet > timestamp_to_key_type; typedef std::map< K, std::pair<V,typename timestamp_to_key_type::iterator> > key_to_value_type; 

Of course, this is impossible, as it is, due to the circular definition. I could hack it with void* , but I am wondering if there is any kind of forward declaration manner or other technique that will improve performance.

(Yes, I know that boost::bimap will boost::bimap problem).

Answer 1

Impossible, consider what types will be:

 timestamp_to_key_type = map< long long, key_to_value_type::iterator > = map< long long, map< K, pair< V, timestamp_to_key_type::iterator > >::iterator > = map< long long, map< K, pair< V, map< long long, map< K, pair< V, map< long long, map< K, pair < V ... 

This is not a problem with forward declarations; you are simply trying to describe a type that is recursively defined by itself. This is no different from:

 struct A { B b; }; struct B { A a; }; 

The only way around this is to lose some static type information. As you said, you can use void* , or you can try defining your own abstract, erasable interface. Your choice.

Answer 2

Break the circular definition with only one of them containing V, and the other with an iterator:

 typedef map<K, V> KVMap; typedef map<long long, typename KVMap::iterator> TSMap; 

If you need to use the key to search for a timestamp, and this timestamp is not stored in V, you can duplicate it in KVMap:

 typedef map<K, pair<V, long long> > KVMap; 

From K, you can use KVMap :: find, get the timestamp, and then use TSMap :: find and get the handle of the corresponding element (for example, erase it).