C++判断两个序列的包含关系: std::includes

std::includes用于判断序列S2是否包含于序列S1,前提是序列S1,S2必须为有序序列(若为无序序列,首先应该通过std::sort使其变为有序序列),返回false(不包含)或者true(包含)。但是该功能并要求序列S2中的元素在序列S1中仍然连续出现,只是用来判断序列S1是否包含S2中的所有元素(不要求连续),并不类似于字符串判断中的子序列函数strstr。判断两个元素是否相等,需要以less和greater为判断依据,因此配合着两个有序序列S1、S2的排序方式(递增或递减),includes算法可以供用户选择less或者greater进行两个元素的大小比较。
若S1、S2为递增数列,includes函数应该以如下方式使用:

includes(S1.begin(),S1.end(),S2.begin(),S2.end());
1
和如下代码完全相同(默认为less比较)

includes(S1.begin(),S1.end(),S2.begin(),S2.end(),less());

但是如果S1和S2是递增数列,includes函数应该以如下方式使用:

includes(S1.begin(),S1.end(),S2.begin(),S2.end(),greater());
1
如果S1或S2中的元素可以重复,那么“S1中包含S2”的定义:假设某元素在S2中出现n次,在S1中出现m次,如果m

template
bool includes(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2,InputIterator2 last2)
{
while (first1!=last1 && first2!=last2) //若均未到达尾端,则进行以下操作
{
if (first2<first1) //说明,first1前面没有小于等于first2的元素,包含情况肯定不成立(有序序列)
return false;
else if (first1<first2)//序列二的相关元素大于
//序列一,序列一前进
first1++;
else //若二者相同,两序列各自前进1
{
first1++;
first2++;
}
}
return first2==first1; //有一个序列走完了,判断最后一关
}

版本二:自定义比较算子

template
bool includes(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2,InputIterator2 last2,Compare comp)
{
while (first1!=last1 && first2!=last2) //若均未到达尾端,则进行以下操作
{
if (comp(first2,first1)) //说明,comp(S2元素,S1元素)为真,包含情况肯定不成立(有序序列)
return false;
else if (comp(first1,first2)) //comp(S1元素,S2元素)为真,序列一前进
first1++;
else //若二者相同,两序列各自前进1
{
first1++;
first2++;
}
}
return first2==first1; //有一个序列走完了,判断最后一关
}

示例(less比较符):

1
2
3
4
5
6
7
8
9
10
11
12
int main(void)
{
int iarr1[]={1,10,5,7,19,4,9,1};
int iarr2[]={1,19,7};
std::sort(std::begin(iarr1),std::end(iarr1));
std::sort(std::begin(iarr2),std::end(iarr2));
bool ret;
ret=includes(std::begin(iarr1),std::end(iarr1),
std::begin(iarr2),std::end(iarr2),
less<int>()); //ret为true
return 0;
}

示例(greater比较符):

1
2
3
4
5
6
7
8
9
10
11
12
int main(void)
{
int iarr1[]={1,10,5,7,19,4,9,1};
int iarr2[]={1,19,7};
std::sort(std::begin(iarr1),std::end(iarr1),greater<int>());
std::sort(std::begin(iarr2),std::end(iarr2),greater<int>());
bool ret;
ret=includes(std::begin(iarr1),std::end(iarr1),
std::begin(iarr2),std::end(iarr2),
greater<int>()); //ret为true
return 0;
}

参考博客
http://classfoo.com/ccby/article/6lkafJ