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

Question

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?

Answer 1

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