Comment puis-je vérifier si deux std::vector est uniquement contenir les mêmes éléments?

J'ai besoin d'un algorithme ou d'une bibliothèque standard la fonction de comparaison de deux éléments vectoriels, comme ci-dessous:

class Utility
{
    template <class T>
    static bool CheckIfVectorsEquivalent(   const std::vector<T> & Vec1,
                                            const std::vector<T> & Vec2)
    {
        //???
    }
};

De travail en vertu de l'spécifications suivantes:

std::vector<int> v1, v2, v3, v4, v5, v6, v7, v8;

//Returns false when not all the elements are matching between vectors
v1.push_back(1);
v1.push_back(3);
v1.push_back(5);
v2.push_back(2);
v2.push_back(3);
v2.push_back(8);
Utility::CheckIfVectorsEquivalent(v1, v2);  //Must return false

//Returns true when all the elements match, even if the are not in the same order
v3.push_back(3);
v3.push_back(1);
v3.push_back(7);
v4.push_back(7);
v4.push_back(3);
v4.push_back(1);
Utility::CheckIfVectorsEquivalent(v3, v4);  //Must return true

//Returns false when one of the vectors is subset of the other one
v5.push_back(3);
v5.push_back(1);
v5.push_back(7);
v6.push_back(7);
v6.push_back(3);
v6.push_back(1);
v6.push_back(18);
v6.push_back(51);
Utility::CheckIfVectorsEquivalent(v5, v6);  //Must return false

//Returns true when the both vectors are empty
Utility::CheckIfVectorsEquivalent(v7, v8);  //Must return true

Est-il standard (avec TSL) manière de procéder? Si non, comment puis-je écrire cet algorithme? Il me confond trop.

OriginalL'auteur hkBattousai | 2012-05-08

  1. 17

    Le standard sera le tri de ces deux vecteurs et de l'aide de l'opérateur ==, qui compare les valeurs correspondantes.

    La solution de l'échantillon à la réalisation de cet algorithme est:

    #include <vector>
#include <algorithm>

template<typename T>
bool compare(std::vector<T>& v1, std::vector<T>& v2)
{
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());
    return v1 == v2;
}

    Sa complexité est O(n*log(n)), en raison de la tri.

    Faire un O(n^2) comparaison de ce que pourrait être le plus rapide pour de très petites séries, mais seulement pour de petits ensembles. Cette réponse est exacte pour 99% du temps.
    "C'est aussi la manière la plus rapide possible de l'algorithme de" la Preuve?
    Pas d'utilisation de jeux ou d'autres choses du genre, mais simplement de tri des vecteurs vient de mon expérience. De la complexité du point de vue de ce est O(n log n). Cela signifie, que vous avez (sans autres hypothèses) de reconnaître n! différents vecteurs de l'égalité, et la taille de l'arbre de décision est log(n!) = Omega(n log n). Plus précis de la preuve peut en être fait de même pour le tri à la limite inférieure.
    Et il y a O(N) dans le meilleur des cas sortes. Comme je l'ai dit "la plus rapide possible" n'est pas une garantie et de l'OMI doit être supprimé.
    Vous venez de vous faire de l'intimidation en changeant une seule mauvaise réponse dans un autre, pire réponse? Votre réponse encore n'a de sens qu'avec une commande, mais maintenant que vous avez retiré une intéressante (et corriger) commentaire sur la complexité dans ce cas.

    OriginalL'auteur Rafał Rawicki

  2. 11

    Si vous pouvez vivre avec juste un c++11 solution, alors std::is_permutation est exactement ce que vous voulez

    template <class FI1, class FI2>
bool is_permutation ( FI1 first, FI1 last, FI2 d_first );

    Si vous ne pouvez pas faire cela, alors à la prochaine boost 1.50 libération, il y aura

    boost::algorithm::is_permutation

    avec la même interface.

    La norme dit, que std::is_permutation, comparer les éléments au plus O(n^2), donc c'est probablement plus lent, mais c'est court à écrire.
    Il est O(N^2).
    Je pense que c'est la meilleure réponse, car elle ne permet pas de faire des hypothèses de commande sur le type T.
    Certainement O(N^2) dans le pire des cas, mais il n'utilise pas de mémoire supplémentaire.

    OriginalL'auteur Marshall Clow

  3. 3

    Créer un multiset de chaque vecteur, puis il suffit de comparer pour l'égalité.

    OriginalL'auteur Alan Stokes

  4. 0

    Il y a un O(n), solution à ce problème de non triés entrées:

    #include <vector>
#include <algorithm>
#include <iostream>
#include <boost/function_output_iterator.hpp>

template <typename T>
T xorfunc(const T& a, const T& b) {
  return a^b;
}

