如何计算两个多重集的就地设置差异？

Question

假设我有两个multisets.我想从第一个多集中删除第二个多集中出现的所有元素,并考虑每个多集中每个元素出现的次数.例如,如果multiset a包含1五次,而multiset 包含b两次,则在计算时a -= b,只1应删除两个实例a.

以下是一些实现此目的的代码:

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

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

Answer 1

虽然std::set_difference要求你把元素放到一个新的集合中,你当然可以通过将元素从原始集合移动到新集合并然后交换它们来优化它(好吧,因为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).