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

If you just need to iterator over all elements, and it is not required to loop over a specific dimension, then you could use a simple pair as key for your unordered_map, like this:

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

(notice I used STL instead of Boost, unordered_map is now also part of the standard STL).

Getting a specific value is simply writing:

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

(or use find if you're not sure if that value is in your map).

To iterate, just iterate over the unordered 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;
   }

To make it a bit more readable, I prefer getting the coordinates first from the iterator, like this:

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

If you have more than 2 dimensions, use std::tuple, or simply write your own Coordinates class to be used as key for the map.

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