Alokator
Alokator – jeden z niskopoziomowych mechanizmów biblioteki STL języka C++, wykorzystywany w kontenerach do dynamicznej alokacji oraz zwalniania pamięci.
Biblioteka STL definiuje wiele różnych struktur danych, takich jak lista (std::list) czy zbiór (std::set), powszechnie nazywanych kontenerami. Ich podstawową własnością jest możliwość zmiany rozmiaru w czasie działania programu, podczas której może dojść do dynamicznej alokacji lub dealokacji pamięci. Za przydzielanie i zwalnianie pamięci w takich sytuacjach odpowiedzialne są alokatory. Standardowa biblioteka szablonów definiuje alokatory wykorzystywane domyślnie przez kontenery. Programista może jednak definiować i wstrzykiwać własne[1].
Pomysłodawcą i twórcą alokatorów był Alexander Stepanov, jeden z głównych autorów biblioteki STL. Początkowo ich celem było zwiększenie elastyczności biblioteki oraz uniezależnienie jej od konkretnych modeli pamięci, co pozwoliłoby na wykorzystanie w niej niestandardowych wskaźników oraz referencji. Jednak podczas dyskusji nad włączeniem biblioteki do standardu języka C++, komitet standaryzacyjny zauważył, że w pełni abstrakcyjny model pamięci wiąże się ze znacznym zmniejszeniem wydajności. Aby temu zapobiec, zwiększono wymagania stawiane alokatorom. W efekcie poziom konfiguracji jest dużo mniejszy niż początkowo zakładał Stepanov.
Istnieje wiele różnych scenariuszy w których zdefiniowane przez programistę alokatory bywają przydatne. Jednym z najczęstszych powodów wykorzystywania własnych alokatorów jest próba zwiększenia wydajności alokacji poprzez wykorzystanie puli pamięci (ang. memory pool). Przykładowo programy, które alokują dużą liczbę małych obiektów mogą zyskać wykorzystując własne alokatory, zarówno jeżeli chodzi o szybkość działania jak i całościowe zużycie pamięci. Inną sytuacją jest zapewnienie ograniczenia dostępu do różnych typów pamięci, na przykład pamięci współdzielonej lub odzyskanej przez mechanizm garbage collection.
Historia edytuj
W marcu 1994 roku Aleksander Stepanov oraz Meng Lee zaprezentowali bibliotekę STL komitetowi standaryzacyjnemu C++[2]. Biblioteka została wstępnie zatwierdzona, pomimo tego, że wskazano kilka niedociągnięć. W szczególności nakazano Stepanovowi jak największe uniezależnienie kontenerów od modelu pamięci, co doprowadziło do stworzenia alokatorów. Konsekwencją tej decyzji było wymuszenie przepisania interfejsów kontenerów w taki sposób, aby akceptowały alokatory napisane przez klientów biblioteki.
W celu zaadaptowania biblioteki do standardu Stepanov współpracował z kilkoma członkami komitetu standaryzacyjnego, włączając w to Adrew Koeninga oraz Bjarne Stroustrupa, którzy odkryli, że własne alokatory mogą zostać wykorzystane do zaimplementowania kontenerów przechowujących obiekty trwałe[3].
Pierwotnie, projekt stworzenia alokatorów opierał się na cechach języka, które nie zostały jeszcze zaakceptowane przez komitet standaryzacyjny (np. korzystanie z szablonów jako argumentów dla innych szablonów). Ponieważ większość z tych cech nie była zaimplementowana w ówczesnych kompilatorach, Bjarne Stroustroup oraz Andy Koening dokładnie sprawdzali, czy cechy te są wykorzystywane poprawnie[3].
Wymagania dla alokatorów edytuj
Każda klasa, która spełnia wymagania stawiane alokatorom może zostać wykorzystana jako alokator. W szczególności, klasa A, której zadaniem jest alokowanie pamięci dla obiektów typu T musi definiować następujące typy[4]:
A::pointer- typ wskaźnika do zaalokowanego obszaru pamięciA::const_pointer- typ stałego wskaźnika do zaalokowanego obszaru pamięciA::reference- typ referencji do zaalokowanego obszaru pamięciA::const_reference- typ stałej referencji do zaalokowanego obszaru pamięciA::value_type- typ obiektu dla którego alokator alokuje pamięćA::size_type- typ mogący przechować rozmiar największego możliwego do zaalokowania obszaru pamięciA::difference_type- typ mogący reprezentować różnicę pomiędzy dwoma dowolnymi wskaźnikami w danym modelu pamięci
Dodatkowo alokator A dla obiektów typu T musi posiadać zdefiniowaną metodę A::pointer A::allocate(size_type n, A<void>::const_pointer hint = 0). Metoda ta zwraca wskaźnik na pierwszy element zaalokowanej tablicy, która jest w stanie pomieścić co najmniej <n> obiektów typu T. Metoda ta alokuje tylko pamięć, nie jest odpowiedzialna za konstrukcje obiektów danego typu. Opcjonalny argument w postaci wskaźnika na pamięć już zaalokowaną przez alokator A może zostać użyty, aby wskazać w jakim obszarze powinna być zrobiona nowa alokacja.
Alokator musi także posiadać zdefiniowaną metodę void A::deallocate(A::pointer p, A::size_type n), która jako parametry przyjmuje wskaźnik zwrócony przez wywołanie metody allocate oraz ilość elementów dla których pamięć ma być zdealokowana (bez niszczenia obiektów).
Tworzenie i usuwanie obiektu jest oddzielone od procesu alokacji i dealokacji pamięci. Alokator musi definiować metody A::construct oraz A::destroy (obie oznaczone jako przestarzałe w C++17, i usunięte w C++20[5]), które będą odpowiedzialne za tworzenie i usuwanie obiektu. Ich implementacja może wyglądać następująco:
template <typename T>
void A::construct(A::pointer p, A::const_reference t)
{
new ((void*) p) T(t);
}
template <typename T>
void A::destroy(A::pointer p)
{
((T*)p)->~T();
}
Poza tym alokatorem powinien spełniać poniższe wymagania[4]:
- powinna posiadać domyślny konstruktor oraz destruktor, które nie mogą wyrzucać wyjątków,
- powinna posiadać dwa konstruktory kopiujące, z których jeden jest szablonem.
Przypisy edytuj
- ↑ Allocators. [dostęp 2012-06-11]. [zarchiwizowane z tego adresu (2012-07-01)]. (ang.).
- ↑ Prezentacja biblioteki STL. [dostęp 2009-06-02].
- ↑ a b Wywiad ze Stepanovem o kontenerach. [dostęp 2009-06-03]. [zarchiwizowane z tego adresu (2012-02-01)]. (ang.).
- ↑ a b Allocators (STL). [dostęp 2012-06-11]. [zarchiwizowane z tego adresu (2012-02-13)]. (ang.).
- ↑ std::allocator. cppreference.com. [dostęp 2021-07-13].