Wstęp
Kontenery asocjacyjne przechowują klucze (liczbowe, tekstowe itp.) oraz ewentualne związane z nimi dodatkowe informacje. Są nastawione na wyszukiwanie, bardziej niż na iterację, czy dostęp swobodny. Omawiane
std::set<> i
std::map<> przechowują elementy w sposób uporządkowany według pewnego kryterium i są implementowane zwykle z użyciem drzew czerwono-czarnych - samobalansujących się drzew wyszukiwawczych. Dlatego iterując po takim kontenerze, klucze zawsze są posortowane.
Kontener std::set<>
std::set<> realizuje zbiór w matematycznym sensie tego słowa. Przechowuje różne wartości i pozwala efektywnie sprawdzać, czy wartość znajduje się w zbiorze. Jest zdefiniowany w nagłówku
<set>. Podstawowe operacje
size(),
empty(),
clear(),
erase() działają analogicznie jak w przypadku
std::vector<>. Ze względu na drzewiastą strukturę, nie ma tu aspektu rezerwacji pamięci, ani dodawania elementów w określone miejsce (porządkowanie elementów w kontenerze jest poza naszą kontrolą). Dodawanie elementów odbywa się przy użyciu metody
insert(), do której po prostu podajemy klucz do dodania. Jeśli klucz już istnieje w zbiorze, operacja dodawania nie zmienia w żaden sposób zawartości kontenera.
#include <iostream>
#include <set>
int main()
{
int dane[ 10 ] = { 1, 9, 2, 3, 1, 4, 6, 5, 5, 8 };
std::set < int > zbior;
for( int i = 0; i < 10; ++i )
zbior.insert( dane[ i ] );
zbior.insert( dane, dane + 10 );
for( auto iter = zbior.begin(); iter != zbior.end(); ++iter )
std::cout << * iter << ' ';
}
1 2 3 4 5 6 8 9
Tablica 10 liczb z 1 duplikatem wewnątrz została dodana do zbioru (2 razy) i jak widać zbiór nie zawiera duplikatów. Dla wyświetlenia zawartości zbioru trzeba już było napisać pętlę z użyciem iteratorów,
std::set<> nie udostępnia na to innego sposobu.
Atutem kontenerów asocjacyjnych jest szybkie wyszukiwanie. Do wyszukiwania w kontenerze zbioru można użyć metody
count(), która przyjmuje klucz i zwraca ilość trafień (w
std::set<> nie ma duplikatów, więc wynik to 0 lub 1), lub metody
find(), która przyjmuje klucz i zwraca iterator na znaleziony element, lub iterator
end(), jeśli elementu nie znaleziono.
#include <iostream>
#include <set>
int main()
{
std::set < int > zbior;
int liczba;
std::cout << "Podaj liczby, bez duplikatow\n";
while( std::cin >> liczba )
{
if( zbior.count( liczba ) > 0 )
std::cout << "Juz podales " << liczba << "!\n";
else
zbior.insert( liczba );
}
}
Kontener std::map<>
std::map<K, V> mapuje klucz typu
K na jakąś dowolną wartość typu
V, która nie bierze udziału w porządkowaniu kontenera, ani wyszukiwaniu. Tutaj też klucze są unikalne, oraz dostępne są wszystkie operacje omówione wcześniej dla zbioru, z tą różnicą, że teraz iterator nie wskazuje na klucz, lecz na parę
std::pair<K, V>. Ten kontener jest zdefiniowany w nagłówku
<map>.
Nową możliwością względem zbioru, jest użycie operatora indeksowania
[], który jako indeks przyjmuje klucz (więc niekoniecznie liczbę) i zwraca referencję na przechowywaną wartość. Ta operacja służy zarówno jako wyszukiwanie, oraz wstawianie elementu (z domyślną wartością) - jeśli klucz nie istniał wcześniej w kontenerze,
zostanie dodany! Takie zachowanie może być niepożądane w niektórych przypadkach, wtedy należy użyć
find(), sprawdzić czy element istnieje i dostać się do niego przez iterator. Inną opcją jest użycie metody
at(), która działa tak samo jak operator
[], ale gdy element nie istnieje, wywołuje błąd, zamiast go dodawać.
#include <iostream>
#include <map>
int main()
{
std::map < int, int > mapa;
int liczba;
std::cout << "Podaj liczby, bez duplikatow\n";
while( std::cin >> liczba )
{
int powt = ++mapa[ liczba ];
if( powt > 1 )
std::cout << "Podales " << liczba << " juz " << powt << " razy!\n";
}
}
Wpisane liczby są przechowywane jako klucze, a wartości to liczby powtórzeń. Użyty jest operator
[], więc klucze są dodawane, jeśli wcześniej nie istniały. Domyślną wartością dla
int jest 0. Nowo dodana, lub znaleziona wartość jest następnie inkrementowana, więc świeżo dodany klucz ma liczbę powtórzeń 1, a klucz który istniał już wcześniej ma tę liczbę podbitą o jeden.
Wskazówki do optymalnego kodu
Powiedzmy, że mamy mapę, przypadkiem zawiera sobie struktury:
struct Struktura
{
int a, b, c;
};
std::map < int, Struktura > mapa;
mapa[ 1 ].a = 3;
mapa[ 1 ].b = 1000;
mapa[ 1 ].c = 0;
To jest przykład, jak
nie należy pisać. Wszędzie, gdzie wchodzą do gry funkcje, łatwo jest napisać coś głupiego, nieoptymalnego. Indeksowanie mapy jest operacją wyszukiwania, która tworzy lub znajduje element w czasie logarytmicznym od ilości elementów w kontenerze. Ten kod wyszukuje element
3 razy, na dodatek w przypadku użycia, w którym to co robimy z elementem jest znacznie szybsze od samego wyszukiwania. Operator indeksowania zwraca tu referencję na element (dlatego możemy go modyfikować) i nic nie stoi na przeszkodzie, by tą referencją zainicjalizować inną referencję:
Struktura & element = mapa[ 1 ];
element.a = 3;
element.b = 1000;
element.c = 0;
Teraz element jest wyszukiwany tylko raz i zachowujemy referencję na niego, by z jej pomocą wykonać interesujące nas kilka operacji. Zamiast referencji można z identycznym skutkiem użyć wskaźnika, tylko składnia będzie nieco inna. Przy wykorzystywaniu metody z referencją zwracaj szczególną uwagę na znak
&. Bez niego kod wciąż będzie się kompilować, ale operacje wykonane na kopii elementu nie będą wpływać na oryginał utworzony w kontenerze.