Cómo eliminar los duplicados de un vector C ++
'E' ocurre tres veces en diferentes posiciones. 'A' ocurre dos veces en diferentes posiciones. 'C' ocurre dos veces en diferentes posiciones. Entonces, 'e', 'a' y 'c' tienen duplicados. Cada uno del resto de los otros caracteres ocurre una vez.
Para eliminar los duplicados en este vector, significa eliminar los duplicados de 'E', 'A' y 'C', y permitir la primera aparición de cada carácter, en su posición. El resultado debe ser:
vectorHay dos formas principales de eliminar duplicados de un vector. Una forma es la forma de fuerza directa o bruta. De esta manera, el primer elemento se verifica contra el resto de los elementos, y se elimina cualquier duplicado. El segundo elemento se verifica contra el resto de los otros elementos a la derecha, eliminando los duplicados. El mismo procedimiento se realiza para el tercer elemento y el resto de los elementos. De esta manera generalmente lleva demasiado tiempo. La otra forma es mantener el vector original y tener una copia ordenada de él. Eliminar los duplicados del vector ordenado al hacer la copia de cualquier elemento duplicado, como clave en un mapa. Finalmente, escanee el vector original desde el principio hasta el final utilizando el mapa para borrar los duplicados.
Estas dos formas pueden denominarse el método de fuerza bruta y el método de clasificación y comparación, respectivamente. Este artículo ilustra en ambos sentidos. No olvide incluir la biblioteca Vector al comienzo del programa.
Eliminar un elemento vectorial
Se elimina un elemento vectorial con la función de miembro de borrado vectorial. La sintaxis es:
Constexpr Iterator Erase (posición const_iterator);El argumento es un iterador que apunta al elemento, para eliminar.
Eliminar duplicados por fuerza bruta
Con este enfoque, el primer elemento se compara con el resto de los elementos de la derecha, uno por uno, y se borra cualquier duplicado. El segundo elemento, si no se borró, se compara con el resto de los otros elementos de la derecha, uno por uno, borrando duplicados. El mismo procedimiento se realiza para el tercer elemento y el resto de los elementos. Este enfoque generalmente lleva demasiado tiempo. El siguiente código lo ilustra con los iteradores:
vectorvtr = 'e', 'g', 'i', 'e', 'a', 'e', 'c', 'a', 'c';para (vector :: iterator itei = vtr.comenzar(); itei
para (vector :: iterator itej = itei+1; itej
VTR.borrar (itej);
para (int i = 0; i
cout<
en las paréntesis del bucle interno.
Eliminar duplicados por clasificación y comparación
Avance del método anterior que hay una gran cantidad de redescanning (releer y comparación) de una secuencia grande, a una pequeña secuencia de elementos del único vector. Si todo el vector se escanea una o dos veces o tres veces, esto probablemente significaría menos acceso de los elementos en comparación con el enfoque anterior. Bueno, todo el vector se puede escanear cuatro o más veces, pero no muchas veces. Esto no debe hacerse necesariamente con el mismo vector. Se puede hacer con copias del vector.
Con el segundo enfoque, el vector original se mantiene mientras una copia ordenada está hecha de él. El vector ordenado se lee (escaneado), borrando el duplicado de elementos consecutivos que ocurrieron más de una vez. Un iterador for-loop puede lograr esto, desde el principio hasta el final del vector ordenado, una vez hasta. Si bien se produce esta lectura y algunos borrados, para cualquier elemento que ocurra más de una vez, se realiza una copia del elemento en un mapa, y el valor correspondiente para esta clave, tiene el valor -1. Este valor de -1 se cambiará a 1 para indicar un duplicado. Cada valor en el mapa es un indicador para el duplicado de su clave que puede ocurrir dos o más veces en el vector original.
Si se requirió el vector ordenado con duplicados eliminados, entonces se devuelve el vector ordenado y el trabajo se realiza. Si se debe mantener el orden de la primera ocurrencia de los elementos del vector, entonces se debe tener lugar el siguiente subprocedimiento (continuar):
Vuelva a leer el vector original desde el principio. Mientras lee, si no se produce una clave en el mapa (el mapa devuelve 0), permita esa clave en el vector original. Esto significa que la clave no tiene duplicado. Si se produce una clave del vector original en el mapa, significa que es la primera aparición de duplicados para ese elemento en el vector. Haga el valor del indicador para la clave en el mapa, 1. Ese valor indicador ahora tiene el valor, 1. Continúe leyendo el resto de los elementos en el vector original y verificar el elemento duplicado con el mapa. Si se encuentra una tecla y el valor de la clave del mapa es 1, entonces el elemento actual es un duplicado. Eliminar el elemento actual. (Recuerde que la primera ocurrencia de una clave duplicada convirtió el valor del indicador correspondiente en el mapa de -1 a 1.) Continúe dando un valor de 1 para los indicadores de clave de mapa, eliminando el elemento vector de corriente original que ya tiene un 1 correspondiente en el mapa del vector original; Hasta que se alcanza el final del vector original. El vector original resultante es el vector sin ningún elemento duplicado, y en el orden con primeros ocurrencias.
Para codificar el mapa en C ++, se debe incluir la biblioteca del mapa (undered_map). Dado que se utilizará la función sort () en la biblioteca de algoritmo, la biblioteca de algoritmo también debe incluirse en el programa. El encabezado para el programa de este enfoque debe ser:
#incluir#incluir
#incluir
#incluir
usando el espacio de nombres STD;
El primer segmento de código en la función principal de C ++ puede ser:
vectorvector
ordenar (VTR.begin (), VTR.fin());
desordenable_map
La primera declaración define el vector original. La segunda declaración hace una copia del vector original. La tercera declaración clasifica el vector copiado. La cuarta declaración declara el mapa, sin inicialización. El siguiente segmento de código en la función principal de C ++ puede ser:
para (vector :: iterator iter = vtr.comenzar(); iterif ( *iter0 == *iter1)
MP [*iter1] = -1;
iter--;
vector :: iterator iter2 = vtr.borrar (iter1);
Este segmento de código borra los duplicados del vector copiado ordenado. Mientras hace eso, crea las entradas del mapa. Tenga en cuenta que en las paréntesis del bucle for-bucle, la iteración alcanza el último pero un elemento (y no el último elemento). Esto se debe a que los elementos actuales y siguientes están involucrados en el código. También tenga en cuenta que cuando se debe borrar un elemento, el iterador se retrasa (disminuye) en un paso.
Si el vector ordenado sin duplicados es lo que se requería, entonces el siguiente código mostraría el resultado:
para (int i = 0; icout<
vTro.borrar (iter);
iter--;
if (mp [*iter] == -1)
MP [*iter] = 1;
La razón para elegir, -1 y 1, en lugar de 0 y 1, es porque el valor predeterminado (ausente) de este mapa es 0. Esto evita la confusión con los elementos que no tienen duplicado en absoluto. Un bucle ordinario de la siguiente manera puede imprimir el vector original final (reducido):
para (int i = 0; icout<
La salida del programa es:
A C E G IE G I A C
La primera línea de la salida es la entrada ordenada sin duplicados. La segunda línea es la entrada en el orden dado, con los duplicados eliminados.
Conclusión
Para eliminar los duplicados de un vector C ++, se puede usar el método de fuerza bruta. Este método suele ser lento. Se recomienda al lector que utilice el método de clasificación y comparación, que generalmente es rápido, para su trabajo comercial. Ambos métodos se han explicado anteriormente.