STL-Karte auf sich?

Question

Ich würde gerne eine std::map enthält std::vector von Iteratoren in sich selber, um eine einfache Implementierung Nähe list-based graph Struktur.

Jedoch, die Typ-Deklaration hat mich ratlos:es würde scheinen, müssen Sie die gesamte Karte-Typ-definition, um die iterator-Typ sagte Karte, wie so:

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

Gibt es irgendeine Art von partial-map-iterator-Typ ich kann nur mit dem Schlüssel-Typ, so kann ich erklären, die volle Karte?

Answer 1

Sie könnten Deklaration eines neuen Typs verwenden vorwärts.

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

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

Mit diesem indirection der Compiler sollten Sie mit ihm durchgehen lassen. Es ist nicht so sehr hübsch, aber ehrlich gesagt ich glaube nicht, dass Sie das selbst leicht Referenzierung brechen können.

Answer 2

Nicht zu hässlich, wenn man bedenkt ...

Dies funktioniert in GCC 4.0.1 kompiliert und fein in Comeau Strict-Modus.

Die Template-Definitionen werden analysiert und verschoben, bis sie instanziiert sind. Der Compiler nicht einmal sehen, was ein rec_map_iterator ist, bis es Zeit ist, zu erstellen, zu welcher Zeit er weiß, wie dies zu tun, 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 > > > {};

Hier ist das Testprogramm I verwendet wird.

#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

ich nicht aus einem Behälter in meiner vorherigen Antwort ableiten mochte so ist hier eine 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) {}
    };
};

Nun müssen Sie rec_map_gen<int>::t verwenden, rec_map_gen<int>::t::iterator, etc, aber Sie haben auch Zugriff auf alle Konstrukteure des std::map. Es ist schade, C ++ nicht erlaubt typedefs Templat werden.

Mit einem Iteratortyp abgeleitet sollte in Ordnung sein. Sie können immer noch einen Reverse-Iterator aus einem Elemente dieser Struktur, zum Beispiel initialisieren.

Answer 4

Neben Potatoswatter Antwort, wenn Sie sich nicht kümmern zu müssen, beziehen sich auf die gesamte Vorlagen-map-Typ, mehrere Male, Sie müssen nur eine Unterklasse der iterator und nicht brauchen jede pre-Erklärungen:

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

Verwenden Sie dann die volle Typ:

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

Auch hier ist eine Aktualisierung (mein Favorit bisher) für C++11 durch die Erklärung rec_map als ein alias, die Vorlagen:

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

Dies funktioniert genauso wie Potatoswatter version:

rec_map<int> my_map;