CODEWITHSUNDEEP
c++vector
Praveen
Praveen

Reputation: 1851

How to check whether a vector is a subset of another in c++

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

std::includes seems to work only for sorted ranges. How can I accomplish this?

Upvotes: 21

Views: 19239

Answers (4)

thayne
thayne

Reputation: 1058

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

Upvotes: 0

Benjamin Lindley
Benjamin Lindley

Reputation: 103761

Copy the vectors. Sort the 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());
}

Upvotes: 36

Andrew Rasmussen
Andrew Rasmussen

Reputation: 15109

This is assuming duplicates do NOT matter. So if you have two instances of the number 99 in vector a, then as long as vector b has at least one instance of the number 99, then 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;
}

Upvotes: 2

Lightness Races in Orbit
Lightness Races in Orbit

Reputation: 385405

My answer assumes that when you say "subset", you are really searching more for the equivalent of a "substring"; that is, maintaining order of elements during the search.

Ultimately, I can't see how you could do this in anything less than O(n*m). Given that, you can just roll your own pretty simply:

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

Live demo.

(You could probably be more creative with the template parameters.)

Upvotes: 9

Related Questions