C ++ mappa ordinamento per chiave

Una mappa è costituita da coppie chiave/valore. Ogni coppia è un elemento. Tutte le chiavi di una mappa sono uniche. Una mappa può essere ordinata per chiavi. L'ordinamento può essere ascendente o discendente. Ascendente è il valore predefinito. L'ordinamento in una mappa non è sempre semplice. Ha bisogno di un oggetto di funzione di confronto. Se l'oggetto di confronto viene ignorato, ha luogo l'ordinamento predefinito.

Se i tasti sono costantemente puntatori a carattere, la mappa viene ordinata dai puntatori chiave e non dai letterali delle stringhe chiave. Questo non è quasi quello che qualcuno vuole. Prendi in considerazione le seguenti coppie chiave/valore di frutta e i loro colori esterni:

"Plum" => "Purple"
"BlackBerry" => "blu scuro"
"Watermelon" => "Green"
"albicocca", => "arancione"
"Papaya" => "Orange"
"banana" => "giallo"

I frutti sono le chiavi e i colori sono i valori. Questo elenco di elementi (coppie chiave/valore) non è ordinato. Il seguente programma crea una mappa di questo elenco così com'è e la visualizza così com'è, non motivata dai letterali delle stringhe:

#includere
#includere
Utilizzo dello spazio dei nomi std;
int main ()

carta geografica MP;
mp ["plum"] = "viola";
mp ["blackberry"] = "blu scuro-nero";
mp ["Watermelon"] = "Green";
mp ["albicocca"] = "arancione";
MP ["Papaya"] = "Orange";
mp ["banana"] = "giallo";
per (mappa:: iterator IT = MP.inizio(); Esso != mp.FINE(); It ++)
cout << it->Primo << " => " << it->secondo << endl;
restituzione 0;

L'output è:

plum => viola
Blackberry => blu scuro-nero
Watermelon => Green
albicocca => arancione
papaya => arancione
banana => giallo

non motorizzato da letterali a stringa, ma ordinati da puntatori. Per utilizzare una mappa in un programma C ++, la libreria delle mappe deve essere inclusa con una direttiva include.

Un altro modo di creare la mappa semplice sopra è il seguente:

#includere
#includere
Utilizzo dello spazio dei nomi std;
int main ()

carta geografica mp ("plum", "viola", "blackberry", "scuro blu-nero", "watermelon", "verde", "albicocca", "arancione" "papaya" , "Orange", "Banana", "Yellow");
per (mappa:: iterator IT = MP.inizio(); Esso != mp.FINE(); It ++)
cout << it->Primo << " => " << it->secondo << endl;
restituzione 0;

L'output è:

plum => viola
Blackberry => blu scuro-nero
Watermelon => Green
albicocca => arancione
papaya => arancione
banana => giallo

Drasso da letterali a stringa, sebbene ordinato dai puntatori. Se i tasti fossero numeri interi, l'output sarebbe stato ordinato per chiavi. In pratica, le chiavi di molte mappe sono letterali stringhe. Questo articolo spiega come le chiavi dei letterali di stringa possono ordinare una mappa.

Contenuto dell'articolo

• Ordinato durante la creazione
• Producendo una gamma che discende
• Confrontare due elementi per chiave
• Ordinamento della mappa creata con l'elenco iniziale
• Conclusione

Ordina durante la creazione

Il modello completo per la costruzione della mappa è:

modello, Classe Allocator = allocatore>> mappa di classe;

Le classi, confronta e allocatore, hanno valori predefiniti. Cioè, hanno una specializzazione predefinita, che non deve essere digitata nelle dichiarazioni della mappa (istanziazioni). Ciò che è interessante qui è la classe di confronto. Il nome della classe è confrontato e la specializzazione predefinita è "inferiore". "meno

Una mappa viene normalmente creata ordinata per chiavi durante la creazione. Se le chiavi sono const char*, allora i puntatori delle stringhe letterali citate verranno ordinati, non i testi letteli. Per avere stringhe come tasti ordinati durante la creazione, le stringhe devono essere letterali di oggetti stringa istanziati dalla classe stringa. Ciò significa che la libreria di stringhe deve essere inclusa, così come la libreria delle mappe.

