std :: queue należy skurczyć się dopasować?

Question

Rozważam użycie std::queue (z std::deque) dla struktury FIFO.

W strukturze danych kolejek dane tylko przesuwały się z tyłu i były widoczne z przodu. Dlatego pamięć z przodu po naciśnięciu elementu nigdy nie będzie używana.

Pamiętam, że std :: vector nie zwalnia pamięci, dopóki nie zostanie jawnie wywołana metoda shrink_to_fit. Co z std::deque?

Czy powinienem rozważyć zwolnienie pamięci z przodu, która nigdy nie będzie ponownie używana?

Answer 1

Nie potrzebujesz dokładnie shrink_to_fit dla kolejki, jeśli jest używana normalnie. std::vector 's shrink_to_fit jest przeznaczony do sytuacji, w których zawartość wektora zmniejszyła się o ogromną ilość, tak, że faktycznie ma korzyści, aby wywołać (raczej kosztowne) realokacja w celu uwolnienia tej ogromnej ilości pamięci. Generalnie nie jest potrzebna, jeśli wektor ma krótki czas życia lub jeśli jego rozmiar nie zmienia się zbytnio.

Po tym, std::deque to inny rodzaj bestii. To zwykle składa się z fragmentów pamięci o ustalonym rozmiarze. Jeśli usuniesz wiele elementów z deque, porcje, które nie zawierają już żadnych elementów, mogą zostać zwolnione. Tak więc największe obciążenie pamięci, które możesz mieć w każdej chwili, jest nieco poniżej dwukrotności wielkości porcji, np. jeśli kolejka zawiera tylko dwa elementy, jeden na końcu kawałka, drugi na początku następnego fragmentu. Dlatego też, std::deque::shrink_to_fit może przesuwać tylko elementy deque w sposób, który uwalnia dokładnie jedną porcję, co nie jest dużym zyskiem (iirc typowa implementacja ma wielkość kawałka o wartości kilku kilobajtów).

Są to bardzo ogólne stwierdzenia, które mogą nie mieć zastosowania w krytycznych sytuacjach pamięci. Jednak jako pojemniki standardowe, żaden wektor nie jest deque'em jawnie zaprojektowany do stosowania w takich ekstremalnych sytuacjach. Jeśli ślad pamięci jest problemem w części programu, w której używasz kolejki, możesz użyć jeszcze jednej struktury danych.

Answer 2

Charakterystyka alokacji pamięci dla std::deque to zdefiniowana implementacja. Standard nie wymaga szczególnego wymagania, jeśli pamięć jest alokowana lub zwalniana aż do zakresu deque. Wymagania asymptotyczne dotyczące implementacji wstawiania, usuwania i dostępu wydajności w niektórych liniach. Ale w tym może być wiele różnic.

Ogólnie rzecz biorąc, jeśli wystrzelisz wystarczająco dużo rzeczy z przodu deque, nastąpi deallokacja pamięci.