template <typename T>
bool compare(const std::vector<T>& v1, const std::vector<T>& v2) {
  if (v1.size() != v2.size())
    return false;

  T result = 0;
  std::transform(v1.begin(), v1.end(), v2.begin(), boost::make_function_output_iterator([&result](const T& r) { result ^= r; }), std::ptr_fun(&xorfunc<T>));
  return !result;
}

    qui fonctionne pour entier entrées et exploite le fait que a ^ b ^ c ^ d == 0 pour toute combinaison de paires de valeurs. Il ne sera jamais à donner de faux négatifs, il pourrait donner de faux positifs potentiellement, mais vous pouvez réduire les autres en O(n) l'espace/temps. Si vous êtes souvent frapper négatifs, alors ce pourrait être utile comme un pré-tri+comparer étape à la règle de l'en sortir rapidement. Il fonctionne pour tous les cas de test que vous avez montré:

    int main() {
    std::vector<int> v1, v2, v3, v4, v5, v6, v7, v8;

    //Returns false when not all the elements are matching between vectors
    v1.push_back(1);
    v1.push_back(3);
    v1.push_back(5);
    v2.push_back(2);
    v2.push_back(3);
    v2.push_back(8);
    std::cout << compare(v1, v2) << " (false)" << std::endl;  //Must return false

    //Returns true when all the elements match, even if the are not in the same order
    v3.push_back(3);
    v3.push_back(1);
    v3.push_back(7);
    v4.push_back(7);
    v4.push_back(3);
    v4.push_back(1);
    std::cout << compare(v3, v4) << " (true)" << std::endl;  //Must return true

    //Returns false when one of the vectors is subset of the other one
    v5.push_back(3);
    v5.push_back(1);
    v5.push_back(7);
    v6.push_back(7);
    v6.push_back(3);
    v6.push_back(1);
    v6.push_back(18);
    v6.push_back(51);
    std::cout << compare(v5, v6) << " false" << std::endl;  //Must return false

    //Returns true when the both vectors are empty
    std::cout << compare(v7, v8) << " true" << std::endl;  //Must return true

}

    Donne:

    0 (false) 
1 (vrai) 
0 false 
1 vrai
    Si ils sont triés déjà, vous pouvez simplement utiliser operator== sur les vecteurs.
    Comment est mismatch une amélioration sur le droit à l'égalité après le tri?
    L'itérateur il vous donne vous indique où se situe la différence qui peut/ne peut pas être de l'intérêt
    Il y a des cas où cela renvoie vrai de manière incorrecte.
    À en juger à partir d'un rapide coup d'œil, vous voulez xor de tous les éléments et s'attendre à obtenir de zéro si ils sont tous égaux, non? Voici le problème: Vec1[0, 12]; Vec2[4, 8].

    OriginalL'auteur Flexo

  5. 0

    Façon la plus simple de le faire est de créer des copies de Vec1 et Vec2, de les trier et de les comparer à l'aide de ==.

    Une autre façon de faire est de construire deux multisets de Vec1 et Vec2 et de les comparer à l'aide de ==.

    Encore une autre façon de le faire est d'utiliser les cartes (std::map ou unordered_map) pour stocker des compteurs - c'est à dire incrémenter la valeur stockée pour chaque élément de Vec1 et de décrémentation pour chaque élément stocké de Vec2, puis vérifiez si la carte contient non nulle éléments. Si il y a des non-zéro les éléments stockés dans la carte, les vecteurs sont non-égalité.

    désordre pseudocode exemple:

    std::vector<Value> vec1, vec2;
//initialize vec1 and vec2, fill with data
typedef int Counter;
typedef unordered_map<Value, Counter> CounterMap;

CounterMap counters;
for (size_t i = 0; i < vec1.size(); i++)
    counters[vec1[i]]++;
for (size_t i = 0; i < vec2.size(); i++)
    counters[vec2[i]]--;

bool equal = true;
for (CounterMap::const_iterator i = coutners.begin(); equal && (i != counters.end()); i++)
    if (i->second != 0)
        equal = false;

    Selon votre STL (ou boost) la mise en œuvre, le type de données, et l'ordre des données stockées dans des vecteurs) l'une de ces méthodes sera plus rapide, mais il est difficile de dire lequel.

    Comparaison d'égalité, de non-ordonnée multisets est le pire des cas en O(N^2), de manière sans doute vaut éviter.

    OriginalL'auteur SigTerm

  6. 0

    Si l'on considère un entier à être assez grand pour que les calculs effectués dans l'algorithme suivant, il est un simple algorithme O(N).

    0: initialisation: Il y a de nombres premiers de la taille de max(v1,v2), produit1=1, produit2=1

    1: retourne false si la taille de la v1 != la taille de la v2

    2:

    foreach (  i in v1 ) {
   product1 *= primes[v1[i]]
   product2 *= primes[v2[i]]
}

    3.

    result product1 == product2;

    OriginalL'auteur Captain Giraffe

  7. -1
      v7.push_back(3);
  v7.push_back(1);
  v7.push_back(7);

  v8.push_back(7);
  v8.push_back(3);
  v8.push_back(1);
  v8.push_back(1);
  v8.push_back(7);

  std::cout << compare(v7, v8) << " true or false" << std::endl;

    la condition ci-dessus, la fonction de comparer renvoie true ou false.J'ai perdu le compte.
    si return true.
    nous ne pouvons pas utiliser la voie:
    Le standard sera le tri de ces deux vecteurs et de l'aide de l'opérateur ==, qui compare les valeurs correspondantes.

    OriginalL'auteur bootry