Quel est le moyen le plus efficace pour effacer les doublons et sortinger un vecteur?

Je suis d’accord avec R. Pate et Todd Gardner ; un std::set pourrait être une bonne idée ici. Même si vous utilisez des vecteurs, si vous avez suffisamment de doublons, vous feriez mieux de créer un ensemble pour faire le sale boulot.

Comparons trois approches:

Juste en utilisant le vecteur, sortinger + unique

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

Convertir en set (manuellement)

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

Convertir en set (en utilisant un constructeur)

 set s( vec.begin(), vec.end() ); vec.assign( s.begin(), s.end() ); 

Voici comment cela fonctionne, car le nombre de doublons change:

Résumé : lorsque le nombre de doublons est suffisant, la conversion en un ensemble est plus rapide, puis les données sont renvoyées dans un vecteur .

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

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

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

J’ai refait le profil de Nate Kohl et obtenu des résultats différents. Pour mon cas de test, le sorting direct du vecteur est toujours plus efficace que l’utilisation d’un ensemble. J’ai ajouté une nouvelle méthode plus efficace, en utilisant un unordered_set .

Gardez à l’esprit que la méthode unordered_set ne fonctionne que si vous avez une bonne fonction de hachage pour le type dont vous avez besoin unifié et sortingé. Pour les ints, c’est facile! (La bibliothèque standard fournit un hachage par défaut qui est simplement la fonction d’identité.) De plus, n’oubliez pas de sortinger à la fin car unordered_set est, eh bien, non ordonné 🙂

J’ai fait quelques recherches dans l’implémentation de set et unordered_set et j’ai découvert que le constructeur construisait réellement un nouveau nœud pour chaque élément, avant de vérifier sa valeur pour déterminer s’il devait être inséré (au moins dans l’implémentation de Visual Studio).

Voici les 5 méthodes:

f1: Juste en utilisant vector , sort + unique

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

f2: Convertir en set (en utilisant un constructeur)

 set s( vec.begin(), vec.end() ); vec.assign( s.begin(), s.end() ); 

f3: convertir en set (manuellement)

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

f4: Convertir en unordered_set (en utilisant un constructeur)

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

f5: Convertir en unordered_set (manuellement)

 unordered_set 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 ints choisi au hasard dans les gammes [1,10], [1,1000] et [1,100000]

