Hvordan fjerne duplikater fra en C ++ vektor
'E' forekommer tre ganger i forskjellige posisjoner. 'A' forekommer to ganger i forskjellige posisjoner. 'C' forekommer to ganger i forskjellige posisjoner. Så 'e', 'a' og 'c' har duplikater. Hver av resten av de andre karakterene oppstår en gang.
For å fjerne duplikater i denne vektoren, betyr det å fjerne duplikatene til 'E', 'A' og 'C', og tillate den første forekomsten av hvert tegn, i sin posisjon. Resultatet skal være:
vektorDet er to hovedmåter å fjerne duplikater fra en vektor. En måte er den direkte eller brute force -måten. På denne måten blir det første elementet sjekket mot resten av elementene, og alle duplikater fjernes. Det andre elementet blir sjekket mot resten av de andre elementene til høyre, og fjerner duplikater. Den samme prosedyren gjøres for det tredje elementet, og resten av elementene. På denne måten tar vanligvis for lang tid. Den andre måten er å opprettholde den opprinnelige vektoren, og ha en sortert kopi av den. Fjern duplikater fra den sorterte vektoren mens du lager kopien av ethvert duplisert element, som tast i et kart. Til slutt, skann gjennom den opprinnelige vektoren fra begynnelse til slutt ved å bruke kartet for å slette duplikater.
Disse to måtene kan omtales som henholdsvis brute-Force-metoden og sort-and-compare-metoden. Denne artikkelen illustrerer begge veier. Ikke glem å inkludere vektorbiblioteket i begynnelsen av programmet.
Fjerne et vektorelement
Et vektorelement fjernes med vektorens slette medlemsfunksjon. Syntaksen er:
constExpr iterator erase (const_iterator posisjon);Argumentet er en iterator som peker på elementet, som skal fjernes.
Fjerne duplikater med brute kraft
Med denne tilnærmingen blir det første elementet sammenlignet med resten av elementene til høyre, en-for-en, og alle duplikater blir slettet. Det andre elementet, hvis det ikke ble slettet, sammenlignes med resten av de andre elementene til høyre, en-for-en, slette duplikater. Den samme prosedyren gjøres for det tredje elementet, og resten av elementene. Denne tilnærmingen tar vanligvis for lang tid. Følgende kode illustrerer den med iteratorer:
VectorVtr = 'E', 'g', 'i', 'e', 'a', 'e', 'c', 'a', 'c';for (vektor :: iterator itei = VTR.begynne(); itei
for (vektor :: iterator itej = itei+1; itej
VTR.slette (itej);
for (int i = 0; i
cout<
I parentesene til den indre for-loopen.
Fjerne duplikater ved sort-and-compare
Legg merke til fra metoden ovenfor at det er mye omskanning (omlesing og sammenligning) fra stor sekvens, til liten sekvens av elementer i den ene vektoren. Hvis hele vektoren skannes en eller to ganger, vil dette sannsynligvis bety mindre tilgang til elementene sammenlignet med ovennevnte tilnærming. Vel, hele vektoren kan til og med skannes fire eller flere ganger, men ikke mange ganger. Dette må ikke nødvendigvis gjøres med samme vektor. Det kan gjøres med kopier av vektoren.
Med den andre tilnærmingen opprettholdes den opprinnelige vektoren mens en sortert kopi er laget av den. Den sorterte vektoren blir lest gjennom (skannet), og sletter duplikatet av påfølgende elementer som skjedde mer enn en gang. En iterator for-loop kan oppnå dette, fra begynnelsen til slutten av den sorterte vektoren, en gang gjennom. Mens denne lesningen og noe sletting finner sted, for ethvert element som oppstår mer enn en gang, blir en kopi av elementet laget nøkkel på et kart, og den tilsvarende verdien for denne tasten, er gitt verdien -1. Denne verdien på -1 vil bli endret til 1 for å indikere en duplikat. Hver verdi på kartet er en indikator for duplikat av nøkkelen som kan oppstå to eller flere ganger i den opprinnelige vektoren.
Hvis den sorterte vektoren med duplikater fjernet var nødvendig, blir den sorterte vektoren returnert, og arbeidet er utført. Hvis rekkefølgen på den første forekomsten av vektorelementene må opprettholdes, må følgende underbehandling finne sted (fortsett):
Les den originale vektoren på nytt fra begynnelsen. Når du leser, hvis en nøkkel ikke oppstår på kartet (kart returnerer 0), kan du tillate den tasten i den opprinnelige vektoren. Dette betyr at nøkkelen ikke har noen duplikat. Hvis en nøkkel på den opprinnelige vektoren oppstår på kartet, betyr det at det er den første forekomsten av duplikater for det elementet i vektoren. Gjør indikatorverdien for nøkkelen på kartet, 1. Den indikatorverdien har nå verdien, 1. Fortsett å lese resten av elementene i den originale vektoren, og sjekk for duplikatelement med kartet. Hvis en nøkkel er funnet og kartverdien er 1, er det gjeldende elementet et duplikat. Fjern det nåværende elementet. (Husk at den første forekomsten av en duplikatnøkkel gjorde den tilsvarende indikatorverdien på kartet fra -1 til 1.) Fortsett å gi en verdi på 1 for karttastindikatorene, fjerne det opprinnelige strømvektorelementet som allerede har en tilsvarende 1 på kartet fra den opprinnelige vektoren; til slutten av den opprinnelige vektoren er nådd. Den resulterende originale vektoren er vektoren uten noe duplikatelement, og i rekkefølgen med første forekomster.
For å kodekart i C ++, må MAP (Unordered_Map) bibliotek inkluderes. Siden sort () -funksjonen i algoritmebiblioteket vil bli brukt, må også algoritmebiblioteket inkluderes i programmet. Overskriften for programmet for denne tilnærmingen, bør være:
#inkludere#inkludere
#inkludere
#inkludere
ved hjelp av navneområdet STD;
Det første kodesegmentet i C ++ hovedfunksjonen kan være:
vektorvektor
Sorter (VTR.Begynn (), VTR.slutt());
uordnede_map
Den første uttalelsen definerer den opprinnelige vektoren. Den andre uttalelsen lager en kopi av den opprinnelige vektoren. Den tredje uttalelsen sorterer den kopierte vektoren. Den fjerde uttalelsen erklærer kartet, uten initialisering. Neste kodesegment i C ++ hovedfunksjonen, kan være:
for (vektor :: iterator iter = vtr.begynne(); iterif ( *iter0 == *iter1)
MP [*iter1] = -1;
iter--;
vektor :: iterator iter2 = vtr.slette (iter1);
Dette kodesegmentet sletter duplikatene fra den sorterte kopierte vektoren. Mens du gjør det, oppretter det kartoppføringene. Merk at i parentesene til for-loopen når iterasjonen det siste-men-en-elementet (og ikke det siste elementet). Dette er fordi gjeldende og neste elementer er involvert i koden. Legg også merke til at når et element skal slettes, blir iteratoren forsinket (dekrementert) med ett trinn.
Hvis den sorterte vektoren uten duplikater er det som var nødvendig, ville følgende kode vise resultatet:
for (int i = 0; icout<
Vtro.slette (iter);
iter--;
if (mp [*iter] == -1)
MP [*iter] = 1;
Årsaken til å velge, -1 og 1, i stedet for 0 og 1, er fordi standard (fraværende) verdi av dette kartet er 0. Dette unngår forvirringen med elementene som ikke har duplikat i det hele tatt. En vanlig for-sløyfe som følger kan skrive ut den endelige (reduserte) originale vektoren:
for (int i = 0; icout<
Utgangen til programmet er:
A c e g iE g i a c
Den første linjen i utgangen er den sorterte inngangen uten duplikater. Den andre linjen er inngangen i den gitte rekkefølgen, med duplikatene fjernet.
Konklusjon
For å fjerne duplikater fra en C ++ -vektor, kan brute-Force-metoden brukes. Denne metoden er vanligvis treg. Leseren anbefales å bruke sort-and-compare-metoden, som vanligvis er rask, for hans/hennes kommersielle arbeid. Begge metodene er forklart ovenfor.