使用两个对象作为 unordered_map 或替代品的哈希键

2021-12-24 00:00:00 hash c++ boost

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

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

element45 与:

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

element1661 与:

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

有:

myType* element1;myType* element2;

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

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

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

boost::unordered_map>>>我的表；

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

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

任何人都可以给我一些关于这个的信息吗?这实际上或概念上是错误的吗?

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

谢谢

解决方案

马上就对我来说很明显你的数据结构代表了一个图(用属性顶点和边连接它们).

<块引用>

此外，当您说这些关系存储在矩阵中."时，您显然是指我将其可视化为矩阵"，因为真正的矩阵表示1对于更大的数字会变得非常低效顶点和稀疏边缘覆盖.

Boost 有一个库:

并将其过滤为:

完整代码

生活在 Coliru

//http://stackoverflow.com/questions/32279268/using-two-objects-as-hash-key-for-an-unordered-map-or-alternatives#include <cassert>#include 模板 结构基本框{struct Point { T x, y;};点 tl, br;朋友 std::ostream&运算符<<(std::ostream& os, Point const& p) { return os <<p.x<<','<<p.y;}朋友 std::ostream&运算符<<(std::ostream& os, BasicBox const& b) { return os <<'[' <<b.tl＜＜';'<<b.br<<']';}朋友 std::istream&运算符>>(std::istream&is,Point&p){字符逗号;if (!(is >> p.x >> 逗号 >> p.y) && (comma == ',')) {is.setstate(std::ios::failbit | is.rdstate());}回报是；}朋友 std::istream&运算符>>(std::istream&is, BasicBox& b) {字符 lbrace, 半, rbrace;如果 (！((是 >> lbrace >> b.tl >> semi >> b.br >> rbrace) &&(lbrace == '[' && semi == ';' && rbrace == ']'))){is.setstate(std::ios::failbit | is.rdstate());}回报是；}};使用 Box = BasicBox;#include #include #include 结构顶点{std::string node_id;};结构边{盒子盒子；};使用 Graph = boost::adjacency_list;#include <fstream>#include 结构过滤器{图 const* _g;bool operator()(Graph::vertex_descriptor v) const {返回 boost::size(boost::adjacent_vertices(v, *_g))>0;}模板 bool operator()(T&&) const { return true;/* 一网打尽*/}};int main() {使用命名空间提升；图常量图 = []{std::ifstream ifs("input.txt");图形结果；boost::dynamic_properties dp;dp.property("node_id", boost::get(&Vertex::node_id, result));dp.property("label", boost::get(&Edge::box, result));read_graphviz(如果，结果，dp)；返回结果；}();//让我们做一些随机任务.喜欢.你懂.像...过滤掉未连接的节点使用 Filtered = filters_graph;过滤器 filter { &graph };过滤过滤(图形，过滤器，过滤器)；boost::dynamic_properties dp;dp.property("node_id", boost::get(&Vertex::node_id, 过滤));dp.property("label", boost::get(&Edge::box,filtered));write_graphviz_dp(std::cout, 过滤, dp);}

<小时>

1 像例如BGL 的AdjacencyMatrix

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

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

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

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 is connected with:

element3 with characteristic [3,1;1,4]
element12 with characteristic [1,1;1,1]
element1780 with characteristic [8,1;1,4]

element1661 is connected with:

element3 with characteristic [3,1;6,4]
element1 with characteristic [1,1;1,9]
element1780 with characteristic [8,1;1,1]

Having:

myType* element1;
myType* element2;

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

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

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;

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.

Thank you

解决方案

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

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

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

If we assume you want to be able to read a graph like2

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

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

Now you leverage the full facilities of the BGL:

Reading the graph from a file

Reading from a graphviz file is a feature3:

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

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

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:

And filters it into:

Full Code

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

1 like e.g. BGL's AdjacencyMatrix

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

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

相关文章