C++ bez cholesterolu

Elementy biblioteki STL

Wprowadzenie

Standardowa Biblioteka Wzorców (Standard Template Library, STL) początkowo powstała jako niezależna biblioteka. Jej pierwotnymi autorami byli Alexander Stepanov (z Hewlett-Packard) i Meng Lee (z Silicon Graphics). Ewoluowała ona również wraz z właściwościami C++, w wyniku czego nie od razu np. pojawiły się w niej elementy wykorzystujące częściową specjalizację. Z aktualnej jej wersji również nie wszystkie elementy zostały wniesione do biblioteki standardowej C++. Biblioteka ta owszem, powstała dość późno, ale takoż nie tak dawno C++ dojrzał do możliwości jej zaimplementowania. Jak sama nazwa wskazuje, biblioteka ta jest bazowana na wzorcach, a nie na właściwościach obiektowych. Dzięki czemu możliwe jest używanie jej właściwości z użyciem obiektów wszystkich typów, również wbudowanych, gdyż elementy bazowe biblioteki są zdefiniowane za pomocą konceptów, a nie klas (pojęcie to objaśnię za chwilę).

STL zatem dostarcza struktury generycznych komponentów C++, które współpracują bez powiązań. Np. iteratory są podzielone na kategorie ujęte w konceptach, ale iteratorem jest również np. regularny wskaźnik (i to iteratorem dość rozbudowanej kategorii!). Na tych wskaźnikach (jak i na wszelkich innych typach zdefiniowanych przez użytkownika) mogą operować wszystkie algorytmy STL. Celem twórców tej biblioteki jest przede wszystkim elastyczność, wydajność i adaptacyjność poszczególnych jej komponentów.

Postaram się opisać tą bibliotekę niezbyt szczegółowo, choćby dlatego, że mnóstwo w niej jest twardej, suchej teorii. Nie jest jednak skomplikowana, ani trudna do zrozumienia, wymaga tylko wprowadzania wielu nowych pojęć. Szczegółowy opis tej biblioteki można znaleźć na stronie SGI o STL.

Biblioteka zawiera pięć najważniejszych rodzajów komponentów:

Ponieważ uniwersalizuje się dostęp do elementów zbiorników, iterowanie po nich, czy wiele innych rzeczy, można zatem np. dostarczyć jedną funkcję, która będzie pracować z każdym typem obiektu i każdym zbiornikiem (pracuje po prostu na zakresie elementów, a co ten zakres stanowi to już jej nie obchodzi), który spełnia odpowiednie wymagania (określone konceptem). Cała biblioteka jest przede wszystkim zbiorem:

Użytkownik może sobie zatem dodać własny komponent dowolnego rodzaju i - jeśli utworzy go zgodnie z regułami i konceptami STL-a - będzie on współpracował zarówno z tworami użytkownika, jak i z pozostałymi komponentami STL-a. Koncepty definiuje się słownie i najbardziej ogólnie; nie mówimy zatem "klasa X ma mieć metodę operator++()", lecz "dla dowolnego x typu X zdefiniowano ++x" (nie wyszczególnia się, czy jest to funkcja składowa, czy zwykła). W konceptach podaje się wyrażenia oznaczające założenia, jakie dany typ ma spełniać; dla każdego zestawu wymagań jest podana tablica, która specyfikuje zestaw prawidłowych wyrażeń i ich semantyki (tablice te są w oryginalnej dokumentacji; ja ich tutaj nie będę przytaczać).

Oto dwa przykłady. Jeśli trzeba scalić dwie tablice do jednej, można to wykonać w ten sposób:

int a[1000];
int b[2000];
int c[3000];
...
merge( a, a + 1000, b, b + 2000, c );

Można też np. scalić wektor i listę do liniowego niezainicjalizowanego obszaru pamięci, można to zrobić tak:

vector<Employee> v;
list<Employee> l;
...
Employee* c = allocator<Employee>().allocate(
  v.size() + l.size()
);
merge(
  v.begin(), v.end(),
  l.begin(), l.end(),
  raw_storage_iterator<Employee*, Employee>(c)
);

gdzie begin() i end() to funkcje składowe typów zbiorczych, które zwracają wartości odpowiednich kategorii iteratorów, a raw_storage_iterator to adaptator, który pozwala algorytmom wstawić rezultat wprost do niezainicjalizowanego obszaru pamięci wywołując odpowiedni konstruktor kopiujący. W tym przykładzie, pierwszy argument funkcji allocate jest ilością przydzielanych elementów (a nie ilością przydzielanych bajtów!).

Iterować można także po strumieniach (istream_iterator, ostream_iterator). Wpisanie wartości przez taki iterator powoduje wysłanie jej do strumienia, podobnie odczytanie - pobranie. Wszystkie algorytmy pracujące ze zbiornikami pracują w stylu "Stąd - dotąd", czyli z określeniem początku i końca ciągu.

Podstawowe komponenty

Do podstawowych komponentów zaliczamy operatory i pary.

Biblioteka STL definiuje symetryczne operatory relacji dla każdego typu, dla którego zdefiniuje się ich przeciwieństwo. Nie będę się skupiał na szczegółach, nadmienię więc tylko, że zdefiniowano je w <functional> i definiuje się następujące operatory:

