Come posso controllare se un vettore è un sottoinsieme di un altro?

Question

Al momento, penso che la mia migliore opzione è quella di utilizzare std :: set_intersection, e quindi controllare se la dimensione dell'ingresso minore è lo stesso del numero di elementi riempite da set_intersection.

C'è una soluzione migliore?

Answer 1

Prova questo:

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

include () .

  

Il include () algoritmo confronta due   sequenze ordinate e restituisce true se   ogni elemento nell'intervallo [START2,   finish2) è contenuta nell'intervallo   [Start1, Finish1). Restituisce false   altrimenti. include () assume che la   sequenze vengono ordinati usando   operatore <(), oppure utilizzando il predicato   comp.

viene eseguito in

  

Al massimo ((Finish1 - start1) + (finish2   - start2)) * 2 -. 1 vengono eseguite comparazioni

Inoltre O (nlog (n)) per l'ordinamento vettori. Non si ottiene è più veloce di così.