从一组集合中查找集合子集的最佳方法

Question

首先,抱歉模糊的标题.

假设我有以下几组:

s1 = ( x1, y1 )
s2 = ( x2 )

m1 = ( x1, y1, y2 )
m2 = ( x1 )
m3 = ( x1 , x2 )

对于每个集合Group 1- 调用集合s,我需要找到集合Group 2- 调用它m- 这m是它的一个子集s.

所以,对于我的例子,答案是:

s1 -> m2
s2 -> nothing

现在,我正在存储值std:set,但如果需要,我可以更改它.此外,集合可能会变大,因此算法需要高效.现在我有一种蛮力的方法,我并不完全满意.

有什么建议？

Answer 1

您没有具体说明您的方法有多暴力。只要您在 std:: 命名空间中使用设置查询函数，那么它们就可能尽可能高效。例如测试 set_intersection( s1.begin(), s2.end(), m1.begin(), m1.end() ) 是否等于 m1。

您可能比这更有效，因为您不需要匹配元素的副本，只是想知道它们都出现了。这可以通过复制 set_intersection 的代码但更改实现以简单地计算匹配元素的数量而不是将它们复制出来来完成。然后，如果计数与 m 的大小相同，则匹配。

至于容器，对于大型集合，我通常更喜欢排序双端队列而不是集合。内存在堆上的分布要少得多，这有助于缓存。它还避免了底层树的开销。当容器被创建一次但被搜索多次时，这尤其有用。