Para (std::pair) z kolei jest to struktura z dwoma polami (first i second) dowolnych typów (podawanych jako parametry wzorca). Dostarcza się też dla nich operatory relacji == i <. Typy mogą być wydedukowane, tylko w tym celu należy użyć funkcji make_pair i podać dwa obiekty, które należy sparować.

Obie te rzeczy są zadeklarowane w <utility>.

Co do operatorów: ich definicje zostały przeniesione do przestrzeni nazw std::rel_ops, zatem trzeba zaimportować tą przestrzeń nazw, żeby ich używać. Jest to wymóg stantardu (w przypadku gcc tak jest dopiero od wersji 3.0). Zwracam uwagę, że jest to też niebezpieczne, bo importując tą przestrzeń nazw do danej jednostki kompilacji, udostępnia się te operatory dla WSZYSTKICH typów bez wyjątku!

Iteratory

Iteratory są podobne do wskaźników użytych do przemieszczania się po tablicy. Mają zdefiniowany operator *, a także określa się dla nich typ wartości (parametr wzorca będący typem), można je porównywać i dlatego definiuje się również typ odległości iteratora (stara wersja dopuszczała różne modele pamięci i w związku z tym np. różne typy odległości; obecna STL zakłada, że program korzysta tylko z jednego modelu pamięci, więc typ odległości jest zawsze ptrdiff_t). Zależnie od tego, jakie operacje iteratory udostępniają, mamy pięć kategorii iteratorów:

Hierarchia tych kategorii wygląda następująco:

input, output -> forward -> bidirectional -> random_access

Iteratory mogą być zmienialne lub stałe (stałe nie pozwalają modyfikować wskazywanego obiektu); zależy od tego wartość zwracana przez operator*, która może być referencją lub referencją do stałej. Stałe iteratory nie spełniają wymagań iteratorów wyjściowych!

Głębszych wyjaśnień wymagają określenia "następny/poprzedni" element i skok o kilka elementów. Iteratory bowiem przede wszystkim służą do tego, żeby poruszać się wewnątrz zbiornika. Do tego potrzebne są reguły opisujące ZAKRESY.

Wiesz zapewne z codziennego życia, że jeśli chcesz podać jakiś zakres (np. że nie będzie cię od wtorku do niedzieli), to zawsze jest problem ze zrozumieniem się, czy kraniec górny to element, który do tego zakresu wchodzi, czy nie (czyli na to ktoś Ci zapewne odpowie: "Czy do niedzieli włącznie?"). Problem bowiem polega na tym, że granice wyznaczające zakres muszą być umieszczone POMIĘDZY elementami, ale żeby pokazać ową granicę, musimy użyć wskazania na elementy, a nie na "pomiędzy-elementy" (nie powiesz przecież "nie będzie mnie od pomiędzy poniedziałkiem a wtorkiem a pomiędzy sobotą a niedzielą"). Zatem to całe "pomiędzy" należy jakoś zdefiniować. I to właśnie STL definiuje ZAWSZE (!) jako "pomiędzy elementem wskazanym, a poprzednim elementem", czyli ta granica jest zawsze PRZED wskazanym elementem.

Co jednak, kiedy chcemy podać jako zakres "cały zbiornik", albo po prostu "aż do ostatniego elementu"? Gdybyśmy wskazali na ostatni element jako górny zakres, to ponieważ zakres kończy się przed wskazanym elementem, nie bylibyśmy w stanie w żaden sposób zawrzeć w zakresie ostatniego elementu. Biblioteka STL zatem definiuje taką wartość iteratora, która wskazuje za ostatni element zbiornika. Np. jeśli mamy taki zbiornik:

int tab[20];

stworzymy dla niego iterator:

int* i;

i przypisz emu mu taką wartość: 

i = tab + 20;

