我想使用 C++ 执行多集交集

Question

我正在使用 std::set<int> 和多集类 std::multiset<int> 来执行一些集合操作 - 并集、交集等。问题是我必须在两个多集之间执行交集- 设置这样我也得到重复的值。当我将它与简单集（而不是多集）一起使用时，交集工作正常，例如

组 1={1,2,3,4,5,6}
Set2={4,5,6,7,8,9}
然后
std::set_intersection 给我一个正确的结果是 {4,5,6}

但是，如果我有一个多重集

多集1{1,1,2,2,3,3,4,4,5,5,6,6}
多集2{4,4,5,5,6,6,7,7,8,8,9,9}

我再次使用 std::set_intersection 它再次给我结果 {4,5,6}

这是不正确的，因为实际的交集是{4,4,5,5,6,6}

虽然我使用多集来保存交集的结果，但我仍然得到了错误的答案。

谁能告诉我如何解决这个问题。

Answer 1

请您post检查您的代码是否有错误？我已经像下面的代码一样编写了一个交集示例并且它有效。

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_intersection( ms1.begin(), ms1.end(), ms2.begin(), ms2.end(), v.begin() );

结果是 1, 1, 2. 这是正确的！

Answer 2

set_intersection 实际上也为多重集执行交集。我认为您对 set_intersection 的调用是错误的。参考资料中描述了您必须满足的一些要求，例如：

The resulting range cannot overlap with either of the input ranges.

不过，请看下面的代码：

#include <iostream>
#include <iterator> // inserter
#include <algorithm> // set_intersection
#include <set> // multiset

int main() {
    std::multiset<int> set1 = { 1,1,2,2,3,3,4,4,5,5,6,6 };
    std::multiset<int> set2 = { 4,4,5,5,6,6,7,7,8,8,9,9 };
    std::multiset<int> intersection;
    std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), std::inserter(intersection, intersection.begin()));

    // prints: 4 4 5 5 6 6 
    for(int elem : intersection) {
        std::cout << elem << ' ';
    } 
}

我想使用 C++ 执行多集交集

I want to perform a multi-set intersection using C++

c++

set

multiset

set-intersection