c++ - repetidos - ¿Cómo hacer que los elementos del vector sean únicos?(eliminar duplicados no adyacentes)
eliminar elementos repetidos de una lista python (11)
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<int>
std::vector<int> stable_unique(const std::vector<int>& input)
{
std::vector<int> result;
result.reserve(input.size());
for (std::vector<int>::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.
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:
- Inserción en un conjunto estándar, pero el problema con este enfoque es que alterará el orden de los elementos.
- Use la combinación de std :: sort y std :: unique. Pero nuevamente el mismo problema de orden.
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?
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<int> s;
vector<int> nodups;
remove_copy_if(v.begin(), v.end(), back_inserter(nodups),
[&s](int x){
return !s.insert(x).second; //-> .second false means already exists
} );
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<int> 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<int, myCmp_> tmpSet; . Por ejemplo, en mi proyecto para ignorar ciertos errores de redondeo.
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 <class FwdIterator>
inline FwdIterator stable_unique(FwdIterator first, FwdIterator last)
{
FwdIterator result = first;
std::unordered_set<typename FwdIterator::value_type> 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<int> 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.
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 <vector>
#include <set>
#include <iostream>
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 ;
}
}
}
Dado que su entrada está en vector<int> 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));
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.
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:
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 compilara 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 <vector>
#include <functional>
#include <boost/bind.hpp>
#include <boost/range.hpp>
#include <boost/iterator/counting_iterator.hpp>
/////////////////////////////////////////////////////////////////////////////////////////////
// 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<T> > make_counting_range( T const& tBegin, T const& tEnd ) {
return boost::iterator_range< boost::counting_iterator<T> >( 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<Func> compare_less( Func func ) {
return compare_less_impl<Func>( func );
}
/////////////////////////////////////////////////////////////////////////////////////////////
// stable_unique
template<class forward_iterator, class predicate_type>
forward_iterator stable_unique(forward_iterator itBegin, forward_iterator itEnd, predicate_type predLess) {
typedef std::iterator_traits<forward_iterator>::difference_type index_type;
struct SIteratorIndex {
SIteratorIndex(forward_iterator itValue, index_type idx) : m_itValue(itValue), m_idx(idx) {}
std::iterator_traits<forward_iterator>::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<SIteratorIndex> vecitidx;
vecitidx.reserve( std::distance(itBegin, itEnd) );
struct FPushBackIteratorIndex {
FPushBackIteratorIndex(std::vector<SIteratorIndex>& vecitidx) : m_vecitidx(vecitidx) {}
void operator()(forward_iterator itValue) const {
m_vecitidx.push_back( SIteratorIndex(itValue, m_vecitidx.size()) );
}
private:
std::vector<SIteratorIndex>& 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<SIteratorIndex>::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<class forward_iterator>
forward_iterator stable_unique(forward_iterator itBegin, forward_iterator itEnd) {
return stable_unique( itBegin, itEnd, std::less< std::iterator_traits<forward_iterator>::value_type >() );
}
void stable_unique_test() {
std::vector<int> 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
}
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).
Por lo que sé, no hay ninguno en stl. Buscar reference .
Puede eliminar algunos de los bucles en fa''s respuesta fa''s usando remove_copy_if :
class NotSeen : public std::unary_function <int, bool>
{
public:
NotSeen (std::set<int> & seen) : m_seen (seen) { }
bool operator ()(int i) const {
return (m_seen.insert (i).second);
}
private:
std::set<int> & m_seen;
};
void removeDups (std::vector<int> const & iv, std::vector<int> & ov) {
std::set<int> 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.
Sin utilizar un set temporal, es posible hacer esto con (posiblemente) alguna pérdida de rendimiento:
template<class Iterator>
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.