7

假设我有两个多重集。我想从第一个多重集中删除第二个多重集中出现的所有元素，尊重每个元素在每个多重集中出现的次数。例如，如果 multiseta包含15 次， multiset 包含b2 次，当我计算 时，应该只删除 的a -= b两个实例。1a

这是一些完成此操作的代码：

 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));
  }

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

4

3 回答 3

14

虽然std::set_difference需要您将元素放入一个新集合中，但您当然仍然可以通过将元素从原始集合移动到新集合中并在之后交换两者来优化它（好吧，因为sint移动不是必需的，但是这样算法保持灵活和通用）。

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）。

于 2013-04-18T09:57:04.647 回答
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.
于 2013-04-18T09:43:32.797 回答
2

由于容器是有序的，您可以同时遍历这两个容器，跳过仅在一组中的值；就像是：

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. 不过，这可能不是线性时间，因为每个元素都需要插入到输出映射中。

更新：在进一步调查中，这似乎std::set_difference是线性的，因为在给出合适的提示时插入需要是线性的，并且insert_iterator会提供正确的提示。因此，如果您不介意构建新的多重集会使用额外的内存，那么这可能被认为更惯用。

于 2013-04-18T09:44:59.817 回答