Corretta gestione della memoria vettoriale

Question

Sto facendo un gioco e ho un vettore di proiettili che volano intorno. Quando il proiettile è finito, faccio bullets.erase (bullets.begin() + i); Quindi il proiettile scompare. Tuttavia non ha alcuna intenzione di ottenere la verga della memoria. Se creo 5000 proiettili, ne creo altri 5.000 dopo che questi muoiono, la memoria rimane la stessa, ma se creo altri 5.000 mentre quelli 5000 stanno volando, assegnerà nuovo spazio. Cosa devo fare per liberare effettivamente questa memoria?

Grazie

Answer 1

La classe std::vector gestisce automaticamente la sua memoria interna. Si espanderà per contenere tanti oggetti quanti ne mettete dentro, ma in generale non si restringerà da solo quando rimuovete gli oggetti (anche se, naturalmente, rilascerà la memoria quando distruggerà).

Il std::vector ha due concetti rilevanti di "dimensione". La prima è la dimensione "riservata", ovvero la quantità di memoria allocata dal sistema da utilizzare per la memorizzazione di elementi vettoriali. Il secondo è la dimensione "usata", ovvero quanti elementi sono logicamente nel vettore. Chiaramente, la dimensione riservata deve essere grande almeno quanto la dimensione usata. Puoi scoprire la dimensione usata con il metodo size() (che sono sicuro che tu già conosci), e puoi scoprire la dimensione riservata usando il metodo capacity().

In genere, quando le dimensioni utilizzate e quelle riservate sono le stesse e si tenta di inserire un nuovo elemento, il vettore allocherà un nuovo buffer interno del doppio della dimensione riservata precedente e copierà tutti gli elementi esistenti in tale buffer . Questo è trasparente per te, tranne per il fatto che invaliderà qualsiasi iteratore che hai in mano. Come ho notato prima, AFAIK, la maggior parte delle implementazioni STL non ridurrà mai le dimensioni riservate come risposta a una cancellazione.

Purtroppo, mentre è possibile forzare un vettore di aumento sua dimensione riservata utilizzando il metodo reserve(), questo non funziona per diminuire la capacità riservata. Per quanto posso dire, la soluzione migliore per effettuare una riduzione della capacità è quella di effettuare le seguenti operazioni:

std::vector<Bullet>(myVector).swap(myVector); 

Che cosa questo farà fare è creare un vettore temporanea che è una copia del vettore originale (ma con il capacità minima necessaria), quindi scambiare i buffer interni dei due vettori.Questo farà sì che il tuo vettore originale abbia gli stessi dati ma una dimensione riservata potenzialmente più piccola.

Ora, poiché la creazione di tale copia temporanea è un'operazione relativamente costosa (ovvero richiede molto più tempo del processore rispetto alle normali letture/inserzioni/eliminazioni), non si desidera eseguirla ogni volta che si cancella un elemento. Per lo stesso motivo, questo è il motivo per cui il vettore raddoppia le dimensioni riservate invece di aumentarle di 1 quando è necessario superare la dimensione esistente. Pertanto, quello che vorrei raccomandare è che dopo aver cancellato un numero relativamente grande di elementi, e sai che non ne aggiungerai altri molto presto, esegui il "trucco" di scambio sopra per ridurre la capacità.

Infine, si può anche prendere in considerazione l'utilizzo di qualcosa di diverso da un std::vector per questo. Cancellare elementi dal centro di un vettore, che sembra che si stiano facendo di frequente, è un'operazione lenta rispetto a molti altri tipi di strutture di dati (poiché il vettore deve copiare tutti gli elementi successivi di uno slot per riempire il buco) . Quale struttura dati è la migliore per i tuoi scopi dipende da che cosa stai facendo con i dati.

Answer 2

è così che normalmente modello di allocazione della memoria del vettore si comporta di fornire una costante operazione di tempo push_back ammortizzato, In sostanza si cerca di indovinare che si potrebbe desiderare per riempire la parte cancellata con un nuovo elemento in modo che non liberare la memoria. In questo modo è possibile evitare allocazioni e deallocazioni costanti. Per aggirare questo, è possibile utilizzare il trucco swap per liberare la memoria vettoriale non utilizzata. Devi scambiare il tuo vettore vuoto con un vettore temporaneo senza nome in modo che quando il vettore temporaneo esce dall'ambito libera la memoria nel suo distruttore, Qualcosa come: vector<int>(c).swap(c)

Answer 3

Primo, std: il metodo di cancellazione vettoriale non è molto efficace, deve spostare tutti gli oggetti dopo quello cancellato. Se l'ordine degli elementi vettoriali (punti elenco) non ha importanza, lo scambio del punto elenco eliminato con l'ultimo punto e l'eliminazione dell'ultimo punto elenco saranno più rapidi (in modo da ottenere una complessità costante anziché una complessità lineare).

In secondo luogo, qual è il vero problema: dopo aver eliminato i 10.000 articoli, la memoria non è stata liberata? Stiamo parlando della memoria libera riportata dal sistema operativo o dello spazio libero sull'heap? È possibile (e molto probabile) che qualche altro oggetto sia stato assegnato dopo la posizione dei dati del vettore, quindi non è possibile liberare semplicemente questa memoria nel sistema operativo; ma può essere riutilizzato per altri oggetti appena creati.

Answer 4

vi consiglio di dare un'occhiata a questi due idiomi e scegliere quello che si adatta di più:
Shrink to fit
Clear & minimize

Answer 5

Non può sbarazzarsi della memoria.
Ma la prossima volta che devi aggiungere un bullit non è necessario ridistribuire più spazio.
Non riutilizza la memoria da cui proviene il proiettile cancellato.

Nota:
Se si esegue la cancellazione dal centro di un contenitore relativamente spesso, il vettore potrebbe non essere il contenitore corretto. Questo è perché se rimuovi l'elemento n allora tutti gli elementi da [n + 1, fine) devono essere spostati verso il basso di uno spazio in memoria.

Answer 6

Quando il proiettile è finito, faccio bullets.erase (bullets.begin() + i);

Non farlo. Se più proiettili sono finiti per fotogramma, ottieni prestazioni orribili, perché i proiettili che non sono finiti verranno copiati più e più volte, cosa che in realtà non è necessaria. Ecco cosa farei:

#include <algorithm> 
#include <functional> 
#include <vector> 

class Bullet 
{ 
    // ... 
public: 
    bool is_finished() const; 
}; 

int main() 
{ 
    std::vector<Bullet> bullets; 
    // ... 
    bullets.erase(
     std::remove_if(
      bullets.begin(), 
      bullets.end(), 
      std::mem_fun_ref(&Bullet::is_finished) 
     ), 
     bullets.end() 
    ); 
} 

Questo approccio sposta solo un proiettile attivo al massimo una volta.