10. Pojemniki, iteratory i algorytmy. Standardowa biblioteka szablonów (STD).

Projekt standardu AINSI C++ zawiera Standardową Bibliotekę Szablonów (STD - standard Template Library).

Pojemniki danych są to, ogólnie mówiąc, obiekty do przechowywania innych obiektów. Ich struktura na ogół odpowiada klasycznym strukturom danych: listom powiązanym, kolejkom, stosom i drzewom. Kod oparty na tych strukturach danych jest złożony i często trudny do zaprogramowania. W jeszcze większym stopniu uwaga ta dotyczy struktur trudniejszych: kolejek dwukierunkowych, kolejek priorytetowych. zbiorów, planów itp. Dlatego istnienie standardowej rozszerzalnej biblioteki szablonów tych klas jest ze wszech miar korzystne.

Każdy pojemnik STL posiada związane z nim funkcje składowe. Niekiedy są one wspólne dla wszystkich pojemników, a niekiedy unikalne dla jednego pojemnika.

Ogólnie mówiąc pojemniki STL dzielimy na następujące klasy:

1. Pojemniki sekwencyjne.

2. Pojemniki skojarzeniowe.

3. Łączniki pojemników.

Uwaga ogólna:

Prze wstawianiu elementów do pojemnika tworzona jest jego kopia. Dlatego wstawiany element powinien mieć dobrze funkcjonujący operator przypisania i konstruktor kopiujący. Pojemniki asocjacyjne i mnogie algorytmy wymagają porównywania elementów. Dlatego należy też zadbać o operatory relacji. Zanim jednak powiemy cos więcej o pojemnikach omówimy iteratory.

10.1. Iteratory.

Iteratory pomyślano jako odpowiedniki wskaźników dla pojemników sekwencyjnych. Dla każdego typu zasobnika iteratory są inne. Niemniej jednak pewne działania iteratorów są wspólne dla wszystkich pojemników: operator dereferencji (*) wykonuje dereferencję iteratora, działanie ++ zwraca iterator do następnego elementu pojemnika

Funkcja begin() zwraca wskazanie iteratora do pierwszego elementu pojemnika, funkcja end() zwraca wskazanie iteratora do pierwszego elementu po ostatnim elemencie pojemnika. Oto program demonstracyjny. Czyta on dwie liczby z klawiatury i wyświetla sumę tych liczb.

#include <iostream>

#include <iterator>

using namespace std;

int main()

{

cout <<"Wprowadz dwie liczby calkowite: ";

istream_iterator < int, int > inputInt(cin);

int liczba1, liczba2;

liczba1= *inputInt; //czytanie ze standardowego wejścia

++inputInt; //przeniesienie iteratora do następnej

liczba2=*inputInt; //czytanie ze standardowego wejścia

cout << "Suma wynosi: ";

ostream_iterator <int> outputInt(cout);

*outputInt = liczba1 + liczba2; //wpisuje wynik do cout

cout << endl;

return 0;

}

Wynikiem tego programu będzie następujący tekst:

Wprowadź dwie liczby całkowite: 12 25

Suma wynosi: 37.

Iteratory należą do kilku kategorii:

1. input - iterator wejściowy. Może przechodzić tylko do przodu. Nie może być użyty do dwukrotnego przejścia tej samej sekwencji (w pojemniku, lub wejściowej).

2. output - iterator wyjściowy. Służy do zapisywania elementów do pojemnika. Może przechodzić w danej chwili tylko o jeden element do przodu.

3. forward - iterator "wprzód) - łączy możliwości iteratorów wejściowych i wyjściowych. Może zapamiętać pozycję iteratorów input i output w pojemniku. - dać informację o stanie.

4. bidirectional - iteratpry dwukierunkowe. Mogą poruszać się wstecz i obsługiwać algorytmy wieloprzxejściowe.

5. random access -iteratory o dostępie bezposrednim. mogą poruszać się w obu kierunkach i mają zdolność bezpośredniego dostępu do dowolnego elementu pojemnika - mogą przeskoczyć dowolną liczbę elementów.

