Find if vector is subvector c++

Question

Assume that I have:

std::vector<string> group;
std::vector<string> subGroup;

Some properties about those two vectors:

1) All elements are unique.

2) They're not sorted, and sorting is not an option.

I need to check if group contains subgroup. If it does, than I need to return true, if it doesn't return false.

Examples:

group = {"A","B","C","D"}, subGroup = {"A","D","E"} -> answer = false

group = {"A","E","C","D"}, subGroup = {"A","D","E"} -> answer = true

My current implementation is:

int cont=0;
if(subGroup.size() > group.size())
    return false;
else{
    for(int i=0; i<subGroup.size(); i++){
        for(int j=0; j<group.size(); j++){
            if(subGroup[i] == group[j]{
                cont++;
            }
        }
    }
    if (cont == subGroup.size())
            return true;
    return false;
}

I checked on this post here locate sub-vector<string> in another vector<string> , but I'm not supposed to use C++11 features and also this answer does not solve my problem (using my example 2 for instance, it will return false).

Two things: is my implementation ok or is there any mistakes? Is there an easier way to implement it using STL features or anything like it?

Answer 1

The two most straightforward solutions are:

• Copy the vectors, sort them, then use includes
• Copy the elements of a group into a set or an unordered_set, and then check each element of subgroup to see if it's in the set (if C++11 were an option, you could use all_of and a lambda to implement the loop)
  • A variant on the same idea: make a set or an unordered_set out of the elements of subgroup, then loop through the elements of group, removing them from the set if present. Return true iff this empties out the set.

In either case, to get reasonable worst case performance guarantees you should immediately return false if subgroup is larger in size than group.

The latter, with unordered_set, has the best asymptotic complexity you can possibly expect (i.e. O(n) where n is the size of group), but I imagine the first option will be more efficient for "typical" examples.

Answer 2

There is a simple solution to this problem, using std:find:

bool            in(std::vector<std::string> const &group,
                   std::vector<std::string> const &subGroup) {
  std::size_t const     subSize = subGroup.size();
  int                   i = 0;

  while (i < subSize && std::find(group.begin(), group.end(), subGroup[i]) != group.end()) {
    i++;
  }
  return (i == subSize);
}