¿Cuál es la forma más eficiente de borrar duplicados y ordenar un vector?

Necesito tomar un vector C ++ con potencialmente muchos elementos, borrar duplicados y ordenarlos.

Actualmente tengo el siguiente código, pero no funciona.

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

¿Cómo puedo hacer esto correctamente?

Además, ¿es más rápido borrar los duplicados primero (similar al código anterior) o realizar primero el tipo? Si realizo primero el tipo, ¿está garantizado que permanecerá ordenado después de que se ejecute std::unique ?

¿O hay otra forma (quizás más eficiente) de hacer todo esto?

Estoy de acuerdo con R. Pate y Todd Gardner ; un std::set podría ser una buena idea aquí. Incluso si está atrapado usando vectores, si tiene suficientes duplicados, sería mejor que creara un conjunto para hacer el trabajo sucio.

Comparemos tres enfoques:

Solo usando vector, ordenar + único

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

Convertir a establecer (manualmente)

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

Convertir a establecer (usando un constructor)

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

Así es como funcionan estos a medida que cambia la cantidad de duplicados:

comparación de vectores y conjuntos de enfoques

Resumen : cuando el número de duplicados es lo suficientemente grande, en realidad es más rápido convertirlo a un conjunto y luego volcar los datos en un vector .

Y por alguna razón, hacer la conversión de conjunto de forma manual parece ser más rápido que usar el constructor de conjunto, al menos en los datos aleatorios de juguete que utilicé.

std::unique solo elimina elementos duplicados si son vecinos: primero debes ordenar el vector antes de que funcione como lo deseas.

std::unique se define como estable, por lo que el vector seguirá ordenándose después de ejecutarse de manera única en él.

Rehice el perfil de Nate Kohl y obtuve resultados diferentes. Para mi caso de prueba, ordenar el vector directamente es siempre más eficiente que usar un conjunto. Agregué un nuevo método más eficiente, usando un unordered_set .

Tenga en cuenta que el método unordered_set solo funciona si tiene una buena función hash para el tipo que necesita uniqued y ordenado. Para los ints, ¡esto es fácil! (La biblioteca estándar proporciona un hash predeterminado, que es simplemente la función de identidad.) Además, no se olvide de ordenar al final, ya que unordered_set está, bueno, desordenado 🙂

Hice algunas excavaciones dentro del set y la implementación unordered_set y descubrí que el constructor realmente construye un nuevo nodo para cada elemento, antes de verificar su valor para determinar si realmente debería insertarse (en la implementación de Visual Studio, al menos).

Aquí están los 5 métodos:

f1: solo usando vector , sort + unique

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

f2: Convertir a set (usando un constructor)

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

f3: Convertir a set (manualmente)

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

f4: Convertir a unordered_set (usando un constructor)

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

f5: Convertir a unordered_set (manualmente)

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

Hice la prueba con un vector de 100,000,000 de ints elegidos al azar en rangos [1,10], [1,1000] y [1,100000]

Los resultados (en segundos, más pequeño es mejor):

 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 

No estoy seguro de para qué estás usando esto, así que no puedo decirlo con 100% de certeza, pero normalmente cuando pienso en un contenedor “ordenado, único”, pienso en un conjunto estándar . Puede ser una mejor opción para su uso:

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

De lo contrario, ordenar antes de llamar es único (como se señaló en las otras respuestas) es el camino a seguir.

std::unique solo funciona en ejecuciones consecutivas de elementos duplicados, por lo que será mejor que primero lo ordene. Sin embargo, es estable, por lo que su vector permanecerá ordenado.

Aquí hay una plantilla para hacerlo por usted:

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

llámalo así:

 removeDuplicates(vectorname); 

La eficiencia es un concepto complicado. Hay consideraciones de tiempo vs. espacio, así como mediciones generales (donde solo obtienes respuestas vagas como O (n)) contra específicas (por ejemplo, la clasificación de burbujas puede ser mucho más rápida que la ordenación rápida, dependiendo de las características de entrada).

Si tiene relativamente pocos duplicados, entonces la ordenación seguida por única y borrada parece ser el camino a seguir. Si tuvieras muchos duplicados, crear un conjunto del vector y dejarlo hacer el trabajo pesado podría superarlo fácilmente.

No se concentre solo en la eficiencia del tiempo tampoco. Sort + unique + erase opera en O (1) espacio, mientras que la construcción del conjunto opera en O (n) espacio. Y tampoco se presta directamente a una paralelización de reducción de mapa (para conjuntos de datos realmente grandes ).

Si no desea cambiar el orden de los elementos, puede probar esta solución:

 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()); } 

Debe ordenarlo antes de llamar a unique porque unique elimina los duplicados que están uno al lado del otro.

