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

Question

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

Yes, I'm fairly certain there's a quicker way, as you're asking. Before posting their first question on stackoverflow.com, everyone should take the tour, read the help center, understand all the requirements for a minimal reproducible example and How to Ask questions here. Not doing any of this results in a poor quality question almost every time. It then gets downvoted, closed, and then deleted. — Sam Varshavchik
– Sam Varshavchik, Commented Jun 19, 2022 at 2:25
std::find? Seems like a good place to start. Let the efficiency of the algorithm help you look at both vectors for a common element. — David C. Rankin
– David C. Rankin, Commented Jun 19, 2022 at 2:25
When you say common elements, do you mean any common elements (e.g., if vector {'x', 'h', 'a', r'} has an 'a'), common runs of elements (i.e., a substring), or something different? If the former, would it be feasible to use a std::vector<std::set<char> > instead of a std::vector<std::vector<char> >? — Schol-R-LEA
– Schol-R-LEA, Commented Jun 19, 2022 at 2:30
Sorry, I meant common elements as in elements that appear in both vectors. I included an example in the question. Also, would adding all the elements to a set and then checking if the size is the same as the sum of the sizes of the vectors be a quicker and valid method to achieve this? — Dave Brown
– Dave Brown, Commented Jun 19, 2022 at 3:05

Haoliang · Accepted Answer · 2022-06-19 02:29:32Z

1

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

answered Jun 19, 2022 at 2:29

Haoliang

1,2946 silver badges12 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Sam Varshavchik Over a year ago

"The more you overthink the plumbing, the easier it is to clog up the drain" -- Scotty, Star Trek III. An unordered set has to deal with heap allocation, hashing, and other wonderfully sophisticated algorithms. A single char [256] array, which is perfectly sufficient, requires none of that jazz, and results in the same number of physical lines, each one of which which will likely compile down to a single machine-language instruction. I would not give even a modern C++ compiler's good chances of optimizing an unordered-set based logic, equivalently.

Haoliang Over a year ago

@SamVarshavchik I agree with you. For simple chars, using set or unordered_set is an overkill. A boolean array is sufficient for 256 characters. However, sometimes we might have other types like strings, or as mentioned in the question, vector of chars. In these situations, a single array is not applicable.

Jerry Coffin · Accepted Answer · 2022-06-19 03:58:34Z

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.

Collectives™ on Stack Overflow

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

2 Answers 2

2 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Related