Standard Template Library
Z Wikipedii
Standard Template Library, STL (ang. standardowa biblioteka szablonów) – biblioteka C++ zawierająca algorytmy, pojemniki, iteratory oraz inne konstrukcje w formie szablonów, gotowe do użycia w programach.
Spis treści |
[edytuj] Historia
Osobą w dużej mierze odpowiedzialną za architekturę tej biblioteki jest Alexander Stepanov. 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++.
[edytuj] Opis
STL jest to tzw. biblioteka generyczna, co oznacza, że jej składniki współpracują równie dobrze 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ą pojemniki, czyli obiekty zbiorcze. Jest ich kilka rodzajów, różnią się konstrukcją i tym samym wydajnością poszczególnych operacji. Np. pojemnik 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 pojemniku 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).
[edytuj] Iteratory
Po zbiornikach 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 (-).
[edytuj] Algorytmy
Oprócz tego w STL-u definiuje się też algorytmy, czyli odpowiednie wzorce funkcji, które mają wykonać pewne abstrakcyjne zadania na określonym pojemniku. 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-u każdy algorytm może pracować na każdym zbiorniku specjalizowanym każdym możliwym typem. Choć oczywiście 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ń.
[edytuj] Linki zewnętrzne
- Strona zawierająca dokumentację STL
- Kolekcja linków do stron poświęconych STL
- Standard Template Library Programmer's Guide - wszechstronny opis STL oparty na oryginalnej dokumentacji firmy Hewlett-Packard
- Boost C++ Libraries - duża kolekcja wydajnych, elastycznych i przenośnych bibliotek generycznych; wiele z nich ma zostać włączonych w skład STL w ramach kolejej aktualizacji standardu języka C++ (tzw. C++0x).