Z pojemników STL stosowanie iteratorów umożliwiają zasobniki sekwencyjne i asocjacyjne. Łączniki pojemników nie maja obsługi iteratorów. Stosuje się na ogół iteratory dwukierunkowe - jedynie pojemniki sekwencyjne vector i deque mają iteratory o dostępie bezpośrednim.

10.2. Algorytmy.

Większość algorytmów łączy się z pojemnikami nie bezpośrednio, lecz za pośrednictwem iteratorów. W związku z tym STL jest rozszerzalna - można dodać do niej nowe algorytmy bez wprowadzania zmian do pojemników STL.

Mamy algorytmy, które zmieniają zawartość pojemników, na których pracują - różnego typu sortowania, odwracania kolejności itp. Mamy też, które po prostu zwracają kopię oryginalnego pojemnika. Niektórych algorytmów mamy po dwie wersje. Na przykład algorytm

replace(start, done, oldValue, newValue)

zamieni w całym zakresie wszystkie kopie oldValue na newValue, ale algorytm

replace_copy(start, done, toWhere, oldValue, newValue)

będzie wpisywał stare wersje elementów w miejsce wskazane przez iterator toWhere.

Mamy algorytmy szukające w pojemnikach wartości minimalnych i maksymalnych.

Algorytmy numeryczne np. iloczyn skalarny:

value= inner_product(InputIter1, InputIter2, OutputIter, val);

lub

value= inner_product(InputIter1, InputIter2, OutputIter, val, binOp1, binOp2);

Iloczyn skalarny to suma iloczynów odpowiadających sobie elementów dwóch pojemników. Wejście wymaga dwóch zakresów, ale wystarczą trzy iteratory, gdyż

dlugość drugiego zakresu musi być taka sama jak długość pierwszego zakresu. Czwarty patrametr to zadawana przez nas wartość początkowa sumy. Wartość końcowa jest zwracana przez algorytm. Druga forma algorytmu ma dwa argumenty dodatkowe - - pierwszy parametr zastępuje sumę, drugi - iloczyn. Na przykład, jeśli chcemy uzyskać iloczyn sum dwóch wektorów, możemy napisać:

inner_product

(

v1.begin(),

v1.end(),

v2.begin(),

1,

times<int>(),

plus<int>()

);

Podobnie mamy skonstruowaną funkcje numeryczną partial_sum

OutputIter=partial_sum(InputIter1, InputIter2, OutputIter);

oraz

OutputIter=partial_sum(InputIter1, InputIter2, OutputIter, binaryOp);

Algorytm powyższy drukuje sumy bieżące w zakresie wejściowym. Na przykład jeśli zbiór zawiera liczby 1,2,3,4,5, wtedy sumy częściowe będą 1,3,6,10,15. Wynik jest umieszczany w drugim zakresie, który może być taki sam jak zakres pierwszy.

W drugiej wersji algorytmu operator+ zastępowany jest dowolnym operatorem dwuargumentowym. Na przykład:

partial_sum

(

set1.begin(),

set1.end(),

vec2.begin(),

times<int>()

);

W powyższej deklaracji założyliśmy, że vec2 jest dostatecznie duży, by zawrzeć wynikowy ciąg wartości.

Obliczenia odwrotne do algorytmu partial_sum przeprowadza algorytm adjacent_difference

OutputIter= adjacent_difference (InputIter1, InputIter2, OutputIter);

oraz

OutputIter= adjacent_difference (InputIter1, InputIter2, OutputIter, binaryOp);

Pierwsza "różnica sąsiednia" (adjacent_difference), jest po prostu równa pierwszej wartości z pierwszego zakresu.

10.3. Pojemniki sekwencyjne.

W STL mamy trzy typy pojemników sekwencyjnych: vector, list i deque. W terminologii J. Grębosza pojemniki te nazywają się wektor, lista (podwójnie łączona) i talia. Odpowiadają one popularnym strukturom danych. Omówimy je tutaj pokrótce, bez podawania jednak przykładów kodów. Przykłady kodów - pełnych pojemników - w powszechnie dostępnych kodach źródłowych STL. Uproszczone wersje kodów dla wymienionych wyżej pojemników znajdują się w Pasji C++ Jerzego Grębosza.

