Обрезать необычные элементы из набора векторов

Question

Допустим, у меня есть набор векторов, где пара определяется следующим образом:

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} };

Я хочу создать новый вектор таким образом, чтобы только элементы, общие для всех входных вектороввводятся в новый вектор следующим образом:

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) время и пространство.