C ++ mapa sortowanie według klucza

Mapa składa się z par kluczy/wartości. Każda para jest elementem. Wszystkie klucze na mapie są wyjątkowe. Mapa można sortować według kluczy. Sortowanie może być rosnące lub zstępujące. Wstęp jest domyślnie. Sortowanie na mapie nie zawsze jest proste. Potrzebuje obiektu funkcji porównawczej. Jeśli obiekt porównawczy jest ignorowany, odbywa się domyślne sortowanie.

Jeśli klucze są stałymi punktami do znaków, mapa jest sortowana przez kluczowe wskaźniki, a nie literałów. Tego prawie nie chce. Rozważ następujące pary klucza/wartości owoców i ich zewnętrzne kolory:

„śliwka” => „fiolet”
„BlackBerry” => „ciemnoniebieski”
„Watermelon” => „zielony”
„morelot”, => "pomarańczowy"
„papaya” => "pomarańczowy"
„Banana” => „żółty”

Owoce to klucze, a kolory są wartościami. Ta lista elementów (pary klucza/wartości) nie jest sortowana. Poniższy program tworzy mapę tej listy i wyświetla ją taką, jaka jest, nieporządkowana przez literały String:

#włączać
#włączać
za pomocą przestrzeni nazw Std;
int main ()

mapa poseł;
MP [„śliwki”] = „fiolet”;
MP [„BlackBerry”] = „Dark Blue-Black”;
MP [„Watermelon”] = „zielony”;
MP [„apricot”] = "Orange";
MP [„papaya”] = "Orange";
MP [„banan”] = „żółty”;
dla (mapa:: iterator it = mp.zaczynać(); To != MP.koniec(); it ++)
Cout << it->Pierwszy << " => " << it->drugi << endl;
powrót 0;

Wyjście to:

śliwka => fiolet
BlackBerry => ciemnoniebieski czarny
Watermelon => zielony
Apricot => Orange
papaya => pomarańczowy
banan => żółty

Nieporty przez literały smyczkowe, ale posortowane przez wskaźniki. Aby użyć mapy w programie C ++, biblioteka map musi zostać dołączona do dyrektywy w dołącz.

Innym sposobem utworzenia powyższej prostej mapy jest następujący:

#włączać
#włączać
za pomocą przestrzeni nazw Std;
int main ()

mapa MP („śliwki”, „fioletowy”, „BlackBerry”, „ciemnoniebieski-czarny”, „Watermelon”, „zielony”, „Apricot”, „Orange”, „Papaya” , „Orange”, „banana”, „żółty”);
dla (mapa:: iterator it = mp.zaczynać(); To != MP.koniec(); it ++)
Cout << it->Pierwszy << " => " << it->drugi << endl;
powrót 0;

Wyjście to:

śliwka => fiolet
BlackBerry => ciemnoniebieski czarny
Watermelon => zielony
Apricot => Orange
papaya => pomarańczowy
banan => żółty

Nieporty przez literały smyczkowe, choć posortowane przez wskaźniki. Gdyby klawisze były liczbami całkowitymi, wyjście byłyby posortowane przez klucze. W praktyce klucze wielu map są literałami smyczkowymi. W tym artykule wyjaśniono, w jaki sposób klucze literałów smyczkowych mogą sortować mapę.

Treść artykułu

• Posortowane podczas stworzenia
• Produkowanie zasięgu schodzącego
• Porównanie dwóch elementów według klucza
• Sortowanie mapy utworzonej z listą inicjalizatora
• Wniosek

Sortuj podczas tworzenia

Pełny szablon konstrukcji mapy to:

szablon, Class Allocator = Allocator>> mapa klas;

Zajęcia, porównaj i alokator, mają wartości domyślne. Oznacza to, że mają domyślną specjalizację, której nie trzeba wpisywać w deklaracjach map (instancje). Interesujące jest tutaj klasa porównawcza. Nazwa klasy jest porównana, a domyślna specjalizacja jest „mniej”. "mniej

Mapa jest zwykle tworzona posortowana przez klucze podczas tworzenia. Jeśli klucze są const char*, wówczas wskaźniki do cytowanych dosłownych sznurków zostaną sortowane, a nie dosłowne teksty. Aby mieć ciągi jako klucze sortowane podczas tworzenia, ciągi muszą być literalem obiektów ciągów utworzonych z klasy ciągów. Oznacza to, że biblioteka ciągów musi być uwzględniona, a także biblioteka map.

