最快的是一对数据结构:
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].find(subset) != element_to_sets[element].end(); 获取元素所属的所有子集
return element_to_sets[element];
对特定子集的所有元素进行有效迭代会很好,但我相信这与其他目标冲突
return set_to_elements[subset];
所有操作都是常数时间和线性内存。内存和时间要求大约是只需要上述最后两个之一的紧凑型的两倍。
[]
如果实际上对性能敏感,则应在实际代码中进行缓存操作结果的微优化。将迭代器从一个容器存储到另一个容器,以使操作 #1 和 #2 更快,是可选的,并且可能会使它们的触摸速度更快,但我不会打扰。