كيف أتحقق مما إذا كان المتجه واحد هو مجموعة فرعية أخرى؟

Question

حاليًا ، أعتقد أن أفضل خياري هو استخدام STD :: set_intersection ، ثم تحقق مما إذا كان حجم الإدخال الأصغر هو نفسه عدد العناصر المملوءة بواسطة set_intersection.

هل هناك حل أفضل؟

Answer 1

جرب هذا:

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

حول يشمل().

تقارن الخوارزمية التي تتضمن () تسلسلتين مصنفين ويعيد صحيحًا إذا كان كل عنصر في النطاق [start2 ، finish2) موجودًا في النطاق [start1 ، finish1). يعود خطأ خلاف ذلك. يتضمن () يفترض أن التسلسلات يتم فرزها باستخدام المشغل <() ، أو باستخدام شركات المسند.

يدير

على الأكثر ((Finish1 - start1) + (Finish2 - start2)) * 2 - 1 يتم إجراء مقارنات.

Plus O (nlog (n)) لفرز المتجهات. لن تحصل عليه أي أسرع من ذلك.