Mapa STL na siebie?

Question

Chciałbym utworzyć std::map, który zawiera std::vector z iteratorów w sobie, aby zaimplementować prostą strukturę graficzną opartą na listach przyległych.

Jednak deklaracja typ ma mnie stumped: wydaje się, trzeba całą definicję typu map, aby uzyskać typ iteracyjnej wspomnianych map, tak:

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

Czy istnieje jakiś częściowej mapy iterator typ I można uzyskać za pomocą tylko typu klucza, więc mogę zadeklarować pełną mapę?

Answer 1

Można użyć deklaracji forward nowego typu.

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

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

Przy takim ustawieniu kompilator powinien pozwolić mu uciec. To nie jest takie piękne, ale szczerze mówiąc, nie sądzę, aby można było łatwo złamać samoczynne odwoływanie się.

Answer 2

Nie zbyt brzydki, biorąc pod uwagę ...

Działa to w GCC 4.0.1 i kompiluje grzywny w Comeau trybie ścisłym.

Definicje szablonów są analizowane i odłożone, dopóki nie zostaną utworzone. Kompilator nawet nie widzi, co to jest rec_map_iterator, dopóki nie nadszedł czas, aby go stworzyć, do czasu gdy wie, jak to zrobić;

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

Oto program testowy, którego użyłem.

#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

mi się nie podoba pochodzący z pojemnika w mojej poprzedniej odpowiedzi, więc tutaj jest alternatywa:

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

Teraz trzeba użyć rec_map_gen<int>::t, rec_map_gen<int>::t::iterator, etc, ale także mieć dostęp do wszystkich std::map - konstruktorów. Szkoda, że ​​C++ nie pozwala na szablonowe szablony.

Użycie wyprowadzonego typu iteratora powinno być OK. Nadal można zainicjować odwrotny iterator z elementu tej struktury, na przykład.

Answer 4

Oprócz odpowiedzi Potatoswatter, o ile nie przeszkadza konieczności odnoszą się do całych matrycy typu map wiele razy, tylko trzeba podklasy iteracyjnej i nie wymaga żadnych wstępnych deklaracji:

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

Następnie korzystać z pełnej typ:

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

również tutaj jest aktualizacja (mój ulubiony tak daleko) dla C++ 11 deklarując rec_map jako alias, który można matrycy:

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

To działa tak samo jak w wersji Potatoswatter:

rec_map<int> my_map;