c++ - 一次性计算两组差值 A\B 和 B\A

Question

如果我有一个表示为排序范围的集合，我可以使用 std::set_difference 来计算 A\B 和 std::set_symmetric_difference 来计算 A\B U B\A。如果我想计算两个不同的集合 A\B 和 B\A 怎么办？

当然，我可以运行 std::set_difference 两次，但这看起来不是很优雅(如果我们有输入迭代器，甚至不可能)。自己编写实现也很容易，但我想知道是否有针对此任务的现成解决方案？

Answer 1

如果您的集合都已排序，则可以使用两个迭代器一次性完成:

• 如果指向的元素在两个集合中，都增加
• 否则，如果 A 的迭代器指向的元素较小，则将其产生给 A\B，并增加 A 的迭代器。
• 否则，将 produce B 的元素增加到 B\A 并增加 B 的迭代器。

类似C++的伪代码:

iter1 = A.begin();
iter2 = B.begin();
while (iter1 != A.end() && iter2 != B.end()) { 
  if (*iter1 == *iter2) { 
    // don't produce anything
    ++iter1; ++iter2;
  } else if (*iter1 < *iter2) { 
    // produce *iter1 to A\B
    ++iter1;
  } else { 
    //produce *iter2 to B\A
    ++iter2;
  }
}

while (iter1 != A.end()) {
  //produce element to A\B
  ++iter1;
}
while (iter2 != B.end()) {
  //produce element to B\A
  ++iter2;
}