gpt4 book ai didi

c++ - 如何使用 C++ STL 和 boost 判断两个排序 vector 是否相交

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:04:18 25 4
gpt4 key购买 nike

我有两个已排序的 C++ std::vector,没有重复项(您可以称它们为集合),我想知道它们是否相交。我不需要公共(public)元素的 vector 。

我在这个问题的末尾使用 boost“范围”库中的 boost::set_intersection 算法编写了代码 (http://www.boost.org/doc/libs/1_50_0/libs/range/doc/html/range/reference/algorithms/set.html)。此代码避免构建公共(public)元素集,但会扫描 vector 的所有元素。

是否可以在不使用循环的情况下使用 boost 和 C++ STL 改进我的函数“相交”?我想停在 vector 中的第一个公共(public)元素处,或者至少避免我的计数器类。

boost 范围库提供“includes”和“set_intersection”但不提供“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;
}

最佳答案

首先回答评论,与采用迭代器的 STL 相比,boost 的 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;
}

关于c++ - 如何使用 C++ STL 和 boost 判断两个排序 vector 是否相交,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12919089/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com