C ++ Kart sorter etter tast

Et kart består av nøkkel/verdipar. Hvert par er et element. Alle nøkler på et kart er unike. Et kart kan sorteres etter nøkler. Sortering kan være stigende eller synke. Stigende er standard. Sortering på et kart er ikke alltid grei. Den trenger et sammenligningsfunksjonsobjekt. Hvis sammenligningsobjektet blir ignorert, finner standard sortering sted.

Hvis tastene er konstante pekere-til-karaktører, blir kartet sortert av nøkkelpekerne, og ikke av nøkkelstrenglitteraler. Dette er neppe det noen vil ha. Tenk på følgende nøkkel/verdipar av frukt og deres ytre farger:

"plomme" => "lilla"
"Blackberry" => "Mørkeblå-svart"
"Watermelon" => "Grønn"
"aprikos", => "oransje"
"Papaya" => "Orange"
"Banan" => "Gul"

Fruktene er nøklene, og fargene er verdiene. Denne listen over elementer (nøkkel/verdipar) er ikke sortert. Følgende program oppretter et kart over denne listen slik det er og viser det som det er, usortert av strenglitteraler:

#inkludere
#inkludere
ved hjelp av navneområdet STD;
int main ()

kart MP;
MP ["Plum"] = "Purple";
MP ["BlackBerry"] = "Dark Blue-Black";
MP ["Watermelon"] = "Green";
MP ["Apricot"] = "Orange";
MP ["Papaya"] = "Orange";
MP ["Banana"] = "Gul";
for (kart:: iterator it = mp.begynne(); den != MP.slutt(); det ++)
cout << it->først << " => "" << it->sekund << endl;
retur 0;

Utgangen er:

plomme => lilla
blackberry => mørkeblå-svart
vannmelon => grønn
aprikos => oransje
papaya => oransje
banan => gul

Usortert av strenglitteraler, men sortert etter pekere. For å bruke et kart i et C ++ -program, må kartbiblioteket inkluderes med et Inkluder -direktiv.

En annen måte å lage det enkle kartet ovenfor, er som følger:

#inkludere
#inkludere
ved hjelp av navneområdet STD;
int main ()

kart MP ("Plum", "Purple", "BlackBerry", "Dark Blue-Black", "Watermelon", "Green", "Apricot", "Orange", "Papaya" , "oransje", "banan", "gul");
for (kart:: iterator it = mp.begynne(); den != MP.slutt(); det ++)
cout << it->først << " => "" << it->sekund << endl;
retur 0;

Utgangen er:

plomme => lilla
blackberry => mørkeblå-svart
vannmelon => grønn
aprikos => oransje
papaya => oransje
banan => gul

Usortert av strenglitteraler, men sortert etter pekere. Hvis nøklene var heltall, ville utdataene blitt sortert etter nøkler. I praksis er nøklene til mange kart strenglitteraler. Denne artikkelen forklarer hvordan nøkler med strenglitteraler kan sortere et kart.

Artikkelinnhold

• Sortert under skapelsen
• Produserer et utvalg av nedgang
• Sammenligne to elementer etter nøkkel
• Sortering av kart opprettet med Initializer -listen
• Konklusjon

Sorter under skapelsen

Hele malen for kartkonstruksjonen er:

mal, Klasseallokator = tildeling>> klassekart;

Klassene, sammenligne og allokatoren, har standardverdier. Det vil si at de har standard spesialisering, som ikke trenger å skrives inn i karterklæringen (instantiations). Det som er av interesse her er sammenligningsklassen. Navnet på klassen er sammenlignet, og standardspesialiseringen er "mindre". "mindre

Et kart opprettes normalt sortert etter nøkler under opprettelsen. Hvis nøklene er const char*, vil pekerne til de siterte bokstavelige strengene bli sortert, ikke de bokstavelige tekstene. For å ha strenger som nøkler sortert under opprettelsen, må strengene være litteraler av strengobjekter instantiert fra strengklassen. Dette betyr at strengbiblioteket må inkluderes, så vel som kartbiblioteket.