to taka wartość iteratora `i' nazywa się wartością ZA-KOŃCOWĄ. Wartość za-końcowa służy przede wszystkim do sprawdzenia, czy "już się dojechało do końca". Koncept STL dla zbiorników (będzie to dokładniej opisane niżej) zakłada, że iterator początkowy oraz końcowy (końcowy wskazuje na ten właśnie tzw. za-koniec) są pobierane odpowiednio metodami begin() i end(). W tym wypadku, jeśli do wskaźnika przypiszemy tablicę, to uzyskujemy iterator begin(), a jeśli do niego dodamy rozmiar zbiornika – end().

Iteratory mają w założeniu wskazywać na jakiś element zbiornika. Jednak to są obiekty, jak inne. Aby zatem wskazywały na coś, trzeba im odpowiednią wartość przypisać. Poza tym, iterator zwykle nie ma pojęcia o zbiorniku, do którego wskazuje (może być coś takiego dodane przez implementację szczególnie dla "wersji debug", ale to już inna rzecz). Aby można było wykonywać na iteratorach określone operacje, wartość iteratora musi spełniać określone warunki, a w szczególności mieć (lub nie mieć) określone właściwości. "Zakońcowość" to jedna z nich. Poza tym, wartości iteratorów mogą być też:

Wyjaśnię jeszcze dokładniej, o co chodzi z "niewłaściwymi" wartościami (i czym się ona różni od osobliwej). Przede wszystkim oczywiście każda wartość osobliwa jest niewłaściwa. Iterator staje się niewłaściwy zawsze po wykonaniu dowolnej operacji wewnątrz zbiornika, która zmieniła jego liczebność (tzn. w tym również wymieniła jeden element na inny). Czasem po takiej operacji iterator staje się osobliwy i wtedy trzeba go tak czy siak ponownie zainicjalizować. Jednak nie zawsze; jesteśmy w stanie w niektórych przypadkach przewidzieć, na co będzie ten iterator nam wskazywać. Przykładowo operacja zastępowania jednego zakresu drugim w ogólności zmienia liczebność zbiornika, ale jeśli wielkość zakresu usuwanego i wstawianego jest taka sama, to iterator nie powinien zmienić elementu wskazywanego (pod warunkiem, oczywiście, że nie należy do usuwanego zakresu). To oznacza, że nie stał się on osobliwym, ale mimo wszystko wykonano operację unieważniającą iterator i dlatego stał się on nieważny.

Inaczej mówiąc, wartość niewłaściwa powstaje po unieważnieniu iteratora, a to, czy ona jest również osobliwa, wynika z niektórych szczególnych warunków. Często jest nawet wyłuskiwalna (jeśli nie stała się przypadkiem wartością za-końcową). Zauważ zatem, że wartość wyłuskiwalna nie musi być właściwa. Dzieje się tak wtedy, gdy iterator wskazuje na obiekt, ale nie taki, jakiego się na tym miejscu spodziewamy. Niedługo dowiesz się zresztą, że niektóre algorytmy mogą spowodować małe zamieszanie wewnątrz zbiornika, wskutek czego iterator, który był WŁAŚCIWY przed operacją, po niej może zostać UNIEWAŻNIONY, tzn. stanie się niewłaściwy (nie zmieniając wartości i pozostając wyłuskiwalnym!).

Właściwości iteratorów mają ze sobą też pewne związki:

Zauważ, że – podobnie jak pusty wskaźnik – wartość za-końcowa jest niewyłuskiwalna, ale za to jest właściwa. Żeby dowiedzieć się, po co dokładnie ona jest, poznajmy następną właściwość iteratorów: iterator `j' nazywamy OSIĄGALNYM z `i', jeśli istnieje skończony ciąg wywołań operatora ++ dla `i', który spowoduje, że i==j. Pamiętaj oczywiście, że nie oznacza to, iż można inkrementować jeden iterator dotąd, aż może w końcu trafi w odpowiednie miejsce w pamięci :). Jeśli iterator j jest osiągalny z i, to oznacza to również, że:

Zwracam bardzo szczególną uwagę na ten ostatni punkt, żeby jakiś mądrala nie zaczął zadawać głupich pytań w stylu "czy jeśli porównam za-koniec jednej tablicy z początkiem drugiej i wyjdzie równe, to znaczy, że mogę się odwołać do wyłuskanego iteratora za-końcowego?". Przede wszystkim bowiem, dwóch iteratorów nie wolno porównywać, jeśli jeden z nich nie jest osiągalny z drugiego (w jakimkolwiek kierunku). "Nie wolno" to znaczy, że wynik porównania niczego nie oznacza i uzależnianie jakiejś operacji od tego wyniku jest niepoprawnym kodem.

W przypadku osiągalności można też mówić o "wstecznej osiągalności", czyli od drugiego do pierwszego można przejść operatorem "--".

I tak doszliśmy do pojęcia ZAKRESU. Zakres jest to taka para iteratorów `i' i `j', że iterator `j' jest osiągalny z `i' i oznaczają początek i koniec pewnego ciągu elementów. Pamiętaj, że iterator wyznaczający koniec NIE WCHODZI do zakresu. Zauważ więc, że:

Dlaczego? Dlatego, że jeśli iterator `x' iteruje po zakresie [i,j), to najpierw przybiera wartość `i', a potem (przed jakąkolwiek operacją!) sprawdzany jest warunek `j==x'; jego spełnienie oznacza, że osiągnięto koniec zakresu. Zakres bardzo przypomina to najbardziej typowe użycie instrukcji for: 

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

Tutaj właśnie zmienna sterująca `i' przechodzi zakres [0,10).

Dla iteratorów istnieje jeszcze jedna możliwość (ponad to, co dotyczy wskaźnika) stania się niewłaściwym. Otóż załóżmy, że iterator wskazuje na obiekt będący na początku zbiornika. Jeśli algorytm spowodował takie zamieszanie, że ten wskazany element nagle znalazł na końcu zbiornika, to iterator staje się niewłaściwy. Zauważ – nie staje się niewłaściwy iterator w sensie wskazania na obiekt (czyli dla iteratora i wartość &*i pozostaje właściwa), czyli innymi słowy pozostaje wyłuskiwalny, ale staje się takim jako sam iterator (iterator utracił jakąś posiadaną właściwość). Wyobraź sobie np., że z iteratorów `i' i `j' drugi był osiągalny z pierwszego. I teraz algorytm przestawił iterator `i' w inne miejsce, w wyniku czego teraz `i' jest osiągalne z `j' (to jest możliwe w przypadku listy). O ile zatem para (i,j) mogła być zakresem przed taką operacją, o tyle po niej już nie może. Czasem się też może zdarzyć, że w zbiorniku o zwartym układzie elementów (np. wektor) usunięto element ze środka. Wtedy na pozycję, na którą wskazywał wcześniej dany iterator, wjechał już zupełnie inny element. Oczywiście takie iteratory należy traktować tak samo, jak iteratory osobliwe. Czyli nie używać :). Możemy co prawda stwierdzić, że iterator taki pozostaje wyłuskiwalny, ale jeśli wiara ta opiera się zbytnio na implementacji, to znaczy że zawierzanie takiej regule jest "niepoprawnym postępowaniem" :).

