Unike og bestilte containere i C ++

6, 10, 2, 8, 4 er et sett; 2, 4, 6, 8, 10 er et sett med de samme heltallene, ordnet i stigende rekkefølge. I matematikk har et sett unike elementer (distinkte elementer), og det vil si at ikke noe element forekommer mer enn en gang. Videre er et multisett et sett, der ethvert element kan oppstå mer enn en gang. 6, 6, 10, 2, 2, 8, 4, 4, 4 er en multisett. 2, 2, 4, 4, 4, 6, 6, 8, 10 er det samme multiset, men med elementene anordnet i stigende rekkefølge. Denne artikkelen omhandler ikke multisett. Den omhandler C ++ datastrukturen som heter, sett.

Et kart i programvare er som en matrise, men det er en matrise med to kolonner i stedet for en. Den første kolonnen har tastene og den andre kolonnen har verdiene. Hver rad er ett par, og lager et nøkkel/verdipar. En nøkkel er direkte relatert til verdien.

Et eksempel på et kart er 'c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10. Det første nøkkelen/verdiparet som er satt inn her, er 'C', 3, der 'C' er nøkkelen og 30 er verdien. Dette kartet er ikke bestilt av nøkler. Bestilling av dette kartet med nøkler produserer 'a', 10, 'b', 20, 'c', 30, 'd', 30, 'e', 40. Legg merke til at det kan være dupliserte verdier, men ikke dupliserte nøkler. Et bestilt kart er et kart bestilt av nøkler.

Et multisett er til et sett, ettersom en multimap er et kart. Dette betyr at det er kart med dupliserte nøkler. Et eksempel på en multiMap er 'a', 10, 'b', 20, 'b', 20, 'c', 30, 'c', 30, 'd ', 30, ' e ', 40. Og som nevnt ovenfor, omhandler ikke denne artikkelen multimap, snarere omhandler den C ++ datastrukturen som heter, MAP.

I C ++ er en datastruktur en struktur med egenskaper (datamedlemmer) og metoder (medlemsfunksjoner). Dataene til strukturen er en liste; Et sett er en liste; Et kart er en liste over nøkkel/verdipar.

Denne artikkelen diskuterer det grunnleggende om sett og kart i C ++, og for å bedre forstå denne artikkelen, burde leseren ha hatt en grunnleggende kunnskap om C++.

Artikkelinnhold:

• Klasse og dets gjenstander
• Opprette et sett eller et kart
• Iterator grunnleggende
• Elementtilgang for sett og kart
• Order av elementer i et sett eller kart
• Andre ofte brukte medlemsfunksjoner
• Konklusjon

Klasse og dets objekter:

I C ++ kalles settet, kartet og andre lignende strukturer containere. En klasse er en generalisert enhet med datamedlemmer, som er variabler, og medlemsfunksjoner som er relatert. Når datamedlemmer får verdier, dannes et objekt. Imidlertid dannes et objekt i en prosess som kalles instantiering. Ettersom en klasse kan føre til forskjellige verdier for de samme datamedlemsvariablene, kan forskjellige objekter deretter bli instantiert fra samme klasse.

I C ++ er et ubrukelig sett en klasse, i tillegg til et ubrukelig kart. Når et objekt blir instantiert fra det ubrukelige settet eller det ubrukelige kartet, blir objektet den virkelige datastrukturen. Med datastrukturer for sett og kart er det viktigste datamedlemmet en liste. Vel, settet og kartet danner en gruppe containere kalt, bestilte assosiative containere. Ubestilt sett og det uordnede kartet eksisterer også, men de er dessverre ikke adressert i denne artikkelen.

Opprette et sett eller et kart:

Instortering av et sett fra settklassen skaper et sett; Instortering av et kart fra kartklassen er å lage et kart. Objektet som er opprettet som er opprettet, får et navn på programmererens valg.

For å lage et sett, bør programmet begynne med:

