Podstawy programowania 11

Kontenery biblioteki standardowej języka C++

Biblioteka standardowa języka C++ udostępnia przydatne typy przechowujące obiekty innych typów. Można o nich myśleć jako o inteligentniejszym kuzynie zwykłych tablic, trzeba jednak pamiętać, że ich funkcjonalność znacznie przekracza zwykłe tablice.

Typy te są w istocie klasami (a dokładniej – szablonami klas), więc podpadają pod programowanie obiektowe, jednak nie trzeba wiele wiedzieć o obiektowości aby z nich korzystać w swoich programach, a mogą sporo ułatwić. Ponieważ przechowują one inne obiekty, mówimy o klasach kontenrowych (ang. containers).

Kontenery dzielimy na dwa rodzaje:

Do tego biblioteka udostępnia jeszcze tzw. adaptery kontenerów (stack, queue, priority_queue).

Kontenery biblioteczne są bardzo wydajne – z reguły nie opłaca się pisać ręcznie własnych analogów, bo i tak nie będą szybsze, stracimy więc tylko czas. Czas lepiej poświęcić na naukę używania klas kontenerowych.

Ponieważ kontenery są szablonami klas, przy ich deklarowaniu należy podać typ/typy obiektów jaki mamy zamiar w nich przechowywać. Dzięki temu kompilator może upewniać się później, że używamy właściwych typów.

Przegląd klas kontenerowych

Kontenery sekwencyjne

Kontenery sekwencyjne przechowują list obiektów w kolejności ich dodawania. Różnią się implementacją, co powoduje, że pewne operacje, które są szybkie z jednym z kontenerów są powolne z innymi kontenerami.

vector

Klasa vector implementuje tablicę, która może dynamicznie zmieniać swój rozmiar poprzez opcjonalne dodawanie elementów na końcu. Same obiekty są oczywiście przechowywane w zadeklarowanej przez obiekt vector tablicy. Jednak kiedy chcemy dopisać element a w tej tablicy nie ma już miejsca, to wektor sam stworzy nową, większą tablicę, przekopiuje do niej istniejące obiekty, usunie niepotrzebne dane i dopisze nasz nowy element na końcu.

Do elementów wektora można odwoływać się zarówno poprzez operator [] (jak do elementów tablicy) jak i poprzez funkcję at(), która dodatkowo sprawdza, czy nie przekraczamy zakresu (ale jest wolniejsza niż []).

Nowy element można dodawać na końcu za pomocą metody push_back() i usuwać z końca metodą pop_back(). Wstawianie i usuwanie w dowolnym miejscu zapewniają metody insert() i erase().

Pełen opis metod klasy vector wraz z ich parametrami znajduje się w dokumentacji.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> v;

    v.push_back(1);
    v.push_back(2);
    v.push_back(3);

    for (vector<int>::size_type i = 0; i < v.size(); ++i)
        cout << v[i] << endl;

    return 0;
}

Zasadniczo powinien to być wyjściowy zamiennik tablicy, jeśli nie potrzebujemy funkcjonalności udostępnianej przez któryś inny kontener. Wektor pozwala szybko dodawać elementy na koniec i szybko odwoływać się do swoich elementów. Wolno idzie mu dodawanie elementów w innym miejscu niż na końcu oraz usuwanie elementów (chyba, że usuwamy od pewnego miejsca do końca).

deque

Klasa deque implementuje dwustronną kolejkę. W przeciwieństwie do wektora opakowuje nie jedną tablicę a wiele tablic. Dlatego też elementy nie są przechowywane w ciągłym obszarze pamięci i ewentualna zmiana rozmiaru nie wymaga kopiowania istniejących elementów (jest więc szybsze niż w przypadku wektora). Pozwala też szybko dodawać elementy na początku, a nie tylko na końcu. Za to dostęp jest trochę wolniejszy.

Dostęp jest podobny jak do wektora, więc mamy w miarę szybki dostęp do dowolnego elementu, z tym, że elementy deque można też dodawać i usuwać z początku listy, dochodzą więc metody push_front() i pop_front().

Pełen opis metod klasy deque wraz z ich parametrami znajduje się w dokumentacji.

#include <iostream>
#include <deque>

using namespace std;

int main() {
    deque<int> q;

    q.push_back(2);
    q.push_back(3);
    q.push_front(1);

    for (deque<int>::size_type i = 0; i < q.size(); ++i)
        cout << q[i] << endl;

    return 0;
}

Kontenera deque używamy, gdy potrzebujemy możliwości szybkiego dodawania i usuwania elementów zarówno z początku jak i końca kontenera.

list

