Come ridimensionare un vettore std :: in modo efficiente per la memoria?

Question

Vorrei ridimensionare un std::vector, per ridurne la capacità alle sue dimensioni esatte, in modo che la memoria aggiuntiva venga liberata. Il trucco di serie sembra essere quella descritta here:

template< typename T, class Allocator > 
void shrink_capacity(std::vector<T,Allocator>& v) 
{ 
    std::vector<T,Allocator>(v.begin(),v.end()).swap(v); 
} 

Il punto di shrink-to-fit è quello di salvare la memoria, ma non questo metodo prima creare una copia completa e poi scambia le istanze? Quindi ad un certo punto - quando la copia è costruita - l'utilizzo della memoria è raddoppiato?

In tal caso, esiste un metodo di restringimento per adattarsi alla memoria? (Nel mio caso il vettore è davvero grande e non posso permettermi di avere in memoria sia l'originale che una copia in memoria.)

Answer 1

Bene, se volessi ridimensionare un array, cosa faresti? Devi crearne uno nuovo e copiare tutti i valori - singolarmente o con memcpy o altro. Non è possibile ridimensionare realmente una matrice in C o C++.

std::vector è praticamente garantito l'implementazione di un array per la sua memorizzazione (IIRC, lo standard non garantisce che sia un array, ma un array è l'unica cosa che può soddisfare i vari requisiti dell'API come ad esempio efficiente ogni operazione deve essere, quindi, in effetti, è garantita anche se tale garanzia non è esplicita). Poiché è implementato utilizzando un array e non è possibile ridimensionare gli array senza copiare, non è possibile ridimensionare i vettori senza copiare.

Si potrebbe, in teoria, hanno una funzione shrink_capacity() che nascondeva il fatto che si doveva temporaneamente più o meno il doppio dei suoi requisiti di dimensione, ma dal momento che std::vector non dispone attualmente di una tale funzione, bisogna fare in realtà una copia esplicita . Il trucco swap è solo un bel modo per farlo.

Se in questo caso ti interessa veramente la memoria, ciò che puoi fare è usare puntatori (o puntatori intelligenti) invece di tenere il vettore direttamente. Potrebbe non essere del tutto desiderabile, ma ridurrebbe i tuoi requisiti di memoria.

Answer 2

Se la tua nuova dimensione è metà dell'originale, potresti essere in grado di farla franca con il posizionamento del nuovo vettore (o un array dynaimc diretto se il vettore non può farlo) nella parte finale non utilizzata di quella vecchia . Non sono sicuro se il vettore memorizza informazioni in quell'area di memoria, quindi questo sarebbe molto intrusivo e spaventoso. Ma è un'idea.

Ora che ci penso, un'operazione di tipo memMove() in cui si copiano le informazioni al contrario dall'ultimo indice utilizzato nell'originale sul retro dell'area inutilizzata nell'originale conserverebbe i dati. Se rendi questo un nuovo posizionamento di un array potresti puntarlo ovunque i nuovi dati sarebbero esistiti nel mezzo nell'area di memoria originale. Un movimento sul posto di per sé.