Prune non-common elements from set of vectors

Question

Let's say I have a set of vector, where Pair is defined as follows:

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

I want to create a new vector, in such a way that only elements which are common to all input vectors are input into the new vector as follows:

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

I have seen many questions asking for how to remove duplicates, but I wish to retain only duplicates.

I asked a similar question, but neglected to mention the non-sortable Pair type, which changes the problem.

Is there an existing efficient STL algorithm or construct that will do this for me, or do I need to write my own?

Possible duplicate of [Create new vector from others, using only duplicates](https://stackoverflow.com/questions/56237655/create-new-vector-from-others-using-only-duplicates) — Blaze, May 21 '19 at 12:13
There are elements to this question that are not covered in the other, such as Pair not being a sortable type. — Ian Young, May 21 '19 at 12:16
That's a different question. You can use `std::pair`, which is sortable, or provide `operator <` for your class. Read [How can I use std::maps with user-defined types as key?](https://stackoverflow.com/questions/1102392/how-can-i-use-stdmaps-with-user-defined-types-as-key). It deals with `std::map`, but it solves exactly the same problem. — Yksisarvinen, May 21 '19 at 12:17
OK so the Pairs are not sortable, but can we implement a hash function for them? — John Zwinck, May 21 '19 at 12:24
@NathanOliver No, no particular order, as the Pair object is not sortable in a meaningful way. — Ian Young, May 21 '19 at 12:40

score 1 · Accepted Answer · answered May 21 '19 at 12:31

Use a hash table to track how many times you've seen each one:

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

It is O(n) time and space.

Prune non-common elements from set of vectors

1 Answers1