インプレースC++設定交差点

Question

C++で二組と交差する標準的な方法は、次の操作を実行することです：

std::set<int> set_1; // With some elements 
std::set<int> set_2; // With some other elements 
std::set<int> the_intersection; // Destination of intersect 
std::set_intersection(set_1.begin(), set_1.end(), set_2.begin(), set_2.end(), std::inserter(the_intersection, the_intersection.end())); 

はどのようにして、インプレース積集合をやって行くのでしょうか？つまり、set_1にset_intersectionの呼び出しの結果を持たせます。明らかに、私はちょうどset_1.swap(the_intersection)を行うことができますが、これはインプレースを交差させるよりもはるかに効率が悪いです。

Answer 1

私はそれを持っていると思う：

std::set<int>::iterator it1 = set_1.begin(); 
std::set<int>::iterator it2 = set_2.begin(); 
while ((it1 != set_1.end()) && (it2 != set_2.end())) { 
    if (*it1 < *it2) { 
     set_1.erase(it1++); 
    } else if (*it2 < *it1) { 
     ++it2; 
    } else { // *it1 == *it2 
      ++it1; 
      ++it2; 
    } 
} 
// Anything left in set_1 from here on did not appear in set_2, 
// so we remove it. 
set_1.erase(it1, set_1.end()); 

誰もが何か問題を参照してください？ 2つのセットのサイズでO（n）と思われる。 cplusplus.comによると、std :: set erase（position）はerase（first、last）がO（log n）の間に償却定数になります。

Answer 2

あなたは簡単にset_1を調べて、各要素を確認してそれが存在するかどうかを確認してください（存在しない場合は削除してください）。セットはソートされているので、それらを線形時間で比較し、イテレーターを使用してエレメントを消去することはamortized constant timeです。私はそれがあなたが始まったものよりも効率的であるとは思っていませんが、ベンチマークはあなたにとって重要ならば賢明でしょう。