使用两个对象作为哈希键的unordered_map或替代方案 [英] Using two objects as hash key for an unordered_map or alternatives

问题描述

在定义了我的对象的myType，我需要存储这些对象之间的关系。这些关系被存储在一个矩阵

Having defined my objects myType, I need to store relations between these objects. These relations are stored on a matrix.

元素的数目是<强>不提前公知的，不是所有的元素都具有一个关系（中element1可以与元素3的关系，但也可以不具有一个以5）和存储器是一个问题。例如，它可能看起来像：

The number of elements is not known in advance, not all elements have a relation (element1 can have a relation with element3, but may not have one with 5) and memory is an issue. For example it could look like:

element45与连接：

element45 is connected with:

• 元素3具有特征性[3,1; 1,4]


• element12与特征[1,1; 1,1]


• element1780与特征[8,1; 1,4]

element1661与连接：

element1661 is connected with:

• 元素3具有特征性[3,1; 6,4]


• 中element1与特征[1,1; 1,9]


• element1780与特征[8,1; 1,1]

有：

myType* element1;
myType* element2;

我想有这样的事情（正确指出的元素）：

I would like to have something like (properly pointed the elements):

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

我也曾想过使用Boost库创建嵌套哈希表：

I have thought on creating a nested hash table using boost library:

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

然而，即使code编译，它崩溃（段错误，它指向一个行计算哈希键）运行一个简单的一行：

However, even if the code compiles, it crashes (Segmentation fault, it points to a line calculating the hash key) running a simple line like:

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

任何人都可以给我一些有关此轻？这是实际或概念错了？

Anyone can give me some light about this? Is this practically or conceptually wrong?

任何其他办法解决这个问题是值得欢迎的。

Any other approach to this problem is welcome.

感谢您

推荐答案

马上蝙蝠似乎很明显，我认为你的数据结构重新present图（带归因顶点和边连接它们）。

Right off the bat it seems obvious to me that your datastructure represent a graph (with attributed vertices and edges connecting them).

此外，当你说的这些关系都存储在一个矩阵。的你显然意味着我想象这是一个矩阵，因为真正的矩阵重新$ P $psentation¹将成为惊人，节省空间低效的较大数量的顶点和稀疏的边缘覆盖。

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图库（BGL）

Boost has a library for that: Boost Graph Library (BGL)

如果我们假设你想能够阅读图表like²

If we assume you want to be able to read a graph like²

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像例如：

Into a BGL compatible model, use typedefs like e.g.:

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

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

现在你利用BGL的全部设施：

Now you leverage the full facilities of the BGL:

从graphviz的文件中读取一个feature³：

Reading from a graphviz file is a feature³:

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算法，流量，生成树，连接部件等）为您处理。或者你可以混合和匹配。例如，让我们过滤掉没有连接出来的节点：

Manipulating the graph

The many algorithms (dijkstra, flow, spanning trees, connected components, etc.) are at your disposal. Or you can mix and match. For example let's filter the nodes that have no connections out:

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的：

Let's write it to graphviz again:

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

演示时间

完整的演示需要你输入图：

DEMO TIME

The full demo takes your input graph:

和过滤它变成：

<大骨节病> 住在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的 AdjacencyMatrix

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

² the format chosen being Graphviz' DOT format: http://www.graphviz.org/

³当然，你也可以使用升压序列化与BGL车型，所以你可以选择一个更紧凑的二进制重新presentation例如

³ Of course you can also use Boost Serialization with BGL models, so you can opt for a more compact binary representation e.g.

这篇关于使用两个对象作为哈希键的unordered_map或替代方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！