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

考虑到<！>＃8230;

，不要太难看

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

Answer 3

我不喜欢在我之前的回答中从容器派生，所以这里有另一种选择：

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 ++不允许对模板进行模板化。

使用派生的迭代器类型应该没问题。例如，您仍然可以从此结构的元素初始化反向迭代器。

Answer 4

除了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;