c++ - 从 vector 集中修剪非公共(public)元素

Question

假设我有一组 vector ，其中 Pair 定义如下:

struct Pair
{
   int A;
   int B;
}

std::vector<Pair> a = { {1,2}, {4,8}, {5,1}, {10,3} };
std::vector<Pair> b = { {1,2}, {4,9}, {5,1}, {10,3} };
std::vector<Pair> c = { {1,3}, {4,10}, {5,1}, {10,4} };

我想创建一个新 vector ，这样只有所有输入 vector 共有的元素才会被输入到新 vector 中，如下所示:

std::vector<Pair> abc = { {5,1} }; //  {5,1} is only common value.

我看到很多问题询问如何删除重复项，但我希望只保留重复项。

我问了一个类似的问题，但忽略了提到不可排序的 Pair 类型，这改变了问题。

是否有现成的高效 STL 算法或构造可以为我执行此操作，还是我需要自己编写？

Answer 1

使用哈希表来跟踪您看到每一个的次数:

std::vector<Pair> abc;
std::unordered_map<Pair, int> count;

for (const auto& vec : {a, b, c})
    for (const Pair& pair : vec)
        if (++count[pair] == 3)
            abc.push_back(pair);

是O(n)的时间和空间。