editar: 38 segundos …

unique solo elimina elementos duplicados consecutivos (lo cual es necesario para que se ejecute en tiempo lineal), por lo que primero debe realizar el orden. Permanecerá ordenado después de la llamada a unique .

Como ya se dijo, unique requiere un contenedor clasificado. Además, unique no elimina elementos del contenedor. En su lugar, se copian al final, los unique retornan un iterador que apunta al primer elemento duplicado, y se espera que invoque erase para eliminar realmente los elementos.

El enfoque estándar sugerido por Nate Kohl, solo usando vector, sort + unique:

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

no funciona para un vector de punteros.

Mire cuidadosamente este ejemplo en cplusplus.com .

En su ejemplo, los “así llamados duplicados” movidos al final en realidad se muestran como? (valores indefinidos), porque esos “llamados duplicados” son A VECES “elementos extra” y A VECES hay “elementos faltantes” que estaban en el vector original.

Se produce un problema al usar std::unique() en un vector de punteros a objetos (pérdidas de memoria, mala lectura de datos de HEAP, duplicados libres, que causan fallas de segmentación, etc.).

Aquí está mi solución al problema: reemplace std::unique() con ptgi::unique() .

Ver el archivo ptgi_unique.hpp a continuación:

 // 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, then upon return from ptgi::unique(), it // suffices to just call vector:erase(, as erase will automatically call delete on each object in the // [dupPosition, end) range for you: // // std::vector objects; // objects.erase(dupPosition, last); // //========================================================================================================== // Example of differences between std::unique() vs ptgi::unique(). // // Given: // int data[] = {10, 11, 21}; // // Given this functor: ArrayOfIntegersEqualByTen: // A functor which compares two integers a[i] and a[j] in an int a[] array, after division by 10: // // // given an int data[] array, remove consecutive duplicates from it. // // functor used for std::unique (BUGGY) or ptgi::unique(IMPROVED) // // // 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 ArrayOfIntegersEqualByTen: public std::equal_to // { // bool operator() (const int& arg1, const int& arg2) const // { // return ((arg1/10) == (arg2/10)); // } // }; // // Now, if we call (problematic) std::unique( data, data+3, ArrayOfIntegersEqualByTen() ); // // TEST1: BEFORE UNIQ: 10,11,21 // TEST1: AFTER UNIQ: 10,21,21 // DUP_INX=2 // // PROBLEM: 11 is lost, and extra 21 has been added. // // More complicated example: // // TEST2: BEFORE UNIQ: 10,20,21,22,30,31,23,24,11 // TEST2: AFTER UNIQ: 10,20,30,23,11,31,23,24,11 // DUP_INX=5 // // Problem: 21 and 22 are deleted. // Problem: 11 and 23 are duplicated. // // // NOW if ptgi::unique is called instead of std::unique, both problems go away: // // DEBUG: TEST1: NEW_WAY=1 // TEST1: BEFORE UNIQ: 10,11,21 // TEST1: AFTER UNIQ: 10,21,11 // DUP_INX=2 // // DEBUG: TEST2: NEW_WAY=1 // TEST2: BEFORE UNIQ: 10,20,21,22,30,31,23,24,11 // TEST2: AFTER UNIQ: 10,20,30,23,11,31,22,24,21 // DUP_INX=5 // // @SEE: look at the "case study" below to understand which the last "AFTER UNIQ" results with that order: // TEST2: AFTER UNIQ: 10,20,30,23,11,31,22,24,21 // //========================================================================================================== // Case Study: how ptgi::unique() works: // Remember we "remove adjacent duplicates". // In this example, the input is NOT fully sorted when ptgi:unique() is called. // // I put | separatators, BEFORE UNIQ to illustrate this // 10 | 20,21,22 | 30,31 | 23,24 | 11 // // In example above, 20, 21, 22 are "same" since dividing by 10 gives 2 quotient. // And 30,31 are "same", since /10 quotient is 3. // And 23, 24 are same, since /10 quotient is 2. // And 11 is "group of one" by itself. // So there are 5 groups, but the 4th group (23, 24) happens to be equal to group 2 (20, 21, 22) // So there are 5 groups, and the 5th group (11) is equal to group 1 (10) // // R = result // F = first // // 10, 20, 21, 22, 30, 31, 23, 24, 11 // RF // // 10 is result, and first points to 20, and R != F (10 != 20) so bump R: // R // F // // Now we hits the "optimized out swap logic". // (avoid swap because R == F) // // // now bump F until R != F (integer division by 10) // 10, 20, 21, 22, 30, 31, 23, 24, 11 // RF // 20 == 21 in 10x // RF // 20 == 22 in 10x // RF // 20 != 30, so we do a swap of ++R and F // (Now first hits 21, 22, then finally 30, which is different than R, so we swap bump R to 21 and swap with 30) // 10, 20, 30, 22, 21, 31, 23, 24, 11 // after R & F swap (21 and 30) // RF // // 10, 20, 30, 22, 21, 31, 23, 24, 11 // RF // bump F to 31, but R and F are same (30 vs 31) // RF // bump F to 23, R != F, so swap ++R with F // 10, 20, 30, 22, 21, 31, 23, 24, 11 // RF // bump R to 22 // 10, 20, 30, 23, 21, 31, 22, 24, 11 // after the R & F swap (22 & 23 swap) // RF // will swap 22 and 23 // RF // bump F to 24, but R and F are same in 10x // RF // bump F, R != F, so swap ++R with F // RF // R and F are diff, so swap ++R with F (21 and 11) // 10, 20, 30, 23, 11, 31, 22, 24, 21 // RF // aftter swap of old 21 and 11 // RF // F now at last(), so loop terminates // RF // bump R by 1 to point to dupPostion (first duplicate in range) // // return R which now points to 31 //========================================================================================================== // NOTES: // 1) the #ifdef IMPROVED_STD_UNIQUE_ALGORITHM documents how we have modified the original std::unique(). // 2) I've heavily unit tested this code, including using valgrind(1), and it is *believed* to be 100% defect-free. // //========================================================================================================== // History: // 130201 dpb dbednar@ptgi.com created //========================================================================================================== #ifndef PTGI_UNIQUE_HPP #define PTGI_UNIQUE_HPP // Created to solve memory leak problems when calling std::unique() on a vector. // Memory leaks discovered with valgrind and unitTesting. #include  // std::swap // instead of std::myUnique, call this instead, where arg3 is a function ptr // // like std::unique, it puts the dups at the end, but it uses swapping to preserve original // vector contents, to avoid memory leaks and duplicate pointers in vector. #ifdef IMPROVED_STD_UNIQUE_ALGORITHM #error the #ifdef for IMPROVED_STD_UNIQUE_ALGORITHM was defined previously.. Something is wrong. #endif #undef IMPROVED_STD_UNIQUE_ALGORITHM #define IMPROVED_STD_UNIQUE_ALGORITHM // similar to std::unique, except that this version swaps elements, to avoid // memory leaks, when vector contains pointers. // // Normally the input is sorted. // Normal std::unique: // 10 20 20 20 30 30 20 20 10 // abcdefghi // // 10 20 30 20 10 | 30 20 20 10 // abegifghi // // Now GONE: c, d. // Now DUPS: g, i. // This causes memory leaks and segmenation faults due to duplicate deletes of same pointer! namespace ptgi { // Return the position of the first in range of duplicates moved to end of vector. // // uses operator== of class for comparison // // @param [first, last) is a range to find duplicates within. // // @return the dupPosition position, such that [dupPosition, end) are contiguous // duplicate elements. // IF all items are unique, then it would return last. // template  ForwardIterator unique( ForwardIterator first, ForwardIterator last) { // compare iterators, not values if (first == last) return last; // remember the current item that we are looking at for uniqueness ForwardIterator result = first; // result is slow ptr where to store next unique item // first is fast ptr which is looking at all elts // the first iterator moves over all elements [begin+1, end). // while the current item (result) is the same as all elts // to the right, (first) keeps going, until you find a different // element pointed to by *first. At that time, we swap them. while (++first != last) { if (!(*result == *first)) { #ifdef IMPROVED_STD_UNIQUE_ALGORITHM // inc result, then swap *result and *first // THIS IS WHAT WE WANT TO DO. // BUT THIS COULD SWAP AN ELEMENT WITH ITSELF, UNCECESSARILY!!! // std::swap( *first, *(++result)); // BUT avoid swapping with itself when both iterators are the same ++result; if (result != first) std::swap( *first, *result); #else // original code found in std::unique() // copies unique down *(++result) = *first; #endif } } return ++result; } template  ForwardIterator unique( ForwardIterator first, ForwardIterator last, BinaryPredicate pred) { if (first == last) return last; // remember the current item that we are looking at for uniqueness ForwardIterator result = first; while (++first != last) { if (!pred(*result,*first)) { #ifdef IMPROVED_STD_UNIQUE_ALGORITHM // inc result, then swap *result and *first // THIS COULD SWAP WITH ITSELF UNCECESSARILY // std::swap( *first, *(++result)); // // BUT avoid swapping with itself when both iterators are the same ++result; if (result != first) std::swap( *first, *result); #else // original code found in std::unique() // copies unique down // causes memory leaks, and duplicate ptrs // and uncessarily moves in place! *(++result) = *first; #endif } } return ++result; } // from now on, the #define is no longer needed, so get rid of it #undef IMPROVED_STD_UNIQUE_ALGORITHM } // end ptgi:: namespace #endif 

