Что возвращает алгоритм 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() );
Каким будет результат?
Из стандарта 25.3.5:
Семантика операций над множествами стандартно обобщается на мультимножества путем определения
union(), содержащего максимальное количество вхождений каждого элемента,intersection(), содержащего минимальное количество, и так далее.
Итак, в вашем примере результат будет (1,1,1,2,2,3,4,0,0,0), поскольку вы инициализировали вектор длиной 10.
Из документации 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.
Из стандарта С++, §25.3.5/1:
В этом разделе определяются все основные операции над множествами над отсортированными структурами. Они также работают с мультимножествами (23.3.4), содержащими несколько копий эквивалентных элементов. Семантика операций над множествами стандартно обобщается на мультимножества, определяя union() как содержащее максимальное количество вхождений каждого элемента, пересечение() как содержащее минимум и так далее.