Tworzenie rosnącego

W poniższym programie mapa jest tworzona, posortowana rosnąca:

#włączać
#włączać
#włączać
za pomocą przestrzeni nazw Std;
int main ()

mapa> MP;
MP [„śliwki”] = „fiolet”;
MP [„BlackBerry”] = „Dark Blue-Black”;
MP [„Watermelon”] = „zielony”;
MP [„apricot”] = "Orange";
MP [„papaya”] = "Orange";
MP [„banan”] = „żółty”;
dla (mapa:: iterator it = mp.zaczynać(); To != MP.koniec(); it ++)
Cout << it->Pierwszy << " => " << it->drugi << endl;
powrót 0;

Wyjście to:

Apricot => Orange
banan => żółty
BlackBerry => ciemnoniebieski czarny
papaya => pomarańczowy
śliwka => fiolet
Watermelon => zielony

Nawet gdyby mniej pominięto z szablonu, sortowanie nadal się wznosiło, ponieważ mniej jest domyślnie.

Tworzenie maleństwa

Aby utworzyć mapę, tak że jest ona sortowana w kolejności malejącej według klawiszy, specjalizacja porównywania musi zostać zakodowana. Poniższy program ilustruje to:

#włączać
#włączać
#włączać
za pomocą przestrzeni nazw Std;
int main ()

mapa> MP;
MP [„śliwki”] = „fiolet”;
MP [„BlackBerry”] = „Dark Blue-Black”;
MP [„Watermelon”] = „zielony”;
MP [„apricot”] = "Orange";
MP [„papaya”] = "Orange";
MP [„banan”] = „żółty”;
dla (mapa:: iterator it = mp.zaczynać(); To != MP.koniec(); it ++)
Cout << it->Pierwszy << " => " << it->drugi << endl;
powrót 0;

Wyjście to:

Watermelon => zielony
śliwka => fiolet
papaya => pomarańczowy
BlackBerry => ciemnoniebieski czarny
banan => żółty
Apricot => Orange

Produkowanie zasięgu schodzącego

Zakres mapy można wytwarzać w kolejności malejącej. Obejmuje to utworzenie drugiej mapy, która jest zakresem od pierwszej mapy. Poniższy program ilustruje to:

#włączać
#włączać
#włączać
za pomocą przestrzeni nazw Std;
int main ()

mapa poseł;
MP [„śliwki”] = „fiolet”;
MP [„BlackBerry”] = „Dark Blue-Black”;
MP [„Watermelon”] = „zielony”;
MP [„apricot”] = "Orange";
MP [„papaya”] = "Orange";
MP [„banan”] = „żółty”;
mapa:: iterator ITB = MP.zaczynać();
ITB ++;
mapa:: iterator Ite = mp.koniec();
Ite--;
mapa> MPR (ITB, ITE);
dla (mapa:: iterator it = mpr.zaczynać(); To != MPR.koniec(); it ++)
Cout << it->Pierwszy << " => " << it->drugi << endl;
powrót 0;

Wyjście to:

śliwka => fiolet
papaya => pomarańczowy
BlackBerry => ciemnoniebieski czarny
banan => żółty

Pierwszy obiekt mapy ma sześć elementów:

Apricot => Orange
banan => żółty
BlackBerry => ciemnoniebieski czarny
papaya => pomarańczowy
śliwka => fiolet
Watermelon => zielony

Rozważany zakres to:

banan => żółty
BlackBerry => ciemnoniebieski czarny
papaya => pomarańczowy
śliwka => fiolet
Watermelon => zielony

W kodzie „ITB ++” wskazuje na „banan”, „żółty” i „Ite-” wskazuje na „Watermelon”, „zielony” dla zakresu. Podczas obsługi zakresu w C ++ końcowy element nie jest zaangażowany w manipulację. I tak wyjście ma cztery elementy z „Watermelon”, „zielony”.

Specjalizacja parametru szablonu Porównanie drugiej mapy jest większa. Gdyby był mniej lub pominięty, zasięg spowodowałby kolejność rosnącą.

Porównanie dwóch elementów według klucza

key_compary key_comp () const

