Podręcznik

W przeciwieństwie do kontenerów sekwencyjnych - w przypadku kontenerów asocjacyjnych o kolejności elementów w kontenerze nie decyduje bezpośrednio ich umieszczanie, lecz są one przechowywane w uporządkowanej postaci. To uporządkowanie może być albo oparte o relację między elementami, albo o relację skrótów umieszczonych w kontenerze wartości - ale zawsze jest to jakaś relacja.

Zbiór

Często interesuje nas szybkie wyszukiwanie, pozwalające na sprawdzenie czy dany element już w kolekcji istnieje. Innym spotykanym przypadkiem jest potrzeba przechowywania w kontenerze tylko unikalnych wartości. Odpowiedzią na obie te potrzeby jest kontener o nazwie set

Zbiór wewnętrznie jest pamiętany jako drzewo binarne (zazwyczaj jest to drzewo znane w teorii jako drzewo czerwono/czarne). Dla takiej struktury danych mamy bardzo niski czas wyszukiwania elementu - rzędu O(log n) gdzie n to ilość elementów w kolekcji.

Inicjacja zbioru może odbywać się przy pomocy listy inicjatora podobnej do tej z wektorów, list czy kolejek. Kod do wyświetlania zawartości też będzie podobny.

    // zbiór o czterech elementach inicjowany listą
    std::set<char> s1{'a', 'b', 'd', 'e', 'a'};

    for (auto element: s1) {
        std::cout << element << "\t";
    }
    std::cout << "\n";

W powyższym kodzie uważny czytelnik zauważy jednak różnicę w stosunku do wektorów. Mimo iż podałem listę 5 elementów - po utworzeniu zbiór ma ich tylko 4. Nie można do zbioru dwa razy wstawić 'a' - dlatego jego drugie wstawienie jest ignorowane.

Podobnie działa metoda insert - wstawia do zbioru element jeśli go jeszcze w nim nie ma, i zwraca parę (iterator wskazujący na wstawiony element, true), natomiast jeśli w zbiorze już jest dany element - nie zmienia go, i zwraca parę (iterator na istniejący element, false)

    char zn = 'a' + rand() % ('h' - 'a' + 1);
    if (s1.insert(zn).second)  {
        std::cout << "Nie było jeszcze " << zn << " w zbiorze - ale już jest\n";
    } else {
        std::cout << "Duplikat " << zn  << "\n";
    }

Tą cechę zbioru można uzyskać do poszukiwania unikalnych wartości w innych kontenerach. Wystarczy w takim wypadku skopiować zawartość przeszukiwanego kontenera do zbioru:

    std::vector<int> v1;
    for (int i=0; i < 100; i++)
        v1.emplace_back(rand()%50);
    std::set<int> s2{v1.begin(), v1.end()};
    std::cout << "W wektorze jest " << v1.size() << " elementów, z czegp " << s2.size() << " unikalnych\n";

Jeśli chcemy sprawdzić czy jakiś element jest w zbiorze - korzystamy z metody find:

    if (auto search = s2.find(2); search != s2.end())
        std::cout << "Znaleziono " << (*search) << '\n';
    else
        std::cout << "Nie znaleziono\n";

Ostania istotna cecha set jest powiązana ze sposobem pamiętania elementów. Skoro są one uporządkowane - to pośrednio wynika z tego, iż wartości elementu nie można zmienić. Więc poniższy kod nie zadziała:

    for (auto& element : s2) {
        element += 2;
    }

Słownik

Jeśli przechowywane dane mają postać listy par, z których jeden z elementów możemy traktować jako klucz, a drugi jako wartość skojarzoną z tym kluczem - to mówimy o słowniku. Wyobraźmy sobie problem przechowywania oceny studenta. Możemy wtedy stwierdzić że kluczem jest identyfikator studenta (dla uproszczenia w przykładzie założymy że jest to tekst zawierający nazwisko i imię), a wartością - ocena. Teoretycznie zatem moglibyśmy przygotować strukturę np taką: 

struct SStudentOcena {
   std::string nazwa; 
   double ocena; 
};

i takch studentów przechowywać po prostu w wektorze / kolejce / na liście:

std::vector<SStudentOcena> studenci; 

Potem - jak chcę się odwołać do poszczególnego studenta - to muszę go znaleźć na liście. Problem pojawia się, jak podstawową operacją wykonywaną przez użytkownika jest zmiana / wystawienie oceny poszczególnym studentom. Wtedy powtarzamy nieoptymalne przeszukiwania. Nieoptymalne - bo studenci mogą być umieszczeni w wektorze w kolejności przypadkowej, więc typowa implementacja algorytmu wyszukiwania będzie liniowa - idąc od pierwszego do ostatniego elementu wektora biorę kolejne nazwiska, sprawdzam czy jest to nazwisko którego szukam - i jeśli tak, to mam sukces...

