set_union с мультимножеством контейнеров?

Question

Что возвращает алгоритм std: set_union, когда один или оба входных контейнера являются мультимножествами с дублированными объектами?Потеряны ли дупс?

Предположим, например:

multiset<int> ms1;
ms1.insert(1);
ms1.insert(1);
ms1.insert(1);
ms1.insert(2);
ms1.insert(3);

multiset<int> ms2;
ms2.insert(1);
ms2.insert(1);
ms2.insert(2);
ms2.insert(2);
ms2.insert(4);

vector<int> v(10);
set_union( ms1.begin(), ms1.end(), ms2.begin(), ms2.end(), v.begin() );

Каким будет выход?

Answer 1

из стандарта 25.3.5:

Семантика операций над множествами обобщается на мультимножества стандартным способом, определяя union() как максимальное количество вхождений каждого элемента, intersection() как минимум и т. Д.

Итак, в вашем примере результат будет (1,1,1,2,2,3,4,0,0,0), поскольку вы инициализировали вектор длиной 10.

Answer 2

Из стандарта C ++, §25.3.5 / 1:

В этом разделе определяются все основные операции над множествами для отсортированных структур.Они также работают с мультимножествами (23.3.4), содержащими несколько копий эквивалентных элементов.Семантика операций над множествами обобщается на мультимножества стандартным способом, определяя union () как максимальное количество вхождений каждого элемента, intersection () как минимум и т.

Answer 3

Из документации о std :: set_union (выделение добавлено).

В простейшем случае set_union выполняет операцию «объединения» из теории множеств: выходной диапазон содержит копию каждого элемента, который содержится в [first1, last1), [first2, last2) или в обоих. Общий случай более сложный, потому что входные диапазоны могут содержать повторяющиеся элементы. Обобщение состоит в том, что если значение появляется m раз в [first1, last1) и n раз в [first2, last2) (где m или n может быть нулем), то оно появляется max (m, n) раз в выходном диапазоне. [1] Set_union является стабильным, что означает, что относительный порядок элементов в каждом входном диапазоне сохраняется, и что если элемент присутствует в обоих входных диапазонах, он копируется из первого диапазона, а не из второго.

Появится max(m,n) раз, где m - это количество раз, которое произошло в ms1, а n - это количество раз, которое произошло в ms2.