Как вычислить разницу между двумя мультимножествами?

Question

Предположим, у меня есть два мультимножества. Я хочу удалить все элементы, которые встречаются во втором мультимножестве из первого мультимножества, с учетом количества раз, когда каждый элемент встречается в каждом мультимножестве. Например, если 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 требует, чтобы поместить элементы в новый набор, вы можете, конечно, еще оптимизировать его просто перемещение элементов из исходного набора в новый и замены обоих потом (Ok, для int s перемещение не обязательно, но таким образом алгоритм сохраняет гибкость и общий с).

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

Answer 2

См std::set_difference

Он будет работать на мультимножествами также.

Из последнего проекта n3485 25.4.5.4 [set.di далее разностная]

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. 

Answer 3

Поскольку контейнеры упорядочены, вы можете перебрать оба сразу, пропуская значения, только в одном наборе; что-то вроде:

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 предоставит правильный намек. Это можно считать более идиоматичным, если вы не возражаете против использования дополнительной памяти для создания нового мультимножества.

Answer 4

Использование std::set_difference, но это делает новую третью коллекцию:

std::multiset<int> v1{1, 2, 5, 5, 5, 9}; 
std::multiset<int> v2{2, 5, 7}; 
std::multiset<int> diff; 

std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), 
        std::inserter(diff, diff.begin())); 

Выходной

1 5 5 9