Klasa list implementuje listę z dowiązaniami. Lista taka nie przechowuje dodawanych elementów w tablicy, lecz w osobnych węzłach powiązanych wskaźnikami. Jeden węzeł wygląda mniej tak (choć szczegóły implementacji mogą się różnić, jest ona i tak ukryta przed programistą):

template<typename T>
class Node {
    Node *prev;
    Node *next;
    T payload;
};

Z dowolnego elementu list łatwo przenieść się do sąsiednich (wykorzystując w jakiś sposób wskaźniki prev i next), ale nie ma łatwego sposobu dostania się do innych przechowywanych przez list obiektów – musimy przejść wszystkie węzły po kolei. Dlatego list nie udostępnia operatora [] ani metody at. Jedynym sposobem poruszania się po elementach są iteratory, na dodatek natychmiastowy dostęp mamy tylko do elementu pierwszego i ostatniego.

W zamian za te niedogodności list pozwala na szybkie dodawanie i usuwanie elementów w dowolnym miejscu kontenera, nie tylko na początku i końcu.

Pełen opis metod klasy list wraz z ich parametrami znajduje się w dokumentacji

#include <iostream>
#include <list>
#include <iterator>

using namespace std;

int main() {
    list<int> l;

    l.push_front(1);
    l.push_back(3);
    // std::next dodano dopiero w C++11
    l.insert(next(l.begin()), 2);

    for (list<int>::iterator it = l.begin(); it != l.end(); ++it)
        cout << *it << endl;

    return 0;
}

Ze względu na problemy ze swobodnym dostępem, klasa list posiada własne metody służące do sortowania itp. Należy ich używać zamiast operacji z biblioteki algorytmów (o algorytmach następnym razem).

array (C++11)

Klasa array daje dostęp do tablicy o ustalonej liczbie elementów (nie zmienia więc rozmiaru). Jest równie szybka jak statyczna tablica z C++ – jednak dodatkowo np. zna swój rozmiar.

Pełen opis klasy array w dokumentacji

forward_list (C++11)

Klasa forward_list jest bardzo podobna do list, jednak węzły zawierają tylko wskaźniki na jeden węzeł – ten następny. Dlatego po forward_list można poruszać się tylko w jedną stronę. Za to węzły zajmują mniej miejsca (co może mieć znaczenie przy przechowywaniu dużej ilości obiektów).

Pełen opis klasy forward_list w dokumentacji

Kontenery asocjacyjne

Kontenery asocjacyjne nie przechowują obiektów w kolejności ich dodawania lecz używają własnej kolejności. W przypadku kontenerów uporządkowanych, elementy przechowywane są w postaci posortowanej, w przypadku kontenerów nieuporządkowanych, kontener używa funkcji skrótu.

set i multiset

Kontener set przechowuje zawsze po jednym egzemplarzu danego typu. Dodawanie kolejnego elementu, który już się w kontenerze znajduje, nie zmienia stanu kontenera. Kontener multiset przechowuje wielokrotnie te same obiekty, tyle razy ile razy je dodano. Oba przechowują uporządkowaną kolekcje obiektów, a metody używają przeszukiwania binarnego.

Oba kontenery potrafią szybko (w czasie logarytmicznym względem rozmiaru) stwierdzić, czy dany obiekt znajduje się w kontenerze czy nie.

Nowe elementy dodajemy używając metody insert(), czas dodawania jest logarytmiczny względem rozmiaru kontenera, chyba, że przy wstawianiu podamy właściwą wskazówkę, która pomoże wstawić element do kontenera – wtedy czas jest stały. Dostęp do obiektów zapewniają iteratory.

#include <iostream>
#include <set>

using namespace std;

int main() {
    set<int> s;
    multiset<int> ms;

    s.insert(1);
    s.insert(2);
    s.insert(3);
    s.insert(1);

    cout << "set: ";
    for (set<int>::iterator it = s.begin(); it != s.end(); ++it)
        cout << *it << " ";
    cout << endl;

    ms.insert(1);
    ms.insert(2);
    ms.insert(3);
    ms.insert(1);

    cout << "multiset: ";
    for (multiset<int>::iterator it = ms.begin(); it != ms.end(); ++it)
        cout << *it << " ";
    cout << endl;


    return 0;
}

map

Kontener map jest wyjątkowy, bo przechowuje pary. Pierwszy element pary jest kluczem, drugi wartością dla danego klucza. Wykorzystanie wygląda tak, jak gdybyśmy mieli tablicę, której elementy są indeksowane nie kolejnymi liczbami, a właśnie wartościami klucza. Wenwętrzna implementacja korzysta z uporządkowanej kolekcji kluczy.