W ogólności zatem, należy wiedzieć, które operacje podstawowe na iteratorach i zbiornikach powodują ich unieważnienie. Na przykład usunięcie elementu ze środka zbiornika powoduje unieważnienie odpowiednich iteratorów w zależności od rodzaju zbiornika. Dla listy unieważniony zostanie tylko iterator wskazujący na usuwany element. Dla wektora - wszystkie od usuniętego aż do końca zbiornika. Dla dwukolejki (deque) i zbiorników sortowanych - wszystkie w całym zbiorniku (zbiorniki sortowane są implementowane - przynajmniej w najpopularniejszej implementacji SGI - jako drzewa zrównoważone i po operacji zmieniającej liczebność zbiornika są ponownie równoważone).

Omówię teraz szczegółowo poszczególne kategorie iteratorów.

Iteratory wejściowe

Dla iteratorów wejściowych `i' prawidłowy jest przede wszystkim odczyt wartości wyrażenia `*i'. Definiuje się też operator ++, ale nie stawia mu się żadnych konkretnych wymagań, poza tym, że *i++ ma mieć taki sam efekt, jak gdyby `i' było wskaźnikiem (ale tylko w ogólności; nie wymaga się np., żeby r==s implikowało ++r==++s). Również poprzednie kopie wartości *r nie muszą być osiągalne, zatem należy pamiętać, że operujące na takich iteratorach algorytmy muszą być jedno-krokowe (nie da się przejść tej samej wartości iteratora dwa razy!). Właściwie to nawet nie powinno się używać bezpośrednio wyrażenia `*i', ale wyłącznie `*i++' (implementacja często odwala całą rzeczywistą robotę w operatorze `*', natomiast `++' nie robi zupełnie nic). Nie owijając w bawełnę, przykładem takiego iteratora jest istream_iterator.

Iteratory wyjściowe

Do nich odnosi się właściwie dokładnie to samo, co do wejściowych z tą tylko różnicą, że wyrażenie `*i' pozwala tylko na zapis do tak wskazanej l-wartości. W szczególności należy spełnić takie dwa warunki:

Modelem takiego iteratora jest ostream_iterator.

Iteratory postępowe

Od tego momentu zaczynają się iteratory, które - poza dodatkowymi właściwościami - mogą być albo wejściowo-wyjściowe (jeśli są zmienialne) albo tylko wejściowe (jeśli są stałe). Tu będą opisywane właściwości iteratorów, które pozwalają na poruszanie się wewnątrz ciągów, zatem kwestia zapisu i odczytu jest tutaj pomijana, poza tym, że dla każdego zbiornika definiuje się zawsze co najmniej iterator i const_iterator.

Iteratory postępowe pozwalają na poruszanie się wewnątrz zbiornika. Zbiornik taki musi być wedle konceptu "zbiornik postępowy" (np. lista jednokierunkowa), tzn. taki, który dla dowolnego elementu wskazanego przez iterator jest w stanie podać następny element poprzez użycie dla iteratora operatora ++. Nie ma żadnych restrykcji co do ilości aktywnych kopii oraz r==s implikuje ++r==++s.

Iteratory dwukierunkowe

Iterator ten pozwala na poruszanie się wewnątrz zbiornika do przodu i do tyłu. Zbiornik taki - jak się można domyślać - musi spełniać koncept "zbiornik dwukierunkowy", a dokładnie spełniać koncepty "zbiornik postępowy" (udostępniający iteratorowi operator ++) i "zbiornik odwracalny" (udostępniający operator --, pozwalający przejść na poprzedni element); modelem takiego zbiornika jest lista dwukierunkowa, a także tablica. Dodatkowo oczywiście r==s implikuje --r==--s, a także spełnione jest --(++r)==r.

Warto też wspomnieć, że dla zbiorników dwukierunkowych (bo zbiorników wyłącznie odwracalnych przecież nie ma:*) definiuje się jeszcze iterator odwrócony. Polega to na tym, że za pomocą operatora ++ porusza się on... do tyłu. Nie jest to wcale takie bezsensowne – proszę nie zapominać, że większość algorytmów pracuje na zakresie oznaczonym początkiem i końcem, przechodząc do następnego elementu operatorem ++. Iterator taki umożliwia tym algorytmom pracować w przeciwnym kierunku.

Iteratory swobodnego dostępu

Iterator ten pozwala na dowolne poruszanie się wewnątrz zbiornika i indeksowanie elementów względem iteratora. Do takich iteratorów można normalnie dodawać wartości typu iterator::difference_type aby przeskoczyć odpowiednią ilość elementów. Iteratory te mogą poruszać się po zbiorniku spełniającym koncept "zbiornika swobodnego dostępu" (np. tablicy) i zdefiniowano dla nich operatory + i -.