Creare ascendente

Nel seguente programma, la mappa viene creata, ordinata in ascesa:

#includere
#includere
#includere
Utilizzo dello spazio dei nomi std;
int main ()

carta geografica> mp;
mp ["plum"] = "viola";
mp ["blackberry"] = "blu scuro-nero";
mp ["Watermelon"] = "Green";
mp ["albicocca"] = "arancione";
MP ["Papaya"] = "Orange";
mp ["banana"] = "giallo";
per (mappa:: iterator IT = MP.inizio(); Esso != mp.FINE(); It ++)
cout << it->Primo << " => " << it->secondo << endl;
restituzione 0;

L'output è:

albicocca => arancione
banana => giallo
Blackberry => blu scuro-nero
papaya => arancione
plum => viola
Watermelon => Green

Anche se meno fossero omessi dal modello, l'ordinamento sarebbe comunque salito perché meno è il valore predefinito.

Creando discendenza

Per creare una mappa, in modo tale che sia ordinata in ordine decrescente per chiavi, la specializzazione di confronto deve essere codificata. Il seguente programma illustra questo:

#includere
#includere
#includere
Utilizzo dello spazio dei nomi std;
int main ()

carta geografica> mp;
mp ["plum"] = "viola";
mp ["blackberry"] = "blu scuro-nero";
mp ["Watermelon"] = "Green";
mp ["albicocca"] = "arancione";
MP ["Papaya"] = "Orange";
mp ["banana"] = "giallo";
per (mappa:: iterator IT = MP.inizio(); Esso != mp.FINE(); It ++)
cout << it->Primo << " => " << it->secondo << endl;
restituzione 0;

L'output è:

Watermelon => Green
plum => viola
papaya => arancione
Blackberry => blu scuro-nero
banana => giallo
albicocca => arancione

Producendo una gamma che discende

Una gamma di una mappa può essere prodotta in ordine decrescente. Ciò comporta la creazione di una seconda mappa, che è un intervallo dalla prima mappa. Il seguente programma illustra questo:

#includere
#includere
#includere
Utilizzo dello spazio dei nomi std;
int main ()

carta geografica MP;
mp ["plum"] = "viola";
mp ["blackberry"] = "blu scuro-nero";
mp ["Watermelon"] = "Green";
mp ["albicocca"] = "arancione";
MP ["Papaya"] = "Orange";
mp ["banana"] = "giallo";
carta geografica:: iterator itb = mp.inizio();
ITB ++;
carta geografica:: iterator ite = mp.FINE();
ite--;
carta geografica> MPR (ITB, ite);
per (mappa:: iterator IT = MPR.inizio(); Esso != Mpr.FINE(); It ++)
cout << it->Primo << " => " << it->secondo << endl;
restituzione 0;

L'output è:

plum => viola
papaya => arancione
Blackberry => blu scuro-nero
banana => giallo

Il primo oggetto Map ha sei elementi che sono:

albicocca => arancione
banana => giallo
Blackberry => blu scuro-nero
papaya => arancione
plum => viola
Watermelon => Green

La gamma considerata è:

banana => giallo
Blackberry => blu scuro-nero
papaya => arancione
plum => viola
Watermelon => Green

Nel codice, "ITB ++" punta a "banana", "giallo" e "ite-" punta a "Watermelon", "Green" per l'intervallo. Quando si gestiscono un intervallo in C ++, l'elemento finale non è coinvolto nella manipolazione. E così l'output ha quattro elementi con "Watermelon", "Green" omesso.

La specializzazione del parametro del modello di confronto della seconda mappa è maggiore. Se fosse meno o omesso, l'intervallo avrebbe portato all'ordine ascendente.

Confrontare due elementi per chiave

key_compare key_comp () const

