c++ - C++检查两个元素是否有共同元素

Question

我希望函数在两个 vector 之间有任何元素匹配时返回 true，

注意:我的 vector 没有排序以下是我的源代码，

bool CheckCommon( std::vector< long > &inVectorA, std::vector< long > &inVectorB )
{
    std::vector< long > *lower, *higher;

    size_t sizeL = 0, sizeH = 0;

    if( inVectorA.size() > inVectorB.size() )
    {
        lower = &inVectorA;
        sizeL = inVectorA.size();
        higher = &inVectorB;
        sizeH = inVectorB.size();
    }
    else
    {
        lower = &inVectorB;
        sizeL = inVectorB.size();
        higher = &inVectorA;
        sizeH = inVectorA.size();
    }

    size_t indexL = 0, indexH = 0;

    for( ; indexH < sizeH; indexH++ )
    {
        bool exists = std::binary_search( lower->begin(), lower->end(), higher->at(indexH) );

        if( exists == true )
            return true;
        else
            continue;
    }
    return false;
}

当 vector B 的大小小于 vector A 的大小时，此方法工作正常，但当 vector B 的大小大于 vector A 的大小时，即使匹配也返回 false。

Answer 1

已发布代码的问题在于，当 vector 未排序时，您不应使用 std::binary_search。该行为仅针对排序范围定义。

如果输入 vector 未排序，则可以使用 find_first_of 检查是否存在找到的第一个公共(public)元素。

bool CheckCommon(std::vector<long> const& inVectorA, std::vector<long> const& nVectorB)
{
    return std::find_first_of (inVectorA.begin(), inVectorA.end(),
                               nVectorB.begin(), nVectorB.end()) != inVectorA.end();
}

find_first_of 的复杂度在 inVectorA.size()*inVectorB.size() 中达到线性；它比较元素，直到找到匹配项。

如果你想修复你的原始算法，那么你可以复制一个 vector 并 std::sort 它，然后 std::binary_search 与它一起工作.

在容器之间进行大量此类匹配的实际程序中，容器通常保持排序。在这种情况下，可以使用 std::set_intersection。然后搜索的复杂度在 inVectorA.size()+inVectorB.size() 中达到线性。

std::find_first_of 比对两个范围进行排序然后在两个范围都相当短或第二个范围是短于第一范围长度的二进制对数。