c++ - 二维 unordered_map

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 而不是 Boost，unordered_map 现在也是标准 STL 的一部分)。

获取特定值就是简单地写:

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

(如果您不确定该值是否在您的 map 中，则使用查找)。

要迭代，只需迭代无序映射:

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 类用作 map 的键。