二維無序圖

Question

typedef boost::unordered_map<int, void*> OneDimentionalNodes; 
typedef boost::unordered_map<int, OneDimentionalNodes> TwoDimentionalNodes; 

TwoDimentionalNodes nodes; 

這個有效嗎？

我不使用任何散列函數，因爲unordered_maps'的鍵是單個整數。它會編譯，但是當我像這樣迭代它時，它試圖訪問this-> hash_function（）（k）時崩潰。

for (TwoDimentionalNodes::iterator it= nodes.begin(); it != nodes.end() ; ++it) 
{ 
    for(OneDimentionalNodes::iterator it2 = nodes[it->first].begin(); it2 != nodes[it->first].end() ; ++it2) 
    { 
    // do stuff 
    } 
} 

我也開放給其他容器用

• O（1）訪問
• O（n）的迭代
• 稀疏

Answer 1

如果你只需要迭代器對所有元素，它不是在一個特定的空間需要循環，那麼你可以使用一個簡單的對作爲關鍵的unordered_map，像這樣：

typedef std::pair<int,int> Coordinates; 
typedef std::unordered_map<Coordinates,void *> TwoDimensionalNodes; 

（請注意，我用STL的替代加速，unordered_map現在也是標準STL的一部分）。

獲得一個特定的值，簡單地寫：

twoDimensionalNodes[std::make_pair(x,y)] 

（或使用發現，如果你不知道這值是在你的地圖）。

要重複，只是遍歷無序地圖：

for (auto it=twoDimensionalNodes.begin();it!=twoDimensionalNodes.end();++it) 
    { 
    std::cout << "x=" << it->first.first; 
    std::cout << "y=" << it->first.second; 
    std::cout << "value=" << it->second; 
    } 

爲了使它有點更具可讀性，我更喜歡從迭代器首先得到的座標，就像這樣：

for (auto it=twoDimensionalNodes.begin();it!=twoDimensionalNodes.end();++it) 
    { 
    Coordinates &coordinates = it->first; 
    std::cout << "x=" << coordinates.first; 
    std::cout << "y=" << coordinates.second; 
    std::cout << "value=" << it->second; 
    } 

如果你有2個以上的維度，使用std :: tuple，或者直接編寫自己的Coordinates類作爲地圖的關鍵字。

Answer 2

使用std::unordered_map從<unordered_map>。 嘗試特化std散列類這樣：

namespace std 
{ 
    template<typename T> 
    struct hash<void*> 
    { 
     std::size_t operator()(void * ptr) const 
     { 
      return (std::size_t)ptr; 
     } 
    }; 
}