Bản đồ STL trên bản thân?

Question

Tôi muốn tạo một std::map có chứa std::vector của các trình vòng lặp vào chính nó, để triển khai cấu trúc biểu đồ dựa trên danh sách kề kề đơn giản.

Tuy nhiên, việc kê khai loại có tôi bối rối: nó sẽ có vẻ bạn cần toàn bộ định nghĩa kiểu bản đồ để có được những loại iterator của nói bản đồ, như vậy:

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

Có một số loại iterator phần sơ đồ loại tôi có thể nhận được chỉ với loại khóa, vì vậy tôi có thể khai báo toàn bộ bản đồ?

Answer 1

Bạn có thể sử dụng khai báo chuyển tiếp loại mới.

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

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

Với trình biên dịch này, trình biên dịch sẽ cho phép bạn thoát khỏi nó. Nó không phải như vậy rất đẹp nhưng thành thật mà nói tôi không nghĩ rằng bạn có thể phá vỡ tự tham khảo một cách dễ dàng.

Answer 2

Không quá xấu xí, xem xét…

Điều này hoạt động trong GCC 4.0.1 và biên dịch tốt ở chế độ nghiêm ngặt Comeau.

Định nghĩa mẫu được phân tích cú pháp và hoãn lại cho đến khi chúng được khởi tạo. Trình biên dịch thậm chí không nhìn thấy những gì một rec_map_iterator là cho đến khi nó là thời gian để tạo ra một, do đó thời gian nó biết làm thế nào để làm như vậy; 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> > > {}; 

Đây là chương trình thử nghiệm tôi đã sử dụng.

#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

tôi không thích bắt nguồn từ một container trong câu trả lời trước đây của tôi vì vậy đây là một sự thay thế:

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

Bây giờ bạn phải sử dụng rec_map_gen<int>::t, rec_map_gen<int>::t::iterator, vv, nhưng bạn cũng có thể truy cập tất cả Các nhà thầu của std::map. Nó quá xấu C++ không cho phép typedefs được templated.

Sử dụng loại trình lặp có nguồn gốc phải là OK. Bạn vẫn có thể khởi tạo một trình lặp ngược lại từ một phần tử của cấu trúc này, ví dụ.

Answer 4

Ngoài câu trả lời Potatoswatter, nếu bạn không nhớ phải tham khảo toàn bộ templated loại bản đồ nhiều lần, bạn chỉ cần phải phân lớp biến lặp và không cần bất kỳ trước tờ khai:

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

Sau đó sử dụng đầy đủ các loại:

map<int, vector<rec_map_iterator<int>>> m; 

Ngoài ra, đây là một bản cập nhật (yêu thích của tôi cho đến nay) cho C++ 11 bằng cách tuyên bố rec_map như một bí danh, có thể được templated:

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

này hoạt động giống như Potatoswatter của phiên bản:

rec_map<int> my_map;