10.3.1. Pojemnik typu vector.

Pojemnik kategorii vector jest uogólnieniem tablicy obiektów. Współpracuje on z iteratorami o dostępie bezpośrednim. Wstawianie elementów na końcu pojemnika jest bardzo szybkie. natomiast wstawianie elementów w środku jest dość wolne (trzeba wtedy przesuwać końcowe elementy, żeby zrobić miejsce dla elementu wstawianego).

Przykład

vector< int > v;

deklaruje relizację klasy vector zwaną v, kt/óra przechowuje wartości całkowite.

Szablon vector wyposażony jest w całą gamę funkcji go obsługujących.

Np. dla naszej deklaracji

v.size() - określa liczbę elementów przechowywanych w danej chwili w zasobniku v.

v.capacity() - określa "wstępna pojemność" wektora - liczbę elementów, którą możemy pomieścić w wektorze v, zanim zwiększy on swoja pojemność automatycznie.

v.push_back(3) - oznacza wstawianie elementu na koniec pojemnika.

Jeśli w pojemniku zabraknie miejsca, wielkość pojemnika jest zwiększana automatycznie. W niektórych realizacjach wielkość pojemnika jest zwiększana dwukrotnie. Aby uniknąć związanego z tym marnotrawstwa pamięci, możemy sami kontrolować dynamiczne rozszerzanie się pojemnika za pomocą funkcji v.resize().

W pojemniku vector mamy jeszcze mnóstwo funkcji typu v.insert(), v.erase(), oraz przeciążone operatory relacji i operatory arytmetyczne.

Uwaga! W pojemnikach, możemy przechowywać nie same elementy, ale wskaźniki do nich. Są to tak zwane pojemniki pośrednie. Ma to znaczenie jeśli same elementy są bardzo duże.

10.3.2. Pojemnik sekwencyjny list.

Pojemnik list jest rozwinięciem popularnej struktury danych - listy podwójnie łączonej - To znaczy takiej, gdzie każdy węzeł listy zawiera wskaźniki do elementów poprzedniego i następnego. Pojemnik typu lista współpracuje z iteratorami dwukierunkowymi. W pojemnikach tego typu efektywne jest wstawianie w środek pojemnika. Pojemnik wyposażono w wiele funkcji wewnętrznych pozwalających na porządkowanie listy, zlewanie uporządkowanych list (w stylu algorytmu mergeSort), usuwanie elementów itd. Na podstawie pojemników typu list, łatwo można tworzyć listy cykliczne, kolejki itp.

10.3.3. Pojemnik sekwencyjny deque.

Słowo deque jest skrótem angielskiego terminu double ended queue - kolejka o dwóch końcach. Pojemnik łączy w sobie zalety list i wektorów.

Pojemnik typu talia łączy ze sobą bloki o ściśle ustalonej wielkości. (tak jak w wektorach) gdy blok się zapełni, rezerwowany jest następny blok pamięci. W sumie otrzymujemy więc jakby listę, złożoną nie z węzłów, tylko z bloków. Dodatkowa pamięć może być przydzielana na obu końcach obiektu deque. Iteratory tej klasy muszą być bardziej inteligentne od iteratorów w pozostałych pojemnikach sekwencyjnych. Pojemnik współpracuje z iteratorami dostępu bezpośredniego.

10.3.4. Podsumowanie własności pojemników sekwencyjnych:

Operacje	Pojemnik
		vector	list	deque
operacje na początku	trudne	łatwe	łatwe
operacje w środku	trudne	łatwe	trudne
operacje na końcu	łatwe	łatwe	łatwe
dostęp do elementów	natychmiastowy	żmudny	natychmiastowy

10.4. Pojemniki skojarzeniowe.

Pojemniki skojarzeniowe umożliwiają bezpośredni dostęp do przechowywania i odzyskiwania danych przez klucze. Pojemniki skojarzeniowe to set, multiset, map i multimap.

10.4.1. Pojemniki set i multiset.