W praktyce jednak w przypadku podobnym do omawianego raczej nie stosuje się losowego ułożenia osób, lecz listy alfabetyczne, i algorytmy wyszukiwania oparte na podziale szukanego zbioru na połowy bazując na relacji większości między poszukiwanym, a środkowym elementem. W STL zaimplementowano to w sposób jeszcze bardziej wyrafinowany. Zauważcie, że takie pary można pamiętać w strukturze podobnej do zbioru - jedynie trzeba zapewnić by do każdego elementu zbioru (klucza) można było "dokleić" ekstra dane (wartość). Taki kontener w STL nazywa się słownikiem (map). W języku polskim wykorzytuje się także określnie tablica asocjacyjna lub po prostu mapa.

Klasa map z biblioteki standardowej jest kontenerem zoptymalizowanym pod kątem przeszukiwania i wstawiania par wartości, z czego klucz musi być unikalny i nie może być zmieniany.

Kolejność elementów w słowniku jest definiowana przez standard języka. Zakłada się, że poszczególne elementy są zawsze ułożnone w kolejności od najmniejszego do największego klucza - wartość nie ma wpływu na położenie. 

Słowniki także można inicjować na wiele sposobów. Naturalnym jest inicjacja poprzez listę inicjacyjną. Dodatkowo - jeśli odwołujemy się do klucza który nie istnieje w danym słowniku - zostanie on do niego dołączony.  Mamy także możliwości kopiowania i przenoszenia innych słowników. Odwoływanie się do elementów mapy odbywa się przez operator indeksowania - gdzie indeksem jest klucz. Przykładowe zastosowanie mapy do pamiętania ocen możecie zobaczyć na poniższym kodzie: 

#include "iostream"
#include "map"

void printStandard17(std::map<std::string, double>& slownik) {
    // odwołanie do zbioru wykorzystując C++17
    for (const auto& [klucz, wartosc] : slownik) {
        std::cout << klucz << " : " << wartosc << std::endl;
    }
}

void printStandard11(std::map<std::string, double>& slownik) {
    // odwołanie starszą, lepiej znaną wersją pętli for C++11
    for (const auto& element : slownik) {
        std::cout << element.first << " : " << element.second << std::endl;
    }
}

int main() {
    // utworzenie i inicjacja 3 wpisami
    std::map<std::string, double> dzienniczek {
            {"Skrzetuski Jan", 4.0},
            {"Wołodyjowski Michał", 3.5},
            {"Kurcewiczówna Helena", 5.0}
    };

    // wydruk
    printStandard17(dzienniczek);

    // dodanie do słownika nowego elementu
    dzienniczek["Zagłoba Onufry"] = 3.0;
    // zmiana istniejącego wspisu
    dzienniczek["Wołodyjowski Michał"] += 0,5;

    // sprawdzenie czy w mapie nie ma określonego klucza
    if (dzienniczek.find("Podbipięta Longin") == dzienniczek.end()) {
        dzienniczek["Podbipięta Longin"] = 3.0;
    }

    // usunięcie klucza z mapy
    dzienniczek.erase("Skrzetuski Jan");

    std::cout << "\nPo zmianach:\n";
    printStandard11(dzienniczek);
    return 0;
}

Inne kontenery asocjacyjne

Oprócz wspomnianego zbioru i słownika mamy jeszcze kilka rzadziej stosowanych kontenerów tego typu:

• multiset - przechowuje posortowane elementy - podobnie jak zbiór. Jednak w przeciwieństwie do zbioru - pozwala na powtarzanie się wartości
• multimap  - podobnie jak słownik przechowuje pary klucz / wartość, przy czym pozwala na powtarzanie się klucza (jednemu kluczowi można przypisać więcej niż jedną wartość
• unordered_set i unordered_map - są to odpowiedniki zbioru i słownika, w których nie układa się elementów korzystając z operatora relacji, lecz wykorzystuje się do tego funkcję skrótu (ang. hash). Wykorzystanie funkcji skrótu pozwala nam na dodatkowe przyspieszenie wyszukiwania w niektórych przypadkach. Dodatkowo - od typu klucza nie wymaga się istnienia funkcji porządkującej (np operatora <) w przypadku tych wersji kontenerów.