mercredi 30 mars 2016

Efficient way of determining whether one vector is a subset of another or not?

Given two sorted vectors consisting of unique values between 0 and some known 'n'. And size of one vector (set1) will always be greater than that of candidate vector set2.

Query: Is to determine whether given set2 is a subset of set1 or not?

Is their any better and efficient way of doing this apart from the following implementation in C++11?

#include <iostream>
#include <vector>


bool subSetCheck(std::vector<int> set1, std::vector<int> set2) {

    //Set1 & 2 are always sorted and contain only unique integers from 0 to some known 'n'
    //Set1 is always larger than Set2 in size

    std::vector<int>::iterator it1 = set1.begin();
    std::vector<int>::iterator it2 = set2.begin();
    bool subSet = true;
    for (; (it1 != set1.end()) && (it2 !=set2.end()) ;) {

        if ( *it1 == *it2) {++it1; ++it2;}
        else if( *it1 > *it2) ++it2;
        else ++it1;
    }

    if (it1 ==set1.end()) subSet = false;

    return subSet;
}

int main () {

    std::vector<int> set1{0,1,2,3,4};
    std::vector<int> set2{0,1,5};

    if (subSetCheck(set1,set2)) std::cout << "Yes, set2 is subset of set1." << std::endl;
    else std::cout << "No! set2 is not a subset of set1." << std::endl;

    return 0;
}

Aucun commentaire:

Enregistrer un commentaire