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

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::t, rec_map_gen::t::迭代器等，但您还可以访问所有std::map的构造函数。遗憾的是 C++ 不允许将 typedef 模板化。

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

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;