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

Question

現在、std::set_intersection を使用し、小さい方の入力のサイズが set_intersection によって埋められた要素の数と同じかどうかを確認するのが最善の方法だと思います。

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

Answer 1

これを試して：

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

include （）について。

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

で実行されます

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

さらに、ベクトルをソートするためのO（nlog（n））。それより速くなることはありません。