Biblioteka dostarcza również funkcje nazwane `advance' i `distance'. Dla iteratorów swobodnego dostępu używają operatorów + i -, a dla wejściowych, postępowych i dwukierunkowych – ++. Funkcje `advance' i `distance' pozwalają odpowiednio przejść od jednego iteratora do drugiego, oddalonego o pewną wartość typu iterator::difference_type (iterator jest podany przez referencję) i zmierzyć odległość pomiędzy dwoma podanymi iteratorami (stara wersja wpisywała wynik do trzeciej wartości podanej przez referencję; nowa, zwracająca wynik jest zależna od właściwości zwanej częściową specjalizacją wzorców i tym samym wprowadzonej w miarę niedawno własności zwanej iterator_traits).

Pliki nagłówkowe: <algorithm>, <iterator>

Wedle tych podanych kategorii iteratorów istnieją iteratory dla konkretnych zbiorników. W zbiornikach STL-a są wewnątrz klas zdefiniowane typy będące iteratorami przeznaczonymi do pracy z tym zbiornikiem:

Są to oczywiście jedynie wewnętrzne definicje typów (przez typedef); ich rzeczywiste klasy są już szczegółem implementacyjnym biblioteki. Nie muszę chyba dodawać, że reverse_iterator istnieją tylko w zbiornikach odwracalnych. Będzie zaraz o nim szerzej.

Przede wszystkim jednak mamy dostępne ogólne klasy dla iteratorów:

Oraz ponadto następujące klasy będące adaptatorami iteratorów:

Koncepty

Zajmijmy się więc najmniejszymi elementami biblioteki. Biblioteka definiuje kilka standardowych konceptów (pomijam tu koncepty iteratorów, inaczej KATEGORIE, gdyż chyba omówiłem je wystarczająco dokładnie).

Typy danych

Dodatkowe wyjaśnienia chyba nie są potrzebne.

Zbiorniki

Zbiorniki posiadają następujące właściwości:

Zbiornik (container)

Jest to obiekt, który zawiera w sobie inne obiekty oraz posiada metody dające do nich dostęp. Posiada zawsze zdefiniowany wewnątrz typ `iterator', który służy do iterowania po jego wnętrzu. Typ wartości zawieranych obiektów musi spełniać koncept "przypisywalny" i "domyślnie-konstruowalny", sam zbiornik również spełnia koncept "przypisywalny". Nie zakłada się nic co do porządkowości tych elementów, ani ile może być aktywnych kopii. Posiada metody: begin, end, size, max_size, empty i swap. Zbiornik zawłaszcza elementy, tzn. trwanie elementów nie przekracza trwania zbiornika. Zakres od begin() do end() jest zawsze zakresem prawidłowym. Jego iterator spełnia koncept iteratora wyjściowego. Od siebie jeszcze dodam - jakiś czas temu zdefiniowałem sobie zbiornik podobny do `list', w którym węzeł był zintegrowany z elementem. Wydaje mi się, że można go nazwać zbiornikiem (i to nawet dwukierunkowym), aczkolwiek zbiornik ten wcale nie wymagał, żeby jego elementy były domyślnie-konstruowalne, a jedynie przypisywalne. A powodem, dla którego ustalono taką regułę jest to, że np. w liście jest węzeł główny, który służy do zwracania go przez end(), jest tworzony z użyciem konstruktora domyślnego (bezargumentowego). Ja węzeł główny zdefiniowałem inaczej, więc domyślny konstruktor do niczego nie jest tam potrzebny. Podobnie nie sądzę, żeby używał go konstruktor typu vector. Istnieją tylko niektóre metody i niektóre algorytmy, które tworzą nowe elementy bez podania wartości i one potrzebują domyślnego konstruktora, ale przecież nikt nie musi ich używać.

Zbiornik postępowy (forward container)

Jest to zbiornik, którego elementy są ułożone kolejno. Każdy element ma swój następny element i zakłada się, że będzie on taki sam przez cały czas (pod warunkiem, że nie zmieni się celowo kolejności elementów przez wykonanie operacji UNIEWAŻNIAJĄCEJ iteratory). Jego iterator spełnia koncept iteratora postępowego. Posiada zatem metody begin() i end().

Zbiornik odwracalny (reversible container)

Jest to zbiornik, którego każdy element ma swój poprzedni (analogicznie jak powyżej). Jego iterator spełnia koncept iteratora dwukierunkowego. Posiada dodatkowo metody rbegin() i rend().

Zbiornik swobodnego dostępu (random access container)

Jest to zbiornik, którego iterator spełnia koncept iteratora swobodnego dostępu. Udostępnia operator [].

Zbiorniki dzielimy następnie na ciągi i zbiorniki asocjacyjne.

Funkcjonały

Funkcjonałem nazywamy klasę, której zdefiniowano operator `()'. Obiekt takiej klasy (obiekt funkcyjny) nazywamy FUNKTOREM. Na rzecz FUNKTORA wywołuje się metodę `operator()', co oznacza "wywołanie funktora". Funktory są w efekcie czymś podobnym do wskaźników do funkcji, z tym tylko, że mają zupełnie inną zawartość: ich pola istnieją tylko na rzecz operacji wykonywanej przez `()', jak również - jeśli nic takiego nie jest potrzebne - mogą to być obiekty fikcyjne (tzn. nie zawierające żadnych pól), a wywołanie funktora może być również rozwinięte. Funktorem może być oczywiście również wskaźnik lub referencja do funkcji. Np. dlatego, że są to jak najbardziej obiekty, dla których wyrażenie "f()" (z odpowiednią liczbą argumentów) jest prawidłowe. Z tym tylko, że jej wywołanie już raczej nie będzie rozwinięte (tzn. jest raczej mało prawdopodobne, że kompilator dokona rozwinięcia w takim przypadku).

