¿Mapa STL sobre sí mismo?

Question

Me gustaría crear un std::map que contenga un std::vector de iteradores en sí mismo, para implementar una estructura gráfica simple basada en listas de adyacencia.

Sin embargo, la declaración de tipo me ha dejado perplejo: parece que necesita toda la definición de tipo de mapa para obtener el tipo de iterador de dicho mapa, así:

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

¿Hay algún tipo de iterador de mapa parcial que pueda obtener solo con el tipo de clave, para poder declarar el mapa completo?

Answer 1

Puede usar la declaración de reenvío de un nuevo tipo.

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

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

Con esta indirección, el compilador debería permitirte salirte con la tuya. No es tan bonito, pero sinceramente, no creo que pueda romper la auto referencia fácilmente.

Answer 2

No demasiado feo, considerando & # 8230;

Esto funciona en GCC 4.0.1 y se compila bien en modo estricto Comeau.

Las definiciones de plantilla se analizan y difieren hasta que se instancian. El compilador ni siquiera ve qué es un rec_map_iterator hasta que es hora de crear uno, momento en el que sabe cómo hacerlo; 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 > > > {};

Aquí está el programa de prueba que utilicé.

#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

No me gustó derivar de un contenedor en mi respuesta anterior, así que aquí hay una alternativa:

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

Ahora tiene que usar rec_map_gen<int>::t, rec_map_gen<int>::t::iterator, etc., pero también tiene acceso a todos los constructores de std::map. Es una lástima que C ++ no permita que los tipos de letra sean moldeados.

Usar un tipo de iterador derivado debería estar bien. Todavía puede inicializar un iterador inverso desde un elemento de esta estructura, por ejemplo.

Answer 4

Además de la respuesta de Potatoswatter, si no le importa tener que consultar el tipo de mapa con plantilla varias veces, solo necesita subclasificar el iterador y no necesita ninguna declaración previa:

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

Luego use el tipo completo:

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

Además, aquí hay una actualización (mi favorita hasta ahora) para C ++ 11 al declarar rec_map como un alias, que puede ser plantilla:

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

Esto funciona igual que la versión de Potatoswatter:

rec_map<int> my_map;