Wstęp - podstawowe informacje o STL-u

STL, czyli o co tyle hałasu

Zanim rozpoczniesz naukę STL-a warto żebyś wiedział coś więcej o tym, czego będziesz się uczył w tym kursie. W świecie programowania C++, hasło STL pojawia się nieustannie i zawsze jest o nim głośno... często początkujące osoby, które nie znają STL-a pytają się co to jest i czemu go tak wszyscy zachwalają. Bardzo często spotykamy się z następującą odpowiedzią: STL jest to zbiór kontenerów, iteratorów i algorytmów - naprawdę świetna sprawa, nie wiem jak bez tego można pisać programy... - ale co to tak naprawdę znaczy? Ostatni termin tj. algorytmy jest zrozumiały, jednak algorytmy w STL-u nie powalają z nóg... raczej można powiedzieć, że biblioteka ta jest uboga, a co gorsza nie ma tam nic co mogłoby się przydać bezpośrednio do gier (np. algorytmy wykrywania kolizji itp - tego w STL-u nie znajdziesz).

Czym są kontenery?

Kontenery (zwane też pojemnikami) są terminologią, która prawdopodobnie porusza wyobraźnię programisty nieznającego STL-a... Może to kontener na śmieci (ale po co mi coś takiego?)... może to coś, do czego mogę wrzucać dane różnego typu i je później odczytywać - wkońcu kolega coś podobnego mi mówił... ale jak by to miało niby działać?.

Definicja kontenera

Kontener jest to struktura danych, która służy do przechowywania danych w zorganizowany sposób. Wszystkie elementy kontenera muszą być takiego samego typu. Każdy kontener umożliwia nam wykonanie takich operacji jak:

• uzyskanie dostępu do danych w kontenerze;
• możliwość dodawania elementów do kontenera;
• możliwość usuwania elementów z kontenera.

Niektóre z nich dają nam również możliwość wyszukiwania elementu w kontenerze. Kontenery w zależności od przyjętej organizacji danych różnią się szybkością wykonywania poszczególnych operacji.

Co to jest złożoność obliczeniowa?

Szybkość nazywana jest przez programistów złożonością obliczeniową i oznaczana jest przez dużą literę O. Złożoność obliczeniowa jest to ilość podstawowych operacji jakie trzeba wykonać, aby został zrealizowany dany algorytm, posiadając określoną ilość danych wejściowych. Przykłady:

• O(K*1) - stała złożoność - algorytm wykonuje się w stałej ilości operacji, niezależnie od ilości danych. (algorytm: najszybszy)
• O(log(K*n)) - złożoność logarytmiczna - algorytm wykonuje logarytmiczną ilość operacji w stosunku do ilości danych wejściowych; n jest to ilość danych wejściowych. Podstawa logarytmu zazwyczaj wynosi 2, jednak czasami może być większa (np. w B-drzewach - nie będą one jednak tematem tego kursu). (algorytm: bardzo szybki)
• O(K*n) - złożoność liniowa - algorytm wykonuje wprost proporcjonalną ilość operacji do ilości danych wejściowych. (algorytm: szybki)
• O(K*n^X) - złożoność wielomianowa - ilość operacji algorytmu jest wprost proporcjonalna do ilości danych wejściowych podniesionej do potęgi X, gdzie X jest stałą większą lub równą 2. (algorytm: wolny)
• O(K*X^n) - złożoność wykładnicza - ilość operacji algorytmu jest wprost proporcjonalna do stałej X większej lub równej 2, podniesionej do potęgi równej ilości danych wejściowych. (algorytm: bardzo wolny)

K - jest to stała, która może mieć wartość zarówno 1 jak i 1000000. Zazwyczaj stała ta jest tak mała, że jest ona pomijalna przy podawaniu złożoności obliczeniowej algorytmów. Najczęściej wynosi ona 1 lub 2.

złożoność obliczeniowa	ilość operacji	ilość danych wejściowych
O(1)	1	100 000
O(log(n))	17	100 000
O(n)	100 000	100 000
O(n^2)	10 000 000 000	100 000
O(2^n)	1 267 650 600 228 230 000 000 000 000 000	100
O(n^n)	88 817 841 970 012 500 000 000 000 000 000 000	25
Procesor 3.0GHz/sek	3 000 000 000

1.2.3. Kontenery dostępne w STL-u

W STL-u znajduje się kilka kontenerów do zarządzania danymi. Każdy z nich posiada inną złożoność obliczeniową dla poniższych operacji:

• odczyt danych;
• dodawanie danych;
• usuwanie danych;
• szukanie danych.

Jak już wcześniej wspomniałem wyszukiwanie danych nie jest dostępne w niektórych kontenerach, jednak jest to zabieg celowy o czym przekonasz się później. Poniżej przedstawiam listę kontenerów jakie znajdziesz w STL-u:

• lista (list)
• tablica (vector)
• tablica podwójnie kończona (deque)
• tablica bitowa (bitset)
• drzewo poszukiwań (set)
• wielokrotne drzewo poszukiwań (multiset)
• mapa poszukiwań (map)
• wielokrotna mapa poszukiwań (multimap)

Oprócz kontenerów w STL-u istnieją również adaptery:

• stos (stack)
• kolejka (queue)
• kolejka priorytetowa (priority_queue)

Opisy poszczególnych kontenerów (i adapterów), złożoności obliczeniowe operacji, przykłady itp. będą przedstawiane stopniowo w kolejnych rozdziałach.

Co to są adaptery?

Adapter jest jednym z wzorców projektowych. Zadaniem adaptera jest przekształcanie interfejsów różnych klas w taki, który jest oczekiwany przez użytkownika. Innymi słowy adapter daje nam metody, za pomocą których możemy np. pobierać i zapisywać dane w określony sposób, ale sposób organizacji danych w adapterze jest nieznany. Dzięki adapterowi możemy zmienić klasę zarządzającą danymi nie zmieniając działania całej aplikacji.

Co to są iteratory?

Iterator jest to obiekt pozwalający na sekwencyjny dostęp do wszystkich danych, znajdujących się w konkretnym kontenerze. Dzięki niemu możemy w łatwy sposób poruszać się po kontenerze, usuwać wybrane elementy lub napisać wyszukiwanie o złożoności obliczeniowej liniowej, jeśli dany kontener nie posiada wyszukiwania.