两个多重集合的原地差集如何计算？

Question

假设我有两个多重集合。我想从第一个多重集合中删除在第二个多重集合中出现的所有元素，并保持每个元素在每个多重集合中出现的次数不变。例如，如果多重集合a包含五次1，而多重集合b包含两次1，那么当我执行a -= b时，a中应该只删除两个1的实例。

下面是一些代码可以实现这个功能：

 multiset<int> a;
 multiset<int> b;

 // remove all items that occur in b from a, respecting count ("a -= b")
 for (multiset<int>::iterator i = b.begin(); i != b.end(); i++) {
    if (a.count(*i) < 1) {
       // error 
    }
    // a.erase(*i) would remove ALL elements equal to *i from a, but we 
    // only want to remove one.  a.find(*i) gives an iterator to the first
    // occurrence of *i in a.
    a.erase(a.find(*i));
  }

当然，有更好/更惯用的方法吗？

- nibot

---

你为什么在将 i 增加后要对其进行解引用？同样，迭代器是开始习惯于使用 ++i 的好理由。这是一个有趣的问题。 - Christian Rau

Answer 1

虽然 std::set_difference 要求将元素放入新的 set 中，但您仍然可以通过将原始集合中的元素“移动”到新集合中，并在之后交换两者来进行优化（对于 int 来说，移动可能并非必要，但这样算法可以保持灵活性和通用性）。

std::multiset<int> c;
std::set_difference(std::make_move_iterator(a.begin()), 
                    std::make_move_iterator(a.end()), 
                    b.begin(), b.end(), 
                    std::inserter(c, c.begin()));
a.swap(c);

虽然不完全是就地排序，但几乎是，并且在复杂度上仍然相当符合惯用方式（因为 std :: insert_iterator 将始终为 std :: multiset :: insert 提供适当的提示）。

- Christian Rau

---

当基础数据类型只是一个 int 时，“移动”是否有任何优势？ - nibot

@nibot 不是，但我更多地是根据通用算法编写的，没有注意到它只涉及整数。 - Christian Rau

Answer 2

请参阅std::set_difference

它也适用于多重集合。

根据最新的草案n3485第25.4.5.4节[set.difference]。

Remarks: If [first1,last1) contains m elements that are equivalent to each other and
[first2, last2) contains n elements that are equivalent to them, the last max(m−n,0)
elements from [first1, last1) shall be copied to the output range.

- indeterminately sequenced

---

有没有一种方法可以原地完成这个操作？ - nibot

@nibot 是的，（我想是这样）我正在尝试找出一个原地版本。 - indeterminately sequenced

@MikeSeymour 它是基于集合的大小线性的，但是由于集合是关联容器，你是否指的是对数？ - indeterminately sequenced

如果您希望输出也是一个multiset，那么每个输出元素都需要进行对数插入，因此总复杂度为O(N log N) - 比线性更慢。如果您可以接受在序列容器中获得结果，那么它可能是线性的；但这距离“从第一个multiset中删除元素”的要求更远。 - Mike Seymour

@MikeSeymour 但是如果使用正确的提示（一个适当设置的std::insert_iterator将使用），向一个multiset中插入数据仍然应该是常数时间，不是吗？ - Christian Rau

@ChristianRau：是的，在仔细阅读标准后，我认为你是正确的；它应该是线性时间，因此与原地版本相比唯一的成本是额外的内存使用。 - Mike Seymour

Answer 3

由于容器已排序，您可以同时遍历两个集合，并跳过仅存在于其中一个集合中的值；可以使用如下代码：

for (auto i = a.begin, j = b.begin(); i != a.end() && j != b.end();) {
    if (*i < *j) {
        ++i;
    } else if (*j < *i) {
        ++j;
    } else {
        i = a.erase(i);
        ++j;
    }
}

这种方法具有线性复杂度，避免了对count和find的对数时间调用。

另外，如果你不介意将要保留的元素移动到一个新的映射中，你可以使用std::set_difference。但是这可能不会是线性时间，因为每个元素都需要插入到输出映射中。

更新：进一步调查表明，当给定适当的提示时，插入被要求为线性，而insert_iterator将提供正确的提示。因此，如果你不介意构建一个新的多重集合并承受额外的内存使用，那么这可能被认为更符合惯用法。

- Mike Seymour

---

我有点惊讶，居然没有标准库函数可以做到这一点。 - nibot

@nibot：该库倾向于支持通用算法（如set_difference），而不是更具体于容器的算法；但我同意，拥有能够原地组合关联式容器的函数将会很有用。 - Mike Seymour