Perché C++ 11/Boost `unordered_map` non rihash durante la cancellazione?

Question

Mi chiedo perché sia ​​C++ 11 che l'hashmap di Boost non si ridimensionino durante la cancellazione degli elementi tramite l'iterazione. Anche se tecnicamente non è una perdita di memoria, penso che potrebbe essere un problema serio nelle applicazioni (è stato un problema nascosto per me, ha avuto difficoltà a rintracciarlo) e potrebbe effettivamente interessare molte applicazioni. Si tratta di un "difetto di progettazione" con il contenitore?

I benchmark e sembra essere che interessano diverse versioni del compilatore (tra cui VS, Clang, GCC)

Il codice per riprodurre il problema è:

std::unordered_map<T1,T2> m; 

for (int i = 0; i < 5000000; i++) 
     m.insert(std::make_pair(i, new data_type)); 


for (map_type::iterator it = m.begin(); it != m.end();) { 
     delete it->second; 
     it = m.erase(it); 
} 

ho creato un file self-contained test che utilizzano un allocatore personalizzato per tenere traccia dell'utilizzo della memoria.

Finché ho capito, il motivo dietro che sta permettendo elementi cancellazione attraverso iterazione e mantenere iteratori validi per non elementi cancellati .. Che sembra un po 'strano requisito in quanto l'inserimento di elementi potrebbe causare un re-hash che invalidare iteratori comunque.

Ma si potrebbe distruggere la mappa direttamente ..

Quale è come mi fisso che (ho avvolto la mappa all'interno di un puntatore intelligente e quando è vuoto ho semplicemente ricreare una nuova mappa vuota, portato per essere più veloce di rilanciare, non so perché.).

In generale, tutte le applicazioni che utilizzano unordered_map come contenitore per gli elementi di cache potrebbe soffrire di tale questione (si consiglia di rimuovere gli elementi dalla cache, ma di solito non si fare un "Reset cache")

Answer 1

Per quanto posso dire che questo comportamento non è tanto il risultato del requisito di non invalidare gli iteratori (std::unordered_map::rehash non li invalida) che il risultato del requisito di complessità per std::unordered_map::erase, che dovrebbe richiedere in media un tempo costante.

Non posso dire, perché è stato specificato come questo, ma vi posso dire, perché è il comportamento predefinito giusta per me:

1. In molte applicazioni, il contenuto del mio la tabella hash è praticamente la costante dopo l'inizializzazione, quindi qui non mi interessa.
2. In caso contrario, almeno il numero medio di elementi rimane più o meno lo stesso (in un ordine di grandezza). Quindi, anche se molti oggetti vengono cancellati a un certo punto nel tempo, i nuovi elementi verranno probabilmente aggiunti poco dopo. In tal caso, lo non ridurrebbe realmente l'ingombro di memoria e l'overhead del ripristino di due volte (una volta dopo la cancellazione e una volta dopo l'aggiunta di nuovi elementi) di solito supererebbe qualsiasi miglioramento delle prestazioni che potrei ottenere attraverso una tabella più compatta.
3. La cancellazione di un numero maggiore di elementi (ad es. Tramite una funzione di filtro) verrebbe notevolmente rallentata da rehash intermedi, se non fosse possibile controllare l'euristica (come è possibile quando si inseriscono elementi modificando max_load_factor).
   Quindi, anche in quei casi in cui è effettivamente utile riprendere, in genere posso prendere una decisione migliore, su quando farlo (ad esempio tramite rehash o copia e swap) rispetto a un'euristica generica in std::unordere_map.

Anche in questo caso, i punti sono vere per i miei casi tipici di utilizzo, non pretendo che siano universalmente vero per il software di altre persone o che erano la motivazione dietro la specificazione del unordered_map

È interessante notare che, VS2015 e libstC++ sembrano attuare rehash(0) diversamente *:

• libstC++ sarà effettivamente ridurre (riallocare) la memoria in cui la tabella è memorizzata
• VS2015 diminuirà la dimensione della tabella (a .k.a. numero di bucket) ma non riallocare il tavolo. Quindi, anche dopo aver rimodellato una mappa di hash vuota, la memoria in eccesso per la tabella non verrà restituita.

Apparentemente, l'unico modo per ridurre al minimo l'ingombro di memoria è copiare e scambiare.

Per quanto riguarda la documentazione, concordo sul fatto che questo dovrebbe essere menzionato esplicitamente da qualche parte, ma d'altra parte è per es. coerente con la documentazione di std::vector::erase(). Inoltre non sono sicuro al 100%, se è davvero impossibile scrivere un'implementazione che rehashes su cancelli almeno a volte, senza violare i requisiti.

---

*) ho dedotto questo dai risultati di bucket_count e getAllocatedBytes() dal vostro allocatore, non dalla realtà guardando il codice sorgente.