Comment puis-je vérifier si un vecteur est un sous-ensemble de l'autre?

Actuellement, je pense que ma meilleure option est d'utiliser std::set_intersection, et de vérifier ensuite si la taille de l'entrée la plus petite est le même que le nombre d'éléments rempli par set_intersection.

Est-il une meilleure solution?

InformationsquelleAutor deworde | 2010-11-01
  1. 37

    Essayez ceci:

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

    Sur comprend().

    Les includes() algorithme compare les deux
    séquences triées et renvoie true si
    chaque élément de l'intervalle [start2,
    finish2) est contenue dans la gamme
    [start1, finish1). Elle retourne false
    sinon. comprend() suppose que l'
    les séquences sont triés à l'aide de
    l'opérateur<(), ou en utilisant le prédicat
    comp.

    s'exécute dans

    À la plupart des ((finish1 - start1) + (finish2
    - start2)) * 2 - 1 les comparaisons sont effectuées.

    Plus O(nlog(n)) pour le tri des vecteurs. Vous n'aurez pas plus vite que ça.

    • Je crois que std::set_intersection va effectuer la même que ci-dessus (c'est à dire (2 * (count1 + count2)) - 1 opérations)
    • Bien pire des cas est le même, mais si le résultat est false, comprend fera du travail beaucoup plus rapide. Et vous avez aussi un vecteur dans l'intersection. Comme les noms l'indiquent set_intersection devraient être utilisées pour la constatation de cette intersection et comprend pour vérifier si un ensemble est sous-ensemble de l'autre.
    • si vos données sont dans std::set vous pouvez utiliser std::set_difference
    • set_intersection et set_difference sont symétriques des opérations de comprend est asymétrique. Ils ne peuvent pas être substitués les uns aux autres.
    InformationsquelleAutor Klark