data-structures - 是否有双向多映射持久数据结构？

Question

换句话说，我们能否有效地对持久数据结构中的多对多关系进行建模？

建议使用一对单向多映射。但是，我不确定这对于在持久数据结构中的删除效果如何。假设我们有键 1..4 到值 "1".."4"并且假设它们每个都引用所有其他的，所以我们有两个在两个方向上看起来都非常相似的 map :

{1 => ["2","3","4"], 2 => ["1","3","4"], ...}
{"1"=> [2,3,4], "2"=> [1,3,4], ...}

现在我们要从系统中完全删除项目 1。这需要更改第一个映射中的一个节点，但需要更改第二个映射中的 n-1 个节点。对于数以千计的 n(在我考虑这个的情况下很可能)，那不是相当昂贵吗？或者是为处理这种类型的变化而优化的多图？这是一个病理性案例，但仍然......

Quadtrees 似乎是一个迷人的想法。我要再考虑一下。

Answer 1

施工证明:bimap Haskell 的软件包。

A Bimap is essentially a bijection between subsets of its two argument types

以及它是如何实现的？

data Bimap a b = MkBimap !(M.Map a b) !(M.Map b a)

作为一对单向图。