STL 자체에 맵이 있습니까?

Question

나는 만들고 싶다 std::map 여기에는 a가 포함되어 있습니다 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 Strict 모드에서 잘 컴파일합니다.

템플릿 정의는 인스턴스화 될 때까지 구문 분석 및 연기됩니다. 컴파일러는 REC_MAP_ITERATOR를 만들 때까지 REC_MAP_ITERATOR가 무엇인지 알 수 없습니다.

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 ++가 TypEdefs를 템플릿으로 만드는 것은 너무 나쁘다.

파생 된 반복자 유형을 사용하는 것은 괜찮아야합니다. 예를 들어이 구조의 요소에서 리버스 반복기를 초기화 할 수 있습니다.

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;

또한 여기에 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;