STL映射到自身？

Question

我想创建一个std::map包含std::vector迭代器的自身,以实现一个简单的基于邻接列表的图形结构.

但是,类型声明让我感到难过:看起来你需要整个地图类型定义来获取所述地图的迭代器类型,如下所示:

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

是否有某种部分地图迭代器类型我只能使用键类型,所以我可以声明完整的地图？

Answer 1

您可以使用新类型的前向声明.

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

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

通过这种间接,编译器应该让你逃脱它.它不是那么漂亮,但说实话,我认为你不能轻易打破自我引用.

Answer 2

考虑到......不是太难看

这适用于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;
}