STL definiuje następujące rodzaje funkcjonałów:

Orzeczniki

Predefiniowane funkcjonały w STL (odpowiadające operatorom):

Adaptatory funkcjonałów:

Adaptatory funkcji składowych:

Oczywiście do wszystkich z nich istnieją także odpowiedniki z const (np. const_mem_fun_t). To takoż są typy i raczej nie używa się ich bezpośrednio, lecz poprzez adaptory mem_fun i mem_fun_ref.

Tu drobna ciekawostka. Przedstawione tu adaptory są bardzo ubogie i średnio wygodne w użyciu. Jeśli kogoś interesuje, polecam zapoznanie się z boost::bind (www.boost.org). Jest on o tyle lepszy, że posiada dużo większe możliwości i jest bardziej ogólny. Nie tylko zastępuje wszystkie powyższe adaptory funkcjonałów, ale także może być użyty w wielu innych sytuacjach, jak również ilość argumentów funkjonałów jest ograniczona do 10, a nie do 2, jak w STL-u. Przykładowo, not1(f) można zapisać też jako bind(logical_not<bool>(),bind(f,_1)). Do kompozycji, boost posiada również rodzinę funkcji compose; powyższe można zapisać także jako compose_f_gx(logical_not<bool>(),f). Z drugiej jednak strony, zetknąłem się z sytuacją, gdzie boost::bind nie chciało działać z pewnych nie do końca jasnych przyczyn, a udało mi się to z std::bind1st.

Zbiorniki

Zbiorniki oraz uogólnienie sposobów posługiwania się nimi to niemal główny powód istnienia STL. Wielka szkoda oczywiście, że taka biblioteka nie powstała wcześniej, wskutek czego twórcy bibliotek specjalistycznych zazwyczaj definiowali swoje (praktycznie każda biblioteka, która miala swoje początki przed 1997 rokiem, włączając takie, jak MFC, czy Qt, dysponuje jakimś solidnym zestawem zbiorników; Qt to nawet posiada replikę STL o nazwie QTL). Żadna z nich jednak nie mogła się poszczycić taką funkcjonalnością, jak te z STL. Zresztą wedle słów Bjarne Stroustrupa, to właśnie dlatego stała się biblioteką standardową.

Istnieją różne rodzaje zbiorników, nawet tej samej kategorii. Sposób iteracji po nich jest zunifikowany, a różnią się one sposobem implementacji, a więc de facto szybkością wykonywanych różnych operacji. Np. wektor jest tablicą, której rozmiar może się zmieniać, jej iteratory są swobodnego dostępu, ale jej powiększanie i wstawianie elementów w środku ("rozpychanie") jest liniowego czasu (nie zawsze oczywiście; dla wektora specyfikuje się wielkość zapasowa, zatem jej powiększanie jest zazwyczaj stałego – amortyzując – czasu; głównie chodzi tutaj o fragmentowanie pamięci w razie powiększania tablicy). Inaczej jest z listą, gdzie wstawianie elementu i jej powiększanie jest stałego czasu, ale jej iteratory są tylko dwukierunkowe.

Należy pamiętać o jeszcze jednej rzeczy: każdemu zbiornikowi można określić sposób przydzielania pamięci (zostaną one opisane dalej); należy podawać to zawsze jako ostatni parametr wzorca.

Ciągi

vector

Ciąg tylnego wstawiania o zmiennej długości i liniowym układzie elementów; jego iteratory są swobodnego dostępu. Udostępnia - poza standardowymi metodami ciągów - również operator []. Iterator wskazujący na element wektora po operacji wstawiania elementu jest unieważniany (chodzi nie tylko o "przesuwanie" elementów w tablicy; poczytaj o funkcji realloc). Ciekawym typem jest vector<bool>, znany wcześniej jako bit_vector (istniał tylko ze względu na brak w niektórych kompilatorach właściwości pt. "partial specialization"). Jego elementy faktycznie zajmują jeden bit (choć oczywiście jego długość jest zawsze przybliżana do pełnego bajtu :*).

list

