5

重複のない 2 つの並べ替えられた C++ std::vector (セットと呼ぶことができます) があり、それらが交差するかどうかを知りたいです。共通要素のベクトルは必要ありません。

ブースト「範囲」ライブラリ（http://www.boost.org/doc/libs/1_50_0/libs/range/doc/html/range）のboost::set_intersectionアルゴリズムを使用して、この質問の最後にコードを書きました/reference/algorithms/set.html)。このコードは、共通要素のセットの構築を回避しますが、ベクトルのすべての要素をスキャンします。

ループを使用せずにブーストと C++ STL を使用して関数の「交差」を改善することは可能ですか? ベクトルの最初の共通要素で停止するか、少なくともカウンター クラスを避けたいと思います。

ブースト範囲ライブラリは、「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;
}
4

1 に答える 1

4

最初にコメントに答えるために、boostのset_intersectionは、イテレータを使用するSTLと比較して、パラメータとして範囲を使用します。

それ以外は、アルゴリズムと複雑さに関して実際の違いはありません。

私の知る限り、やりたいことを実行するための既成のライブラリ関数はありません。これは、2つのシーケンスが一意であるかどうかをテストし、そうでない場合はすぐに停止するだけです。

また、それらが本当にユニークである場合、常に「最悪のシナリオ」が発生することを理解する必要があります。

複雑さはO（N + M）ですが、コレクションの1つでバイナリ検索を使用して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;
 }
于 2012-10-16T16:43:53.103 に答える