确定一个向量是否是另一个向量的子集的有效方法？

Question

给定两个排序的向量,由0和一些已知的'n'之间的唯一值组成.并且一个向量(set1)的大小总是大于候选向量set2的大小.

查询:是否确定给定的set2是否是set1的子集？

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

Answer 1

你可以使用std::includes:

std::vector<int> a{1,2,3,4,5};
std::vector<int> b{1,2,6};
std::cout << std::includes(a.begin(), a.end(), b.begin(), b.end()) << std::endl;