STL自体にマップしますか？

StackOverflow https://stackoverflow.com/questions/1403501

  •  05-07-2019
  •  | 
  •  

質問

単純な隣接リストベースのグラフ構造を実装するために、イテレータのstd::mapを含むstd::vectorをそれ自体に作成したいと思います。

ただし、型宣言には困惑しています：マップのイテレータ型を取得するには、次のようにマップ型定義全体が必要なようです：

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

キータイプだけで取得できる部分的なマップイテレータタイプがあるので、フルマップを宣言できますか？

役に立ちましたか？

解決

新しい型の前方宣言を使用できます。

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

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

このインダイレクションを使用すると、コンパイラはそれを回避できるはずです。 それほどきれいではありませんが、正直なところ、自己参照を簡単に破ることはできないと思います。

他のヒント

あまりにも見苦しくありません。<！>＃8230;

これはGCC 4.0.1で動作し、Comeau strictモードで正常にコンパイルされます。

テンプレート定義は解析され、インスタンス化されるまで延期されます。コンパイラーは、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;
}

以前の回答でコンテナから派生するのは好きではなかったので、代替手段を次に示します。

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 ++ではtypedefをテンプレート化できないのは残念です。

派生イテレータタイプを使用しても問題ありません。たとえば、この構造体の要素から逆イテレータを初期化できます。

Patotoswatterの答えに加えて、テンプレート化されたマップタイプ全体を複数回参照する必要がある場合は、イテレータをサブクラス化するだけで、事前宣言は不要です。

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;

また、テンプレートとして使用できるrec_mapをエイリアスとして宣言することによるC ++ 11の更新（これまでのところ私のお気に入り）です：

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;
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top