Skape stigende

I det følgende programmet opprettes kartet, sortert stigende:

#inkludere
#inkludere
#inkludere
ved hjelp av navneområdet STD;
int main ()

kart> MP;
MP ["Plum"] = "Purple";
MP ["BlackBerry"] = "Dark Blue-Black";
MP ["Watermelon"] = "Green";
MP ["Apricot"] = "Orange";
MP ["Papaya"] = "Orange";
MP ["Banana"] = "Gul";
for (kart:: iterator it = mp.begynne(); den != MP.slutt(); det ++)
cout << it->først << " => "" << it->sekund << endl;
retur 0;

Utgangen er:

aprikos => oransje
banan => gul
blackberry => mørkeblå-svart
papaya => oransje
plomme => lilla
vannmelon => grønn

Selv om mindre ble utelatt fra malen, ville sorteringen fortsatt ha vært stigende fordi mindre er standard.

Skape synkende

For å lage et kart, slik at det er sortert i synkende rekkefølge etter nøkler, må sammenligning av spesialiseringen kodes. Følgende program illustrerer dette:

#inkludere
#inkludere
#inkludere
ved hjelp av navneområdet STD;
int main ()

kart> MP;
MP ["Plum"] = "Purple";
MP ["BlackBerry"] = "Dark Blue-Black";
MP ["Watermelon"] = "Green";
MP ["Apricot"] = "Orange";
MP ["Papaya"] = "Orange";
MP ["Banana"] = "Gul";
for (kart:: iterator it = mp.begynne(); den != MP.slutt(); det ++)
cout << it->først << " => "" << it->sekund << endl;
retur 0;

Utgangen er:

vannmelon => grønn
plomme => lilla
papaya => oransje
blackberry => mørkeblå-svart
banan => gul
aprikos => oransje

Produserer et utvalg av nedgang

Et utvalg av et kart kan produseres i synkende rekkefølge. Dette innebærer å lage et andre kart, som er et område fra det første kartet. Følgende program illustrerer dette:

#inkludere
#inkludere
#inkludere
ved hjelp av navneområdet STD;
int main ()

kart MP;
MP ["Plum"] = "Purple";
MP ["BlackBerry"] = "Dark Blue-Black";
MP ["Watermelon"] = "Green";
MP ["Apricot"] = "Orange";
MP ["Papaya"] = "Orange";
MP ["Banana"] = "Gul";
kart:: iterator itb = mp.begynne();
ITB ++;
kart:: iterator ite = mp.slutt();
ite--;
kart> mpr (itb, ite);
for (kart:: Iterator IT = MPR.begynne(); den != Mpr.slutt(); det ++)
cout << it->først << " => "" << it->sekund << endl;
retur 0;

Utgangen er:

plomme => lilla
papaya => oransje
blackberry => mørkeblå-svart
banan => gul

Det første kartobjektet har seks elementer som er:

aprikos => oransje
banan => gul
blackberry => mørkeblå-svart
papaya => oransje
plomme => lilla
vannmelon => grønn

Rekkevidden som er vurdert er:

banan => gul
blackberry => mørkeblå-svart
papaya => oransje
plomme => lilla
vannmelon => grønn

I koden peker “ITB ++” på “Banana”, “Yellow” og “Ite-” peker på “Watermelon”, “Green” for rekkevidden. Når du håndterer et område i C ++, er det endelige elementet ikke involvert i manipulasjonen. Og slik har utgangen fire elementer med “Watermelon”, “Green” utelatt.

Spesialiseringen av sammenligningsmalparameteren til det andre kartet er større. Hvis det var mindre eller utelatt, ville rekkevidden resultert i stigende rekkefølge.

Sammenligne to elementer etter nøkkel

KEY_COMPARE KEY_COMP () const

