tengoCómo borrar elemento duplicado en el vector, de manera eficiente
vector<string> data ; // I hold some usernames in it
En ese vector, tengo elemento (s) por duplicado, por lo que quiero borrar este/estos elemento (s) .Are Hay algún algoritmo o función de biblioteca para borrar elemento (s) duplicado (s)?
ex :
In data;
abba, abraham, edie, Abba, edie
After operation;
abba, abraham, edie, Abba
Si usted puede ordenar los elementos en el contenedor, la solución sencilla y relativamente eficiente sería:
std::sort(data.begin(), data.end());
data.erase(std::unique(data.begin(), data.end()), data.end());
¿No sería mejor usar 'stable_sort' aquí? – Naveen
@Naveen: ¿Por qué? Solo necesita una clasificación estable si la posición relativa de elementos equivalentes importa, y eso obviamente no importa si solo va a eliminar duplicados de todos modos. –
a menos que específicamente desee mantener la primera aparición del grupo de equivalencia. –
No estoy seguro de que hay una muy buena manera de hacerlo. Lo que haría es ordenar (en una matriz diferente, si necesita el original en el tacto) y luego ejecutarlo.
"set" no permite duplicados. Puede usar eso para filtrar duplicados.
Pero eso no preservará el orden presente en el 'vector'. – Naveen
Sí, no lo hará. Si desea conservar el orden, la complejidad aumentaría. Básicamente cree un nuevo vector, para cada elemento en el vector existente {si existe en el conjunto, no haga nada, de lo contrario agréguelo para agregarlo al vecotr de destino} –
Si realmente necesita hacerlo de manera eficiente, a continuación, primero debe hacer una ordenación in situ y luego ir por el contenedor usted mismo en lugar de usar std :: unique, buscar elementos únicos en un vector nuevo, y luego hacer un intercambio.
Acabo de comprobar el código fuente de std :: unique, se moverá mucho al encontrar un duplicado, el movimiento perjudica el rendimiento del vector.
'std :: unique' solo debe requerir una sola pasada a través del archivo ordenado secuencia. ¿A qué te refieres con "hará mucho [movimiento] [s] cuando encuentre un duplicado"? –
es un pase único, pero cada vez que encuentra un duplicado, necesita moverlo hasta el final. 0 1 1 2 2 3 -> 0 1 2 2 3 1 -> 0 1 2 3 1 2. – Shuo
¿Es importante el orden relativo de los elementos? es decir, ¿le importan los elementos que se barajan durante las operaciones o desea obtener una secuencia en el mismo orden? –