Y aquí está el progtwig de prueba UNIT que utilicé para probarlo:

 // QUESTION: in test2, I had trouble getting one line to compile,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::ostringstream #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: toString() should *always* be a const method // // NOTE: it is probably more efficient to call getNum() intead // of toString() 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::string& msg, const std::vector& nums ); int main() { test1(); test2(); return 0; } // test1() uses a vector (namely vector), so there is no problem with memory loss void test1() { int data[] = { 10, 20, 21, 22, 30, 31, 23, 24, 11}; // turn C array into C++ vector std::vector nums(data, data+9); // arg3 is a functor IntegerVectorIterator dupPosition = ptgi::unique( nums.begin(), nums.end(), IntegerEqualByTen() ); nums.erase(dupPosition, nums.end()); nums.erase(nums.begin(), dupPosition); } //================================================================================== // test2() uses a vector, so after ptgi:unique(), we have to be careful in // how we eliminate the duplicate Integer objects stored in the heap. //================================================================================== void test2() { int data[] = { 10, 20, 21, 22, 30, 31, 23, 24, 11}; // turn C array into C++ vector of Integer* pointers std::vector nums; // put data[] integers into equivalent Integer* objects in HEAP for (int inx = 0; inx < 9; ++inx) { nums.push_back( new Integer(data[inx]) ); } // print the vector to stdout printIntegerStarVector( "TEST2: ORIG nums before UNIQUE", nums ); // arg3 is a functor #if 1 // corrected version which fixes SEGMENTATION FAULT and all memory leaks reported by valgrind(1) // I THINK we want to use new C++11 cbegin() and cend(),since the equal_to predicate is passed "Integer *&" // DID NOT COMPILE //OUT IntegerStarVectorIterator dupPosition = ptgi::unique( const_cast(nums.begin()), const_cast(nums.end()), IntegerEqualByTenPointer() ); // DID NOT COMPILE when equal_to predicate declared "Integer*& arg1, Integer*& arg2" //OUT IntegerStarVectorIterator dupPosition = ptgi::unique( const_cast(nums.begin()), const_cast(nums.end()), IntegerEqualByTenPointer() ); // okay when equal_to predicate declared "Integer* arg1, Integer* arg2" IntegerStarVectorIterator dupPosition = ptgi::unique(nums.begin(), nums.end(), IntegerEqualByTenPointer() ); #else // BUGGY version that causes SEGMENTATION FAULT and valgrind(1) errors IntegerStarVectorIterator dupPosition = std::unique( nums.begin(), nums.end(), IntegerEqualByTenPointer() ); #endif printIntegerStarVector( "TEST2: modified nums AFTER UNIQUE", nums ); int dupInx = dupPosition - nums.begin(); std::cout << "INFO: dupInx=" << dupInx <<"\n"; // delete the dup Integer* objects in the [dupPosition, end] range for (IntegerStarVectorIterator iter = dupPosition; iter != nums.end(); ++iter) { delete (*iter); } // shrink the vector // NB: the Integer* ptrs are NOT followed by vector::erase() nums.erase(dupPosition, nums.end()); // print the uniques, by following the iter to the Integer* pointer for (IntegerStarVectorIterator iter = nums.begin(); iter != nums.end(); ++iter) { std::cout << "TEST2: uniq = " << (*iter)->getNum() << "\n"; } // remove the unique objects from heap for (IntegerStarVectorIterator iter = nums.begin(); iter != nums.end(); ++iter) { delete (*iter); } // shrink the vector nums.erase(nums.begin(), nums.end()); // the vector should now be completely empty assert( nums.size() == 0); } //@ print to stdout the string: "info_msg: num1, num2, .... numN\n" void printIntegerStarVector( const std::string& msg, const std::vector& nums ) { std::cout << msg << ": "; int inx = 0; ConstIntegerStarVectorIterator iter; // use const iterator and const range! // NB: cbegin() and cend() not supported until LATER (c++11) for (iter = nums.begin(), inx = 0; iter != nums.end(); ++iter, ++inx) { // output a comma seperator *AFTER* first if (inx > 0) std::cout << ", "; // call Integer::toString() std::cout << (*iter)->getNum(); // send int to stdout // std::cout << (*iter)->toString(); // also works, but is probably slower } // in conclusion, add newline std::cout << "\n"; } 

About alexK7 benchmarks. I tried 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. Aquí está el código:

 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::string& 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 .