#inkludere
#inkludere
ved hjelp av navneområdet STD;

Legg merke til direktivet “#include”, som inkluderer det faste biblioteket som har den angitte klassen som angitt datastrukturer vil bli instantiert.

For å lage et kart, bør programmet begynne med:

#inkludere
#inkludere
ved hjelp av navneområdet STD;

Legg merke til direktivet “#include”, som inkluderer kartbiblioteket som har kartklassen som kartdatastrukturer vil bli instantiert.

Syntaksen for å lage et tomt sett er:

sett Objektnavn

Eksempel:

sett setobj;

Et eksempel for å lage et sett med innhold er:

sett setobj (6, 10, 2, 8, 4);

Syntaksen for å lage et tomt kart er:

kart Objektnavn

Eksempel:

kart mapobj;

Et eksempel for å lage et kart med innhold er:

kart mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);

Iterator grunnleggende:

En iterator er en utdypet peker, som kan brukes til å krysse listen over datastrukturen fra begynnelse til slutt.

BEGIN () Medlemsfunksjon

Start () Medlemsfunksjonen returnerer en iterator som peker på det første elementet på listen. Følgende eksempel illustrerer dette for settet:

sett setobj (6, 10, 2, 8, 4);
sett:: iterator iter = setobj.begynne();
cout << *iter << '\n';

Legg merke til måten å begynne () har blitt brukt med setobj og dot -operatøren. iter er det returnerte iteratorobjektet. Legg også merke til måten den er erklært. * er indireksjonsoperatøren. Som brukt med ITER, returnerer det det første elementet i settet; Det første elementet er 2 i stedet for 6 - se forklaring nedenfor.

Følgende eksempel illustrerer bruken av start () -funksjonen for kartet:

kart mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
kart:: iterator iter = mapobj.begynne();
cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Legg merke til måten Begin () har blitt brukt med Mapobj og DOT -operatøren. iter er det returnerte iteratorobjektet. Legg også merke til måten den er erklært. "Først", som brukt her, refererer til nøkkelen. “Second” refererer til verdien som tilsvarer nøkkelen. Observer hvordan de har blitt brukt med ITER for å få startelementkomponentene på listen. Det første elementet er a, 10 i stedet for c, 30 - se forklaring nedenfor.

"BEGIN () const" medlemsfunksjonen

"Begin () const" -medlemsfunksjonen returnerer en iterator som peker på det første elementet på listen når erklæringen til settet begynner med Const (for konstant). Under denne tilstanden kan verdien på listen, referert til av iteratoren som er returnert, ikke endres av iteratoren. Følgende eksempel illustrerer bruken for settet:

const sett setobj (6, 10, 2, 8, 4);
sett:: const_iterator iter = setobj.begynne();
cout << *iter << '\n';

Legg merke til måten å begynne () har blitt brukt med setobj og dot -operatøren. Ingen "const" er blitt skrevet like etter begynnelse (). Imidlertid har "const" gått foran erklæringen. iter her er det returnerte konstante iteratorobjektet, som er forskjellig fra den normale iteratoren. Legg også merke til måten den er erklært. * er indireksjonsoperatøren; Som brukt med iter, returnerer det det første elementet i settet. Det første elementet er 2 i stedet for 6 - se forklaring nedenfor.

Følgende eksempel illustrerer bruken av "Begin () const" -funksjonen for kartet:

const kart mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
kart:: const_iterator iter = mapobj.begynne();
cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Legg merke til måten Begin () har blitt brukt med Mapobj og DOT -operatøren. Ingen "const" er blitt skrevet like etter begynnelse (). Imidlertid har "const" gått foran erklæringen. iter her er det returnerte konstante iteratorobjektet, som er forskjellig fra den normale iteratoren. Legg også merke til måten den er erklært. “Først”, som brukt her, refererer til nøkkelen; “Second”, som brukt her, refererer til verdien som tilsvarer nøkkelen. Observer hvordan de har blitt brukt med ITER for å få startelementkomponentene på listen. Det første elementet er a, 10 i stedet for c, 30 - se forklaring nedenfor.

