代码之家 › 专栏 › 技术社区 › genpfault

STL映射到自身?

containers map stl c++

genpfault · 技术社区 · 16 年前

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

但是,类型声明让我很困惑:似乎您需要整个映射类型定义来获取所述映射的迭代器类型,如:

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

是否有某种类型的局部映射迭代器类型,我可以只使用键类型来获取,这样我就可以声明完整的映射了?

4 回复 | 直到 9 年前

nasmorn 16 年前

可以使用新类型的正向声明。

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

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

有了这个间接的方向,编译器应该可以让您摆脱它。它不是很漂亮,但老实说,我认为你不能轻易打破自我参照。

Potatoswatter 16 年前

不太难看,考虑到_

这在GCC4.0.1中工作,并在COMEAU严格模式下编译良好。

模板定义被解析和延迟,直到它们被实例化。编译器甚至在创建一个rec-map-迭代器之前都看不到它是什么,到那时它就知道如何创建了;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;
}

Potatoswatter 16 年前

我不喜欢从我以前的答案中的容器派生,所以这里有一个替代方法:

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

使用派生迭代器类型应该可以。例如,您仍然可以从这个结构的元素初始化反向迭代器。

ValleyForge 9 年前

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

另外,这里有一个更新(我目前为止最喜欢的),通过声明ReCyMax作为别名,可以被模板化:

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;