Standard Template Library

Standard Template Library, STL – biblioteka C++ zawierająca algorytmy, kontenery, iteratory oraz inne konstrukcje w formie szablonów, gotowe do użycia w programach.

Historia

Osobą w dużej mierze odpowiedzialną za architekturę tej biblioteki jest Alexander Stepanov(inne języki). STL początkowo powstawała jako niezależna biblioteka rozwijana przez firmę Hewlett Packard, później większość przyjętych tam rozwiązań przeszła do biblioteki standardowej C++.

Opis

STL jest to tzw. biblioteka generyczna, oznacza to, że jej komponenty są parametryzowane, niemal każdy z nich jest szablonem. Umożliwia to równie dobrą współpracę z typami wbudowanymi w język, z typami wbudowanymi w bibliotekę, co z typami zdefiniowanymi przez użytkownika, pod warunkiem, że spełniają pewne określone warunki.

Jedną z najważniejszych rzeczy wprowadzonych przez STL, są kontenery, czyli obiekty zbiorcze. Jest ich kilka rodzajów, różnią się konstrukcją i tym samym wydajnością poszczególnych operacji. Np. kontener typu vector trzyma obiekty w liniowym obszarze pamięci, co umożliwia swobodny dostęp (ang. random access) do wszystkich elementów – można ten zbiornik indeksować liczbą całkowitą, podobnie jak robi to się ze zwykłymi tablicami. Niestety, wstawienie nowego elementu gdziekolwiek indziej niż na końcu jest operacją liniowego czasu, gdyż trzeba „odsunąć” elementy, żeby zrobić miejsce na nowy. Z kolei, w kontenerze typu list, wstawianie i usuwanie elementów jest operacją o stałym czasie wykonania, ale nie jest możliwe indeksowanie.

Koncept określa podstawowe warunki, jakie powinien spełniać typ, aby móc być zaliczonym do odpowiedniej kategorii i tym samym obsługiwanym przez odpowiednie elementy biblioteki. Określa też możliwości, jakie udostępnia dany typ. Np. list jest zbiornikiem dwukierunkowym, co oznacza, że można się po nim poruszać jedynie krokowo w obu kierunkach. Natomiast vector jest zbiornikiem swobodnego dostępu i umożliwia poza tym jeszcze indeksowanie elementów wewnątrz zbiornika. Inny model z kolei prezentują sortowane zbiorniki asocjacyjne, jak set i map. Elementy wewnątrz nich są posortowane i wyszukiwanie elementu jest podobne do wyszukiwania binarnego, które posiada logarytmiczną złożoność czasową. Zbiornik set jest zwykłym zbiornikiem asocjacyjnym i zawiera tylko elementy kluczowe (służy tylko do tego, żeby można było w nim łatwo dany element wyszukać), natomiast map jest parowym zbiornikiem asocjacyjnym i zawiera pary klucz-wartość.

Istnieją też koncepty stanowiące wymagania dla typów użytkownika. Np. „przypisywalny” oznacza, że obiekt ma mieć możliwość przypisania do niego wartości, a „domyślnie konstruowalny” oznacza, że typ musi posiadać konstruktor domyślny. Zbiorniki list i vector stawiają takie wymagania, gdyż implementacja zakłada tworzenie takich obiektów „bez podania przyczyny” (lista ma jeden element nieużywany, który stanowi węzeł łączący początek z końcem i jest używany do określania tzw. za-końca).

Jednym z elementów biblioteki są tzw. alokatory^[1].

Iteratory

Po kontenerach można się poruszać za pomocą iteratorów. Są to specjalne obiekty przeznaczone do takich właśnie operacji. Iterator, podobnie jak wszystko w STL-u, musi podpadać pod określony koncept. Koncept iteratora spełnia np. wskaźnik, gdyż można na nim wykonać operacje wymagane dla iteratora; co więcej, jest to iterator swobodnego dostępu, gdyż udostępnia zarówno operatory ++ i --, jak też operację awansu (+= i -=) i dystansu (-).

Algorytmy

Oprócz tego w STL definiuje się też algorytmy, czyli odpowiednie wzorce funkcji, które mają wykonać pewne abstrakcyjne zadania na określonym kontenerze. Przykładowym algorytmem jest „for_each”, który ma wywołać podany funktor na określonym zakresie elementów. Innymi przykładami algorytmów są „reverse”, który odwraca kolejność elementów w zbiorniku, „find”, który wyszukuje określoną wartość w zbiorniku, czy „find_if”, który wyszukuje element spełniający warunek określony podanym funktorem.

W STL każdy algorytm może pracować na każdym zbiorniku specjalizowanym każdym możliwym typem. Choć nie każda kombinacja algorytmu i zbiornika ma sens, np. nie ma sensu wywoływać algorytmu „sort” na zbiorniku takim jak set. Taki sposób zaprogramowania tej biblioteki zapewnił jej szerokie zastosowanie oraz generyczność, czyli możliwość adaptowania się do elementów nieznanych w momencie jej opracowywania.

Ponieważ szablony C++ są bardzo efektywne, STL jest o wiele popularniejszy niż podobne biblioteki pisane dla C, w przypadku których wydajność była istotnie niższa od ręcznie programowanych rozwiązań.