Denne medlemsfunksjonen returnerer en kopi av sammenligningsobjektet som brukes av kartbeholderen for å sammenligne nøkler. Et sammenligningsobjekt er et funksjonsobjekt. Det vil ta to nøkler som argumenter og returnere sant hvis venstre nøkkel er mindre enn høyre. Med det skal kodesegmentet være:

KEY_COMPARE KC = MP.KEY_COMP ();
bool bl = kc ("vannmelon", "aprikos");

Key_Compare er ikke gjenkjent av kompilatoren. Å eliminere Key_Compare i dette kodesegmentet, ved å erstatte KC i den andre uttalelsen, resulterer i:

bool bl = mp.key_comp () ("vannmelon", "aprikos");

Følgende program illustrerer bruken av Key_comp ().

#inkludere
#inkludere
#inkludere
ved hjelp av navneområdet STD;
int main ()

kart MP;
MP ["Plum"] = "Purple";
MP ["BlackBerry"] = "Dark Blue-Black";
MP ["Watermelon"] = "Green";
MP ["Apricot"] = "Orange";
MP ["Papaya"] = "Orange";
MP ["Banana"] = "Gul";
bool bl = mp.key_comp () ("vannmelon", "aprikos");
cout << bl << endl;
retur 0;

Utgangen er 0 for falsk.

Det virkelige problemet med kodesegmentet ovenfor er at navneområdet for Key_Compare ikke var godt uttrykt. Hvis segmentet var,

kart:: Key_Compare KC = MP.KEY_COMP ();
bool bl = kc ("vannmelon", "aprikos");

Det ville ha fungert (akseptert av kompilatoren).

verdi_compare value_comp () const

Denne medlemsfunksjonen ligner på Key_comp (). Merk: Her er det ikke verdien av nøkkelen/verdiparet som blir referert til; Det er elementet i nøkkelen/verdiparet. Så de to argumentene for Value_Compare -funksjonsobjektet er iteratorelementer. Følgende program bruker value_comp (), ved å sammenligne de første og siste elementene, “apricot”, “oransje” og “Watermelon”, “Green”:

#inkludere
#inkludere
#inkludere
ved hjelp av navneområdet STD;
int main ()

kart> MP;
MP ["Plum"] = "Purple";
MP ["BlackBerry"] = "Dark Blue-Black";
MP ["Watermelon"] = "Green";
MP ["Apricot"] = "Orange";
MP ["Papaya"] = "Orange";
MP ["Banana"] = "Gul";
kart:: iterator itb = mp.begynne();
kart:: iterator ite = mp.slutt();
ite--;
kart:: Value_Compare VC = MP.verdi_comp ();
bool bl = vc ( *itb, *ite);
cout << bl << endl;
retur 0;

Utgangen er 1, for sann. Iteratorene ITB og ITE ble henvist til å ha sine elementer, med indireksjonsoperatøren.

Sortering av kart opprettet med Initializer -listen

I det følgende programmet, der sorteringen er synkende, er nøklene strengobjekter, instantiert fra strengklassen:

#inkludere
#inkludere
#inkludere
ved hjelp av navneområdet STD;
int main ()

kart> MP ("Plum", "Purple", "BlackBerry", "Dark Blue-Black", "Watermelon", "Green", "Apricot", "Orange", "Papaya "," oransje ", " banan "," gul ");
for (kart:: iterator it = mp.begynne(); den != MP.slutt(); det ++)
cout << it->først << " => "" << it->sekund << endl;
retur 0;

Utgangen er:

vannmelon => grønn
plomme => lilla
papaya => oransje
blackberry => mørkeblå-svart
banan => gul
aprikos => oransje

Konklusjon

Et kart opprettes sortert etter nøkler, stigende. Stigende er standardbestillingen. For å få det til å gå ned, legg til malparameterspesialisering, større som det tredje argumentet, inn i malens argumentliste. Merk: Hvis tastene er strenger, må de bli instantiert fra strengklassen, som illustrert ovenfor. Strengnøkler som const-char* eller char-arr [], ender opp med tipsene sine sorterte og ikke deres bokstaver.