¿Mapa de 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 de gráficos simple basada en listas de adyacencia.

Sin embargo, la declaración de tipo me tiene perplejo: parecería que necesita toda la definición del 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; 

¿Existe algún tipo de mapa iterador parcial tipo I puede obtener solo el tipo de clave, ¿así puedo declarar el mapa completo?

Answer 1

Puede usar la declaración directa de un tipo nuevo.

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

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

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

Answer 2

No demasiado feo, teniendo en cuenta ...

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

Las definiciones de plantilla se analizan y difieren hasta que se crean instancias. El compilador ni siquiera ve qué es un rec_map_iterator hasta que es hora de crear uno, y para entonces 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

que no me gusta que deriva de un contenedor en mi respuesta anterior así que aquí tiene 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 usted tiene que utilizar rec_map_gen<int>::t, rec_map_gen<int>::t::iterator, etc, pero también tiene acceso a toda std::map 's constructores. Es una lástima que C++ no permita que los typedefs sean modelados.

El uso de un tipo de iterador derivado debe ser correcto. Aún puede inicializar un iterador inverso desde un elemento de esta estructura, por ejemplo.

Answer 4

Además de la respuesta de Potatoswatter, si no te importa tener que referirse a los de plantilla de tipo de mapa entero varias veces, sólo es necesario subclase el iterador y no necesita ningún pre-declaraciones:

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

continuación, utilizar el tipo completo:

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

Además, aquí es una actualización (mi favorito hasta ahora) para C++ 11 declarando rec_map como un alias, que puede ser 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) 
    {} 
}; 

Esto funciona igual que la versión de Potatoswatter:

rec_map<int> my_map;