Questa funzione membro restituisce una copia dell'oggetto di confronto utilizzato dal contenitore della mappa per confrontare le chiavi. Un oggetto di confronto è un oggetto funzione. Ci vorrebbero due chiavi come argomenti e ritornano vero se la chiave sinistra è inferiore a destra. Con ciò, il segmento del codice dovrebbe essere:

key_compare kc = mp.key_comp ();
bool bl = kc ("anguria", "albicocca");

key_compare non è riconosciuto dal compilatore. Eliminare key_compare in questo segmento di codice, sostituendo KC nella seconda istruzione, si traduce in:

bool bl = mp.key_comp () ("Watermelon", "Albicoch");

Il seguente programma illustra l'uso di key_comp ().

#includere
#includere
#includere
Utilizzo dello spazio dei nomi std;
int main ()

carta geografica MP;
mp ["plum"] = "viola";
mp ["blackberry"] = "blu scuro-nero";
mp ["Watermelon"] = "Green";
mp ["albicocca"] = "arancione";
MP ["Papaya"] = "Orange";
mp ["banana"] = "giallo";
bool bl = mp.key_comp () ("Watermelon", "Albicoch");
cout << bl << endl;
restituzione 0;

L'output è 0 per false.

Il vero problema con il segmento di codice sopra è che lo spazio dei nomi per key_compare, non è stato ben espresso. Se il segmento era,

carta geografica:: key_compare kc = mp.key_comp ();
bool bl = kc ("anguria", "albicocca");

Avrebbe funzionato (accettato dal compilatore).

value_compare value_comp () const

Questa funzione membro è simile a KEY_COMP (). Nota: qui, non è il valore della coppia chiave/valore a cui si fa riferimento; è l'elemento della coppia chiave/valore. Quindi, i due argomenti per l'oggetto funzione value_compare sono elementi iterator. Il seguente programma utilizza valori_comp (), confrontando il primo e l'ultimo elementi, "Apricot", "Orange" e "Watermelon", "Green":

#includere
#includere
#includere
Utilizzo dello spazio dei nomi std;
int main ()

carta geografica> mp;
mp ["plum"] = "viola";
mp ["blackberry"] = "blu scuro-nero";
mp ["Watermelon"] = "Green";
mp ["albicocca"] = "arancione";
MP ["Papaya"] = "Orange";
mp ["banana"] = "giallo";
carta geografica:: iterator itb = mp.inizio();
carta geografica:: iterator ite = mp.FINE();
ite--;
carta geografica:: value_compare vc = mp.value_comp ();
bool bl = vc ( *Itb, *ite);
cout << bl << endl;
restituzione 0;

L'output è 1, per vero. Gli iteratori ITB e Ite erano dereferenziati di avere i loro elementi, con l'operatore indirezione.

Ordinamento della mappa creata con l'elenco iniziale

Nel seguente programma, in cui è decrescente l'ordinamento, i tasti sono oggetti stringa, istanziati dalla classe String:

#includere
#includere
#includere
Utilizzo dello spazio dei nomi std;
int main ()

carta geografica> mp ("plum", "viola", "blackberry", "blu scuro-nero", "watermelon", "verde", "albicocca", "arancione" "papaya "," Orange ", " Banana "," Yellow ");
per (mappa:: iterator IT = MP.inizio(); Esso != mp.FINE(); It ++)
cout << it->Primo << " => " << it->secondo << endl;
restituzione 0;

L'output è:

Watermelon => Green
plum => viola
papaya => arancione
Blackberry => blu scuro-nero
banana => giallo
albicocca => arancione

Conclusione

Una mappa viene creata ordinata per chiavi, ascendente. Ascendente è l'ordine predefinito. Per distinguerlo, aggiungi la specializzazione dei parametri del modello, maggiore come terzo argomento, nell'elenco degli argomenti del modello. Nota: se le chiavi sono stringhe, devono essere istanziate dalla classe String, come illustrato sopra. Tasti di stringa come const-car* o char-arr [], finiscono con i loro puntatori ordinati e non i loro letterali.