Les résultats (en secondes, 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 

Je ne suis pas sûr de ce que vous utilisez, donc je ne peux pas le dire avec une certitude de 100%, mais normalement, quand je pense à un conteneur “sortingé, unique”, je pense à un std :: set . Cela pourrait convenir mieux à votre casse-tête:

 std::set foos(vec.begin(), vec.end()); // both sorted & unique already 

Sinon, le sorting avant d’appeler unique (comme indiqué dans les autres réponses) est la solution.

std::unique ne fonctionne que sur des exécutions consécutives d’éléments en double, vous feriez donc mieux de sortinger en premier. Cependant, il est stable, votre vecteur restra donc sortingé.

Voici un modèle pour le faire pour vous:

 template void removeDuplicates(std::vector& vec) { std::sort(vec.begin(), vec.end()); vec.erase(std::unique(vec.begin(), vec.end()), vec.end()); } 

appelez ça comme:

 removeDuplicates(vectorname); 

L’efficacité est un concept compliqué. Il y a des considérations de temps et d’espace, ainsi que des mesures générales (où vous n’obtenez que des réponses vagues telles que O (n)) par rapport à des mesures spécifiques (par exemple, le sorting par bulles peut être beaucoup plus rapide que le sorting rapide).

Si vous avez relativement peu de doublons, alors sortingez suivi par unique et effacer semble être la voie à suivre. Si vous aviez un nombre relativement important de doublons, créer un ensemble à partir du vecteur et le laisser se soulever pourrait facilement le battre.

Ne vous concentrez pas uniquement sur l’efficacité du temps. Sort + unique + erase fonctionne dans l’espace O (1), tandis que la construction de l’ensemble opère dans l’espace O (n). Et ni l’une ni l’autre ne se prête directement à une parallélisation avec réduction de la carte (pour des ensembles de données vraiment énormes ).

Si vous ne souhaitez pas modifier l’ordre des éléments, vous pouvez essayer cette solution:

 template  void RemoveDuplicatesInVector(std::vector & vec) { set values; vec.erase(std::remove_if(vec.begin(), vec.end(), [&](const T & value) { return !values.insert(value).second; }), vec.end()); } 

Vous devez le sortinger avant d’appeler unique car unique ne supprime que les doublons côte à côte.

edit: 38 secondes …

unique ne supprime que les éléments dupliqués consécutifs (ce qui est nécessaire pour qu’il s’exécute en temps linéaire), vous devez donc d’abord effectuer le sorting. Il restra sortingé après l’appel à l’ unique .

Comme déjà indiqué, unique nécessite un conteneur sortingé. De plus, unique ne supprime pas réellement les éléments du conteneur. Au lieu de cela, ils sont copiés à la fin, unique retourne un iterator pointant vers le premier élément dupliqué de ce type, et vous devez appeler erase pour supprimer les éléments.

L’approche standard proposée par Nate Kohl, en utilisant simplement vector, sort + unique:

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

ne fonctionne pas pour un vecteur de pointeurs.

Regardez attentivement cet exemple sur cplusplus.com .

Dans leur exemple, les “soi-disant doublons” déplacés à la fin sont affichés comme suit: (valeurs non définies), car les “soi-disant doublons” sont parfois des “éléments supplémentaires” et certains éléments “manquants” se trouvaient dans le vecteur d’origine.

Un problème survient lors de l’utilisation de std::unique() sur un vecteur de pointeurs vers des objects (memory leaks, mauvaise lecture des données HEAP, libérations en double, qui provoquent des erreurs de segmentation, etc.).

Voici ma solution au problème: remplacer std::unique() par ptgi::unique() .

Voir le fichier ptgi_unique.hpp ci-dessous:

 // ptgi::unique() // // Fix a problem in std::unique(), such that none of the original elts in the collection are lost or duplicate. // ptgi::unique() has the same interface as std::unique() // // There is the 2 argument version which calls the default operator== to compare elements. // // There is the 3 argument version, which you can pass a user defined functor for specialized comparison. // // ptgi::unique() is an improved version of std::unique() which doesn't looose any of the original data // in the collection, nor does it create duplicates. // // After ptgi::unique(), every old element in the original collection is still present in the re-ordered collection, // except that duplicates have been moved to a contiguous range [dupPosition, last) at the end. // // Thus on output: // [begin, dupPosition) range are unique elements. // [dupPosition, last) range are duplicates which can be removed. // where: // [] means inclusive, and // () means exclusive. // // In the original std::unique() non-duplicates at end are moved downward toward beginning. // In the improved ptgi:unique(), non-duplicates at end are swapped with duplicates near beginning. // // In addition if you have a collection of ptrs to objects, the regular std::unique() will loose memory, // and can possibly delete the same pointer multiple times (leading to SEGMENTATION VIOLATION on Linux machines) // but ptgi::unique() won't. Use valgrind(1) to find such memory leak problems!!! // // NOTE: IF you have a vector of pointers, that is, std::vector, then upon return from ptgi::unique() // you would normally do the following to get rid of the duplicate objects in the HEAP: // // // delete objects from HEAP // std::vector objects; // for (iter = dupPosition; iter != objects.end(); ++iter) // { // delete (*iter); // } // // // shrink the vector. But Object * pointers are NOT followed for duplicate deletes, this shrinks the vector.size()) // objects.erase(dupPosition, objects.end)); // // NOTE: But if you have a vector of objects, that is: std::vector 

Et voici le programme UNIT Test que j’ai utilisé pour le tester:

 // QUESTION: in test2, I had trouble getting one line to comstack,which was caused by the declaration of operator() // in the equal_to Predicate. I'm not sure how to correctly resolve that issue. // Look for //OUT lines // // Make sure that NOTES in ptgi_unique.hpp are correct, in how we should "cleanup" duplicates // from both a vector (test1()) and vector (test2). // Run this with valgrind(1). // // In test2(), IF we use the call to std::unique(), we get this problem: // // [dbednar@ipeng8 TestSortRoutes]$ ./Main7 // TEST2: ORIG nums before UNIQUE: 10, 20, 21, 22, 30, 31, 23, 24, 11 // TEST2: modified nums AFTER UNIQUE: 10, 20, 30, 23, 11, 31, 23, 24, 11 // INFO: dupInx=5 // TEST2: uniq = 10 // TEST2: uniq = 20 // TEST2: uniq = 30 // TEST2: uniq = 33427744 // TEST2: uniq = 33427808 // Segmentation fault (core dumped) // // And if we run valgrind we seen various error about "read errors", "mismatched free", "definitely lost", etc. // // valgrind --leak-check=full ./Main7 // ==359== Memcheck, a memory error detector // ==359== Command: ./Main7 // ==359== Invalid read of size 4 // ==359== Invalid free() / delete / delete[] // ==359== HEAP SUMMARY: // ==359== in use at exit: 8 bytes in 2 blocks // ==359== LEAK SUMMARY: // ==359== definitely lost: 8 bytes in 2 blocks // But once we replace the call in test2() to use ptgi::unique(), all valgrind() error messages disappear. // // 130212 dpb dbednar@ptgi.com created // ========================================================================================================= #include  // std::cout, std::cerr #include  #include  // std::vector #include  // std::ossortingngstream #include  // std::unique() #include  // std::equal_to(), std::binary_function() #include  // assert() MACRO #include "ptgi_unique.hpp" // ptgi::unique() // Integer is small "wrapper class" around a primitive int. // There is no SETTER, so Integer's are IMMUTABLE, just like in JAVA. class Integer { private: int num; public: // default CTOR: "Integer zero;" // COMPRENSIVE CTOR: "Integer five(5);" Integer( int num = 0 ) : num(num) { } // COPY CTOR Integer( const Integer& rhs) : num(rhs.num) { } // assignment, operator=, needs nothing special... since all data members are primitives // GETTER for 'num' data member // GETTER' are *always* const int getNum() const { return num; } // NO SETTER, because IMMUTABLE (similar to Java's Integer class) // @return "num" // NB: toSsortingng() should *always* be a const method // // NOTE: it is probably more efficient to call getNum() intead // of toSsortingng() when printing a number: // // BETTER to do this: // Integer five(5); // std::cout << five.getNum() << "\n" // than this: // std::cout << five.toString() << "\n" std::string toString() const { std::ostringstream oss; oss << num; return oss.str(); } }; // convenience typedef's for iterating over std::vector typedef std::vector::iterator IntegerVectorIterator; typedef std::vector::const_iterator ConstIntegerVectorIterator; // convenience typedef's for iterating over std::vector typedef std::vector::iterator IntegerStarVectorIterator; typedef std::vector::const_iterator ConstIntegerStarVectorIterator; // functor used for std::unique or ptgi::unique() on a std::vector // Two numbers equal if, when divided by 10 (integer division), the quotients are the same. // Hence 50..59 are equal, 60..69 are equal, etc. struct IntegerEqualByTen: public std::equal_to { bool operator() (const Integer& arg1, const Integer& arg2) const { return ((arg1.getNum()/10) == (arg2.getNum()/10)); } }; // functor used for std::unique or ptgi::unique on a std::vector // Two numbers equal if, when divided by 10 (integer division), the quotients are the same. // Hence 50..59 are equal, 60..69 are equal, etc. struct IntegerEqualByTenPointer: public std::equal_to { // NB: the Integer*& looks funny to me! // TECHNICAL PROBLEM ELSEWHERE so had to remove the & from *& //OUT bool operator() (const Integer*& arg1, const Integer*& arg2) const // bool operator() (const Integer* arg1, const Integer* arg2) const { return ((arg1->getNum()/10) == (arg2->getNum()/10)); } }; void test1(); void test2(); void printIntegerStarVector( const std::ssortingng& msg, const std::vector& nums ); int main() { test1(); test2(); return 0; } // test1() uses a vector 

About alexK7 benchmarks. I sortinged them and got similar results, but when the range of values is 1 million the cases using std::sort (f1) and using std::unordered_set (f5) produce similar time. When the range of values is 10 million f1 is faster than f5.

If the range of values is limited and the values are unsigned int, it is possible to use std::vector, the size of which corresponds to the given range. Voici le code:

 void DeleteDuplicates_vector_bool(std::vector& v, unsigned range_size) { std::vector v1(range_size); for (auto& x: v) { v1[x] = true; } v.clear(); unsigned count = 0; for (auto& x: v1) { if (x) { v.push_back(count); } ++count; } } 

Here’s the example of the duplicate delete problem that occurs with std::unique(). On a LINUX machine, the program crashes. Read the comments for details.

 // Main10.cpp // // Illustration of duplicate delete and memory leak in a vector after calling std::unique. // On a LINUX machine, it crashes the progam because of the duplicate delete. // // INPUT : {1, 2, 2, 3} // OUTPUT: {1, 2, 3, 3} // // The two 3's are actually pointers to the same 3 integer in the HEAP, which is BAD // because if you delete both int* pointers, you are deleting the same memory // location twice. // // // Never mind the fact that we ignore the "dupPosition" returned by std::unique(), // but in any sensible program that "cleans up after istelf" you want to call deletex // on all int* poitners to avoid memory leaks. // // // NOW IF you replace std::unique() with ptgi::unique(), all of the the problems disappear. // Why? Because ptgi:unique merely reshuffles the data: // OUTPUT: {1, 2, 3, 2} // The ptgi:unique has swapped the last two elements, so all of the original elements in // the INPUT are STILL in the OUTPUT. // // 130215 dbednar@ptgi.com //============================================================================ #include  #include  #include  #include  #include "ptgi_unique.hpp" // functor used by std::unique to remove adjacent elts from vector struct EqualToVectorOfIntegerStar: public std::equal_to { bool operator() (const int* arg1, const int* arg2) const { return (*arg1 == *arg2); } }; void printVector( const std::ssortingng& msg, const std::vector& vnums); int main() { int inums [] = { 1, 2, 2, 3 }; std::vector vnums; // convert C array into vector of pointers to integers for (size_t inx = 0; inx < 4; ++ inx) vnums.push_back( new int(inums[inx]) ); printVector("BEFORE UNIQ", vnums); // INPUT : 1, 2A, 2B, 3 std::unique( vnums.begin(), vnums.end(), EqualToVectorOfIntegerStar() ); // OUTPUT: 1, 2A, 3, 3 } printVector("AFTER UNIQ", vnums); // now we delete 3 twice, and we have a memory leak because 2B is not deleted. for (size_t inx = 0; inx < vnums.size(); ++inx) { delete(vnums[inx]); } } // print a line of the form "msg: 1,2,3,..,5,6,7\n", where 1..7 are the numbers in vnums vector // PS: you may pass "hello world" (const char *) because of implicit (automatic) conversion // from "const char *" to std::string conversion. void printVector( const std::string& msg, const std::vector& vnums) { std::cout << msg << ": "; for (size_t inx = 0; inx < vnums.size(); ++inx) { // insert comma separator before current elt, but ONLY after first elt if (inx > 0) std::cout << ","; std::cout << *vnums[inx]; } std::cout << "\n"; } 

 std::set s; std::for_each(v.cbegin(), v.cend(), [&s](int val){s.insert(val);}); v.clear(); std::copy(s.cbegin(), s.cend(), v.cbegin()); 

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

If you are looking for performance and using std::vector , I recommend the one that this documentation link provides.

 std::vector myvector{10,20,20,20,30,30,20,20,10}; // 10 20 20 20 30 30 20 20 10 std::sort(myvector.begin(), myvector.end() ); const auto& it = std::unique (myvector.begin(), myvector.end()); // 10 20 30 ? ? ? ? ? ? // ^ myvector.resize( std::distance(myvector.begin(),it) ); // 10 20 30 

If you don’t want to modify the vector (erase, sort) then you can use the Newton library , In the algorithm sublibrary there is a function call, copy_single

 template  void copy_single( INPUT_ITERATOR first, INPUT_ITERATOR last, std::vector &v ) 

so You can:

 std::vector copy; // empty vector newton::copy_single(first, last, copy); 

where copy is the vector in where you want to push_back the copy of the unique elements. but remember you push_back the elements, and you don’t create a new vector

anyway, this is faster because you don’t erase() the elements (which takes a lot of time, except when you pop_back(), because of reassignment)

I make some experiments and it’s faster.

Also, you can use:

 std::vector copy; // empty vector newton::copy_single(first, last, copy); original = copy; 

sometimes is still faster.

 void EraseVectorRepeats(vector  & v){ TOP:for(int y=0; y 

This is a function that I created that you can use to delete repeats. The header files needed are just and .