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;
}

Answer 3

I didn't like deriving from a container in my previous answer so here's an alternative:

template< class key >
struct rec_map_gen {
    struct i;
    typedef map< key, vector< i > > t;
    struct i : t::iterator {
        i( typename t::iterator v )
        : t::iterator(v) {}
    };
};

Now you have to use rec_map_gen<int>::t, rec_map_gen<int>::t::iterator, etc, but you also have access to all std::map's constructors. It's too bad C++ doesn't allow typedefs to be templated.

Using a derived iterator type should be OK. You can still initialize a reverse iterator from an element of this structure, for example.

Answer 4

In addition to Potatoswatter's answer, if you don't mind having to refer to the entire templated map type multiple times, you only need to subclass the iterator and don't need any pre-declarations:

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

Then use the full type:

map<int, vector<rec_map_iterator<int>>> m;

Also, here's an update (my favorite so far) for C++11 by declaring rec_map as an alias, which can be templated:

template<class key>
struct rec_map_iterator;

template<class key>
using rec_map = map<key, vector<rec_map_iterator<key>>>;

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)
    {}
};

This works the same as Potatoswatter's version:

rec_map<int> my_map;