C++ bez cholesterolu: Programowanie generyczne w C++: Elementy biblioteki STL 3.3 Elementy biblioteki STL wprowadzenie Standardowa Biblioteka Wzorców (Standard Template Library, STL) jest aktualnie częścią biblioteki standardowej C++. Dostarcza ona struktury generycznych komponentów C++, które współpracują bez powiązań. Zaznaczam z góry, że STL nie jest programowana obiektowo, lecz z użyciem wzorców. Dzięki temu, że wszelkie definicje bazowe są konceptami raczej, niż klasami, komponenty STL współpracują nie tylko z typami definiowanymi przez użytkownika, ale również z typami wbudowanymi. 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: algorytm: definiuje procedurę obliczeniową zbiornik (typ zbiorczy): zarządza zestawami zasobów pamięci iterator: dostarcza algorytmowi założeń do poruszania się wewnątrz obiektu zbiorczego. funkcjonał: opakowuje funkcję w obiekt do używania przez inne komponenty (funkcjonały z kolei mają swoje specjalizacje jak np. orzeczniki) adaptator: adaptuje komponent (dowolnego rodzaju) dla dostarczenia innego interfejsu. 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: reguł, wedle których należy tworzyć komponenty podstawowych komponentów utworzonych wedle tych reguł 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ć). Koncepty zostaną dokładniej opisane w podrozdziale d. 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 = allocate( v.size() + l.size(), (Employee*)0 ); 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!), zaś drugi argument jest nieużywany i istnieje tylko ze względu na konieczność specjalizacji wzorca (przykład ten skopiowałem z oryginalnej dokumentacji STL-a w wersji HP, autorstwa Aleksieja Stiepanowa; osobiście wolałbym pisać "allocate<Employee>( size )", a nie "allocate( size, (Employee*)0 )" ). 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. Wszytkie 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 "function.h" i definiuje się następujące operatory: `!=' odwraca `==' `>' to samo, co `<' (!) `<=' odwraca `>' `>=' odwraca `<' Para 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>. Iteratory Iteratory to uogólnienie wskaźników; 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: wejściowe (input); pozwalają na odczyt z iterowanego obiektu wyjściowe (output); pozwalają na zapis w iterowanym obiekcie postępowe (forward); pozwalają pobrać "następny" element dwukierunkowe (bidirectional); pozwalają pobrać "poprzedni" element swobodnego dostępu (random access); pozwalają przeskoczyć kilka elementów do przodu lub do tyłu 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 przypiszemu mu taką wartość: i = tab + 20; to taka wartość iteratora `i' nazywa się wartością ZA-KOŃCOWĄ. Wartości iteratorów mogą być też: WYŁUSKIWALNE, jeśli dla przyjętej przezeń wartości zdefiniowano operator * (w przypadku wskaźnika oznacza to, że musi być mu przypisany jakiś konkretny obiekt). WŁAŚCIWE, jeśli -- najprościej mówiąc -- wskazują na taki element, jakiego się na tym miejscu spodziewamy (nie musi jednocześnie być wyłuskiwalny!). OSOBLIWE, jeśli nie zostały zainicjalizowane (to pojęcie jest już chyba znane, jeśli nie - wróć do rozdziału o deklaracji zmiennych :*). Takie wartości -- pamiętaj -- są NAJCZĘŚCIEJ niewłaściwe. Zauważ, ż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!). Dla iteratorów istnieje więc 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 wskaźnika (czyli dla iteratora i wartość &*i pozostaje właściwa), czyli innymi słowy pozostaje wyłuskiwalny, ale staje się takim we własnym sensie. Jeśli bowiem przypisujemy iteratorowi jakąś wartość, to iterator wskazuje na węzeł danego elementu. Jednak algorytm może też przestawić węzeł w inne miejsce. Może też nadpisać wartość, którą trzymał dany węzeł (a przezeń iterator), co spowoduje, że iterator jako wskaźnik stanie się niewłaściwy, choć pozostanie wyłuskiwalny. W takim przypadku po prostu wartość, jaka była pod tym iteratorem zmieniła znaczenie i dlatego nie będzie po tej operacji tym, czego możnaby się po niej spodziewać. Zapamiętaj: wartości za-końcowe nie są wyłuskiwalne wartości wyłuskiwalne i za-końcowe są zawsze nieosobliwe 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. Widzimy więc, że wartość za-końcowa służy przede wszystkim do sprawdzenia, czy "już się dojechało do końca". I tak doszliśmy do pojęcia ZAKRESU. Zakres jest to para iteratorów, które 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: Jeśli ++i == j, to [i, j) zawiera tylko jeden element, mianowicie `*i'. Zakres [i, i) to zakres pusty. 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). 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ć jednokrokowe (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++'. 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: należy coś wpisać przez iterator przed jego zinkrementowaniem (++), czyli ciąg ` i++; i++; ' nie jest prawidłowym kodem dowolna wartość iteratora wyjściowego może mieć najwyżej jedną aktywną kopię, czyli ` i = j; *i++ = a; *j = b; ' nie jest prawidłowym kodem 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 conajmniej 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 źródłowe: algobase.h, iterator.h 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: iterator const_iterator reverse_iterator const_reverse_iterator 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: istream_iterator (dla strumienia wejściowego) ostream_iterator (dla strumienia wyjściowego) Oraz ponadto następujące klasy będące adaptatorami iteratorów: front_insert_iterator - wstawiający zawsze z przodu back_insert_iterator - wstawiający zawsze z tyłu insert_iterator - wstawiający zawsze na określonej pozycji Te iteratory specjalizuje się iteratorem zbiornika, a inicjuje się bezpośrednio zbiornikiem, insert_iterator'owi dodatkowo trzeba podać pozycję i ten jako jedyny może się przemieszczać. Zazwyczaj nie używa się ich bezpośrednio, lecz za pomocą pomocniczych funkcji front_inserter, back_inserter i inserter. Np. jeśli chcemy skopiować tablicę do listy, która jest pusta, nie możemy napisać po prostu: copy( tab, tab+20, ls ); gdyż spowodowałoby to wylot. Tak można zrobić tylko gdy lista zawiera już 20 elementów, a owa operacja spowoduje ich nadpisanie. Jeśli chcemy te elementy dorzucić do listy, należy napisać: copy( tab, tab+20, back_inserter( ls ) ); reverse_iterator reverse_bidirectional_iterator Te adaptatory należy konkretyzować iteratorem; powstały iterator przy pomocy operatora ++ przechodzi na poprzedni element (bidirectional dodatkowo operatorem -- na następny). Zbiorniki spełniające koncept "zbiornika odwracalnego" posiadają metody rbegin() i rend(), które zwracają właśnie reverse_iterator (oczywiście rbegin() zwraca ostatni element, a rend() wartość za-końcową, poprzedzającą pierwszy element). Te identyfikatory są też definiowane wewnętrznie przez każdy zbiornik dwukierunkowy, zatem np. reverse_iterator<vector<int>::iterator> jest równoważne vector<int>::reverse_iterator (a to się chyba pisze krócej :*). raw_storage_iterator Ten adaptator również konkretyzuje się iteratorem, ale nie każdy iterator może przyjąć, tylko ten, który może iterować po liniowej pamięci (szczegółowo zostanie opisany przy alokatorach). 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 domyślnie-konstruowalny (default-constructible; definiuje konstruktor() ) przypisywalny (assignable; definiuje = i konstruktor kopiujący) porównywalny (equality-comparable; definiuje ==) porządkowalny (less-than-comparable; definiuje <) Dodatkowe wyjaśnienia chyba nie są potrzebne. zbiorniki Zbiornik: 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 []. Ciągi: ciąg (sequence) Jest to zbiornik postępowy o zmiennej długości, którego elementy są ułożone w ścisłym liniowym porządku. Wspiera wstawianie i usuwanie elementów. ciąg przedniego wstawiania (front insertion sequence) Jest to ciąg, który umożliwia wstawianie elementów na początek zbiornika oraz pozyskiwanie elementów z początku zbiornika. Posiada do tego stosowne metody i skróty (front, push_front, pop_front). ciąg tylnego wstawiania (back insertion sequence) Jak wyżej, ale na koniec zbiornika - back, push_back, pop_back. Zbiorniki asocjatywne: zbiornik asocjatywny (associative container) Jest to zbiornik o zmiennej długości, który pozwala na operowanie elementami na podstawie kluczy. Pozwala na wstawianie i usuwanie elementów, ale jest to jakby "worek": nie pozwala np. na wstawianie elementu na konkretnej pozycji (wynika to stąd, że elementy wewnątrz zbiornika są posortowane i to zbiornik wybiera, gdzie element należy wstawić). Należy pamiętać, że elementy takiego zbiornika nie są "przypisywalne", nie mają zatem iteratora zmienialnego. Zbiornik ten definiuje typy key_type i value_type, które mogą być takie same. zwykly zbiornik asocjatywny (simple ...) Jest to zbiornik asocjatywny, którego elementy same są kluczami, tzn. key_type i value_type to ten sam typ. Modelem tego konceptu jest `set'. parowy zbiornik asocjatywny (pair ...) Jest to zbiornik asocjatywny, którego elementy są parami. Jedna z nich to key_type, czyli wartość-klucz, a druga to value_type, czyli konkretna wartość. W tym zbiorniku oczywiście nie można zmieniać elementów, ale można zapisywać w elemencie wartości (czyli (*i).second jest przypisywalne). Modelem tego konceptu jest `map'. sortowany ... (sorted ...) Jest to zbiornik asocjatywny, którego elementy są posortowane rosnąco wedle wartości klucza. Klucz musi być oczywiście porządkowalny. unikalny ... (unique ...) Jest to zbiornik asocjatywny, którego klucze są unikalne (tzn. nie mogą w danym zbiorniku istnieć dwa klucze będące równymi - operator `=='), co oznacza w praktyce, że dodanie do zbiornika elementu równego jednemu z już w nim będących nie zostanie wykonane (tzn. zostanie zignorowane). wielokrotny ... (multiple ...) Jest to zbiornik asocjatywny, w którym dopuszcza się dowolną ilość takich samych kluczy, co w praktyce oznacza, że po usunięciu ze zbiornika elementu o podanym kluczu, nadal może on w nim występować! 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. STL definiuje następujące rodzaje funkcjonałów: generator Inaczej funkcja bez argumentów. funkcja unarna Inaczej funkcja z jednym argumentem. funkcja binarna Inaczej funkcja z dwoma argumentami. Algorytmy STL nie używają nigdzie więcej, niż dwóch argumentów dla funkcjonałów. generator adaptacyjny Jest to generator, który zdefiniował wewnątrz typ `result_type', będący typem zwracanym przez funktor. funkcja unarna adaptacyjna Jest to funkcja unarna, która zdefiniowała wewnątrz typy `result_type' i `argument_type'. funkcja binarna adaptacyjna Jest to funkcja binarna, która zdefiniowała wewnątrz typy `result_type', `first_argument_type' i `second_argument_type'. Modelem operacji monoidalnej jest dodawanie i mnożenie, a ich elementami niezależnymi są - jak wiemy - odpowiednio 0 i 1. orzeczniki: orzecznik (predicate) Jest to funkcja unarna, która ORZEKA o spełnieniu jakiegoś warunku, czyli sprawdza warunek i zwraca prawdę lub fałsz. Przykładem może być funkcja, która sprawdza, czy liczba jest dodatnia. orzecznik binarny Jest to funkcja binarna, analogiczna do powyższej. Przykładem może być funkcja, która sprawdza, czy podane argumenty są sobie równe. orzecznik adaptacyjny Jest to orzecznik, a zarazem funkcja unarna adaptacyjna. Definiuje argument_type, a result_type jako bool. orzecznik binarny adaptacyjny Jest to orzecznik, a zarazem funkcja binarna adaptacyjna. Definiuje typy argumentów, a result_type jako bool. Predefiniowane funkcjonały w STL (odpowiadające operatorom): operacje arytmetyczne plus (+) minus (-) multiplies (*) divides (/) modulus (%) negate (-) (unarna) operacje relacji equal_to ( == ) not_equal_to ( != ) less ( < ) greater ( > ) less_equal ( <= ) greater_equal ( >= ) operacje logiczne logical_and ( && ) logical_or ( || ) logical_not ( ! ) Tu drobna uwaga -- mimo, że standardowo w C++ operatory te przyjmują typ bool, to jednak są to nadal wzorce funkcjonałów, czyli można specyfikować dowolny typ przyjmowanego przez nie argumentu (w efekcie i tak wywoła się podany operator). Po co -- nie wiem. Nie zdefiniowano nawet bool jako domyślnego parametru wzorca (ale z drugiej strony to jest dobre; nie należy zapominać, że taki operator ktoś sobie mógł przeciążyć i to niekoniecznie zgodnie z tymi typami). Adaptatory funkcjonałów: binder1st - tworzy funkcję unarną z binarnej, "przywiązując" podany argument jako pierwszy dla tej binarnej; nie należy tego używać wprost, lecz za pomocą pomocniczej funkcji `bind1st' binder2nd - jak powyżej, ale przywiązuje drugi argument pointer_to_unary_function, pointer_to_binary_function - pakuje wskaźnik do funkcji w funkcjonał adaptacyjny. Zarówno unarną jak i binarną funkcję pakuje się poprzez funkcję pomocniczą ptr_fun(). Funkcja ta jako argument przyjmuje wskaźnik do funkcji i zwraca stosowny funktor. unary_negate, binary_negate - adaptatory odwracające znaczenie odpowiednio orzecznika i orzecznika binarnego. Używa się tutaj również funkcji pomocniczych odpowiednio not1 i not2. Adaptatory funkcji składowych: mem_fun_t - zamienia metodę bezargumentową na funkcjonał. Należy używać funkcji pomocniczej mem_fun, która jako argument przyjmuje wskaźnik na metodę. Daje do możliwość podania również metody wirtualnej z klasy bazowej, co umożliwia połączenie generycznego programowania z dziedziczeniem i polimorfizmem. Utworzony zostanie funktor unarny, którego argument jest wskaźnikiem do typu wartości. mem_fun_ref_t - jak powyżej; należy stosować mem_fun_ref, a utworzony funktor jako argument przyjmuje referencję do typu wartości. mem_fun1_t - jak mem_fun_t, ale zamienia metodę z jednym argumentem na binarny funkcjonał. Pierwszym argumentem jest wskaźnik do typu wartości. mem_fun1_ref_t - wyjaśnienia chyba zbędne 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; przykładowo 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. 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 (m. in. jedne z najbardziej zabiedzonych "kolekcje" z biblioteki MFC razem z tym zabiedzonym "uniwersalnym iteratorem" zwanym POSITION). Żadna z nich jednak nie mogła się poszczycić taką funkcjonalnością, jak te z STL. 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 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 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" 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). 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 asocjatywne 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. Dzielą się one na: ze względu na to, co stanowi wartość kluczową: zbiór: set, multiset; jedynym istotnym parametrem jest tutaj pierwszy mapa: map, multimap; należy podać dwa parametry: klucz oraz typ danych im przyporządkowanych ze względu na restrykcje co do równości elementów: unikalne: set, map wielokrotne: multiset, multimap 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 TRAKTOWANIA znaku (character traits) no i - tradycyjnie - alokator. Reguły traktowania 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 char_traits<charT>, gdzie charT jest pierwszym parametrem wzorca. Najważniejsze rzeczy nt. basic_string napisałem wcześniej (pisząc o nim jako o typie string). 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 for_each( first, last, unary_fn ) Dla każdego elementu z zakresu [first, last) wywołaj unary_fn. find( first, last, value ) find_if( first, last, pred ) Znajdź w podanym zakresie wartość równą value (_if - spełniającą pred). Zwraca iterator wskazujący na znaleziony element lub last jeśli nie znalazł. adjacent_find( first, last ) Znajdź taki element, że jego następnik jest mu równy. adjacent_find( first, last, pred ) Znajdź taki element `i', że pred( *i, *i+1 ) jest spełniony. Dodatkowym warunkiem jest oczywiście, że oba iteratory są prawidłowe. Jak poprzednio, jeśli element nie zostanie znaleziony, zwracany jest last. find_first_of( first1, last1, first2, last2 [, pred] ) Jak `find', ale znajduje w zakresie [first1, last1) którykolwiek z elementów z zakresu [first2, last2). Jeśli podano `pred', jest on użyty do porównywania elementów, jeśli nie, używa się operatora ==. count( first, last, value [, size] ) Zlicza elementy równe `value' w podanym zakresie. Nowsza wersja zwraca tą liczbę, a starsza DODAJE tą wartość do zmiennej podanej (przez referencję) jako `size'. Starsza wersja istnieje tylko przez wsteczną kompatybilność, być może zostanie w przyszłości usunięta. count_if( first, last, pred [, size] ) Jak wyżej, ale elementy spełniające `pred'. mismatch( first1, last1, first2 [, pred] ) Porównuje dwa zakresy (operatorem == lub `pred' jeśli podano). Zwraca PARĘ, w której są odpowiednio iterator z pierwszego zakresu i iterator symetrycznie mu odpowiadający z drugiego. Jeśli na którejś pozycji podane zakresy się różnią, zwracana jest para iteratorów, których dereferencje się różnią, jeśli zakresy okażą się identyczne - pierwszym z pary jest last1. equal( first1, last1, first2 [, pred] ) Identyczny z mismatch( first1, last1, first2 [, pred] ).first == last1. search( first1, last1, first2, last2 [, pred] ) Wyszukuje w zakresie [first1, last1) ciąg [first2, last2); zwraca wartość iteratora z pierwszego zakresu, na którym szukany ciąg się zaczyna; jeśli nie znaleziono - last1. search_n( first, last, count, value [, pred] ) Szuka w podanym zakresie ciągu `count' elementów równych `value' lub spełniających z nią `pred'. find_end( first1, last1, first2, last2 [, pred] ) Ta nazwa jest trochę myląca; bardziej odpowiadałaby jej pewnie search_end lub nawet rsearch. Funkcja robi zgoła to samo co search z tym tylko że od końca. Jeśli ciąg nie zostanie znaleziony, zwracana jest wartość last1. Algorytmy zmienające copy( first, last, result ) Kopiuje elementy z podanego zakresu do `result' wywołując kolejno operator przypisania. Zwróć uwagę, że powoduje NADPISYWANIE, a nie WSTAWIANIE elementów, nie można więc użyć jej do wstawiania elementów do pustego zbiornika. Możliwym rozwiązaniem problemu jest tutaj zaadaptowanie iteratora wskazującego w zbiorniku docelowym przez insert_iterator (lub back_insert_iterator). Zauważ też, że jeśli zakresy się na siebie nakładają (tzn. result jest osiągalne z first i last jest osiągalne z result), copy nie może zostać użyte; w takim wypadku jednak przyda się copy_backward. copy_backward( first, last, result ) Jak copy, ale kopiuje od tyłu i - co ważne - result jest GÓRNYM zakresem docelowym (wartością za-końcową zakresu docelowego!). swap( x, y ) Zamienia miejscami x i y. Argumenty muszą spełniać koncept "przypisywalny". iter_swap( x, y ) Identyczne z swap( *x, *y ), gdzie x i y są iteratorami postępowymi. Istnieje ze względu na to, że niektóre kompilatory nie radzą sobie z wydedukowaniem typów argumentów przy wywołaniu jako `swap'. swap_ranges( first, last, first2 ) Zamienia miejscami podane zakresy. transform( first, last, result, op1 ), transform( first1, last1, first2, result, op2 ) - Przekształca przy pomocy podanej funkcji podany zakres elementów. Pierwsza wersja pobiera argumenty z podanego zakresu, przetwarza przy pomocy op1 i wstawia wynik poprzez result. Druga wersja podobnie, z tym że pobiera pierwszy argument z pierwszego zakresu, a drugi - z drugiego. replace( first, last, old, new ) Zamienia w podanym przedziale wszystkie znalezione wartości `old' na `new' (oba podane przez referencję). replace_if( first, last, pred, new ) Jak replace, ale dla elementów spełniających `pred'. replace_copy( first, last, result, old, new ) Jak copy, ale jeśli w źródłowym zakresie wartość == old, wstawiane jest tam `new'. replace_copy_if( first, last, result, pred, new ) Jak replace_copy, ale sprawdzany jest `pred'. fill( first, last, value ) Wypełnia podany zakres wartością (operator przypisania). fill_n( first, count, value ) Jak fill, ale górny zakres jest first + count. generate( first, last, op ) Jak fill, ale wartość uzyskuje z generatora `op'. generate_n ... remove( first, last, value ) Usuwa z podanego zakresu elementy równe podanej wartości. W rzeczywistości oczywiście nic nie jest usuwane (tzn. nie zmienia się size() zbiornika), a jedynie następuje nadpisanie elementów tak, aby nie było wśród nich podanej wartości oraz kolejność elementów została zachowana. Otrzymujemy z tego nowy zakres, gdzie początek jest taki sam, natomiast koniec zakresu jest zwracany jako rezultat i jest on równy last (jeśli nie ma w podanym zakresie szukanej wartości) lub wstecznie osiągalny z last. Zakres wyznaczany od nowego końca zakresu do poprzedniego pozostaje niezmieniony. remove_if( first, last, pred ) Jak `remove', ale sprawdza orzecznikiem warunek. remove_copy( first, last, result, value ) Jak `remove', ale wykonuje kopiowanie. remove_copy_if( first, last, result, pred ) ... unique( first, last [, pred] ) Działa identycznie jak remove, z tym że usuwa wszystkie elementy, które są sobie równe z wyjątkiem jednego z nich (tzn. po wykonaniu każdy element jest unikalny). Jeśli podamy `pred', testuje się nim dwa sąsiednie elementy, w przeciwnym wypadku używa się operatora ==. unique_copy( first, last, result ) Kopiuje elementy, pomijając powtarzające się. reverse( first, last ) Odwraca kolejność elementów w zakresie (iteratory dwukierunkowe!) reverse_copy ... rotate( first, mid, last ) Zamienia zakres [mid, last) z [first, mid). rotate_copy ... partition( first, last, pred ) Dzieli przedział na dwie części, gdzie wcześniejsza zawiera elementy spełniające podany warunek, a dalsza nie. Iterator rozpoczynający ten drugi zakres jest zwracany. Nie gwarantuje się tej samej kolejności elementów po operacji. stable_partition Jak partition, ale gwarantuje się zachowanie tej samej kolejności elementów po operacji. Sortowanie sort( first, last [, comp] ) Sortowanie (introsort). Sortowanie jest niestabilne, tzn. jeśli elementy są sobie równe, nie gwarantuje się, że pozostaną względem siebie ułożone tak samo. Sortowanie jest rosnące, porównania dokonuje się operatorem < lub podanym orzecznikiem `comp'. stable_sort Sortowanie stabilne. Używa merge sort. partial_sort( first, mid, last ) Sortowanie częściowe wg algorytmu heapsort. Polega to na tym, że elementy w efekcie są posortowane, ale tylko na pierwszych mid - first pozycjach; pozostałe są ułożone w nieokreślonym porządku. Reszta jak sort. partial_sort_copy ... is_sorted Sprawdza, czy elementy są posortowane (wg < lub podanego orzecznika) nth_element( first, nth, last ) nth_element( first, nth, last, pred ) Podobne do partition( first, last, bind1st( less<T>, *nth ) ). Dokonuje takiego podziału zbiornika, że wszystko, co jest mniejsze (operator < lub podany orzecznik) niż to, co podano jako 'nth' znajduje się zakresie [first, nth). lower_bound( first, last, value [, comp] ) Zwraca iterator wskazujący na najwcześniejsze miejsce w przedziale, w które tą wartość należałoby wstawić nie naruszając porządku. upper_bound Jak wyżej, ale najpóźniejsze miejsce. equal_range( first, last, value [, comp] ) Zwraca parę iteratorów, które wyznaczają pod-zakres podanego zakresu, którego elementy są równe `value' (tzn. ani value < *i, ani *i < value) lub nie jest spełniony `comp' dla dowolnej kolejności argumentów. binary_search Działa identycznie, jak `find' z tym, że kryteria wyszukiwania (i argumenty) są identyczne jak w equal_range. merge Scala dwa zakresy wrzucając je do wskazanego miejsca docelowego. inplace_merge( first, mid, last [, comp] ) Podany przedział powinien być podzielony na dwie posortowane części (jak po wykonaniu partition). Funkcja porządkuje elementy w całym przedziale (jak widać, stable_sort to jakby wywołanie partition i inplace_merge). 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. includes( first1, last1, first2, last2 [, comp] ) Sprawdza, czy w zakresie 2 znajdują się wszystkie te elementy, co w zakresie 1. Wymaga się, żeby zakresy były posortowane rosnąco. Nie ma wymagań, aby elementy były unikalne i dopuszcza się, żeby zakres 2 zawierał więcej takich samych elementów, niż zakres 1; musi jednak zawierać ich conajmniej tyle, co zakres 1. set_union( first1, last1, first2, last2, result [, comp] ) Tzw. "suma zbiorów"; w sumie to samo, co merge, ale elementy powinny być w obu zakresach posortowane, a operacja jest stabilna (nie narusza sortowania). set_intersection Jak wyżej, część wspólna zbiorów. set_difference Jak wyżej, różnica zbiorów. set_symmetric_difference Jak wyżej, różnica symetryczna zbiorów. Sterty push_heap( first, last ) Wstawia element poprzedni od `last' do sterty (zakłada się, że zakres [first, last - 1) już jest stertą). pop_heap Usuwa największy element ze sterty. make_heap Tworzy z podanego zakresu stertę. sort_heap Sortuje stertę (niestabilnie!). Algorytmy numeryczne min max min_element max_element Tu chyba nie trzeba tłumaczyć. *_element wymagają zakresu, a min i max dwóch wartości spełniających "porządkowalne". Wszystkie jako ostatni argument mogą mieć orzecznik. next_permutation prev_permutation Przekręca podany zakres na następną/poprzednią permutację. Zwraca wartość bool oznaczającą, czy operacja została wykonana. accumulate( first, last, init [, bin_op] ) Sumuje elementy z podanego zakresu, ustawiając wartość początkową zmiennej sumującej na `init'; jej wartość jest zwracana. Opcjonalnie bin_op może być użyte zamiast dodawania (pierwszym argumentem jest poprzednia wartość zmiennej sumującej). inner_product( first1, last1, first2, init [, op1, op2] ) Normalnie funkcja ta najpierw wykonuje result = init, a potem dla każdej pary elementów <i, j> z dwóch zakresów wykonuje `result += *i * *j'. W drugiej wersji op1 zastępuje dodawanie, a op2 mnożenie. partial_sum( first, last, result [, op] ) Liczy sumy częściowe wstawiając je do `result' (op może zastąpić dodawanie). Przykładowo, do *result wstawiane jest *first, do *(result + 1) wstawiane jest *first + *(first + 1) i tak dalej. adjacent_difference Liczy różnice kolejnych elementów. Pierwszy element jest przepisywany, a każdy następny jest różnicą elementu na danej pozycji i jego poprzednika. Alokatory Jak wspomniano, ostatnim parametrem wzorca zbiornika może być alokator. Decyduje on o tym, w jaki sposób będzie przydzielana pamięć na rzecz danego zbiornika. Istnieją również odpowiednie funkcje, które oznaczają jawne wywołanie konstruktora lub destruktora. O alokatorach należy myśleć jako o "czarnych skrzynkach": można zdecydować, jakiego alokatora zbiornik używa, ale nie można wpływać na to, JAK zbiornik danego alokatora używa. Rodzaje alokatorów alloc Domyślny alokator. Jest bezpieczny dla wątków i najlepszy dla większości zastosowań. pthread_alloc Alokator specjalizowany dla wątków (dostępny tylko, jeśli twój system udostępnia wątki POSIXa), stosowany dla typów, których pamięć ma nie być dzielona pomiędzy wątkami. Jest nieco szybszy od alloc, szczególnie w systemach wieloprocesorowych, ale dla każdego wątku używa osobnej puli pamięci. Może zatem spowodować fragmentację pamięci, gdyż pamięć zwolniona w jednym wątku nie może być użyta przez drugi. single_client_alloc Szybszy nieco od alloc dla pojedynczego wątku, ale nie jest bezpieczny dla wątków. malloc_alloc Bezpieczny dla wątków, ale powolny. W zasadzie nie nadaje się do konkretnych zastosowań, a jedynie do testowania i debugowania; posiada bowiem dobre narzędzia do sprawdzania zakresów i wykrywania przecieków pamięci (patrz informacje o funkcji malloc). Użytki allocate( size, type_def ) Przydziela pamięć na `size' elementów (nie `size' bajtów!); drugi argument jest nieużywany i służy tylko sprecyzowaniu parametru wzorca (należy podać tam dowolną wartość typu, jaki ma zostać zwrócony). deallocate( ptr ) Zwalnia pamięć trzymaną przez `ptr'. construct( x ) construct( x, value ) Wywołuje konstruktor dla obiektu, którego pamięć wskazana jest przez x. Wartość `value' jest podana przez stałą referencję i musi być typu akceptowalnego przez konstruktor typu obiektu wskazanego przez x. destroy( x ) destroy( first, last ) Wywołuje destruktor dla obiektu wskazanego przez x lub dla zakresu obiektów wskazanych iteratorami first i last. raw_storage_iterator Adaptator iteratora, który przy użyciu wywołuje `construct'. Jeśli `r' jest typu tego adaptatora, adaptującego iterator `i', to *r = v jest tożsame z construct( &*i, v ). uninitialized_fill( first, last, value ) Jak `construct', ale dla zakresu elementów. uninitialized_copy( first, last, result ) Jak `construct', ale symetrycznie pomiędzy zakresami.