如何使用C++ STL和boost來判斷兩個已排序的向量是否相交

Question

我有兩個沒有重複的已排序C++ std ::向量（您可以稱它們爲集合），我想知道它們是否相交。我不需要共同元素的向量。

我在boost問題的範圍內使用boost :: set_intersection算法編寫了這個問題最後的代碼（http://www.boost.org/doc/libs/1_50_0/libs/range/doc /html/range/reference/algorithms/set.html）。這段代碼避免了構造一組通用元素，但是掃描了矢量的所有元素。

是否有可能改善我的功能「相交」使用boost和C++ STL而不使用循環？我想停止向量中的第一個通用元素，或者至少避開我的counter類。

增強範圍庫提供「包含」和「set_intersection」，但不是「相交」。這使我認爲「相交」是微不足道的或在其他地方提供，但我找不到它。

謝謝！

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

Answer 1

首先回答評論，boost的set_intersection將範圍作爲參數與STL獲取迭代器進行比較。

除此之外，關於算法和複雜性沒有真正的區別。

據我所知，沒有現成的庫函數來做你想做的事情，這只是測試如果兩個序列是唯一的，如果它們不是立即停止。

你還必須認識到，當他們真的是獨一無二的時候，你總是會遇到「最壞的情況」。

複雜度爲O（N + M），儘管您也可以在其中一個集合上使用二進制搜索，使其成爲O（N log M）或O（M log N），如果其中一個更大比其他這可以是一個很大的節約。 （例如，N = 1000000，M = 20，M log N只有約400）

你可以通過取1的中位數來找到它，並比較不同線程中的子範圍。

還有一個「可怕」的解決方案，讓你的函子在交點投擲中被調用，從而使你脫離循環。 （是的，即使它隱藏在算法中也是如此）。我們可以很簡單地編寫自己的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; 
}