如何使用C++ STL和Boost判断两个已排序向量是否相交

Question

如何使用C++ STL和Boost判断两个已排序向量是否相交

5

我有两个已排序的不含重复元素的C++ std::vector（也可以称为集合），我想知道它们是否相交。我不需要公共元素的向量。

我使用boost“range”库中的boost :: set_intersection算法编写了这个问题最后的代码（http://www.boost.org/doc/libs/1_50_0/libs/range/doc/html/range/reference/algorithms/set.html）。该代码避免了构造公共元素集，但会扫描向量的所有元素。

是否可能使用boost和C++ STL改进我的“intersects”函数而不使用循环？我想在向量中停止第一个公共元素或至少避免我的计数器类。

boost范围库提供“includes”和“set_intersection”，但不提供“intersects”。这使我认为“intersects”是微不足道的或提供在其他地方，但我找不到它。

谢谢！

#include <vector>
#include <string>
#include <boost/assign/list_of.hpp>
#include <boost/function_output_iterator.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/algorithm_ext/erase.hpp>

template<typename T>
class counter
{
    size_t * _n;
public:
    counter(size_t * b) : _n(b) {}
    void operator()(const T & x) const
    {
        ++*_n;
    }
};

bool intersects(const std::vector<std::string> & a, const std::vector<std::string> & b)
{
    size_t found = 0;
    boost::set_intersection(a, b, boost::make_function_output_iterator(counter<std::string>(&found)));
    return found;
}

int main(int argc, char ** argv)
{
    namespace ba = boost::assign;
    using namespace std;
    vector<string> a = ba::list_of(string("b"))(string("vv"))(string("h"));
    vector<string> b = ba::list_of(string("z"))(string("h"))(string("aa"));
    boost::erase(a, boost::unique<boost::return_found_end>(boost::sort(a)));
    boost::erase(b, boost::unique<boost::return_found_end>(boost::sort(b)));
    cout << "does " << (intersects(a, b) ? "" : "not ") << "intersect\n";
    return 0;
}

- Stuart Pook

4

为什么要使用boost？已经有了std::unique和std::set_intersection。 - Kiril Kirov

我认为你不能在不编写自己的循环的情况下改进你的函数。 - jrok

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- CashCow · Accepted Answer

首先回答评论，boost的set_intersection将范围作为参数，而STL的set_intersection则将迭代器作为参数。

除此之外，算法和复杂度方面没有实质性的区别。

据我所知，目前没有现成的库函数可以做到您想要的功能，即仅在两个序列不唯一时立即停止测试。

您还需要意识到，在它们确实是唯一的情况下，您总会有“最坏情况”。

时间复杂度为O（N+M），但您也可以在其中一个集合上使用二分查找，这将使其变为O（N log M）或O（M log N），如果一个集合比另一个大得多，则可以大大节省时间。（例如：N=1000000，M=20，M log N仅约为400）

您可以通过取其中一个的中位数，找到另一个的中位数，并在单独的线程中比较子范围来“缩小”。

还有一种“可怕”的解决方案，即让在交集上被调用的函数对象抛出异常，从而打破循环。（是的，即使它隐藏在算法中，也有一个函数对象）。我们可能可以自己编写一个函数对象，使其非常简单地达到O（N+M）的复杂度。我将使用4个迭代器来完成它：

 template< typename Iter1, typename Iter2 >
 bool intersects( Iter1 iter1, Iter1 iter1End, Iter2 iter2, Iter2 iter2End )
 {
      while( iter1 != iter1End && iter2 != iter2End )
      {
         if( *iter1 < *iter2 )
         {
             ++iter1;
         }
         else if ( *iter2 < *iter1 )
         {
             ++iter2;
         }
         else
             return true;
      }
      return false;
 }

 // Predicate version where the compare version returns <0 >0 or 0

 template< typename Iter1, typename Iter2, typename Comp >
 bool intersects( Iter1 iter1, Iter1 iter1End, Iter2 iter2, Iter2 iter2End, Comp comp )
 {
      while( iter1 != iter1End && iter2 != iter2End )
      {
         int res = comp( *iter1, *iter2 );
         if( res < 0 )
         {
             ++iter1;
         }
         else if ( res > 0 )
         {
             ++iter2;
         }
         else
             return true;
      }
      return false;
 }