« Kontenery asocjacyjne std::set<> i std::map<>, lekcja »
Rozdział 50. Kontenery asocjacyjne std::set<> i std::map<> (lekcja)
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zarejestruj się!
Autor: pekfos
Kurs C++

Kontenery asocjacyjne std::set<> i std::map<>

[lekcja] Rozdział 50. Kontenery asocjacyjne std::set<> i std::map<>

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.
C/C++
#include <iostream>
#include <set>


int main()
{
    int dane[ 10 ] = { 1, 9, 2, 3, 1, 4, 6, 5, 5, 8 };
    std::set < int > zbior;
   
    // pojedynczo
    for( int i = 0; i < 10; ++i )
         zbior.insert( dane[ i ] );
   
    // lub wszystkie naraz (para iteratorów)
    zbior.insert( dane, dane + 10 );
   
    // 'std::set<int>::iterator' zamiast 'auto', przed C++11
    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.
C/C++
#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 )
        // lub
        //if(zbior.find(liczba) != zbior.end())
             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ć.
C/C++
#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:
C/C++
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ę:
C/C++
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.
Poprzedni dokumentNastępny dokument
Wprowadzenie do standardowych algorytmówWyrażenia lambda (C++11)