Alokator w C++
Alokator to jeden z mechanizmów niskiego poziomu w bibliotece STL języka C++, który służy do dynamicznej alokacji oraz zwalniania pamięci w kontenerach.
Biblioteka STL oferuje różnorodne struktury danych, takie jak lista (std::list) czy zbiór (std::set), które nazywane są kontenerami. Ich kluczową cechą jest możliwość zmiany rozmiaru w trakcie działania programu, co wiąże się z dynamiczną alokacją lub dealokacją pamięci. To alokatory są odpowiedzialne za przydzielanie i zwalnianie pamięci w takich okolicznościach. Standardowa biblioteka szablonów dostarcza domyślne alokatory dla kontenerów, jednak programiści mogą również definiować i wprowadzać własne.
Inicjatorem i twórcą alokatorów był Alexander Stepanov, jeden z głównych autorów biblioteki STL. Jego pierwotnym celem było zwiększenie elastyczności biblioteki i odseparowanie jej od konkretnych modeli pamięci, co umożliwiłoby wykorzystanie niestandardowych wskaźników oraz referencji. Jednak podczas dyskusji na temat włączenia biblioteki do standardu języka C++, komitet standaryzacyjny zauważył, że całkowicie abstrakcyjny model pamięci prowadzi do znacznego spadku wydajności. Aby temu przeciwdziałać, zaostrzone zostały wymagania dotyczące alokatorów. W efekcie, stopień konfiguracji jest znacznie mniejszy niż pierwotnie przewidywał Stepanov.
Wiele scenariuszy, w których zdefiniowane przez programistów alokatory okazują się użyteczne, można wskazać. Najczęstszym powodem korzystania z własnych alokatorów jest dążenie do zwiększenia wydajności alokacji przez zastosowanie puli pamięci (ang. memory pool). Na przykład, aplikacje alokujące dużą liczbę małych obiektów mogą zyskać na szybkości działania oraz efektywności zużycia pamięci, stosując własne alokatory. Inny przypadek to zapewnienie ograniczonego dostępu do różnych typów pamięci, jak pamięć współdzielona czy pamięć odzyskana przez mechanizm garbage collection.
Historia
W marcu 1994 roku Alexander Stepanov oraz Meng Lee przedstawili bibliotekę STL komitetowi standaryzacyjnemu C++. Mimo że biblioteka została wstępnie zaakceptowana, wskazano pewne niedociągnięcia. W szczególności, zalecano Stepanovowi maksymalne uniezależnienie kontenerów od modelu pamięci, co doprowadziło do powstania alokatorów. W wyniku tej decyzji zmieniono interfejsy kontenerów, aby akceptowały alokatory zdefiniowane przez użytkowników biblioteki.
Aby dostosować bibliotekę do standardu, Stepanov współpracował z kilkoma członkami komitetu standaryzacyjnego, w tym z Andrew Koeningiem oraz Bjarne Stroustrupem, którzy zauważyli, że własne alokatory mogą być używane do implementacji kontenerów przechowujących obiekty trwałe.
Pierwotnie projekt alokatorów opierał się na cechach języka, które jeszcze nie zostały zatwierdzone przez komitet standaryzacyjny (np. wykorzystanie szablonów jako argumentów dla innych szablonów). Ponieważ wiele z tych cech nie było wtedy implementowanych w dostępnych kompilatorach, Bjarne Stroustrup oraz Andy Koening dokładnie sprawdzali, czy te cechy są poprawnie wykorzystywane.
Wymagania dla alokatorów
Każda klasa spełniająca wymagania dla alokatorów może być używana jako alokator. Klasa A, która ma na celu alokowanie pamięci dla obiektów typu T, musi definiować następujące typy:
- A::pointer – typ wskaźnika do zaalokowanej pamięci
- A::const_pointer – typ stałego wskaźnika do zaalokowanej pamięci
- A::reference – typ referencji do zaalokowanej pamięci
- A::const_reference – typ stałej referencji do zaalokowanej pamięci
- A::value_type – typ obiektu, dla którego alokator alokuje pamięć
- A::size_type – typ mogący pomieścić rozmiar największego możliwego do zaalokowania obszaru pamięci
- A::difference_type – typ reprezentujący różnicę pomiędzy dwoma dowolnymi wskaźnikami w danym modelu pamięci
Dodatkowo, alokator A dla obiektów typu T musi mieć zdefiniowaną metodę A::pointer A::allocate(size_type n, A
Alokator musi również posiadać zdefiniowaną metodę void A::deallocate(A::pointer p, A::size_type n), która przyjmuje jako parametry wskaźnik zwrócony przez wywołanie metody allocate oraz liczbę elementów do dealokowania (bez niszczenia obiektów).
Proces tworzenia i usuwania obiektów jest oddzielony od alokacji i dealokacji pamięci. Alokator powinien definiować metody A::construct oraz A::destroy (obie oznaczone jako przestarzałe w C++17 i usunięte w C++20), które odpowiedzialne są za tworzenie i usuwanie obiektów. Ich implementacja może wyglądać następująco:
Oprócz tego, alokator powinien spełniać poniższe wymagania:
- powinien mieć domyślny konstruktor oraz destruktor, które nie mogą zgłaszać wyjątków,
- powinien mieć dwa konstruktory kopiujące, z których jeden jest szablonem.
