STL carte sur lui-même?

Question

J'aimerais créer un std::map qui contient un std::vector d'itérateurs en lui-même, afin de mettre en œuvre une structure de graphique simple basée sur une liste de contiguïté.

Cependant, la déclaration de type m'a laissé perplexe: il semblerait que vous ayez besoin de toute la définition du type de carte pour obtenir le type d'itérateur de cette carte, comme suit:

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

Existe-t-il un type d'itérateur de carte partiel que je peux obtenir uniquement avec le type de clé afin de pouvoir déclarer la carte complète?

Answer 1

Vous pouvez utiliser la déclaration anticipée 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 beau, mais honnêtement, je ne pense pas que vous puissiez briser le référencement de soi-même facilement.

Answer 2

Pas trop moche, vu & # 8230;

Ceci fonctionne dans GCC 4.0.1 et compile très bien en mode strict Comeau.

Les définitions de modèles sont analysées et différées jusqu'à leur instanciation. Le compilateur ne voit même pas ce qu'est un rec_map_iterator tant qu'il n'est pas temps d'en créer un. Il ne sait pas 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

Je n'ai pas aimé dériver d'un conteneur dans ma réponse précédente. Voici donc 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) {}
    };
};

Vous devez maintenant utiliser rec_map_gen<int>::t, rec_map_gen<int>::t::iterator, etc., mais vous avez également accès à tous les constructeurs de std::map. C'est dommage que C ++ n'autorise pas la création de modèles de types.

L'utilisation d'un type d'itérateur dérivé devrait être correcte. 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 voulez bien faire référence au type de carte complet basé sur un modèle plusieurs fois, il vous suffit de sous-classer l'itérateur et de ne nécessiter aucune déclaration préalable:

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

Utilisez ensuite le type complet:

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

En outre, voici une mise à jour (ma préférée jusqu'à présent) pour C ++ 11 en déclarant rec_map comme un alias pouvant être modélisé:

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 manière que la version de Potatoswatter:

rec_map<int> my_map;