实现一个集合覆盖数据结构

Question

我想实现一个数据结构来表示抽象数据类型"集合的覆盖"。集合的元素由整数索引表示，子集也是如此。每个元素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. 其他什么？

常见操作包括：

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

- clstaudt

---

性能取决于您要在此数据结构上执行的操作。请提供有关您的用例的更多信息。 - nosid

@nosid 添加了常用操作。 - clstaudt

Answer 1

最快的（实现时间方面）方法是使用一对数据结构：

std::vector< std::unordered_set<X> > set_to_elements;
std::unordered_map< X, std::unordered_set<std::size_t> > element_to_sets;

保持两个一致的方法是使用 boost 多索引容器，这样双向操作可能更加高效。

将元素分配给子集。

set_to_elements[subset].insert(element);
element_to_sets[element].insert( subset );

从子集中删除一个元素（并可能将其移动到另一个子集）。

set_to_elements[subset].erase(element);
element_to_sets[element].erase( subset );

检查一个元素是否属于特定子集

return set_to_elements[subset].find(element) != set_to_elements[subset].end();

或者返回element_to_sets[element]中是否存在subset，获取元素所属的所有子集

return element_to_sets[element];

希望能够高效迭代遍历特定子集的所有元素，但我认为这与其他目标存在冲突。

return set_to_elements[subset];

所有操作都是常数时间和线性内存。与仅需要上述最后两个之一的紧凑型相比，内存和时间要求大约翻倍。

如果实际上对性能敏感，应在实际代码中对[]操作的结果进行缓存微调。将一个容器的迭代器存储到另一个容器中，以使操作#1和#2更快，是可选的，可能会使它们稍微快一点，但我不会费心。

- Yakk - Adam Nevraumont

Answer 2

你可以尝试阅读Matt Austern的论文分段迭代器和分层算法。他讨论了如何高效处理形式为container<container<T>>的分层数据结构。需要解决的一个问题是迭代，就好像你有一个扁平的container<T>。为此，标准库算法需要专门针对所谓的分段迭代器进行特化。 分段迭代器是一个两级数据结构，除了执行顶层迭代外，还包含一个本地迭代器以深入一级。因为这些本地迭代器本身也可以是分段迭代器，所以可以允许任意嵌套的数据结构（例如树和图）。

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

- TemplateRex