mapa STL para si mesmo?

Question

Eu gostaria de criar um std::map que contém um std::vector de iteradores em si mesmo, para implementar uma estrutura de gráfico com base em lista de adjacência simples.

No entanto, a declaração tipo tem me perplexo: parece que você precisa toda a definição do tipo de mapa para obter o tipo de iterador do referido mapa, assim:

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

Existe algum tipo de mapa parcial iterador do tipo I pode começar com apenas o tipo de chave, para que eu possa declarar o mapa completo?

Answer 1

Você pode usar a declaração para a frente de um novo tipo.

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

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

Com este engano o compilador deve deixá-lo fugir com ele. Não é muito bonito, mas honestamente, eu não acho que você pode quebrar a auto referenciar facilmente.

Answer 2

Não é muito feio, considerando ...

Isso funciona no GCC 4.0.1 e compila bem no modo estrito Comeau.

As definições de modelo são analisados ??e adiada até que eles estão instanciado. O compilador nem sequer ver o que um rec_map_iterator é até que é hora de criar um, pelo tempo que ele sabe como fazê-lo; 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 > > > {};

Aqui está o programa de teste que eu usei.

#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

Eu não como decorrente de um recipiente na minha resposta anterior, então aqui está uma 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) {}
    };
};

Agora você tem que usar rec_map_gen<int>::t, rec_map_gen<int>::t::iterator, etc, mas você também tem acesso a construtores tudo de std::map. É muito ruim C ++ não permite typedefs a ser templated.

Usando um tipo de iterador derivado deve ser OK. Ainda pode inicializar uma iteração reversa a partir de um elemento desta estrutura, por exemplo.

Answer 4

Além de resposta de Potatoswatter, se você não se importa de ter para se referir a todo o templated tipo Mapa várias vezes, você só precisa subclasse o iterador e não precisa de nenhum pré-declarações:

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

Em seguida, use o tipo completo:

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

Além disso, aqui está uma atualização (o meu favorito até agora) para C ++ 11, declarando rec_map como um alias, que pode 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)
    {}
};

Isso funciona da mesma como a versão de Potatoswatter:

rec_map<int> my_map;