Prezentacja wybranej biblioteki C++.
Standard Template Library (w skrócie STL) jest standardową biblioteką szablonów, wchodzącą w skład podstawowych bibliotek C++. Kontenery (zwane także pojemnikami), iteratory i algorytmy, jakie można znaleźć w bibliotekach STL'a są nieodłączną częścią współczesnego programowania w C++.
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.
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ć?.
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.
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.
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.
Adapter stosu (std::stack)
Stos jest to struktura danych, w której dostęp do danych jest możliwy tylko do jednego elementu, zwanego wierzchołkiem. Stos jest określany mianem LIFO (Last In First Out), czyli ostatni wchodzący element jest pierwszym wychodzącym.
Stos w STL'u posiada następujące operacje:
push - umieszczenie nowego elementu na szczycie stosu;
pop - zdjęcie istniejącego elementu ze szczytu stosu;
empty - informacja czy stos jest pusty;
size - zwraca ilość elementów umieszczonych na stosie;
top - zwraca wartość szczytowego elementu na stosie.
Aby móc skorzystać ze stosu w C++, należy dołączyć plik nagłówkowy:
#include <stack>
Kolejnym krokiem, jaki musimy wykonać jest utworzenie stosu. Zapis uogólniony wygląda tak:
std::stack< TYP_DANYCH > nazwa_stosu;
Stos może przechowywać dowolny typ danych - mogą być to typy, które już znasz czyli:
std::stack<int> stos1; //stos przechowujący liczby
std::stack<std::string> stos2; // stos przechowujący stringi (czyli tekst)
Mogą to być również struktury danych lub klasy, które utworzysz:
struct SDane
{
int liczba;
std::string tekst;
};
class CKlasa
{
private:
SDane dane[2];
public:
SDane& DajDane(int indeks)
{
return dane[indeks];
}
};
//...
std::stack<SDane> stos3;
std::stack<CKlasa> stos4;
Jak widać utworzenie stosu dowolnego typu danych jest proste i sprowadza się do napisania jednej linijki.
Metoda push służy do umieszczenia nowego elementu na szczycie stosu.
void push(const TYP_DANYCH& wartosc);
Standardowa złożoność obliczeniowa metody: O(1).
Przykład
#include <stack>
int main()
{
std::stack< int > stosLiczb;
stosLiczb.push(123);
stosLiczb.push(12);
stosLiczb.push(55);
return 0;
Metoda pop służy do zdjęcia istniejącego elementu ze szczytu stosu.
void pop();
Standardowa złożoność obliczeniowa metody: O(1).
Przykład
#include <stack>
#include <iostream>
#include <conio.h>
int main()
{
std::stack< int > stosLiczb;
int liczba = 0;
do
{
std::cout<<"Podaj liczbe (0 - konczy wprowadzanie liczb): ";
liczba = 0;
std::cin>>liczba;
if(liczba!=0) stosLiczb.push(liczba);
}while(liczba!=0);
std::cout<<"Liczby zdjete ze stosu: ";
while(stosLiczb.empty()==false)
{
std::cout<<stosLiczb.top()<<", ";
stosLiczb.pop();
}
getch();
return 0;
}
Adapter kolejki (std::queue)
Kolejka jest to struktura danych, w której dostęp do danych jest możliwy tylko do pierwszego i ostaniego elementu. Kolejka jest określana mianem FIFO (First In First Out), czyli pierwszy wchodzący element jest pierwszym wychodzącym.
Kolejka w STL'u posiada następujące operacje:
push - umieszczenie nowego elementu na końcu kolejki;
pop - usunięcie istniejącego elementu z początku kolejki;
empty - informacja czy kolejka jest pusta;
size - zwraca ilość elementów umieszczonych w kolejce;
front - zwraca wartość pierwszego elementu w kolejce.
back - zwraca wartość ostatniego elementu w kolejce.
Aby móc skorzystać z kolejki w C++, należy dołączyć plik nagłówkowy:
#include <queue>
Kolejnym krokiem, jaki musimy wykonać jest utworzenie kolejki. Zapis uogólniony wygląda tak:
std::queue< TYP_DANYCH > nazwa_kolejki;
Kolejka może przechowywać dowolny typ danych - mogą być to typy, czyli:
std::queue<int> kolejka1; //kolejka przechowująca liczby
std::queue<std::string> kolejka2; //kolejka przechowująca stringi (czyli tekst)
Mogą to być również struktury danych lub klasy, które utworzysz:
struct SDane
{
int liczba;
std::string tekst;
};
class CKlasa
{
private:
SDane dane[2];
public:
SDane& DajDane(int indeks)
{
return dane[indeks];
}
};
//...
std::queue<SDane> kolejka3;
std::queue<CKlasa> kolejka4;
Jak widać utworzenie kolejki dowolnego typu danych jest proste i sprowadza się do napisania jednej linijki.
Adapter kolejki priorytetowej (std::priority_queue)
Kolejka priorytetowa jest to struktura danych, w której dostęp do danych jest możliwy tylko do pierwszego elementu, a dane w niej są uporządkowane nierosnąco (lub niemalejąco). Kolejka priorytetowa jest określana mianem FIFO (First In First Out), czyli pierwszy wchodzący element jest pierwszym wychodzącym.
Uporządkowanie nierosnące jest to taki porządek danych, w którym każda następna wartość jest mniejsza lub równa od swojego poprzednika.
Przykładowy porządek liczb nierosnący:
50,40,40,39,30,18,18,2,1,1,0
Uporządkowanie niemalejące jest to taki porządek danych, w którym każda następna wartość jest większa lub równa od swojego poprzednika.
Przykładowy porządek liczb niemalejący:
1,1,2,3,4,33,77,87,88,88,99
Kolejka priorytetowa w STL'u posiada następujące operacje:
push - umieszczenie nowego elementu na końcu kolejki priorytetowej;
pop - usunięcie istniejącego elementu z początku kolejki priorytetowej;
empty - informacja czy kolejka priorytetowa jest pusta;
size - zwraca ilość elementów umieszczonych w kolejce priorytetowej;
top - zwraca wartość pierwszego elementu w kolejce priorytetowej.
Kontener tablicy (std::vector)
Vector jest to tak zwany kontener na dane(pojemnik), inaczej dynamiczna tablica. W owej tablicy mamy dostęp do każdego jej elementu oraz możemy w każdym momencie zwiększać jej wielkość.
Takimi funkcjami posługujemy się używając Victora:
push_back(); -dodaje do końca tablicy nowy element podany w nawiasie
insert(); - dodaje element do dynamicznej tablicy w podanym miejscu
begin(); - wskazuje pierwszy element dynamicznej tablicy
end(); - wskazuje na koniec dynamicznej tablicy
size(); - zwraca ilość elementów tablicy
Sam język C++, jak i STL mają wiele wad. Z bardziej uciążliwych można wymienić następujące (język):
Brakuje odśmiecania
Brakuje delegatów
Brakuje wyrażeń regularnych
Zbyt mało wyspecjalizowany system rzutowania - brakuje np. konwersji liczba <-> std::string, czy bezpiecznej konwersji numerycznej (która ostrzega przy stracie cyfr)
Operatory nie są definiowane grupami (np. osobna definicja += i +)
Brakuje wyspecjalizowanych narzędzi (np. do obsługi systemu plików, reprezentacji czy typów matematycznych, ...)
Skomplikowana składnia konkretna języka, co utrudnia tworzenie narzędzi analizujących kod (np. intellisense)
oraz z STLa:
Brakuje wyrażeń lambda - definiowanie funkcji w miejscu, przez co rzadko korzysta się np. z std::for_each
Uciążliwa składnia dla definiowania iteratorów (b. długie i nieczytelne zapisy). Przydałby się typ auto, który będzie w C++0x
Bardzo słabe wsparcie dla funkcji operujących na zakresach (te, przyjmujące parę iteratorów). Trudno jest np. złożyć funkcję, która będzie aplikowana do każdego elementu. Można korzystać tylko z podstawowych operacji. Np. funkcje plus, multiplies, divides, modulus, negate. Ze składania jest tylko bind1st i bind2nd (w SGI jest też compose do składania funkcji).
Niejasny interfejs. Przydałaby się wersja tego operatora ze słówkiem const.
Jest to biblioteka na dodanie funkcjonalności do języka. Nie dodaje wyspecjalizowanych narzędzi (sieć, system plików)
Biblioteka BOOST została stworzona aby uzupełnić braki STLa i samego języka. Jest wygodna, szybka, ale nie jest pozbawiona wad. Niektóre biblioteki (np. od wątków) potrafią bardzo wydłużyć czas kompilacji (chociaż tutaj powołuję się na jednego z uczestników forum www.gamedev.pl). Wadą jest złożoność niektórych implementacji. Jest to niewidoczne dla programisty, do czasu aż nie zostanie wygenerowany błąd.
Kolejną wadą, jest to że biblioteka jest mało znana. Niestety zdarza się rezygnować w projektach, z tego potężnego wsparcia, bo osoby chcące wykorzystać kod mogą sobie nie poradzić.
BOOST ma jednak więcej zalet niż wad. Są też znacznie istotniejsze. Wbrew ogólnemu przekonaniu BOOST łatwo się instaluje. Wydałem polecenie:
$ sudo aptitude install libboost-dev libboost-doc
Pod mniej przyjaznymi systemami operacyjnymi może być trochę gorzej, ale i tak instalacja sprowadza się do pobrania biblioteki z www.boost.org (klikając na taki wielki czerwony przycisk z prawej).
Korzystanie z biblioteki jest również proste. Biblioteki boost, w większości, nie są kompilowane. Oznacza to, że nie trzeba ich linkować do swojego projektu. Aby mieć inteligentne wskaźniki piszesz na początku pliku
#include <boost/shared_ptr.hpp>
I już są. Nie trzeba przekazywać żadnych opcji do linkera. W przypadku bibliotek regex (wyrażenia regularne) i signals (sygnały, delegaty) trzeba przekazać do linkera odpowiednio:
-lboost_regex i -lboost_signals
Też nie jest to trudne. To są jedyne z ważnych, wykorzystywanych na co dzień bibliotek, które wymagają linkowania.
Kolejna zaleta to wyśmienita współpraca z STL. Biblioteka BOOST powoduje, że na nowo odkrywa się STL. Np. korzystznie z for_each czy transform. BOOST wymienia też wadliwe elementy STL (np. mem_fun i mem_fun_ref).
Biblioteki BOOST są pisane przez wyśmienitych programistów i znawców C++ (np. tych pracujących nad standardem C++). Jest to gwaranację dobrej jakości. Wystarczy
np. popatrzeć na wymagania na GSoC dla ludzi piszących biblioteki.
Biblioteki BOOST, w końcu, dają programistom C++ wyspecjalizowane narzędzie do większości z typowych zadań.
Bibliografia:
8