c++ - 1つのリストにあるすべての要素を別のC++から削除します

Question

l1とl2の2つのリストがあるとしましょう。l1 --l2を実行したいのですが、これはl2の要素でもある要素を削除してl1を返します。

これを行うための素朴なループアプローチを考えることができますが、それは本当に非効率的です。C ++でこれを行う効率的な方法は何ですか？

例として、l1=[1,2,6,8]およびl2=[2,8]の場合、l1-l2は[1,6]を返す必要があります。

みんなありがとう

Answer 1

順序は重要ですか？リストに重複が含まれますか？

そうでない場合は、set_differenceを実行することをお勧めします

ただし、重複がある場合、set_differenceは、削除する重複要素の最初の出現のみを削除すると思います。

Answer 2

これは、ハッシュセットを使用して償却線形時間で実行できます。

まず、空のセットHを作成します。L1をループして、各要素をHに挿入します。

次に、L2をループします。L2の各要素について、その要素がHにない場合に限り、ベクトルに追加します。

Hが定数時間の挿入とアクセスを提供し、定数時間の追加構造を使用して一時的な結果を格納する場合、アルゴリズム全体はリストのサイズの合計で線形になります。

Answer 3

O(n^2)最初のリストの各要素を2番目のリストの各要素と比較する必要があるため、単純なアプローチを採用します。

もう少し良いアプローチは、リスト（O(n*log(n))）を並べ替えてから、リストを反復処理することです。それらがソートされている場合、必要なパスは1つだけなので、時間はO(n*log(n))です。

さらに良いアプローチは、2番目のリストのすべての要素を（）に挿入しstd::unordered_set、O(n)最初のリスト（）の各要素を反復処理して、O(n)それがセットに含まれているかどうかを確認することです（O(1)償却時間）。これでうまくいくはずです。-これは、重複がない場合にのみ機能します。

Answer 4

ソートされていない場合のO（n ^ 2）ナイーブな方法でそれを実行したい場合は、少しのトリック<algorithm>とstd::bind（またはオプションでない場合はブースト）トリックでそれを実行できます。

#include <list>
#include <algorithm>
#include <iostream>
#include <functional>
#include <iterator>

int main() {
  std::list<std::string> a = {"foo", "bar", "baz", "woof"},
                         b = {"baz", "bar", "random other thing"};

  a.erase(std::remove_if(a.begin(), a.end(), std::bind(std::equal_to<std::list<std::string>::iterator>(), b.end(), std::bind(std::find<std::list<std::string>::iterator, std::string>, b.begin(), b.end(), std::placeholders::_1))), a.end());

  std::copy(a.begin(), a.end(), std::ostream_iterator<std::string>(std::cout, "\n"));
}