确定多个集合中的唯一值

Question

在这个项目中，有多个 sets，其中它们包含 1 - 9 的值。在其中，我需要有效地确定是否有值在一个 set 中是唯一的，但是不是其他人。

例如：

std::set<int> s_1 = { 1, 2, 3, 4, 5 };
std::set<int> s_2 = { 2, 3, 4 };
std::set<int> s_3 = { 2, 3, 4, 6 };

注意： sets 的数量未知，直到 runtime.

如您所见，s_1 包含 1 和 5 的唯一值，而 s_3 包含 6 的唯一值。

确定唯一值后，上述 sets 应该只包含唯一值 ，例如：

// s_1 { 1, 5 }
// s_2 { 2, 3, 4 }
// s_3 { 6 }

到目前为止我尝试的是loop遍历所有sets并记录出现的numbers的count。但是我想知道是否有更有效的解决方案。

Answer 1

标准 C++ 库中有标准算法，用于对 2 个集合进行交集、差分和并集运算。

如果我很了解你的问题，你可以这样做：对所有集合（在循环中）进行交集以确定基数，然后在每个集合和基数之间应用差异？您可以根据您当前的实施对此进行基准测试。应该会更快。

查看此答案。

Getting Union, Intersection, or Difference of Sets in C++

编辑：cf Tony D. 评论：您基本上可以使用 std::bitset<> 和二元运算符（& | 等）执行相同的操作，这应该更快。根据您输入的实际大小，可能值得一试。

Answer 2

我会在 c# 中提出这样的建议

Dictionary<int, int> result = new Dictionary<int, int>();
foreach(int i in sets){
   if(!result.containskey(i))
      result.add(i,1);
   else
      result[i].value = result[i].value+1;
}

现在计数值只有1的数字表示它是唯一的，然后找到具有这些数字的集合...

Answer 3

我建议：

开始将所有集合中的所有元素插入到多映射中。
这里每个元素都是一个键，集合名称是值。
一个你的多重地图充满了所有集合中的所有元素，然后循环遍历 multimap 并计算其中的每个元素多图。
如果任何键的计数为 1，这意味着它的唯一性和值那将是集合名称。

确定多个集合中的唯一值

Determine unique values across multiple sets

c++

set