我想实现一个数据结构来表示抽象数据类型"集合的覆盖"。集合的元素由整数索引表示,子集也是如此。每个元素
uint64_t e
至少分配给一个但可能多个子集uint64_t s
。可以通过在std::vector
中存储子集索引来实现这一点。任何元素将被分配到的子集数量通常比元素总数要小得多。
性能(时间和内存)很重要,你会推荐哪种实现方式?
std::vector<std::vector<uint64_t>>
std::vector<std::unordered_set<uint64_t>>
std::vector<std::set<uint64_t>>
- 其他什么?
常见操作包括:
- 将元素分配给子集
- 从子集中删除元素(可能将其移动到另一个子集)
- 检查元素是否是特定子集的成员
- 获取所有包含元素的子集
- 高效地迭代特定子集的所有元素会很好,但我认为这与其他目标冲突