Ciąg przedniego i tylnego wstawiania o zmiennej długości, gdzie każdy element trzymany jest przez węzeł podwójnie wiązany. Jego iteratory są dwukierunkowe. Operacja taka jak splatanie dwóch list jest stałego czasu. Co ważne, usuwanie i wstawianie elementów nie unieważnia iteratorów (z wyjątkiem tych, które wskazują na usuwane elementy). Należy jednak pamiętać, że jeśli `i' i `j' są iteratorami wyznaczającymi zakres wewnątrz zbiornika, to wstawienie elementu wewnątrz tego zakresu dla wektora oznacza unieważnienie iteratora górnego zakresu, ale nie zmienia dystansu pomiędzy `i' a `j'; w przypadku listy jest odwrotnie: iteratory pozostają ważne, ale zmienia się dystans pomiędzy nimi.

deque

Nazwa jest skrótem od "double-ended queue" ("dwukońcowa kolejka", czy też, mówiąc krócej, "dwukolejka") i wymawia się jak "deck". Jest bardzo podobna do wektora, jej iteratory są również swobodnego dostępu. Nie udostępnia jednak metod reserve i capacity. Najbardziej typowym użyciem tego ciągu jest dodawanie i usuwanie elementów na jednym z jej końców (metody push_front, push_back, pop_front, pop_back). Iteratory są unieważniane zawsze przy każdym (również na końcach!) wstawianiu elementów, przy usuwaniu tylko z jej środka, a z końców tylko te, które wskazują na usuwane. Typ ten zresztą z reguły nie jest nigdy używany bezpośrednio; jest on tylko podstawą wykorzystywaną potem przez adaptatory `stack' i `queue' (choć te adaptatory potrafią adaptować dowolny zbiornik, acz `deque' jest domyślny).

Zwracam uwagę na charakterystyczne rzeczy każdego z tych ciągów. Wektor np. nie jest ciągiem przedniego wstawiania (i podobnie string, który ma z wektorem co nieco wspólnego), zatem nie ma push_front() i pop_front(). Wektor i dwukolejka mają z kolei pewne wspólne cechy, odróżniające je od listy: są to zbiorniki, w którym elementy są ułożone w "jednym ciągu" (i właśnie dlatego są zbiornikami swobodnego dostępu). To powoduje, że łatwiej się po nich iteruje, liczenie liczby elementów, czy dystansu między dwoma iteratorami, jest stałego czasu. W przypadku listy takie operacje są liniowego czasu (w ilość elementów). Lista jednak może być dowolnie dzielona na kawałki i sklejana i te operacje są dla listy stałego czasu (a łatwo sobie wyobrazić, ile zamieszania to by powodowało w przypadku wektora, czy dwukolejki). Tak samo, w przypadku listy usunięcie dowolnego elementu i wstawienie w dowolnym miejscu jest takoż stałego czasu. W ogólności, listy nie należy stosować tam, gdzie trzeba wciąż elementy przeglądać, czy liczyć (podpowiem tylko, że "najszybszy" algorytm sortujący, introsort, w przypadku listy okazuje się najwolniejszy, właśnie z tych powodów), a wektora i dwukolejki tam, gdzie należy wciąż elementy przekładać z miejsca na miejsce lub też często elementy się usuwa z kolejki i wkłada.

Tak przy okazji, to co tu napisałem o dwukolejce, to nie jest do końca prawda. Dwukolejka jest bardzo szczególnym zbiornikiem, ze względu na swoją budowę. Jest to coś, co mi zresztą jakiś czas temu przyszło do głowy (acz nie w takiej postaci): zbiornik klejony. To polega na tym, że wewnątrz tego zbiornika są mniejsze zbiorniki, które dopiero przechowują elementy. To powoduje, że można swobodnie i dość szybko doklejać kolejne elementy z jednej i drugiej strony, jeśli się coś nie mieści, to tworzy się kolejny podzbiornik i jedzie dalej. Nie wiem tego dokładnie, ale mógłbym sobie wyobrazić, że nawet wstawianie w środku jakiegoś elementu byłoby mniej kosztowne, niż w przypadku wektora (zauważ, że każdy z podzbiorników może sam sobie specyfikować pojemność zapasową!). To wszystko ma niestety jedną poważną wadę (i właśnie z tego powodu nie o takim zbiorniku klejonym myślałem): jak się można domyślać, iteracja po tym zbiorniku nie jest taka prosta. Każdy awans iteratora jest obarczony porównywaniem w celu sprawdzenia, czy iterator po awansie będzie nadal siedział w tym samym podzbiorniku, a także każde porównanie z innym iteratorem to porównanie dwóch (a nie jednej, jak w większości) wartości. Podobnie size(), jak się można domyślać, będzie może nie liniowy, ale też i nie taki znów stały. Dlatego też należy sobie raczej darować iterowanie po takim zbiorniku, w miarę możliwości (ja miałem pomysł trochę inny – powinno się zgenerycyzować sposób iteracji po zbiorniku i wyznaczać, które algorytmy pracują jednolicie na całym zbiorniku – jak for_each – i te wołać po kolei dla każdego podzbiornika, a które muszą pracować na całym – jak sort – i te już wołać normalnie).

Adaptatory ciągów

stack

Tzw. "stos", czyli "LIFO" (last in, first out - odrzucanie i zbieranie elementu z tego samego końca). Posiada metody push i pop, które odrzucają i zbierają element. Należy pamiętać, że typem zwracanym pop jest void. Powód jest prosty - metoda top zwraca element szczytowy przez referencję, gdyż tak jest "most efficient", a pop tak elementu zwracać nie może. Można podać dowolny podległy zbiornik, ale domyślnym jest deque.

queue

Tzw. "kolejka", czyli "FIFO" (first in, first out - odrzucanie na jeden koniec, a zbieranie z drugiego). Posiada metody push i pop, a także front, która zwraca przez referencję najbliższy element.

priority_queue

Podobna do kolejki, z tym że jej elementy są zawsze odpowiednio poukładane, zgodnie z regułami sterty - patrz make_heap itp. (trzecim parametrem wzorca jest orzecznik; domyślnie stosuje się operator `<'). Domyślnym podległym zbiornikiem jest vector. Nie umożliwia iterowania po elementach (mimo, że iteratory są swobodnego dostępu), a powodem tego jest właśnie sterta.

Zbiorniki asocjacyjne

Tu się rozdrabniać nie będę. Właściwości tych zbiorników zostały opisane przy konceptach. Wyszczególnię tylko, jakie typy należą do konkretnych właściwości.

Ze względu na to, co stanowi wartość kluczową, dzielą się one na:

Przypominam, że elementy będące kluczami są stałe (czyli nie spełniają konceptu `przypisywalny')! W przypadku mapy oczywiście same elementy zbiornika uważa się za stałe, ale samo pole `second' ma zachowaną pierwotną wariancję.

Ze względu na restrykcje co do równości elementów, zbiorniki dzielą się na:

Zbiorniki asocjacyjne mają też specjalizowane metody find() i insert(). Wstawianie elementów do tego zbiornika nie powinno wskazywać miejsca wstawiania; zostanie ono wybrane przez zbiornik. Istnieje, owszem, metoda insert() z dodatkowym argumentem, iteratorem, ale – jak się wyraża dokumentacja – stanowi on jedynie podpowiedź, a w praktyce ta metoda istnieje tylko dlatego, żeby była zgodna z insert() w ciągach. Dla zbioru oczywiście metoda find() jest kluczowa o tyle, że pozwala stwierdzić, czy dany element się znajduje w zbiorze (zbiór głównie do tego jest właśnie przeznaczony). W ogólności, zbiorniki asocjacyjne przeznacza się do tego, żeby w nich później wyszukiwać; zbiór do tego, żeby grupować elementy, a mapę do tego, żeby ustanawiać powiązanie elementów pomiędzy dwoma zbiorami (np. napis do liczby całkowitej, czy liczbę całkowitą do wskaźnika na funkcję itp.). Odradzam (i to STANOWCZO odradzam!) trzymanie w zbiorze "poważnych" obiektów (uprzedzam, bo widziałem już np. trzymanie w zbiorze wskaźników do dużych obiektów). Zbiór powinien zawierać tylko takie obiekty, wśród których będzie coś wyszukiwane przez porównanie. Metoda find() również istnieje właśnie dlatego, że – odmiennie, niż ogólny algorytm find() – wyszukuje binarnie. Tzn. dokładnie to nie jest tak; wyszukiwanie jest po prostu logarytmicznego czasu, ale i sam zbiornik ma niekiedy skomplikowaną budowę (w wyniku czego iteracja po nim nie jest stałego czasu, a co najwyżej amortyzownanego stałego). W ogólności: zbiorniki sortowane mają zoptymalizowane operacje wyszukiwania i po części operacje wstawiania (obie logarytmicznego czasu), ale niestety iteracja po nim jest wolniejsza, niż np. w przypadku wektora (ale też nie do tego są te zbiorniki przeznaczone).

Pakiet łańcuchów

Najbardziej znanym łańcuchem jest string, który jest łańcuchem znaków typu char. Jest to jednak nie tyle typ, ile specjalizacja wzorca basic_string, który jako parametry wzorca przyjmuje typ znaku, reguły CECHOWANIA znaku (character traits) no i - tradycyjnie - alokator.

Reguły cechowania znaków to po prostu klasa, która zawiera odpowiednie definicje typów i statyczne metody, określające sposób wykonywania odpowiednich operacji. Taka klasa jest oczywiście nawet zdefiniowana i to jako wzorzec (zatem domyślnie drugim parametrem wzorca basic_string jest std::char_traits, gdzie charT jest pierwszym parametrem wzorca). Najważniejsze rzeczy nt. basic_string napisałem wcześniej (pisząc o nim jako o typie string), szczegółowiej zostanie opisany w następnym rozdziale.

Algorytmy

Algorytmy są bezwzględnie jedną z najmocniejszych stron STL-a, a zarazem największej jej części. Główną ich zaletą jest to, że potrafią pracować prawie ze wszystkim, wystarczy jedynie, żeby dany typ spełniał pewne wymagania. Algorytmy są zaimplementowane jako wzorce funkcji.

Algorytmy niezmieniające

Tzn. nie modyfikujące układu obiektów w zbiorniku. Aktualnie, wszystkie poza for_each, to najróżniejsze wyszukiwacze.

Algorytmy zmienające

Sortowanie

Algorytmy niezmieniające dla posortowanych zakresów

Scalanie zakresów

Operacje na zbiorach

Te algorytmy operują na nie tyle zbiorach, co posortowanych rosnąco zakresach. Udostępniają znane z matematyki operacje na zbiorach, jak "zawieranie się zbiorów", "suma zbiorów" i "różnica zbiorów", tylko coś tu nie widzę operacji "należy do zbioru" (find to nie jest to, bo nie jest to algorytm specjalizowany do posortowanych zakresów); być może autorzy stwierdzili, że jej uogólnieniem jest `includes', w końcu można jej podać zakres składający się z jednego elementu (ostatecznie zbiorniki, które reprezentują zbiory mają swoje find, tylko nie wiem po co w takim razie wprowadzono dodatkowo poniższe algorytmy).

Sterty

Algorytmy numeryczne