检查两个元素在C++中是否具有公共元素

Question

我希望函数在两个向量之间存在任何元素匹配时返回true,

Note : My vectors are not sorted 以下是我的源代码,

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

当矢量B的大小小于矢量A的大小时,这工作正常,但是当矢量B的大小大于矢量A的大小时,即使存在匹配也返回假.

Answer 1

发布代码的问题在于,未std::binary_search对矢量进行排序时不应使用.仅针对排序范围定义行为.

如果输入向量未排序,则可以使用find_first_of检查是否存在找到的第一个公共元素.

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(); 它会比较元素直到找到匹配项.

如果你想修复原始算法,那么你可以制作一个向量的副本std::sort,然后std::binary_search使用它.

在容器之间进行大量此类匹配的实际程序中,容器通常保持分类.然后搜索的复杂性达到线性 inVectorA.size()+inVectorB.size().

std::find_first_of 比两个范围排序然后在两个范围相当短或第二范围短于第一范围长度的二进制对数时搜索匹配更有效.