STL карту на себя? - PullRequest
Новая
       31

STL карту на себя?

12 голосов
/ 10 сентября 2009

Я хотел бы создать std::map, который содержит в себе std::vector итераторов, чтобы реализовать простую структуру графа на основе списка смежности.

Однако объявление типа поставило меня в тупик: может показаться, что вам нужно полное определение типа карты, чтобы получить тип итератора для указанной карты, например: 

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

Есть ли какой-то тип итератора частичной карты, который я могу получить только с помощью типа ключа, чтобы я мог объявить полную карту?

Ответы [ 4 ]

14 голосов
/ 10 сентября 2009

Вы можете использовать предварительное объявление нового типа. 

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

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

С этим косвенным указанием компилятор должен позволить вам сойти с рук. Это не очень красиво, но, честно говоря, я не думаю, что вы можете легко сломать ссылку на себя.

5 голосов
/ 10 сентября 2009

Не так страшно, учитывая…

Это работает в GCC 4.0.1 и прекрасно компилируется в строгом режиме Comeau.

Определения шаблонов анализируются и откладываются до момента их создания. Компилятор даже не видит, что такое rec_map_iterator, пока не пришло время его создать, и к тому времени он уже знает, как это сделать; 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 > > > {};

Вот тестовая программа, которую я использовал. 

#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;
}
2 голосов
/ 27 января 2017

В дополнение к ответу Potatoswatter, если вы не возражаете против необходимости ссылаться на весь шаблонный тип карты несколько раз, вам нужно только создать подкласс итератора и не требовать каких-либо предварительных объявлений: 

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

Тогда используйте полный тип: 

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

Кроме того, вот обновление (мое любимое на данный момент) для C ++ 11, объявив rec_map в качестве псевдонима, который можно задавать в качестве шаблона: 

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

Это работает так же, как версия Potatoswatter: 

rec_map<int> my_map;
2 голосов
/ 10 сентября 2009

Мне не понравилось получение из контейнера в моем предыдущем ответе, так что вот альтернатива: 

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

Теперь вы должны использовать rec_map_gen<int>::t, rec_map_gen<int>::t::iterator и т. Д., Но у вас также есть доступ ко всем конструкторам std::map. Жаль, что C ++ не позволяет шаблонизировать шаблоны.

Использование производного типа итератора должно быть в порядке. Вы все еще можете инициализировать обратный итератор из элемента этой структуры, например.

...