Le moyen le plus efficace pour effacer les doublons et trier un vecteur c ++?

Question

J'ai besoin de prendre un C++ vecteur avec potentiellement un grand nombre d'éléments, d'effacer les doublons, et de les trier. Ressemble à ce code fera l'affaire: (Correction--il ne sera pas; la prochaine fois que je vais la tester avant de la poster. Merci pour les commentaires.)

vec.erase(
      std::unique(vec.begin(), vec.end()),
      vec.end());
std::sort(vec.begin(), vec.end());

Est-il plus rapide pour effacer les doublons première (codé ci-dessus) ou effectuer le tri en premier? Si je ne effectuer le tri d'abord, est-il assuré de rester triés après std::unique est exécuté?

Ou est-il un moyen plus efficace pour faire tout cela?

Answer 1

Je suis d'accord avec R. Pate et Todd Gardner; un std::set pourrait être une bonne idée ici. Même si vous êtes coincé à l'aide de vecteurs, si vous avez assez de doublons, vous pourriez être mieux de créer un jeu pour faire le sale travail.

Nous allons comparer trois approches:

Juste à l'aide de vecteur, de tri + unique

sort( vec.begin(), vec.end() );
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );

Convertir pour définir (manuellement)

set<int> s;
unsigned size = vec.size();
for( unsigned i = 0; i < size; ++i ) s.insert( vec[i] );
vec.assign( s.begin(), s.end() );

Convertir pour définir (à l'aide d'un constructeur)

set<int> s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );

Voici comment effectuer ces que le nombre de doublons changements:

Résumé: lorsque le nombre de doublons est assez grand, il est effectivement plus rapide de convertir un ensemble et puis vidage des données de retour dans un vecteur.

Et pour une raison de faire la conversion manuellement semble être plus rapide que d'utiliser le constructeur d'ensemble, au moins sur le jouet des données aléatoires que j'ai utilisé.

Answer 2

J'ai refait Nate Kohl's de profilage et a obtenu des résultats différents. Pour mon cas de test, directement tri le vecteur est toujours plus efficace que l'utilisation d'un ensemble. J'ai ajouté une nouvelle méthode plus efficace, à l'aide d'un unordered_set.

Gardez à l'esprit que la unordered_set méthode ne fonctionne que si vous avez une bonne fonction de hachage pour le type dont vous avez besoin uniqued et triés. Pour les entiers, c'est facile! (La bibliothèque standard fournit un hachage par défaut qui est tout simplement l'identité de la fonction.) Aussi, n'oubliez pas de tri à la fin, car unordered_set est, ainsi, non ordonnée :)

J'ai fait quelques recherches à l'intérieur de l'ensemble et unordered_set mise en œuvre et a découvert que le constructeur en fait la construction d'un nouveau nœud pour chaque élément, avant de vérifier sa valeur pour déterminer si elle devrait en fait être inséré (dans Visual Studio de la mise en œuvre, au moins).

Voici les 5 méthodes:

f1: Juste à l'aide de vecteur, de tri + unique

sort( vec.begin(), vec.end() );
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );

f2: Convertir (à l'aide d'un constructeur)

set<int> s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );

f3: Convertir (manuellement)

set<int> s;
for (int i : vec)
    s.insert(i);
vec.assign( s.begin(), s.end() );

f4: Convertir unordered_set (à l'aide d'un constructeur)

unordered_set<int> s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );
sort( vec.begin(), vec.end() );

f5: Convertir unordered_set (manuellement)

unordered_set<int> s;
for (int i : vec)
    s.insert(i);
vec.assign( s.begin(), s.end() );
sort( vec.begin(), vec.end() );

J'ai fait le test avec un vecteur de 100 000 000 d'entiers choisis au hasard dans l'intervalle [1,10], [1,1000], et [1,100000]

Les résultats (en secondes, le plus petit est mieux):

range         f1       f2       f3       f4      f5
[1,10]      1.6821   7.6804   2.8232   6.2634  0.7980
[1,1000]    5.0773  13.3658   8.2235   7.6884  1.9861
[1,100000]  8.7955  32.1148  26.5485  13.3278  3.9822

Answer 3

std :: unique ne supprime que les éléments en double s'ils sont voisins: vous devez d'abord trier le vecteur avant qu'il ne fonctionne comme prévu.

std :: unique est défini pour être stable, donc le vecteur sera toujours trié après son exécution unique.

Answer 4

Je ne sais pas ce que vous utilisez cela pour, donc je ne peux pas dire avec certitude à 100 %, mais normalement quand je pense conteneur « trié, unique », je pense un std::set. Il pourrait être un meilleur ajustement pour votre usecase :

Sinon, le tri avant d’appeler uniques (comme les autres réponses soulignés) est le chemin à parcourir.

Answer 5

``ne fonctionne que sur des essais consécutifs des éléments en double, donc vous feriez mieux trie d’abord. Toutefois, il est stable, donc votre vecteur restera triée.