Slutt () medlemsfunksjon

Slutt () Medlemsfunksjon returnerer en iterator som peker rett etter slutten av listen. Følgende eksempel illustrerer dette for settet:

sett setobj (6, 10, 2, 8, 4);
sett:: iterator iter = setobj.slutt();
cout << *iter << '\n';

Legg merke til måten ende () har blitt brukt med setobj og dot -operatøren. iter er det returnerte iteratorobjektet. Legg også merke til måten den er erklært. * er indireksjonsoperatøren; Som brukt med Iter, returnerer det det siste+1 -elementet i settet. I forfatterens datamaskin er dette siste+1 -elementet 5, som ikke er på listen. Så forsiktig med å bruke dette elementet.

Følgende eksempel illustrerer bruken av enden () -funksjonen for kartet:

kart mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
kart:: iterator iter = mapobj.slutt();
cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Legg merke til måten ende () har blitt brukt med mapobj og dot -operatøren. iter er det returnerte iteratorobjektet. Legg også merke til måten den er erklært. * er indireksjonsoperatøren; Som brukt med iter, returnerer det det siste+1 -elementet på kartet. I forfatterens datamaskin er dette siste+1 -elementet , 0, som ikke er i listen. Så forsiktig med å bruke dette elementet.

"End () const" medlemsfunksjon

"End () const" medlemsfunksjonen returnerer en iterator som peker rett etter slutten av listen når erklæringen til settet begynner med Const (for konstant). Under denne tilstanden kan verdien på listen, referert til av iteratoren som er returnert, ikke endres av iteratoren. Følgende eksempel illustrerer bruken for settet:

const sett setobj (6, 10, 2, 8, 4);
sett:: const_iterator iter = setobj.slutt();
cout << *iter << '\n';

Legg merke til måten ende () har blitt brukt med setobj og dot -operatøren. Ingen "const" er blitt skrevet rett etter slutten (). Imidlertid har "const" gått foran erklæringen. iter er det returnerte iteratorobjektet. Legg også merke til måten den er erklært. * er indireksjonsoperatøren; Som brukt med Iter, returnerer det det siste+1 -elementet i settet.

Følgende eksempel illustrerer bruken av "end () const" -funksjonen for kartet:

const kart mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
kart:: const_iterator iter = mapobj.slutt();
cout << "" << (*iter).first <<',' << (*iter).second << "\n";

Legg merke til måten ende () har blitt brukt med mapobj og dot -operatøren. Ingen "const" er blitt skrevet rett etter slutten (). Imidlertid har "const" gått foran erklæringen. iter er det returnerte konstante iteratorobjektet, som er forskjellig fra den normale iteratoren. Også nøye observere måten den er erklært.

Elementtilgang for sett og kart:

Sett

Med settet blir elementet lest ved hjelp av indireksjonsoperatøren. De to første elementene i et sett blir lest i følgende eksempel:

sett setobj (6, 10, 2, 8, 4);
sett:: iterator iter = setobj.begynne();
cout << *iter << '\n';
++iter;
cout << *iter << '\n';

Utgangen er 2, deretter etterfulgt av 4 - se forklaring nedenfor. For å peke på neste element på listen, økes iteratoren.

Merk: Et element kan ikke endres ved hjelp av indireksjonsoperatøren for settet. For eksempel "*iter = 9;" det er ikke mulig.

kart

Et kart består av nøkkel/verdipar. En verdi kan leses ved hjelp av den tilsvarende tasten, og endres ved hjelp av samme tast. Følgende kodesegment illustrerer dette:

kart mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
cout << mapObj['b'] << '\n';
mapobj ['b'] = 55;
cout << mapObj['b'] << '\n';