Zarówno do dodawania jak i do dostępu do obiektów służy operator [] lub funkcja at. Działanie ich jest jednak trochę inne niż dla tablicy. Wywołanie operatora [] z jakimś kluczem powoduje zwrócenie referencji do obiektu stowarzyszonego z tym kluczem. Jeżeli w kontenerze nie ma takiego klucza, to kontener tworzy nową wartość stowarzyszoną z tym kluczem i zwraca referencję do tej nowej wartości. Przekazanie nieistniejącego klucza do at spowoduje zgłoszenie błędu.

Kontener map przechowuje dla każdej wartości klucza tylko jedną wartość. Wstawianie wartości i wyszukiwanie kluczy ma złożoność logarytmiczną względem wielkości kontenera.

Do dostępu do wszystkich elementów kontenera najlepiej użyć iteratora. Należy zwrócić uwagę, że dereferencja iteratora daje parę klucz-wartość, z której trzeba dodatkowo wyłuskać potrzebny element.

#include <iostream>
#include <map>

using namespace std;

int main() {
    map<string, int> m;

    m["jeden"] = 1;
    m["dwa"] = 2;
    m["trzy"] = 3;

    for (map<string, int>::iterator it = m.begin(); it != m.end(); ++it)
        cout << it->first << ": " << it->second << endl;

    return 0;
}

multimap

Kontener multimap jest podobny do map, z tym, że może przechowywać różne wartości stowarzyszone z tym samym kluczem. Nie obsługuje operatora [] ani metody at, dostęp do przechowywanych obiektów jedynie poprzez iteratory.

unordered_set, unordered_multiset,
unordered_map, unordered_multimap (C++11)

Kontenery te mają taki sam interfejs i zachowanie jak ich uporządkowane odpowiedniki, jednak wewnętrzna implementacja nie korzysta z sortowania obiektów/kluczy. Zamiast tego korzysta z funkcji skrótu (haszującej). Przez to obiekty są przechowywane w zaskakującym porządku, za to operacje wstawiania i wyszukiwania są szybsze. Zamiast czasu logarytmicznego, wstawianie i wyszukiwanie odbywa się średnio w czasie stałym (choć czas wykonania jednostkowej operacji może być większy).

Adaptery kontenerów

stack

Adapter stack implementuje stos. Nie jest kontenerem w ścisłym sensie, gdyż jest nadbudowany na innym kontenerze (choć można używać go jak kontenera i nie mieć o tym pojęcia).

Stos to struktura danych przypominająca stos talerzy. Możemy zawsze położyć nowy obiekt na szczycie stosu, ale pobrać możemy też tylko ze szczytu. Obiekt położony na stosie jako ostatni jest zdejmowany jako pierwszy. Angielski akronim takiego zachowania to LIFO (last in, first out).

Standardowo stack opakowuje kontener deque, ale można to zmienić Standardowe kontenery vector i list równie dobrze nadają się jako kontener do zbudowania stosu.

Obiekty na stos wkładamy używając metody push() i usuwamy ze szczytu metodą pop(). Dostęp do elementu na szczycie zapewnia metoda top().

#include <iostream>
#include <stack>

using namespace std;

int main() {
    stack<int> s;

    s.push(1);
    s.push(2);
    s.push(3);

    while (!s.empty()) {
        cout << s.top() << endl;
        s.pop();
    }

    return 0;
}

queue

Adapter queue implementuje kolejkę. Elementy wkładamy na koniec kolejki, a zdejmujemy z przodu kolejki. Tym samym obiekt wstawiony jako pierwszy jest zdejmowany jako pierwszy. Po angielsku FIFO (first in, first out).

Interfejs jest podobny do adaptera stack. Metoda push() wstawia na koniec kolejki, metoda pop() usuwa pierwszy element. Do dostępu do obiektów służą metody front() i back().

#include <iostream>
#include <queue>

using namespace std;

int main() {
    queue<int> q;

    q.push(1);
    q.push(2);
    q.push(3);

    while (!q.empty()) {
        cout << q.front() << endl;
        q.pop();
    }

    return 0;
}

priority_queue

Adapter priority_queue implementuje kolejkę priorytetową. Elementy wkładamy do kolejki, a z przodu kolejki zdejmujemy zawsze element największy. Adapter priority_queue utrzymuje w opakowywanym kontenerze strukturę kopca.

Interfejs jest podobny do adaptera stack. Metoda push() wstawia do kolejki, metoda pop() usuwa pierwszy element. Do dostępu do największego obiektu służy metoda top().

#include <iostream>
#include <queue>

using namespace std;

int main() {
    priority_queue<int> q;

    q.push(1);
    q.push(2);
    q.push(3);

    while (!q.empty()) {
        cout << q.top() << endl;
        q.pop();
    }

    return 0;
}