二维无序图

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