¿Cómo hacer que los elementos del vector sean únicos? (eliminar duplicados no adyacentes)

Tengo un vector que contiene pocos duplicados no adyacentes.

Como un simple ejemplo, considere:

2 1 6 1 4 6 2 1 1 

Estoy tratando de hacer este vector único eliminando los duplicados no adyacentes y manteniendo el orden de los elementos.

El resultado sería:

 2 1 6 4 

Las soluciones que probé son:

  1. Inserción en un conjunto estándar, pero el problema con este enfoque es que alterará el orden de los elementos.
  2. Use la combinación de std :: sort y std :: unique. Pero nuevamente el mismo problema de orden.
  3. Eliminación manual duplicada:

      Define a temporary vector TempVector. for (each element in a vector) { if (the element does not exists in TempVector) { add to TempVector; } } swap orginial vector with TempVector. 

Mi pregunta es:

¿Hay algún algoritmo STL que pueda eliminar los duplicados no adyacentes del vector? ¿Cuál es su complejidad?

Creo que lo harías así:

Yo usaría dos iteradores en el vector:

El primero de uno lee los datos y lo inserta un conjunto temporal.

Cuando los datos leídos no estaban en el conjunto, cópielos del primer iterador al segundo e increméntelos.

Al final, solo conserva los datos hasta el segundo iterador.

La complejidad es O (n .log (n)) ya que la búsqueda de elementos duplicados usa el conjunto, no el vector.

 #include  #include  #include  int main(int argc, char* argv[]) { std::vector< int > k ; k.push_back( 2 ); k.push_back( 1 ); k.push_back( 6 ); k.push_back( 1 ); k.push_back( 4 ); k.push_back( 6 ); k.push_back( 2 ); k.push_back( 1 ); k.push_back( 1 ); { std::vector< int >::iterator r , w ; std::set< int > tmpset ; for( r = k.begin() , w = k.begin() ; r != k.end() ; ++r ) { if( tmpset.insert( *r ).second ) { *w++ = *r ; } } k.erase( w , k.end() ); } { std::vector< int >::iterator r ; for( r = k.begin() ; r != k.end() ; ++r ) { std::cout < < *r << std::endl ; } } } 

Sin utilizar un set temporal, es posible hacer esto con (posiblemente) alguna pérdida de rendimiento:

 template Iterator Unique(Iterator first, Iterator last) { while (first != last) { Iterator next(first); last = std::remove(++next, last, *first); first = next; } return last; } 

utilizado como en:

 vec.erase( Unique( vec.begin(), vec.end() ), vec.end() ); 

Para conjuntos de datos más pequeños, la simplicidad de implementación y la falta de asignación adicional pueden compensar la mayor complejidad teórica de utilizar un set adicional. Sin embargo, la medida con una contribución representativa es la única manera de estar seguro.

Puede eliminar algunos de los bucles en la respuesta de fa usando remove_copy_if :

 class NotSeen : public std::unary_function  { public: NotSeen (std::set & seen) : m_seen (seen) { } bool operator ()(int i) const { return (m_seen.insert (i).second); } private: std::set & m_seen; }; void removeDups (std::vector const & iv, std::vector & ov) { std::set seen; std::remove_copy_if (iv.begin () , iv.end () , std::back_inserter (ov) , NotSeen (seen)); } 

Esto no afecta la complejidad del algoritmo (es decir, como está escrito, también es O (n log n)). Puede mejorar esto usando unordered_set, o si el rango de sus valores es lo suficientemente pequeño, simplemente podría usar una matriz o bitarray.

Como la pregunta era “¿hay algún algoritmo de STL …? ¿Cuál es su complejidad?” tiene sentido implementar la función como std::unique :

 template  inline FwdIterator stable_unique(FwdIterator first, FwdIterator last) { FwdIterator result = first; std::unordered_set seen; for (; first != last; ++first) if (seen.insert(*first).second) *result++ = *first; return result; } 

Así que así es como se implementa std::unique más un conjunto adicional. El conjunto unordered_set será más rápido que un set regular. Se eliminan todos los elementos que se comparan con el elemento que los precede (el primer elemento se conserva porque no podemos unificar nada). El iterador devolvió puntos al nuevo final dentro del rango [first,last) .

EDITAR: La última oración significa que el contenedor en sí NO se modifica por unique . Esto puede ser confuso. El siguiente ejemplo realmente reduce el contenedor al conjunto unificado.

 1: std::vector v(3, 5); 2: v.resize(std::distance(v.begin(), unique(v.begin(), v.end()))); 3: assert(v.size() == 1); 

La línea 1 crea un vector { 5, 5, 5 } . En la llamada de la línea 2, unique devuelve un iterador al segundo elemento, que es el primer elemento que no es único. Por lo tanto, la distance devuelve 1 y el resize vuelve a cortar el vector.

