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