c++ - 如何计算两个多重集的就地集差？

Question

假设我有两个多重集。我想从第一个多重集中删除第二个多重集中出现的所有元素，考虑每个元素在每个多重集中出现的次数。例如，如果多重集 a 包含五次 1，多重集 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 来说，移动不是必需的，但这样算法就保持了灵 active 和通用性)。

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).