No hay ningún algoritmo de STL que haga lo que quiera preservando el orden original de la secuencia.

Podría crear un std::set estándar de iteradores o índices en el vector, con un predicado de comparación que use los datos referenciados en lugar de los iteradores / índices para ordenar cosas. Luego borras todo del vector que no está referenciado en el conjunto. (Por supuesto, también podría usar otro std::vector de iterators / indexes, std::sort y std::unique that, y usar esto como referencia en cuanto a qué conservar).

Basado en la respuesta de @fa. También se puede volver a escribir utilizando el algoritmo STL std::stable_partition :

 struct dupChecker_ { inline dupChecker_() : tmpSet() {} inline bool operator()(int i) { return tmpSet.insert(i).second; } private: std::set tmpSet; }; k.erase(std::stable_partition(k.begin(), k.end(), dupChecker_()), k.end()); 

De esta manera es más compacto y no es necesario que cuidemos los iteradores.

Parece incluso no introducir una gran penalización de rendimiento. Lo uso en mi proyecto que necesita manejar vectores bastante grandes de tipos complejos a menudo y no hace una diferencia real.

Otra buena característica es que es posible ajustar la unicidad usando std::set tmpSet; . Por ejemplo, en mi proyecto para ignorar ciertos errores de redondeo.

Hay un buen artículo de John Torjo que trata esta cuestión de manera sistemática. El resultado que se le ocurre parece más genérico y más eficiente que cualquiera de las soluciones sugeridas hasta ahora:

http://www.builderau.com.au/program/java/soa/C-Removing-duplicates-from-a-range/0,339024620,320271583,00.htm

https://web.archive.org/web/1/http://articles.techrepublic%2ecom%2ecom/5100-10878_11-1052159.html

Desafortunadamente, el código completo de la solución de John parece que ya no está disponible y John no respondió. Por lo tanto, escribí mi propio código que se basa en motivos similares a los suyos, pero difiere intencionalmente en algunos detalles. No dude en ponerse en contacto conmigo (vschoech think-cell com) y discutir los detalles si lo desea.

Para hacer que el código comstackra para usted, agregué algunas de mis propias cosas de la biblioteca que uso regularmente. Además, en lugar de ir con stl simple, utilizo boost para crear código más genérico, más eficiente y más legible.

¡Que te diviertas!

 #include  #include  #include  #include  #include  ///////////////////////////////////////////////////////////////////////////////////////////// // library stuff template< class Rng, class Func > Func for_each( Rng& rng, Func f ) { return std::for_each( boost::begin(rng), boost::end(rng), f ); }; template< class Rng, class Pred > Rng& sort( Rng& rng, Pred pred ) { std::sort( boost::begin( rng ), boost::end( rng ), pred ); return rng; // to allow function chaining, similar to operator+= et al. } template< class T > boost::iterator_range< boost::counting_iterator > make_counting_range( T const& tBegin, T const& tEnd ) { return boost::iterator_range< boost::counting_iterator >( tBegin, tEnd ); } template< class Func > class compare_less_impl { private: Func m_func; public: typedef bool result_type; compare_less_impl( Func func ) : m_func( func ) {} template< class T1, class T2 > bool operator()( T1 const& tLeft, T2 const& tRight ) const { return m_func( tLeft ) < m_func( tRight ); } }; template< class Func > compare_less_impl compare_less( Func func ) { return compare_less_impl( func ); } ///////////////////////////////////////////////////////////////////////////////////////////// // stable_unique template forward_iterator stable_unique(forward_iterator itBegin, forward_iterator itEnd, predicate_type predLess) { typedef std::iterator_traits::difference_type index_type; struct SIteratorIndex { SIteratorIndex(forward_iterator itValue, index_type idx) : m_itValue(itValue), m_idx(idx) {} std::iterator_traits::reference Value() const {return *m_itValue;} index_type m_idx; private: forward_iterator m_itValue; }; // {1} create array of values (represented by iterators) and indices std::vector vecitidx; vecitidx.reserve( std::distance(itBegin, itEnd) ); struct FPushBackIteratorIndex { FPushBackIteratorIndex(std::vector& vecitidx) : m_vecitidx(vecitidx) {} void operator()(forward_iterator itValue) const { m_vecitidx.push_back( SIteratorIndex(itValue, m_vecitidx.size()) ); } private: std::vector& m_vecitidx; }; for_each( make_counting_range(itBegin, itEnd), FPushBackIteratorIndex(vecitidx) ); // {2} sort by underlying value struct FStableCompareByValue { FStableCompareByValue(predicate_type predLess) : m_predLess(predLess) {} bool operator()(SIteratorIndex const& itidxA, SIteratorIndex const& itidxB) { return m_predLess(itidxA.Value(), itidxB.Value()) // stable sort order, index is secondary criterion || !m_predLess(itidxB.Value(), itidxA.Value()) && itidxA.m_idx < itidxB.m_idx; } private: predicate_type m_predLess; }; sort( vecitidx, FStableCompareByValue(predLess) ); // {3} apply std::unique to the sorted vector, removing duplicate values vecitidx.erase( std::unique( vecitidx.begin(), vecitidx.end(), !boost::bind( predLess, // redundand boost::mem_fn required to compile boost::bind(boost::mem_fn(&SIteratorIndex::Value), _1), boost::bind(boost::mem_fn(&SIteratorIndex::Value), _2) ) ), vecitidx.end() ); // {4} re-sort by index to match original order sort( vecitidx, compare_less(boost::mem_fn(&SIteratorIndex::m_idx)) ); // {5} keep only those values in the original range that were not removed by std::unique std::vector::iterator ititidx = vecitidx.begin(); forward_iterator itSrc = itBegin; index_type idx = 0; for(;;) { if( ititidx==vecitidx.end() ) { // {6} return end of unique range return itSrc; } if( idx!=ititidx->m_idx ) { // original range must be modified break; } ++ititidx; ++idx; ++itSrc; } forward_iterator itDst = itSrc; do { ++idx; ++itSrc; // while there are still items in vecitidx, there must also be corresponding items in the original range if( idx==ititidx->m_idx ) { std::swap( *itDst, *itSrc ); // C++0x move ++ititidx; ++itDst; } } while( ititidx!=vecitidx.end() ); // {6} return end of unique range return itDst; } template forward_iterator stable_unique(forward_iterator itBegin, forward_iterator itEnd) { return stable_unique( itBegin, itEnd, std::less< std::iterator_traits::value_type >() ); } void stable_unique_test() { std::vector vecn; vecn.push_back(1); vecn.push_back(17); vecn.push_back(-100); vecn.push_back(17); vecn.push_back(1); vecn.push_back(17); vecn.push_back(53); vecn.erase( stable_unique(vecn.begin(), vecn.end()), vecn.end() ); // result: 1, 17, -100, 53 } 

