How to get identical pairs from two vectors in c++

Question

I define two vectors: std::vector<std::pair<int, int> > vec1 and std::vector<std::pair<int, int> > vec2.

I want to find same pairs from vec1 and vec2. For example, vec1 = {{1,2}, {1,9}, {2,13}, {3,5}}, vec2 = {{8, 7}, {4,2}, {2,10}, {1,9}}. Then the result should be {{1,9}}.

How can I do this?

score 7 · Answer 1 · answered Nov 30 '15 at 15:21

You could do it if you sort your vectors with std::sort and then use std::set_intersection to find their common elements in the following way:

std::vector<std::pair<int, int>> v1 {{1,2}, {1,9}, {2,13}, {3,5}};
std::vector<std::pair<int, int>> v2 {{8,7}, {4,2}, {2,10} ,{1,9}};

std::sort(v1.begin(), v1.end());
std::sort(v2.begin(), v2.end());

std::vector<std::pair<int, int>> v_intersection;
std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(),
                      std::back_inserter(v_intersection));

LIVE DEMO

score 3 · Answer 2 · edited May 23 '17 at 10:31

The answer by 42 has a running time of O(n*log(n)) for the sorting process of the two vectors (where n is the size of the larger vector). If this is an issue, you can also create an unordered_set and fill it with the elements of one vector, and then use copy_if to retain only the elements from the other vector that are also contained in the set, resulting in a running time of O(n).

struct pairhash {
    template <typename T, typename U>
    std::size_t operator()(const std::pair<T, U>& p) const {
        return std::hash<T>()(p.first) ^ std::hash<U>()(p.second);
    }
};
struct pairequal {
    template <typename T, typename U>
    bool operator()(const std::pair<T, U>& p0, const std::pair<T, U>& p1) const {
        return (p0.first == p1.first) && (p0.second == p1.second);
    }
};

void findEqualPairs() {
    std::vector<std::pair<int, int>> vec1{ { 1, 2 }, { 1, 9 }, { 2, 13 }, { 3, 5 } };
    std::vector<std::pair<int, int>> vec2{ { 8, 7 }, { 4, 2 }, { 2, 10 }, { 1, 9 } };

    std::unordered_set<std::pair<int, int>, pairhash, pairequal> set2(
        vec2.begin(), vec2.end());
    std::vector<std::pair<int, int>> intersection;
    std::copy_if(vec1.begin(), vec1.end(),
        std::back_inserter(intersection),
        [&](const std::pair<int, int>& p) { 
            return set2.find(p) != set2.end(); });

    std::cout << "intersection:" << std::endl;
    for (auto it : intersection) {
        std::cout << it.first << ", " << it.second << std::endl;
    }
}

(The pairhash is taken from this answer)

How to get identical pairs from two vectors in c++

2 Answers2