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 的大小时，即使存在匹配，也会返回 false。

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

可以使用它。

在容器之间进行大量此类匹配的实际程序中，容器通常保持排序。在这种情况下可以使用

std::set_intersection

。那么搜索的复杂度在

inVectorA.size()+inVectorB.size()

中达到线性。

当两个范围都相当短或第二个范围比第一个范围的长度的二进制对数短时，

std::find_first_of

比对两个范围进行排序然后搜索与

std::set_intersection

的匹配更有效。

Answer 2

您可以使用一种定义明确的算法，称为

std::set_intersection

来检查这些向量之间是否存在任何公共元素。

前提条件：- 两个向量都已排序。

Answer 3

您可以执行以下操作。迭代第一个向量。对于每个元素，使用

std::find

查看它是否存在于另一个向量中。如果找到，则它们至少有一个共同元素，因此返回 true。否则，移动到第一个向量的下一个元素并重复此过程。如果你一直通过第一个向量而没有找到公共元素，则没有交集，因此返回 false。

bool CheckCommon(std::vector<long> const& inVectorA, std::vector<long> const& nVectorB)
{
    for (auto const& num : inVectorA)
    {
        auto it = std::find(begin(nVectorB), end(nVectorB), num);
        if (it != end(nVectorB))
        {
            return true;
        }
    }
    return false;
}

Answer 4

使用

std::set_intersection

是一种选择。由于向量的元素是排序的，因此代码可以简化为：

#include <algorithm>
#include <iterator>

bool CheckCommon( const std::vector< long > &inVectorA, const std::vector< long > &inVectorB )
{
    std::vector< long > temp;
    std::set_intersection(inVectorA.begin(), inVectorA.end(), 
                          inVectorB.begin(), inVectorB.end(),
                          std::back_inserter(temp));
    return !temp.empty()
}

缺点是在执行

set_intersection

时会创建一个临时向量（但也许在将来，如果您想知道哪些元素是常见的，这可以被视为“特征”）。

Answer 5

这是一个使用排序向量的实现，不构造新容器，并且仅具有线性复杂度（更详细：

O(container1.size()+ container2.size())

：

template< class ForwardIt1, class ForwardIt2 >
bool has_common_elements( ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first, ForwardIt2 s_last )
{
    auto it=first;
    auto s_it=s_first;
    while(it<last && s_it<s_last)
    {
        if(*it==*s_it)
        {
            return true;
        }

        *it<*s_it ? ++it : ++s_it;  //increase the smaller of both
    }
    return false;
}

演示

Answer 6

您的代码使用

std::binary_search

，其前提条件是（来自http://en.cppreference.com/w/cpp/algorithm/binary_search）：

要使

std::binary_search

成功，范围

[first, last)

必须至少部分排序，即它必须满足以下所有要求：

• 相对于

  element < value

  或

  comp(element, value)

  进行分区
  • 相对于

    !(value < element)

    或

    !comp(value, element)

  进行分区
  • 对于所有元素，如果

    element < value

    或

    comp(element, value)

    是

    true

    那么

    !(value < element)

    或

    !comp(value, element)

    也是

    true

完全排序的范围满足这些标准，调用

std::partition

产生的范围也是如此。

您用于测试的示例数据（发布于 http://ideone.com/XCYdM8）不符合该要求。而不是使用：

   vectorB.push_back(11116);
   vectorB.push_back(11118);
   vectorB.push_back(11112);
   vectorB.push_back(11120);
   vectorB.push_back(11190);
   vectorB.push_back(11640);
   vectorB.push_back(11740);

如果您使用如下所示的排序向量

   vectorB.push_back(11112);
   vectorB.push_back(11116);
   vectorB.push_back(11118);
   vectorB.push_back(11120);
   vectorB.push_back(11190);
   vectorB.push_back(11640);
   vectorB.push_back(11740);

你的函数会正常工作。

PS 你已经设计好了你的代码，如果较长的

std::vector

被排序，该功能将正常工作。

PS2 另一种选择是在调用函数之前对较长的

std::vector

进行排序。

std::sort(B.begin(), B.end());

Answer 7

我认为这可能是一个很好的检查（排序向量的情况），比二分搜索的解决方案更有效：

template <class IteratorT>
bool empty_intersection(IteratorT a0, IteratorT a1, IteratorT b0,
                        IteratorT b1) {
  if (a0 == a1 || b0 == b1)
    return true;
  for (;;)
  {
    if (*a0 == *b0)
      return false;
    if (*a0 < *b0)
    {
      if (++a0 == a1)
        return true;
    } else if (++b0 == b1)
      return true;
  }
}