Mi pregunta es:

¿Hay algún algoritmo STL que pueda eliminar los duplicados no adyacentes del vector? ¿Cuál es su complejidad?

Las opciones de STL son las que usted mencionó: coloque los elementos en un std::set , o llame a std::sort , std::unique y llame a erase() en el contenedor. Ninguno de estos cumple con su requisito de “eliminar los duplicados no adyacentes y mantener el orden de los elementos”.

Entonces, ¿por qué el STL no ofrece otra opción? Ninguna biblioteca estándar ofrecerá todo para las necesidades de cada usuario. Las consideraciones de diseño de la STL incluyen “ser lo suficientemente rápido para casi todos los usuarios”, “ser útil para casi todos los usuarios” y “proporcionar seguridad de excepción tanto como sea posible” (y “ser lo suficientemente pequeño para el Comité de Estándares” como la biblioteca Stepanov originalmente escribió era mucho más grande, y Stroustrup eliminó algo así como 2/3 de ella).

La solución más simple que puedo pensar se vería así:

 // Note: an STL-like method would be templatized and use iterators instead of // hardcoding std::vector std::vector stable_unique(const std::vector& input) { std::vector result; result.reserve(input.size()); for (std::vector::iterator itor = input.begin(); itor != input.end(); ++itor) if (std::find(result.begin(), result.end(), *itor) == result.end()) result.push_back(*itor); return result; } 

Esta solución debe ser O (M * N) donde M es el número de elementos únicos y N es la cantidad total de elementos.

Por lo que sé, no hay ninguno en stl. Buscar referencia .

Basado en la respuesta de @Corden, pero utiliza la expresión lambda y elimina los duplicados en lugar de escribirlos en el vector de salida

  set s; vector nodups; remove_copy_if(v.begin(), v.end(), back_inserter(nodups), [&s](int x){ return !s.insert(x).second; //-> .second false means already exists } ); 

Dado que su entrada está en vector foo , puede usar remove para hacer el trabajo de patas aquí, luego, si desea reducir el tamaño del vector, simplemente use erase contrario, utilice last como su iterador de un solo paso cuando quieres que se elimine el vector con duplicados, pero la orden se conserva:

 auto last = end(foo); for(auto first = begin(foo); first < last; ++first) last = remove(next(first), last, *first); foo.erase(last, end(foo)); 

Ejemplo en vivo

En cuanto a la complejidad del tiempo, esto será O (nm) . Donde n es el número de elementos ym es la cantidad de elementos únicos. En cuanto a la complejidad del espacio, esto utilizará O (n) porque elimina en su lugar.