W pojemnikach tych kluczami są same elementy (np. nazwisko). Różnica miedzy pojemnikami multiset i set polega na tym, że w pojemniku multiset dopuszcza się stosowanie tych samych kluczy, w zaś pojemniku set - nie. Uporządkowanie elementów może być określone za pomocą obiektu funkcyjnego np. less<int>. Pojemniki set i multiset maja takie same funkcje składowe Klasy te współpracują z iteratorami dwukierunkowymi.

Uwaga! Implementacja pojemników typu set i multiset opiera się na teorii struktur danych. Na ogół implementuje się te klasy jako tzw. czerwono-czarne drzewo przeszukiwania binarnego (np. Sedgewick R.: Algorytmy w C++, ReadMe, Warszawa 1999).

10.4.2. Pojemniki skojarzeniowe map i multimap.

Nazwa "map" pochodzi od angielskiego słowa "map" - odwzorowanie. Elementami tych klas są pary (pair), zawierające klucz i wartość. Typowym przykładem pojemnika multimap jest słownik angielsko-polski: jednemu słowu angielskiemu odpowiada wiele słów polskich. Pojemnik multimap jest często nazywana relacją jeden-do-wielu.

Pojemnik map natomiast jest to relacja jeden-do-jednego: jednemu kluczowi odpowiada tylko jedno skojarzenie. W stosunku do tego pojemnika używany jest też termin tablica asocjacyjna.

10.5. Łączniki pojemników (adapters).

W STL mamy trzy łączniki pojemników - stos, kolejkę i kolejkę z pierwszeństwem. -stack, queue i priority queue. Każdy z tych łączników może być implementowany za pomocą podległej struktury danych. Dla każdej z tych struktur zdefiniowane są składowe push i pop - implementujące wstawianie elementów do łącznika i usuwanie z niego tych elementów.

Łącznik stos działa na zasadzie LIFO - ostatni na wejściu, pierwszy na wyjściu. Stos może się opierać na wszystkich typach pojemników sekwencyjnych.

Łącznik kolejka działa na zasadzie FIFO - pierwszy na wejściu, pierwszy na wyjściu. Domyślnie kolejka jest implementowana z deque.

W łączniku kolejka z pierwszeństwem nowy element jest wstawiany do posortowanej podległej struktury danych, a usuwany z jej początku. Pojemnik może być oparty na pojemnikach vector i dequeue, ale częściej jest oparty na pojemniku vector.

Oto przykładowy program testujący łącznik stack:

#include <iostream>

#include <stack>

#include <vector>

#include <list>

using namespace std;

template< class T >

void popElements( T &s );

int main()

{

stack< int, deque < int > > intDequeStack; // domyslnie stos oparty na klasie deque

stack< int, vector< int > > intVectorStack;

stack< int, list< int > > intListStack;

for ( int i = 0; i < 10; ++i ) {

intDequeStack.push(i);

intVectorStack.push(i);

intListStack.push(i);

}

cout << "Usuwanie z intDequeStack: ";

popElements( intDequeStack );

cout << "\nUsuwanie z intVectorStack: ";

popElements( intVectorStack );

cout << "\nUsuwanie z intListStack: ";

popElements( intListStack );

cout << endl;

return 0;

}

template< class T >

void popElements( T &s )

{

while ( !s.empty() )

{

cout << s.top() << ' ';

s.pop();

}

}

Wyniki tego programu będą następujace:

Usuwanie z intDequeStack: 9 8 7 6 5 4 3 2 1 0

Usuwanie z intVectorStack: 9 8 7 6 5 4 3 2 1 0

Usuwanie z intListStack: 9 8 7 6 5 4 3 2 1 0

Obecnie biblioteka STL została włączona przez głównych dostarczycieli C++ do ich kompilatorów. Można również znaleźć jej wersje w Internecie - wystarczy nastawic wyszukiwarkę na hasło STL. Kody implementowane w Borlandzie C++ różnią się nieco od klasycznych realizacji biblioteki. Prócz tego Borlan uruchomił niezależną, swoją bibliotekę pojemników, w której można znaleźc pojemniki bardziej rozwinięte i bardziej złożone.

9

Piotr Staniewski

C++ Studia Zaoczne. Wykład 7

---