定义对象 myType 后，我需要存储这些对象之间的关系。这些关系存储在矩阵中。

事先不知道元素的数量，并非所有元素都有关系(element1 可以与 element3 有关系，但可能与 5 没有关系)并且内存是一个问题。例如它可能看起来像:

element45 与:

• 具有特征 [3,1;1,4] 的元素 3
• 具有特征[1,1;1,1]的元素12
• 具有特征 [8,1;1,4] 的元素 1780

element1661 连接到:

• 具有特征 [3,1;6,4] 的元素 3
• 具有特征 [1,1;1,9] 的元素 1
• 具有特征 [8,1;1,1] 的元素 1780

拥有:

myType* element1;
myType* element2;

我想要类似的东西(正确指出元素):

my_table[element1][element2][1][2]=7;

我考虑过使用 boost 库创建一个嵌套哈希表:

boost::unordered_map<myType*, boost::unordered_map<myType*,
                std::vector<std::vector <unsigned short int> > > > my_table;

但是，即使代码编译通过，它也会崩溃(段错误，它指向计算哈希键的一行)运行一个简单的行，如:

my_table[element1][element2].resize(2);
for(int t=0; t<2; ++t)
    my_table[element1][element2][t].resize(2);

任何人都可以给我一些启发吗？这在实践上还是概念上是错误的？

欢迎使用任何其他方法解决此问题。

谢谢

最佳答案

在我看来，您的数据结构显然代表了一个图(具有连接它们的属性顶点和边)。

Furthermore when you say "These relations are stored on a matrix." you apparently mean "I visualize this as a matrix", since a true matrix representation¹ would become horrifically space-inefficient for larger number of vertices and sparse edge coverage.

Boost 有一个库: Boost Graph Library (BGL)

如果我们假设您希望能够阅读这样的图表²

graph X {
    element1; element12; element166; element1780; element3; element4; 

    element45   -- element3    [ label="[3,1;1,4]" ];
    element45   -- element12   [ label="[1,1;1,1]" ];
    element45   -- element1780 [ label="[8,1;1,4]" ];

    element1661 -- element1    [ label="[1,1;1,9]" ];
    element1661 -- element3    [ label="[3,1;6,4]" ];
    element1661 -- element1780 [ label="[8,1;1,1]" ];
}

进入 BGL 兼容模型，使用 typedef，例如:

struct Vertex { 
    std::string node_id;
};
struct Edge {
    Box box; 
};

using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Vertex, Edge>;

现在您可以利用 BGL 的全部功能:

从文件中读取图表

从 graphviz 文件中读取是一项功能³:

std::ifstream ifs("input.txt");
Graph result;

boost::dynamic_properties dp;
dp.property("node_id", boost::get(&Vertex::node_id, result));
dp.property("label",   boost::get(&Edge::box, result));

read_graphviz(ifs, result, dp);

操作图形

许多算法(dijkstra、流、生成树、连接组件等)任您使用。或者你可以混合搭配。例如，让我们过滤掉没有连接的节点:

struct Filter {
    Graph const* _g;

    bool operator()(Graph::vertex_descriptor v) const {
        return boost::size(boost::adjacent_vertices(v, *_g))>0;
    }

    template <typename T>
    bool operator()(T&&) const { return true; /*catch-all*/ }
};

using Filtered = filtered_graph<Graph, Filter, Filter>;
Filter filter { &graph };
Filtered filtered(graph, filter, filter);

让我们再次将其写入 graphviz:

boost::dynamic_properties dp;
dp.property("node_id", boost::get(&Vertex::node_id, filtered));
dp.property("label",   boost::get(&Edge::box, filtered));

write_graphviz_dp(std::cout, filtered, dp);

演示时间

完整的演示采用您的输入图:

并将其过滤成:

完整代码

Live On Coliru

// http://stackoverflow.com/questions/32279268/using-two-objects-as-hash-key-for-an-unordered-map-or-alternatives
#include <cassert>
#include <iostream>

template <typename T> struct BasicBox {
    struct Point { T x, y; };

    Point tl, br;

    friend std::ostream& operator<<(std::ostream& os, Point const& p) { return os << p.x << ',' << p.y;                 } 
    friend std::ostream& operator<<(std::ostream& os, BasicBox const& b) { return os << '[' << b.tl << ';' << b.br << ']'; } 

    friend std::istream& operator>>(std::istream& is, Point& p) {
        char comma;

        if (!(is >> p.x >> comma >> p.y) && (comma == ',')) {
            is.setstate(std::ios::failbit | is.rdstate());
        }
        return is;
    } 
    friend std::istream& operator>>(std::istream& is, BasicBox& b) {
        char lbrace, semi, rbrace;
        if (!(
            (is >> lbrace >> b.tl >> semi >> b.br >> rbrace) &&
            (lbrace == '[' && semi == ';' && rbrace == ']')
        )) {
            is.setstate(std::ios::failbit | is.rdstate());
        }
        return is;
    }
};
using Box = BasicBox<int>;

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <libs/graph/src/read_graphviz_new.cpp>

struct Vertex { 
    std::string node_id;
}; 
struct Edge {
    Box box; 
};

using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Vertex, Edge>;

#include <fstream>
#include <boost/graph/filtered_graph.hpp>

struct Filter {
    Graph const* _g;

    bool operator()(Graph::vertex_descriptor v) const {
        return boost::size(boost::adjacent_vertices(v, *_g))>0;
    }

    template <typename T>
    bool operator()(T&&) const { return true; /*catch-all*/ }
};

int main() {
    using namespace boost;

    Graph const graph = []{ 
        std::ifstream ifs("input.txt");
        Graph result;

        boost::dynamic_properties dp;
        dp.property("node_id", boost::get(&Vertex::node_id, result));
        dp.property("label",   boost::get(&Edge::box, result));

        read_graphviz(ifs, result, dp);
        return result;
    }();

    // let's do some random task. Like. You know. Like... Filter out the unconnected nodes
    using Filtered = filtered_graph<Graph, Filter, Filter>;
    Filter filter { &graph };
    Filtered filtered(graph, filter, filter);

    boost::dynamic_properties dp;
    dp.property("node_id", boost::get(&Vertex::node_id, filtered));
    dp.property("label",   boost::get(&Edge::box, filtered));

    write_graphviz_dp(std::cout, filtered, dp);
}

¹ 比如BGL's AdjacencyMatrix

² 选择的格式是 Graphviz 的 DOT 格式:http://www.graphviz.org/

³ 当然，您也可以将 Boost 序列化与 BGL 模型一起使用，因此您可以选择更紧凑的二进制表示，例如

关于c++ - 使用两个对象作为 unordered_map 或替代方案的哈希键，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/32279268/