Mappa STL su se stesso?

Question

Vorrei creare un std::map che contiene un std::vector di iteratori in se stesso, per implementare una semplice struttura grafica basata sull'elenco di adiacenza.

Tuttavia, la dichiarazione del tipo mi ha lasciato perplesso: sembrerebbe che tu abbia bisogno dell'intera definizione del tipo di mappa per ottenere il tipo di iteratore di detta mappa, in questo modo:

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

Esiste una sorta di tipo di iteratore di mappa parziale che posso ottenere solo con il tipo di chiave, quindi posso dichiarare la mappa completa?

Answer 1

È possibile utilizzare la dichiarazione diretta di un nuovo tipo.

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

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

Con questa indiretta il compilatore dovrebbe lasciarti andare via. Non è così bello ma onestamente non penso che tu possa rompere facilmente l'auto-referenziamento.

Answer 2

Non troppo brutto, considerando & # 8230;

Funziona in GCC 4.0.1 e si compila bene in modalità rigorosa Comeau.

Le definizioni del modello vengono analizzate e rinviate fino a quando non vengono istanziate. Il compilatore non vede nemmeno cosa sia un rec_map_iterator fino a quando non è il momento di crearne uno, a quel punto sa come farlo; 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 > > > {};

Ecco il programma di test che ho usato.

#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

Non mi piaceva derivare da un contenitore nella mia risposta precedente, quindi ecco un'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) {}
    };
};

Ora devi usare rec_map_gen<int>::t, rec_map_gen<int>::t::iterator, ecc., ma hai anche accesso a tutti i costruttori di std::map. È un peccato che C ++ non consenta di creare modelli di typedef.

L'uso di un tipo di iteratore derivato dovrebbe essere OK. Ad esempio, puoi ancora inizializzare un iteratore inverso da un elemento di questa struttura.

Answer 4

Oltre alla risposta di Potatoswatter, se non ti dispiace dover fare riferimento all'intero tipo di mappa modello più volte, devi solo sottoclassare l'iteratore e non hai bisogno di pre-dichiarazioni:

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

Quindi usa il tipo completo:

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

Inoltre, ecco un aggiornamento (il mio preferito finora) per C ++ 11 dichiarando rec_map come alias, che può essere modellato:

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

Funziona allo stesso modo della versione di Potatoswatter:

rec_map<int> my_map;