Find if vector is a C ++ subvector
Suppose I:
std::vector<string> group;
std::vector<string> subGroup;
Some properties of these two vectors:
1) All items are unique.
2) They are not sorted and sorting is not an option.
I need to check if a group contains a subgroup. If so, then 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:
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 this post here to find sub-vector <string> in another vector <string> , but I shouldn't use C ++ 11 capabilities and this answer doesn't solve my problem (for example, in my example 2 it will return false).
Two things, is my implementation ok or are there bugs? Is there an easier way to implement it with STL functions or something similar?
source to share
The two simplest solutions:
- Copy the vectors, sort them, then use includes
- Copy the elements of the group to
set
orunordered_set
and then check each elementsubgroup
to see if they are in the set (if C ++ 11 was an option, you can also use aall_of
lambda to implement the loop)- A variation on the same idea: make
set
orunordered_set
from elementssubgroup
, then swipe over the elementsgroup
, removing them from the set, if any. Returntrue
if this frees the set.
- A variation on the same idea: make
In any case, to get reasonable worst-case performance guarantees, you should immediately return false if subgroup
larger than group
.
The latter, c unordered_set
, has the best asymptotic complexity you can expect (ie O(n)
, where n
is the size group
), but I believe the former will be more efficient for "typical" examples.
source to share
Can be used std::set
std::set<std::string> group ; // Fill it first !
std::vector<std::string> subgroups {"A","D","E"} ;
std::vector<std::string>::iterator i = subgroups.begin() ;
std::pair<std::set<std::string>::iterator,bool> p;
for( ; i != subgroups.end(); ++i )
{
p = group.insert( *i );
if( p.second ) // Present in group
{
break;
}
}
if( i == subgroups.end() )
std::cout << std::boolalpha << true ;
else
std::cout << std::boolalpha << false ;
source to share
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);
}
source to share