c++ - 反復なしで 2 番目のセットに含まれる最初のセット要素から要素を削除する

Question

2組のペアがあります（c++ 11は使用できません）

std::set<std::pair<int,int> > first;
std::set<std::pair<int,int> > second;

そして、最初のセットから2番目のセットにあるすべての要素を削除する必要があります(最初に削除する2番目の要素が含まれている場合)。2番目のセットを反復することでこれを行うことができます.最初の要素から同じ要素を消去する場合、反復せずにこれを行う方法はありますか?

Answer 1

私の理解が正しければ、基本的には、1 番目と 2 番目の差を計算する必要があります。<algorithm>そのための機能があります。

std::set<std::pair<int, int>> result;
std::set_difference(first.begin(), first.end(), second.begin(), second.end(), inserter(result, result.end()));

Answer 2

反復せずにこれを行う方法はあるのだろうか。

いいえ。内部的には、セットはバランスの取れたバイナリ ツリーです。構造を反復せずにセットを操作する方法はありません。(コードの利便性ではなく、実装の効率性に関心があると思われるため、内部で反復する必要があるライブラリ ルーチンを意図的に無視しました)。

ただし、セットはソートされているため、各要素の反復とルックアップの代わりに、各要素を反復して削除することができます (したがって、操作の数はセットサイズの合計です)。他のセットの要素数の底 2 の対数を繰り返しています)。セットの 1 つが他のセットよりもはるかに小さい場合にのみ、反復/検索アプローチが勝ちます。ライブラリのset_difference関数の実装 (Amen の回答に記載) を見ると、2 つの反復を適切に行う方法が示されているはずです。

より効率的なものが必要な場合は、以前にそれを達成する方法を考える必要があります。たとえば、ペアを同じサイズの 2 次元マトリックスにフラグとして格納し、2 番目のセットの否定と AND を使用できるようにします。それが実用的かどうかは、保存している int 値の範囲、必要なメモリ量が目的に合っているかどうかによって異なります....

Answer 3

はい、できます。

検出するだけでなく、削除する場合は、別の<algorithm>関数remove_copy_if()を使用します。

http://www.cplusplus.com/reference/algorithm/remove_copy_if/

私見では。それがどのように機能するかを理解することはそれほど難しくありません。