Rozmiar a pojemność
2007-12-17 22:09Od kiedy w Bibliotece Standardowej języka C++ istnieje szablon vector, nie trzeba się już martwić kłopotami z dynamiczną alokacją pamięci dla tablic o zmiennym rozmiarze. Szablon ten jest na tyle sprytny, że zapewnia wszystkie zalety zwykłych tablic – łącznie z możliwością uzyskania wskaźnika na ciągły obszar pamięci zawierający elementy. Jednocześnie sam kontroluje rozmiar tablicy oraz wykorzystanie pamięci.
W sensownej implementacji STL jest to osiągnięte poprzez strukturę samorozszerzalnej tablicy. W skrócie można to określić jako alokację większej ilości pamięci niż faktycznie potrzeba – po to, aby dodawanie nowego elementu trwało w przybliżeniu czas stały (w tzw. sensie zamortyzowanym). Całkowita ilość pamięci wykorzystywana aktualnie przez wektor to jego pojemność i jest ona możliwa do pobrania metodą capacity (zwraca ona liczbę elementów, które jeszcze się zmieszczą bez realokacji). Natomiast metoda size zwraca liczbę aktualnie zawartych w tablicy obiektów, czyli jej rozmiar.
Istotne jest, aby te dwie wartości rozróżniać. Kiedy zaś zrównają się ze sobą, następne dodanie elementu wymusi ponowną alokację bloku pamięci dla całej tablicy (zwykle dwukrotnie większego) i przekopiowanie jej zawartości w nowe miejsce.
Taka operacja jest oczywiście kosztowna (liniowa względem rozmiaru tablicy) i dlatego chcielibyśmy, żeby odbywała się jak najrzadziej. Używając metody reserve możemy naraz zaalokować pamięć na tyle elementów, ile będziemy potrzebowali – a więc zwiększyć jej pojemność (lecz nie rozmiar!), jak to widać na poniższym mało inteligentnym przykładzie:
- vector<int> aSquares;
- aSquares.reserve (100); // alokujemy pamięć na sto elementów
- for (int i = 0; i< 100; ++i)
- aSquares.push_back (i * i);[/cpp]
- Warto wiedzieć, że pojemność wektora nigdy się sama z siebie nie zmniejszy. Jeżeli więc kiedyś zawierał on 1000 elementów, a obecnie tylko 10, to i tak w pamięci zajmie on miejsce potrzebne na przechowanie tego tysiąca. Nie ma też żadnej metody do "obcinania" nadmiarowej pojemności. Można jednak posłużyć się pewną sztuczką:
- [cpp]aSquares.resize (10); // usuwamy elementy poza pierwszymi 10-oma
- vector<int>(aSquares).swap (aSquares);
Tworzymy tutaj kopię wektora, używając konstruktora kopiującego. Trik polega na tym, że w czasie tworzenia tej kopii zostanie przydzielona dokładnie taka ilość pamięci, jaka jest potrzebna dla elementów wektora. Potem jeszcze zamieniamy ten chwilowy wektor z oryginalnym… i już :)
-
Firkraag:
December 20th, 2007 o 23:30Korzystając z tego sposobu można również zwolnić całą pamięć zajmowaną przez wektor (albo prawie całą, bo takie słuchy mnie doszły):
std::vector<int>().swap(aSquares);
-
Reg:
December 23rd, 2007 o 14:47Warto dodać, że to się nazywa Swap Trick.
-
yarpen:
December 27th, 2007 o 21:12Jest szansa, ze wejdzie co C++0x jako resize_capacity.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1870.html
Recent posts