Ta funkcja członka zwraca kopię obiektu porównawczego używanego przez kontener mapy do porównywania kluczy. Obiekt porównawczy jest obiektem funkcyjnym. Zakładałoby to dwa klucze jako argumenty i powróciłby, gdyby lewy klucz jest mniej niż prawy. Dzięki temu segment kodu powinien być:

key_compary kc = mp.key_comp ();
bool Bl = kc („Watermelon”, „morela”);

Key_comprena nie jest rozpoznawana przez kompilator. Eliminowanie key_compreu w tym segmencie kodu, zastępując KC w drugim instrukcji, powoduje:

Bool Bl = MP.key_comp () („Watermelon”, „morel”);

Poniższy program ilustruje użycie key_comp ().

#włączać
#włączać
#włączać
za pomocą przestrzeni nazw Std;
int main ()

mapa poseł;
MP [„śliwki”] = „fiolet”;
MP [„BlackBerry”] = „Dark Blue-Black”;
MP [„Watermelon”] = „zielony”;
MP [„apricot”] = "Orange";
MP [„papaya”] = "Orange";
MP [„banan”] = „żółty”;
Bool Bl = MP.key_comp () („Watermelon”, „morel”);
Cout << bl << endl;
powrót 0;

Dane wyjściowe to 0 dla fałszu.

Prawdziwym problemem z powyższym segmentem kodu jest to, że przestrzeń nazw dla Key_compre. Jeśli segment był,

mapa:: key_compary kc = mp.key_comp ();
bool Bl = kc („Watermelon”, „morela”);

Zadziałałoby (zaakceptowane przez kompilatora).

value_compary value_comp () const

Ta funkcja członka jest podobna do key_comp (). Uwaga: tutaj nie jest to wartość pary klucza/wartości, o której mowa, o której mowa; jest to element pary klucza/wartości. Tak więc dwa argumenty dotyczące obiektu funkcji wartości_compary są elementami iteratorem. Poniższy program używa wartości_comp (), porównując pierwsze i ostatnie elementy, „apricot”, „pomarańczowy” i „Watermelon”, „zielony”:

#włączać
#włączać
#włączać
za pomocą przestrzeni nazw Std;
int main ()

mapa> MP;
MP [„śliwki”] = „fiolet”;
MP [„BlackBerry”] = „Dark Blue-Black”;
MP [„Watermelon”] = „zielony”;
MP [„apricot”] = "Orange";
MP [„papaya”] = "Orange";
MP [„banan”] = „żółty”;
mapa:: iterator ITB = MP.zaczynać();
mapa:: iterator Ite = mp.koniec();
Ite--;
mapa:: value_compary vc = mp.value_comp ();
bool Bl = vc ( *itb, *ite);
Cout << bl << endl;
powrót 0;

Dane wyjściowe to 1, dla prawda. Iteratorzy ITB i ITE zostały odniesione do posiadania swoich elementów, z operatorem pośredniego.

Sortowanie mapy utworzonej z listą inicjalizatora

W poniższym programie, w którym sortowanie maleje, klawisze są obiektami ciągów, utworzone z klasy String:

#włączać
#włączać
#włączać
za pomocą przestrzeni nazw Std;
int main ()

mapa> MP („pllum”, „fioletowy”, „BlackBerry”, „ciemnoniebieski-czarny”, „Watermelon”, „zielony”, „Apricot”, „Orange”, „Papaya „,„ Orange ”, „ banana ”,„ żółty ”);
dla (mapa:: iterator it = mp.zaczynać(); To != MP.koniec(); it ++)
Cout << it->Pierwszy << " => " << it->drugi << endl;
powrót 0;

Wyjście to:

Watermelon => zielony
śliwka => fiolet
papaya => pomarańczowy
BlackBerry => ciemnoniebieski czarny
banan => żółty
Apricot => Orange

Wniosek

Mapa jest tworzona sortowana według klawiszy, rosnących. WSPÓŁPRODZENIE to domyślna kolejność. Aby to zejść, dodaj specjalizację parametrów szablonu, większą jako trzeci argument, do listy argumentów szablonu. Uwaga: Jeśli klucze są ciągami, muszą być utworzone z klasy ciągów, jak pokazano powyżej. Klucze smyczkowe jako const-char* lub char-arr [], kończą się posortowanymi wskaźnikami, a nie literałami.