How to check if a vector is a subset of another in C ++

Question

I am trying to find a simple way to check if a vector is a subset of another without sorting the order of the elements in the vector. Both vectors contain elements of random numbers in them.

std::includes seems to work only for sorted ranges. How can i do this?

Answer 1

Copy the vectors. Sort copies. Then use std::includes on the copies.

 template <typename T> bool IsSubset(std::vector<T> A, std::vector<T> B) { std::sort(A.begin(), A.end()); std::sort(B.begin(), B.end()); return std::includes(A.begin(), A.end(), B.begin(), B.end()); } 

Answer 2

My answer suggests that when you say “subset”, you are really looking more for the equivalent of “substring”; that is, maintaining the order of the elements during the search.

---

Ultimately, I don't see how you could do this in less than O(n*m) . Given this, you can simply simply collapse your own:

 template <typename T1, typename T2> bool contains(std::vector<T1> const& a, std::vector<T2> const& b) { for (typename std::vector<T1>::const_iterator i = a.begin(), y = a.end(); i != y; ++i) { bool match = true; typename std::vector<T1>::const_iterator ii = i; for (typename std::vector<T2>::const_iterator j = b.begin(), z = b.end(); j != z; ++j) { if (ii == a.end() || *j != *ii) { match = false; break; } ii++; } if (match) return true; } return false; } 

demo version.

(You can probably be more creative with template options.)

Answer 3

This suggests that duplicates do not matter. Therefore, if you have two instances of the number 99 in the vector a, then as long as the vector b has at least one instance of the number 99, it will be declared as a subset.

 bool isSubset(const std::vector<int>& a, const std::vector<int>& b) { for (std::vector<int>::const_iterator i = a.begin(); i != a.end(); i++) { bool found = false; for (std::vector<int>::const_iterator j = b.begin(); j != b.end(); j++) { if (*i == *j) { found = true; break; } } if (!found) { return false; } } return true; } 

Answer 4

Without sorting ...

 template <typename T> bool isSubsetOrEqual(std::vector<T> const& a, std::vector<T> const& b) { for(auto const& av:a){ if(std::find(b.begin(),b.end(),av)==b.end()) return false; } return true; }