Utgangen er:

20
55

Dot -operatøren har ikke blitt brukt her. I stedet er det den firkantede parentesoperatøren, som tar nøkkelen som innhold, som har blitt brukt.

Order av elementer i et sett eller kart:

Elementer kan settes inn i et sett, i hvilken som helst rekkefølge. Imidlertid, når den er satt inn, omorganiserer settet elementene i stigende rekkefølge. Stigende ordre er standardbestillingen. Hvis det er nødvendig med nedgangsrekkefølge, må settet erklæres som i følgende eksempel:

sett > setobj (6, 10, 2, 8, 4);

Så etter typen, e.g., Int, for malen er det et komma, etterfulgt av "større" i vinkelbrakettene.

Elementer kan settes inn i et kart i hvilken som helst rekkefølge. Når det først er satt inn, omorganiserer kartet elementene i stigende rekkefølge av nøkkel (bare) mens du opprettholder forholdet mellom hver nøkkel og dets verdi. Stigende ordre er standardordre; Hvis det er nødvendig med nedgangsrekkefølge, må kartet deklareres som i følgende eksempel:

kart > mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);

Så etter typeparet, e.g., “Char, Int”, for malen er det et komma, etterfulgt av “større” i vinkelbrakettene.

Krysser et sett

Mens-loop eller for-loop med iteratoren kan brukes til å krysse et sett. Følgende eksempel bruker en for-loop for å krysse et sett som er konfigurert i synkende rekkefølge:

sett > setobj (6, 10, 2, 8, 4);
for (sett:: iterator iter = setobj.begynne(); iter != setobj.slutt(); ++ iter)

cout << *iter << ";

Utgangen er:

10 8 6 4 2

Økt en iterator peker det på neste element.

Krysser et kart

While-loop eller For-loop med iteratoren kan brukes til å krysse et kart. Følgende eksempel bruker en for-loop for å krysse et kart som er konfigurert i synkende rekkefølge:

kart > mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
for (kart:: iterator iter = mapobj.begynne(); iter != mapobj.slutt(); ++ iter)

cout << "" << (*iter).first << ", " << (*iter).second << "" << ", ";

Utgangen er:

e, 40, d, 30, c, 30, b, 20, a, 10,

Økt en iterator peker det på neste element. "Først", i koden, refererer til nøkkelen og "andre" refererer til tilsvarende verdi. Legg merke til hvordan disse verdiene er oppnådd for utgangen.

Andre ofte brukte medlemsfunksjoner:

Størrelsen () -funksjonen

Denne funksjonen returnerer et heltall, som er antall elementer i listen. Sett eksempel:

sett > setobj (6, 10, 2, 8, 4);
cout << setObj.size() << '\n';

Utgangen er 5.

Karteksempel:

kart > mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
cout << mapObj.size() << '\n';

Utgangen er 5.

Insert () -funksjonen

sett

Set tillater ikke duplikat. Så, alle duplikat som er satt inn, blir lydløst avvist. Med settet er argumentet til Insert () -funksjonen verdien som skal settes inn. Verdien er montert i en posisjon, der rekkefølgen i settet forblir stigende eller synker. Eksempel:

sett setobj (6, 10, 2, 8, 4);
setobj.sett inn (6);
setobj.sett inn (9);
setobj.sett inn (12);
for (sett:: iterator iter = setobj.begynne(); iter != setobj.slutt(); ++ iter)

cout << *iter << ";

Utgangen er:

2 4 6 8 9 10 12

Merk: INSERT () medlemsfunksjonen kan brukes til å befolke et tomt sett.

kart

Kart tillater ikke duplikat med tast. Så, alle duplikat som er satt inn, blir lydløst avvist. Med kartet er argumentet til Insert () -funksjonen nøkkelen/verdiparet i tannregulering. Elementet er montert i en posisjon etter nøkkel, der rekkefølgen på kartet forblir stigende eller synker. Eksempel:

