STL map onto itself?

Question

I'd like to create a std::map that contains a std::vector of iterators into itself, to implement a simple adjacency list-based graph structure.

However, the type declaration has me stumped: it would seem you need the entire map type definition to get the iterator type of said map, like so:

map< int, Something >::iterator MyMap_it;  // what should Something be?
map< int, vector<MyMap_it> > MyMap_t;

Is there some sort of partial map iterator type I can get with just the key type, so I can declare the full map?

Answer 1

You could use forward declaration of a new type.

class MapItContainers;
typedef map<int, MapItContainers>::iterator MyMap_it;

class MapItContainers
{
public:
 vector<MyMap_it> vec;
};

With this indirection the compiler should let you get away with it. It is not so very pretty but honestly I don't think you can break the self referencing easily.

Answer 2

Not too ugly, considering…

This works in GCC 4.0.1 and compiles fine in Comeau strict mode.

The template definitions are parsed and deferred until they're instantiated. The compiler doesn't even see what a rec_map_iterator is until it's time to create one, by which time it knows how to do so ;v) .

template< class key >
struct rec_map;

template< class key >
struct rec_map_iterator : rec_map< key >::iterator {
    rec_map_iterator( typename rec_map< key >::iterator i)
    : rec_map< key >::iterator(i) {}
};

template< class key >
struct rec_map : map< key, vector< rec_map_iterator< key > > > {};

Here's the test program I used.

#include <iostream>
#include <map>
#include <vector>

using namespace std;

template< class key >
struct rec_map;

template< class key >
struct rec_map_iterator : rec_map< key >::iterator {
    rec_map_iterator( typename rec_map< key >::iterator i)
    : rec_map< key >::iterator(i) {}
};

template< class key >
struct rec_map : map< key, vector< rec_map_iterator< key > > > {};

int main( int argc, char ** argv ) {
    rec_map< int > my_map;

    my_map[4];
    my_map[6].push_back( my_map.begin() );

    cerr << my_map[6].front()->first << endl;

    return 0;
}