How to compute in-place set difference of two multisets?

c++

Solution

While `std::set_difference` requires you to put the elements into a new set, you can certainly still optimize it by just moving the elements from the original set into the new one and swapping both afterwards (Ok, for `int`s moving isn't neccessary, but this way the algorithm keeps flexible and generic).

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

Not completely in-place, but nearly and still quite idiomatic while being linear in complexity (since the `std::insert_iterator` will always provide a proper hint to `std::multiset::insert`).

Problem

Suppose I have two multisets. I want to remove all elements that occur in the second multiset from the first multiset, respecting the number of times each element occurs in each multiset. For example, If multiset `a` contains `1` five times, and multiset `b` two times, when I compute `a -= b`, only two instances of `1` should be removed from `a`. Here is some code that accomplishes this: ``` 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)); } ``` Surely there's a better / more idiomatic way?

Original source