C++设置如何检查集合列表是否包含子集
我有一个集合列表，现在列表是一个向量，但它不需要是。
vector<unordered_set<int>> setlist;
然后我用一些数据填充它，例如它看起来像这样：
[ {1, 2}, {2, 3}, {5, 9} ]
现在我有另一组，让我们说它是这样的： {1, 2, 3}
我想检查是否有列表中的这些集合是上述集合的子集。例如，setlist[0] 和 setlist[1] 都是子集，因此输出将为 true
我的想法是循环遍历整个向量并使用以下命令检查是否有任何索引是子集std::includes 函数，但我正在寻找一种更快的方法。这可能吗？
I have a list of sets, right now the list a vector but it does not need to be.
vector<unordered_set<int>> setlist;
then i am filling it with some data, lets just say for example it looks like this:
[ {1, 2}, {2, 3}, {5, 9} ]
Now i have another set, lets say its this: {1, 2, 3}
I want to check if any of these sets in the list is a subset of the above set. For example, setlist[0] and setlist[1] are both subsets, so the output would be true
My idea is to loop through the whole vector and check if any of the indexes are a subset using the std::includes function, but I am looking for a faster way. Is this possible?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
考虑使用
set列表代替。这允许您使用std::include。按集合中的元素数量（即从元素数量最少的集合到项目数量最多的集合）对向量进行排序后，对向量运行循环。内循环将从当前索引开始。这可以避免您检查较小集合中是否包含较大集合。如果整数范围不太大，您可以考虑使用 < 来实现该集合code>std::bitset（如果包含 n，则位 n 为 true）。然后用非常快的逻辑运算完成包含测试（例如
subset & large_set == subset）。您仍然可以按count对向量进行排序，但考虑到逻辑运算的速度，不确定是否需要这样做。Consider using a list of
set<int>instead. This allows you to usestd::include. Run your loop on the vector after having sorted it by number of elements in the set (i.e. from the sets with the smallest number of elements, to the sets with the largest number of items). The inner loop will start at the current index. This avoids that you check inclusion of the larger sets in the smaller ones.If the range of the integers is not too large, you could consider implementing the set with a
std::bitset(bit n is true if n is included). The inclusion test is then done with very fast logical operation (e.g.subset & large_set == subset). You could still sort the vector bycount, but not sure that this would be needed considering the speed of the logical operation.