如何将stl::map用作二维数组

Question

您能告诉我们如何将stl:map用作二维数组吗？我想像mymap[i][j]一样访问单个元素，但事先不知道i或j的值。还有其他更好的方法可以实现相同的功能吗？

- user243655

---

你使用 map 的原因是什么？ - dreamlax

不，没有特定的原因。如果有更好的选择，你可以告诉我吗？ - user243655

@ebtest，你知道i和j的值的限制吗？ - dreamlax

Answer 1

你可以这样做。

std::map<int, std::map<int, int> > mymap;

例如：

#include <map>
#include <iostream>

int main() 
{
    std::map<int, std::map<int, int> > mymap;

    mymap[9][2] = 7;
    std::cout << mymap[9][2] << std::endl;

    if (mymap.find(9) != mymap.end() && mymap[9].find(2) != mymap[9].end()) {
        std::cout << "My map contains a value for [9][2]" << std::endl;
    } else {
        std::cout << "My map does not contain a value for [9][2]" << std::endl;
    }

    return 0;
}

在标准输出上打印了7，然后是"My map contains a value for [9][2]"。

- Andrew Stein

---

谢谢您的回复。现在如何检查索引i，j处是否有元素？ - user243655

更新了我的答案，展示了如何从映射中插入和提取int元素。 - Andrew Stein

更新了示例以展示如何检查地图是否包含元素。 - Andrew Stein

@Andrew Stein：+1，但是你检查存在的方法的缺点是它不能在const限定的方法中使用（因为std::map没有operator[] const）。 - dreamlax

应该是 else { cout << "不包含 [9][2] 的值"; } 吧？ - Graphics Noob

Answer 2

一个更加符合STL标准的替代Andrew Stein方案的解决方法是简单地使用：

typedef std::map<std::pair<int, int>, int > AMapT;
AMapT mymap;
mymap[std::make_pair(2, 4)] = 10;
...
AMapT::iterator f = mymap.find(std::make_pair(3, 5));

例如，使用这种方式，您不需要链接两个调用map::find来搜索单个值。

- Carlos Scheidegger

---

我可以将其用作三维数组吗？ - user243655

值得指出的是，std::map 要求键可进行小于比较。Carlos 的解决方案之所以有效，是因为 std::pair 提供了字典序小于比较器。http://www.sgi.com/tech/stl/pair.html - rwong

ebtest，你可以这样做，但代码看起来会很丑陋：std::map<std::pair<int, std::pair<int, int> >, int>。最好使用Boost的tuple类型或者自己编写结构体和构造函数。正如rwong所指出的，你还需要一个小于比较运算符。 - Carlos Scheidegger

Answer 3

考虑使用kd树。每个分支级别将依次比较i和j的值。请参见http://en.wikipedia.org/wiki/Kd-tree。

- BenG

---

希望能提供一些使用KD树的示例:/ - knoxgon