あるベクトルが別のベクトルのサブセットであるかどうかを確認するにはどうすればよいですか？

Question

現在、私の最良の選択肢は、std :: set_intersectionを使用してから、小さな入力のサイズがset_intersectionで満たされた要素の数と同じかどうかを確認することだと思います。

より良い解決策はありますか？

Answer 1

これを試して：

if (std::includes(set_one.begin(), set_one.end(),
                  set_two.begin(), set_two.end()))
{
// ...
}

約 （）を含む.

include（）アルゴリズムは2つのソートされたシーケンスを比較し、範囲のすべての要素[start2、finish2）が範囲[start1、finish1）に含まれている場合にtrueを返します。それ以外の場合はfalseを返します。 （）は、シーケンスが演算子<（）を使用してソートされるか、Predicate compを使用してソートされていることを想定しています。

走ります

最大で（（finish1 -start1） +（finish2 -start2）） * 2-1比較が実行されます。

プラスO（nlog（n））ベクトルのソート用。あなたはそれよりも速くそれを手に入れることはありません。