Quickest way to find if there is a common element between 2 vectors in CPP-CodePudding

I want to check if there are common elements between 2 vectors. Is there a quicker way than looping through each element for both vectors and checking if they are the same?

By common element I mean an element "a" that exists in both vectors.

I only want to check IF there are common elements not how many, so I was thinking maybe I could use that to make a quicker piece of code.

I was also thinking of adding all elements to a set and checking if the set's size is equal to the sum of the sizes of the two vectors. Would this work?

The two vectors consist of vectors of chars. For example

vector<vector<char>> vec1 = {{'a','b'}, {'c'}};
vector<vector<char>> vec2 = {{'a'},{'b'},{'c'}};
// Notice that, in this case, {'c'} would the the common element
// because it exists in both vectors

CodePudding user response：

We can create a set to store the elements in one vector.

set<vector<char>> elements;
for (auto v : vec1) {
    elements.insert(v);
}

Then iterating through the elements in the second vector, to see if they exist in the unordered_set:

for (auto v : vec2) {
    if (elements.count(v) > 0) {
        // do the logic for common elements
    }
}

CodePudding user response：

If you're willing to duplicate the two inputs into sets, one simple way to do the job would be to use std::set_intersection and check whether the result is empty:

#include <set>
#include <algorithm>
#include <iostream>
#include <vector>

using container = std::vector<std::vector<char>>;

// sets are sorted, so we need to support comparison for the contained object
bool operator<(std::vector<char> const &a, std::vector<char> const &b) {
    std::string aa(a.begin(), a.end());
    std::string bb(b.begin(), b.end());

    return aa < bb;
}

bool contains_common_element(container const &a, container const &b) {
    container intersection;

    std::set<std::vector<char>> aa { a.begin(), a.end() };
    std::set<std::vector<char>> bb { b.begin(), b.end() };

    std::set_intersection(aa.begin(), aa.end(),
                          bb.begin(), bb.end(),
                          std::inserter(intersection, intersection.end()));

    return !intersection.empty();
}

int main() {
    using std::vector;

    // do a few tests:
    vector<vector<char>> vec1 = {{'a','b'}, {'c'}};
    vector<vector<char>> vec2 = {{'a'},{'b'},{'c'}};
    vector<vector<char>> vec3 = {{ 'd'}, {'a', 'b'}};
    vector<vector<char>> vec4 = {{ 'e' } , {'f'}};

    std::cout << std::boolalpha << contains_common_element(vec1, vec2) << "\n";
    std::cout << contains_common_element(vec1, vec3) << "\n";
    std::cout << contains_common_element(vec2, vec3) << "\n";
    std::cout << contains_common_element(vec3, vec4) << "\n";
}

This could be somewhat inefficient though: it'll scan through the entirety of both inputs looking for all intersections, where we only care whether there's at least one.