kart mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
mapobj.sett inn ('e', 80);
mapobj.sett inn ('f', 50);
mapobj.sett inn ('g', 60);
for (kart:: iterator iter = mapobj.begynne(); iter != mapobj.slutt(); ++ iter)
cout << "" << (*iter).first << ", " << (*iter).second << "" << ", ";

Utgangen er:

a, 10, b, 20, c, 30, d, 30, e, 40, f, 50, g, 60,

Merk: INSERT () medlemsfunksjonen kan brukes til å befolke et tomt kart.

Den tomme () funksjonen

Denne funksjonen returnerer sann hvis listen er tom, og falsk hvis annet. Sett eksempel:

sett setobj (6, 10, 2, 8, 4);
bool ret = setobj.tømme();
cout << ret << '\n';

Utgangen er 0 for falsk, noe som betyr at settet her ikke er tomt.

Karteksempel:

kart mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
bool ret = mapobj.tømme();
cout << ret << '\n';

Utgangen er 0 for falsk, noe som betyr at kartet her ikke er tomt.

Sletting () -funksjonen

sett

Tenk på følgende kodesegment:

sett setobj (10, 20, 30, 40, 50);
sett:: iterator iter = setobj.begynne();
sett:: iterator itr = setobj.slette (iter);
cout << "new size: " << setObj.size() << '\n';
cout << "next value: " << *itr << '\n';
itr = setobj.slette (ITR);
cout << "new size: " << setObj.size() << '\n';
cout << "next value: " << *itr << '\n';

Utgangen er:

Ny størrelse: 4
Neste verdi: 20
Ny størrelse: 3
Neste verdi: 30

Sletting () -funksjonen tar en iterator som peker på et element som et argument. Etter å ha slettet elementet, returnerer slette () -funksjonen en iterator som peker på neste element.

kart

Tenk på følgende kodesegment:

kart mapobj ('a', 10, 'b', 20, 'c', 30, 'd', 40, 'e', 50);
kart:: iterator iter = mapobj.begynne();
kart:: iterator itr = mapobj.slette (iter);
cout << "new size: " << mapObj.size() << '\n';
cout << "next value pair: " << (*itr).first <<',' << (*itr).second << "\n";
itr = mapobj.slette (ITR);
cout << "new size: " << mapObj.size() << '\n';
cout << "next value pair: " << (*itr).first <<',' << (*itr).second << "\n";

Utgangen er:

Ny størrelse: 4
Neste verdipar: B, 20
Ny størrelse: 3
Neste verdipar: C, 30

Sletting () -funksjonen tar en iterator som peker på et element som et argument. Etter å ha slettet elementet, returnerer slette () -funksjonen en iterator som peker på neste element.

Den klare () -funksjonen

Den klare () -funksjonen fjerner alle elementene i listen. Sett eksempel:

sett setobj (6, 10, 2, 8, 4);
setobj.klar();
cout << setObj.size() << '\n';

Utgangen er 0.

Karteksempel:

kart mapobj ('c', 30, 'b', 20, 'd', 30, 'e', 40, 'a', 10);
mapobj.klar();
cout << mapObj.size() << '\n';

Utgangen er 0.

Konklusjon:

En angitt datastruktur i C ++ er en struktur der listen over elementer er lagret i stigende rekkefølge som standard, eller i synkende rekkefølge etter programmerers valg. Alle elementene i settet er unike. En kartdatastruktur i C ++ er en struktur der listen er en hasj av nøkkel/verdipar, lagret i stigende rekkefølge av nøkler som standard, eller i synkende rekkefølge av nøkler etter programmererens valg. Tastene er også unike, og det kan være dupliserte verdier. Det viktigste datamedlemmet til en av strukturene er listen. Enten har struktur medlemsfunksjoner, hvorav noen ofte brukes.