La carte STL sur elle-même?

Question

Je voudrais créer un std::map qui contient un std::vector d'itérateurs dans lui-même, pour implémenter une structure de graphe basée sur une liste d'adjacence simple.

Toutefois, la déclaration de type m'a déconcerté: il semble que vous avez besoin toute la définition du type de carte pour obtenir le type iterator de ladite carte, comme ceci:

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

Y at-il une sorte de carte partielle iterator type je peux obtenir avec juste le type de clé, afin que je puisse déclarer la carte complète?

Answer 1

Vous pouvez utiliser la déclaration avant d'un nouveau type.

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

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

Avec cette indirection, le compilateur devrait vous permettre de vous en sortir. Ce n'est pas très joli, mais honnêtement, je ne pense pas que vous puissiez briser l'autoréférence facilement.

Answer 2

Pas trop laid, considérant ...

Cela fonctionne dans GCC 4.0.1 et compile bien en mode strict Comeau.

Les définitions de modèle sont analysées et différées jusqu'à ce qu'elles soient instanciées. Le compilateur ne voit même pas ce qu'est un rec_map_iterator jusqu'à ce qu'il soit temps d'en créer un, d'ici là il sait comment le faire, 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> > > {}; 

Voici le programme de test que j'ai utilisé.

#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

ne me plaisait pas dériver d'un récipient dans ma réponse précédente alors voici une 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) {} 
    }; 
}; 

Maintenant, vous devez utiliser rec_map_gen<int>::t, rec_map_gen<int>::t::iterator, etc, mais vous avez aussi accès à tous std::map les constructeurs. C'est dommage que C++ n'autorise pas typedefs à modéliser. L'utilisation d'un type d'itérateur dérivé devrait être OK. Vous pouvez toujours initialiser un itérateur inverse à partir d'un élément de cette structure, par exemple.

Answer 4

En plus de la réponse de Potatoswatter, si vous ne me dérange pas d'avoir à se référer à l'ensemble du type de carte basé sur un modèle plusieurs fois, il vous suffit de sous-classe l'itérateur et ne pas besoin de pré-déclarations:

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

Ensuite, utilisez le type complet:

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

de plus, voici une mise à jour (mon préféré à ce jour) pour 11 C++ en déclarant rec_map comme un alias, qui peut être 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) 
    {} 
}; 

Cela fonctionne de la même que la version Potatoswatter:

rec_map<int> my_map;