Come rimuovere i duplicati da un vettore C ++
'E' si verifica tre volte in posizioni diverse. 'A' si verifica due volte in posizioni diverse. "C" si verifica due volte in posizioni diverse. Quindi, 'e', 'a' e 'c' hanno duplicati. Ciascuno degli altri personaggi si verifica una volta.
Per rimuovere i duplicati in questo vettore, significa rimuovere i duplicati di "e", "a" e "c" e consentire la prima occorrenza di ciascun personaggio, nella sua posizione. Il risultato dovrebbe essere:
vettoreEsistono due modi principali per rimuovere i duplicati da un vettore. Un modo è il modo di forza diretta o bruta. In questo modo, il primo elemento viene controllato contro il resto degli elementi e qualsiasi duplicato viene rimosso. Il secondo elemento viene controllato contro il resto degli altri elementi a destra, rimuovendo i duplicati. La stessa procedura viene eseguita per il terzo elemento e il resto degli elementi. In questo modo di solito richiede troppo tempo. L'altro modo è mantenere il vettore originale e averne una copia ordinata. Rimuovere i duplicati dal vettore ordinato mentre si crea la copia di qualsiasi elemento duplicato, come chiave in una mappa. Infine, scansiona il vettore originale dall'inizio alla fine usando la mappa per cancellare i duplicati.
Questi due modi possono essere indicati rispettivamente come metodo bruto-forza e il metodo di ordinamento. Questo articolo illustra in entrambi i modi. Non dimenticare di includere la libreria vettoriale all'inizio del programma.
Rimozione di un elemento vettoriale
Un elemento vettoriale viene rimosso con la funzione membro della cancellazione vettoriale. La sintassi è:
CONSTEXPR iterator Erase (posizione const_iterator);L'argomento è un iteratore che indica l'elemento, da rimuovere.
Rimozione dei duplicati per forza bruta
Con questo approccio, il primo elemento viene confrontato con il resto degli elementi a destra, uno a uno e qualsiasi duplicato viene cancellato. Il secondo elemento, se non è stato cancellato, viene confrontato con il resto degli altri elementi a destra, uno a uno, cancellando i duplicati. La stessa procedura viene eseguita per il terzo elemento e il resto degli elementi. Questo approccio di solito richiede troppo tempo. Il seguente codice lo illustra con iteratori:
vectorvtr = 'e', 'g', 'i', 'e', 'a', 'e', 'c', 'a', 'c';per (vector :: iterator itei = vtr.inizio(); Itei
per (vector :: iterator itej = itei+1; itej
VTR.cancella (Itej);
per (int i = 0; i
cout<
tra le parentesi del per anello interno.
Rimozione dei duplicati per tipo e compare
Si noti dal metodo sopra che c'è molto riescanning (rilettura e confronto) da una grande sequenza, a una piccola sequenza di elementi di un vettore. Se l'intero vettore viene scansionato una o due volte o tre volte, ciò significherebbe probabilmente meno accessi degli elementi rispetto all'approccio sopra. Bene, l'intero vettore può anche essere scansionato quattro o più volte, ma non molte volte. Questo non deve necessariamente essere fatto con lo stesso vettore. Può essere fatto con copie del vettore.
Con il secondo approccio, il vettore originale viene mantenuto mentre una copia ordinata viene effettuata da esso. Il vettore ordinato viene letto attraverso (scansionato), cancellando il duplicato di elementi consecutivi che si sono verificati più di una volta. Un iteratore per loop può raggiungere questo obiettivo, dall'inizio alla fine del vettore ordinato, una volta attraverso. Mentre questa lettura e una certa cancellazione sono in corso, per qualsiasi elemento che si verifica più di una volta, una copia dell'elemento viene creata in una mappa e il valore corrispondente per questa chiave viene dato il valore -1. Questo valore di -1 verrà modificato in 1 per indicare un duplicato. Ogni valore nella mappa è un indicatore per il duplicato della sua chiave che potrebbe verificarsi due o più volte nel vettore originale.
Se è stato richiesto il vettore ordinato con i duplicati rimossi, viene restituito il vettore ordinato e il lavoro viene svolto. Se è necessario mantenere l'ordine della prima occorrenza degli elementi vettoriali, è necessario che la seguente sub-procedura deve aver luogo (Continua):
Rileggi il vettore originale dall'inizio. Durante la lettura, se una chiave non si verifica nella mappa (la mappa restituisce 0), consentire quella chiave nel vettore originale. Ciò significa che la chiave non ha duplicato. Se si verifica una chiave del vettore originale nella mappa, significa che è la prima occorrenza di duplicati per quell'elemento nel vettore. Effettua il valore dell'indicatore per la chiave nella mappa, 1. Quel valore dell'indicatore ora ha il valore, 1. Continua a leggere il resto degli elementi nel vettore originale e controlla l'elemento duplicato con la mappa. Se viene trovata una chiave e il valore della chiave della mappa è 1, allora l'elemento corrente è un duplicato. Rimuovi l'elemento corrente. (Ricorda che la prima occorrenza di una chiave duplicata ha trasformato il valore dell'indicatore corrispondente nella mappa da -1 a 1.) Continua a dare un valore di 1 per gli indicatori della chiave della mappa, rimuovendo l'elemento vettoriale corrente originale che ha già un corrispondente 1 nella mappa del vettore originale; Fino alla fine del vettore originale. Il vettore originale risultante è il vettore senza alcun elemento duplicato e nell'ordine con le prime occorrenze.
Al fine di codificare la mappa in C ++, la libreria MAP (UNORDERD_MAP) deve essere inclusa. Poiché verrà utilizzata la funzione Ord () nella libreria dell'algoritmo, anche la libreria dell'algoritmo deve essere inclusa nel programma. L'intestazione per il programma di questo approccio dovrebbe essere:
#includere#includere
#includere
#includere
Utilizzo dello spazio dei nomi std;
Il primo segmento di codice nella funzione principale C ++ può essere:
vettorevettore
Ordina (VTR.inizio (), vtr.FINE());
UNORDERD_MAP
La prima dichiarazione definisce il vettore originale. La seconda dichiarazione fa una copia del vettore originale. La terza istruzione ordina il vettore copiato. La quarta affermazione dichiara la mappa, senza inizializzazione. Il segmento di codice successivo nella funzione principale C ++ può essere:
per (vector :: iterator iter = vtr.inizio(); iterif ( *iter0 == *iter1)
mp [*iter1] = -1;
iter--;
Vector :: iterator iter2 = vtr.cancella (iter1);
Questo segmento di codice cancella i duplicati dal vettore copiato ordinato. Mentre lo fa, crea le voci della mappa. Si noti che nelle parentesi del per loop, l'iterazione raggiunge l'ultimo ma elemento (e non l'ultimo elemento). Questo perché gli elementi attuali e i prossimi sono coinvolti nel codice. Si noti inoltre che quando un elemento deve essere cancellato, l'iteratore viene ritardato (decrementato) di un passaggio.
Se il vettore ordinato senza duplicati è ciò che era richiesto, il seguente codice mostrerebbe il risultato:
per (int i = 0; icout<
vtro.cancella (iter);
iter--;
if (mp [*iter] == -1)
mp [*iter] = 1;
Il motivo della scelta, -1 e 1, anziché 0 e 1, è perché il valore predefinito (assente) di questa mappa è 0. Questo evita la confusione con gli elementi che non hanno affatto duplicato. Un normale per loop come segue può stampare il vettore originale finale (ridotto):
per (int i = 0; icout<
L'output del programma è:
A c e g iE g i a c
La prima riga dell'uscita è l'ingresso ordinato senza duplicati. La seconda riga è l'input nell'ordine dato, con i duplicati rimossi.
Conclusione
Al fine di rimuovere i duplicati da un vettore C ++, è possibile utilizzare il metodo bruto-forza. Questo metodo è generalmente lento. Si consiglia al lettore di utilizzare il metodo di ordinamento, che di solito è veloce, per il suo lavoro commerciale. Entrambi i metodi sono stati spiegati sopra.