C ++ uordnede settfunksjoner
En hash -tabell brukes til å konstruere et uordnet sett der verdiene blir konvertert til hash -tabellindekser for å sikre at å sette inn en verdi alltid blir tilfeldig tildelt. Faktum er at de opererer godt nok og normalt gir en konstant tidssøkingsoperasjon. Alle funksjoner på det uordnede settet krever vanligvis en konstant tid O (1). Selv om de i den verste situasjonen kan ta opp til den lineære tiden o (n) basert på den operasjonelle hasjalgoritmen.
Det uordnede settet kan omfatte nøkler av noe slag, enten de er forhåndsdefinerte eller brukerdefinerte datatyper. Men når vi erklærer nøklene til de brukerdefinerte datastrukturer, må vi derfor indikere sammenligningsmetoden som brukes til å sammenligne nøklene.
Forskjell mellom sett og uordnet sett
Et sett er en bestilt samling av forskjellige nøkler. Men et uordnet sett er en samling nøkler som kan ordnes i hvilken som helst sekvens. Implementering av sett som en balansert trestruktur gjør det mulig å beholde rekkefølgen på komponentene. Setoperasjoner har en O (log n) tidskompleksitet, men et uordnet sett har en O (1). Tallrike metoder er definert for det uordnede settet. Men de mest populære er størrelsen og den tomme metoden for lagring, å finne verdien av nøkkelen, og sette inn og fjerne for konfigurasjon. Bare de distinkte tastene støttes av det uordnede settet; For dupliserte nøkler kan det brukes en uordnet multisett.
Funksjoner som brukes til uordnede sett
Det uordnede settet har følgende metoder:
- Sett inn (): Denne funksjonen legger til et nytt element i beholderen.
- Slutt () Funksjon: Den returnerer en iterator som peker på varen etter slutten.
- Count () Funksjon: Det teller antall ganger et spesifikt element vises i et uordnet sett.
- Finn () Metode: Den finner en komponent i settet.
- Clear () Funksjon: Det tømmer et uordnet sett ved å fjerne alle komponentene.
- Cbegin () -funksjon: Den returnerer en konstant iterator som tilsvarer det første medlemmet i det uordnede settet.
- Cend () -funksjon: Den returnerer en konstant iterator med den siste verdien i det uordnede settet.
- Bucket_Size (): I et uordnet sett returnerer denne funksjonen den totale tellingen av elementer som er til stede i en viss bøtte.
- Sletting () -funksjon: Den sletter fra start til slutt om det bare er en komponent eller en samling av elementer.
- Størrelse () Funksjon: Det gir det uordnede settet til varetallet.
- Swap () -funksjon: Den lar deg bytte data fra to uordnede sett.
- Emplace () -funksjon: Legger til et element som bruker denne funksjonen i et uordnet sett.
- MAX_SIZE (): Denne funksjonen returnerer de fleste elementene et uordnet sett er i stand til å holde.
- Tom () metode: Det sjekker om et uordnet sett er tomt.
- Lik rekkevidde: Det returnerer et område med alle elementer som har den forhåndsbestemte verdien som deres verdi.
- Hash -metode (): Dette er en unary metode som bare godtar en parameter og konstruerer sin avkastningsverdi på en entall størrelse_t verdi.
- Reserve () -funksjon: Den brukes til å kreve et uordnet setts kapasitet som skal endres.
- Bøtte () -funksjon: Den returnerer varens bøtte nummer.
- BUCKET_COUNT () Funksjon: Et uordnet setts totale antall bøtter returneres med denne metoden.
- Load_factor (): Den returnerer kapasitetsfaktoren som ofte brukes til det uordnede settet.
- Rehash () -funksjon: Det øker spekteret av bøtter i det uordnede settet til det definerte antallet eller høyere.
- Max_load_factor (): den returnerer den ultimate lastekapasitetsindeksen som det uordnede settet kan støtte.
- Emplace_hint () -funksjon: Med bruk av et hint legger den bare til et nytt element til et uordnet sett hvis verdien er distinkt.
- Key_eq () -funksjon: Den gir en boolsk verdi basert på sammenligningen.
Utførelsen av forskjellige uordnede funksjoner i C ++ språk dekkes i denne artikkelen.
Eksempel 1:
Gjennomsnittlig prosesseringstid for funksjonene for funn (), innsats () og sletting () er konstant. Hvis nøkkelen ikke er til stede i det definerte settet, gir Find () -metoden en iterator til slutt () -funksjonen; ellers returnerer den en iterator til nøkkelattributtet. For å skaffe nøkkelen ved å henvise nøkkelverdiene med * operatøren, fungerer iteratoren som en peker til nøkkelattributtene. Følgende er en forekomst av en erklæring for Find (), Sett inn () og iterasjonsfunksjoner i et uordnet sett.
#inkludereved hjelp av navneområdet STD;
int main ()
uordnede_setstrenger;
strenger.Sett inn ("i");
strenger.Sett inn ("kjærlighet");
strenger.Sett inn ("til");
strenger.Sett inn ("Play");
strenger.Sett inn ("badminton");
String key = "Like";
hvis (strenger.finn (nøkkel) == strenger.slutt())
cout<< key << " to explore " <
cout<< "explore " << key <
hvis (strenger.finn (nøkkel) == strenger.slutt())
cout<< key << " to explore\n" ;
ellers
cout<< "explore " << key <
uordnede_set :: iterator i;
for (i = strenger.begynne(); Jeg != strenger.slutt(); i ++)
cout<< (*i) <
Vi innlemmer overskriftsfilen i begynnelsen av denne koden. Deretter går vi inn i standard navneområdet som STD. Deretter påkaller vi main () -funksjonen. Innenfor denne funksjonen erklærer vi det uordnede settet. Her bruker vi et uordnet sett for å ordne elementene i settene. Vi passerer strengen som parameter for den uordnede settfunksjonen. Deretter setter vi inn de forskjellige strengene i settene. Vi passerer de mange strengene som argumentene til innsatsen () -funksjonen. Deretter spesifiserer vi verdien av nøkkelen ved å bruke nøkkelordet "-tasten". Find () -metoden brukes i neste trinn. Denne funksjonen brukes for å finne den nødvendige strengen til settet.
Vi bruker enden () -metoden for å avslutte strengene. Denne funksjonen returnerer iteratoren når nøkkelen ikke eksisterer i settet. Kommandoen “cout” blir brukt for å skrive ut uttalelsen. Deretter initialiserer vi igjen en verdi for "nøkkel" -attributtet. Vi finner verdien av en attributt i strengen ved å bruke Find () -funksjonen og avslutte strengen ved hjelp av enden () -metoden. Vi bruker "cout" -uttalelsen for å vise resultatet. Vi itererer over hele settet og skriver ut innholdet i settet ved å bruke "cout" -uttalelsen. Vi bruker den uordnede settmetoden så vel som å erklære iteratoren som "jeg". "For" -sløyfen er ansatt.
Først initialiserer vi en variabel og bruker deretter BEGIN () -funksjonen for å starte den spesifiserte strengen. Videre definerer vi løkkenes tilstand. Slutt () -funksjonen kalles. Verdien av iteratoren økes med 1. Til slutt brukes "cout" -uttalelsen for å vise verdien av iteratoren.
Eksempel 2:
I dette tilfellet vil vi utføre en kode der vi erklærer en liste over forskjellige verdier, og så finner vi alle duplikatene fra den listen ved bruk av den uordnede settfunksjonen.
#inkludereved hjelp av navneområdet STD;
ugyldig utskriftsduplikater (int a [], int b)
uordnede_setintset;
uordnede_setduplikat;
for (int j = 0; j < b; j++)
if (intet.finn (a [j]) == intset.slutt())
Intset.sett inn (a [j]);
ellers
duplisere.sett inn (a [j]);
cout<< "The list of duplicated elements: ";
uordnede_set :: iterator det;
for (det = duplikat.begynne(); den != duplikat.slutt(); det ++)
cout<< *it << " ";
int main ()
int a [] = 11, 30, 42, 21, 94, 35, 11, 77, 62, 89, 94, 35;
int b = størrelse av (a) / størrelse av (int);
printduplicates (a, b);
retur 0;
Her inkluderer vi biblioteket. I neste trinn bruker vi standard navneområde som STD. Vi bruker metoden Print () for å vise replikatet i den definerte matrisen ved bruk av et uordnet sett. Vi gir en matrise og en variabel for å forvrenge heltallet som argumenter for printduplicates () -metoden.
Nå erklærer vi de uordnede settene for å skaffe og lagre duplikatene. Den uordnede settfunksjonen brukes. Vi passerer heltallet som parameter. Deretter bruker vi en annen uordnet settfunksjon for å finne duplikatelementene. Her bruker vi “for” -sløyfen. Vi erklærer en variabel av "for" -sløyfen. Deretter spesifiserer vi tilstanden. Deretter øker vi verdien “j”. Vi kaller Find () -funksjonen for å finne det definerte elementet i matrisen. Vi passerer det spesifikke elementet som argumentet for denne funksjonen. Hvis det nødvendige elementet allerede er til stede i matrisen, setter vi inn det duplikatsettet.
Vi viser de dupliserte verdiene til matrisen ved å bruke "cout" -uttalelsen. Vi erklærer variabelen “It” for iteratoren for det uordnede settet. "For" -sløyfen påføres. Deretter brukes BEGIN () og END () metoder i "for" -sløyfen. Etter det kaller vi Main () -funksjonen. Vi initialiserer en variabel “a”. Deretter definerer vi elementene for matrisen, og denne matrisen lagres i en variabel “A”. Vi finner størrelsen på den nødvendige matrisen ved å bruke størrelse av () -metoden. Vi passerer matrisen som parameter for denne funksjonen.
Vi deler den resulterende verdien med heltallets størrelse. Verdien vi får etter deling lagres i en variabel “B”. Vi viser duplikatverdiene til matrisen ved hjelp av printDuplicate () -metoden. Til slutt bruker vi kommandoen “Return 0”.
Eksempel 3:
Et dataelement kan legges til den uordnede settbeholderen ved hjelp av den innebygde C ++ standardmalbibliotekfunksjonen - Instert () -funksjonen. Hvert element i et uordnet sett har en bestemt verdi og legges bare til hvis det ikke er tilgjengelig i settet. Siden beholderen bruker flere hashingmetoder, utføres innsatsen automatisk på det punktet som optimalt oppfyller kravet. Som et resultat forbedres beholderens størrelse betydelig av antall hentet varer.
Parametere for innsats () -metode:
- Verdi: Den definerer verdien som skal legges til beholderen.
- Først, sist: iteratorer som gir en rekke komponenter. Merk at området omfatter alle komponenter mellom det første elementet og det siste elementet, for eksempel det som er spesifisert av det første elementet, men avslutter elementet som er pekt på av det siste elementet.
Metoden returnerer et par, og har paret :: Først konfigurert til en iterator som refererer til det nye oppdaterte elementet eller den tilsvarende komponenten som allerede er til stede i settet. Hvis et nytt dataelement blir lagt til, blir paret :: andre komponent i paret justert til True; Ellers er det spesifisert som usant hvis et identisk element allerede er til stede.
Følgende program viser den nevnte funksjonen:
#inkludere#inkludere
#inkludere
ved hjelp av navneområdet STD;
int main ()
uordnede_set set = "mandag", "tirsdag";
String str = "onsdag";
Sett.sett inn (str);
cout<< "The set of week days is:"
<
cout<< m
<< " ";
cout<
Først av alt integrerer vi de nødvendige overskriftsfilene. Det er ansvarlig for inngangs- og utgangsfunksjonalitetene. Overskriftsfilen inneholder erklæringen av strengene. Den tredje har alle uordnede settene. Vi bruker standard navneområde som STD. Deretter starter vi kodingen inne i kroppen til Main () -funksjonen etter å ha ringt Main () -funksjonen. Vi bruker det uordnede settet med strenger.
Her definerer vi elementene i settet mitt. Vi spesifiserer de to dagene i uken. Nå indikerer vi verdien av strengen som vi ønsker å bli satt inn i det nødvendige settet. Vi setter inn den strengen ved å bruke Sett inn () -metoden. Uttalelsen om "cout" er brukt for å vise teksten "settet med hverdager er". Vi bruker "cout" -uttalelsen igjen før vi legger inn "return 0" -kommandoen. Denne "cout" uttalelsen skriver ut alle ukedagens navn.
Konklusjon
Bruken av C ++ uordnede settfunksjoner dekkes i denne artikkelen. Vi implementerte de flere kodene på Devc ++ -programvare der vi benyttet mange funksjoner relatert til de uordnede settene. Uordnede sett er datastrukturer som kan inneholde forskjellige komponenter i hvilken som helst rekkefølge og gi effektiv tilgang til spesifikke elementer basert på deres verdi. I første omgang benyttet vi oss av de flere uordnede settfunksjonene for å undersøke hvordan koden fungerer. Ved hjelp av Find () -metoden identifiserte vi et bestemt element i settet. Ved hjelp av slutt () -funksjonen avsluttet vi det uordnede settet. I den andre illustrasjonen konstruerte vi en matrise som inneholder forskjellige heltall. Både gjentatte og ikke-gjentatte verdier er inkludert i matrisen. For å finne duplikatverdiene i den spesifiserte matrisen, brukte vi Find () -metoden. Insert () -metoden ble brukt i det siste eksemplet for å tilføre en verdi til det nødvendige uordnede settet.