c++ - set_union 与多集容器？

Question

当一个或两个输入容器是具有重复对象的多重集时，算法 std:set_union 的返回是什么？dup会迷路吗？

让我们假设例如：

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

来自std::set_union 的文档（添加了重点）。

在最简单的情况下，set_union 执行集合论中的“联合”操作：输出范围包含包含在 [first1, last1)、[first2, last2) 或两者中的每个元素的副本。一般情况更复杂，因为输入范围可能包含重复元素。概括来说，如果一个值在 [first1, last1) 中出现 m 次，在 [first2, last2) 中出现 n 次（其中 m 或 n 可能为零），则它在输出范围内出现 max(m,n) 次。[1] Set_union 是稳定的，这意味着保留每个输入范围内元素的相对顺序，并且如果两个输入范围中都存在一个元素，则它是从第一个范围而不是第二个范围复制的。

它会出现max(m,n)次数，其中m是它出现的次数ms1，是它出现n的次数ms2。

Answer 3

根据 C++ 标准，§25.3.5/1：

本节定义了排序结构的所有基本集合操作。它们还适用于包含多个等效元素副本的多重集 (23.3.4)。通过定义 union() 包含每个元素的最大出现次数，intersection() 包含最小值，等等，集合操作的语义以标准方式推广到多集。