C++ 2D地图？类似于2D数组吗？

Question

能否制作一个二维地图？

像这样：

map< int, int, string> testMap;

填写这些值的方式如下：

testMap[1][3] = "Hello";

感谢您的时间 :)

- mrg95

Answer 1

是的，在 std::map 中使用 std::pair。

std::map< std::pair<int, int>, string> testMap;
testMap[std::make_pair(1,3)] = "Hello";

- andre

---

有趣。通常我可能会使用这个，但是我实际上正在使用Qt Creator，所以我不认为它们有标准库。他们可能有类似的东西，但我不确定。例如，我使用QMap而不是std :: map。好在语法是相同的。 - mrg95

Qt Creator只是一款IDE（集成开发环境），并不是一个编译器或C++的不同形式。因此，即使在处理定义QMap的Qt库时，您仍然可以在Qt Creator中编写标准的C++代码（例如使用std::map），并且可以很好地进行编译。 - user2530166

这将比RyanMcK的解决方案更加高效。 - Cory Nelson

这样做会更有效率吗？ - mrg95

一个 std::pair 不像添加一个额外的 std::map 那么重。使用一个 map 嵌套另一个 map 进行查找的时间复杂度是 O(Lg(n)*Lg(n))，而仅使用一个 pair 只需要 O(Lg(n)) 的时间复杂度。 - andre

这绝对不是 O(lg(n)*lg(n))，而是 O(lg(n) + lg(n)) 或简写为 O(lg(n))。第一个映射查找需要 lg(n) 时间，第二个也需要 lg(n) 时间。当然，这是假设“数组”是正方形的情况下。这可能应该被拆分为 m 和 n，但它仍然可以以类似的方式简化。 - michaelgulak

Answer 2

你可以嵌套两个地图：

#include <iostream>
#include <map>
#include <string>

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

    m[1][3] = "Hello";

    std::cout << m[1][3] << std::endl;

    return 0;
}

- user2530166

Answer 3

如果有帮助的话，这里提供了一个基于andre答案构建的类的代码，它允许通过像常规2D数组一样的方括号运算符进行访问：

template<typename T>
class Graph {
/*
    Generic Graph ADT that uses a map for large, sparse graphs which can be
    accessed like an arbitrarily-sized 2d array in logarithmic time.
*/
private:
    typedef std::map<std::pair<size_t, size_t>, T> graph_type;
    graph_type graph;
    class SrcVertex {
    private:
        graph_type& graph;
        size_t vert_src;
    public:
        SrcVertex(graph_type& graph): graph(graph) {}
        T& operator[](size_t vert_dst) {
            return graph[std::make_pair(vert_src, vert_dst)];
        }
        void set_vert_src(size_t vert_src) {
            this->vert_src = vert_src;
        }
    } src_vertex_proxy;
public:
    Graph(): src_vertex_proxy(graph) {}
    SrcVertex& operator[](size_t vert_src) {
        src_vertex_proxy.set_vert_src(vert_src);
        return src_vertex_proxy;
    }
};

- Paul Nickerson