c++ - 同じオブジェクトへのポインターの 2 つのセットの違いを見つける

Question

同じオブジェクトへの 2 つのポインターのセットの違いを見つけるにはどうすればよいですか?

両方のセットのすべてのオブジェクトを反復せずに効率的な方法はありますか?

私はこれらのセットの2つを持っています:

std::set<Object*>

オブジェクトのプライベート メンバー(名前) が他のオブジェクト名と同じ場合、それはオブジェクトが同じであることを意味します。

Answer 1

STLのアルゴリズムライブラリは素晴らしく、拡張可能で、十分に活用されていません。

これにより、セットの差がベクトルとして得られます（これをセットに変換できると思いますが、少なくとも要求した内容については必要ありません。セットは既にソートされているため、ベクトルの方が高速です）。

template<typename T>
std::vector<T> set_diff(std::set<T> const &a, std::set<T> const &b) {
    std::vector v<T>;
    std::set_difference(a.begin(), a.end(), b.begin(), b.end(), v.begin());
    return v;
}

オプションで、コンストラクターの後に置きます

    v.reserve(a.size() + b.size());

帰国前（C ++ 11）

    v.shrink_to_fit();

注a：これにより、にないアイテムが生成されbます。2つのうちの一方にあるすべてのアイテムを検索し、もう一方には検索しない場合は、std::set_symmetric_difference代わりにを使用します。

Answer 2

あなたが違うと思うのは、1つのセットにしか現れないポインター要素を見つけることだと思います。最も効率的な方法は、2 つのセットを同期的に反復することです。これには O(n+m) 時間しかかかりません。ここで、n、m は 2 つのセットのサイズを示し、一般に問題の下限です。

幸いなことに、STL コンテナー セットはバランスのとれた二分探索木をベースとして使用するため、すべての要素を線形時間で順番に反復できるため、O(n+m) を実現できます。

template<typename T>
std::vector<T> set_diff(std::set<T> const &a, std::set<T> const &b) {
  std::vector<T> v;
  auto ita = a.begin();
  auto itb = b.begin();
  while (ita != a.end() && itb != b.end()) {
    if (*ita == *itb) {
      ++ita, ++itb;
    } else if (*ita < *itb) {
      v.push_back(*ita);
      ++ita;
    } else {
      v.push_back(*itb);
      ++itb;
    }
  }
  for (; ita != a.end(); v.push_back(*ita), ++ita);
  for (; itb != b.end(); v.push_back(*itb), ++itb);
  return v;
}