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

Question

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

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

element45与以下内容相关联:

• element3具有特征[3,1; 1,4]
• element12具有特征[1,1; 1,1]
• element1780具有特征[8,1; 1,4]

element1661连接到:

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

有:

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;

但是,即使代码编译,它也会崩溃(Segmentation fault,它指向计算哈希键的一行),运行一条简单的行,如:

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

任何人都能给我一些关于这个的消息吗？这实际上或概念上是错误的吗？

欢迎使用任何其他方法来处理这个问题.

谢谢

Answer 1

对我而言,对我而言,您的数据结构代表一个图形(具有连接它们的属性顶点和边缘)似乎很明显.

此外,当你说" 这些关系存储在一个矩阵上 "时,你显然意味着"我把它想象成一个矩阵",因为对于大量的顶点和稀疏的边缘覆盖,真正的矩阵表示¹将变得非常低效.

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

¹喜欢例如BGLAdjacencyMatrix

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

³当然,您也可以使用BGL模型的Boost Serialization,因此您可以选择更紧凑的二进制表示,例如