, – 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 . 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 trzyma obiekty w liniowym obszarze pamięci, co umożliwia swobodny dostęp () 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 , 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. jest zbiornikiem dwukierunkowym, co oznacza, że można się po nim poruszać jedynie krokowo w obu kierunkach. Natomiast 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 i . Elementy wewnątrz nich są posortowane i wyszukiwanie elementu jest podobne do wyszukiwania binarnego, które posiada logarytmiczną złożoność czasową. Zbiornik 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 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 i 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.
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 . 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ń.
Zobacz też Active Template Library
Przypisy
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
Kategoria:Biblioteki C++