c++ - 实现集合覆盖数据结构

Question

我想实现一个表示抽象数据类型的数据结构 "cover of a set" .集合的元素由整数索引表示，子集也是如此。每个元素 uint64_t e被分配给至少一个但可能是多个子集 uint64_t s .这可以通过将子集索引存储在 std::vector 中来实现。 .任何元素将被分配到的子集的数量通常远小于元素的总数。

性能(时间和内存)很重要，那么您会推荐哪种实现方式？

1. std::vector<std::vector<uint64_t>>
2. std::vector<std::unordered_set<uint64_t>>
3. std::vector<std::set<uint64_t>>
4. 还有什么事吗？

常用操作包括:

• 将元素分配给子集
• 从一个子集中删除一个元素(并可能将其移动到另一个子集中)
• 检查一个元素是否是特定子集的成员
• 获取元素所属的所有子集
• 对特定子集的所有元素进行高效迭代会很好，但我认为这与其他目标有冲突

Answer 1

您可以尝试阅读论文 Segmented Iterators and Hierarchial Algorithms作者:马特·奥斯汀。他讨论了如何高效地处理 container<container<T>> 形式的分层数据结构 .需要解决的一个问题是迭代，就好像你有一个平面 container<T> .为此，标准库算法需要专门用于所谓的分段迭代器。

分段迭代器是一种两级数据结构，除了执行顶层迭代外，它还包含一个局部迭代器以更深一层。因为这些局部迭代器本身也可以是分段迭代器，这就允许任意嵌套数据结构(比如树和图)。

离散集合的集合覆盖可以构造为 std::vector<std::set<T>> .将 STL 算法应用于这样的容器要么很麻烦，要么需要分段迭代器和分层算法。不幸的是，标准库和 Boost 都没有真正实现这一点，因此您需要做一些工作。