Unordered_map copia/rilascia oggetti contenuti se c'è un'operazione di inserimento/rimozione/rimessa laterale?

Question

Voglio memorizzare piccoli oggetti in unordered_map, mi chiedo solo se può copiare/rilasciare oggetti contenuti se c'è qualche operazione di inserimento/rimozione/rimessa laterale? Penso che unordered_map usi la lista dei collegamenti per memorizzare coppie chiave/valore, non dovrebbe avere bisogno di copiare/rilasciare oggetti come il vettore per la riallocazione della memoria.

Answer 1

C++ 11 norma: § 23.2.5/8

Gli elementi di un contenitore associativo non ordinata sono organizzati in segmenti. Le chiavi con lo stesso codice hash appaiono nello stesso bucket. Il numero di bucket viene automaticamente aumentato quando gli elementi vengono aggiunti a un contenitore associativo non ordinato, in modo che il numero medio di elementi per bucket venga mantenuto al di sotto di un limite. Il rimbalzo invalida gli iteratori, modifica l'ordine tra gli elementi e le modifiche in cui gli elementi vengono visualizzati, ma non invalida i puntatori o riferimenti agli elementi. Per unordered_multiset e unordered_multimap, il rehashing mantiene l'ordine relativo di elementi equivalenti.

Insomma per unordered_map,
In caso di inserimento/cancellazione operazioni,

• Tutti iteratori vengono invalidate quando rimasticare si verifica, ma i riferimenti rimangono inalterati.

Answer 2

Ho fatto un test utilizzando questo codice:

#include <iostream> 
#include <unordered_set> 
#include <unordered_map> 

struct A 
{ 
    static int copies; 

    A(int a): a(a){} 
    A(A const& pA){std::cout << "A copy" << std::endl; ++copies; a = pA.a;} 
    A& operator=(A const& pA){std::cout << "= operator" << std::endl; a = pA.a; ++copies; return *this;} 

    int a; 



    bool operator==(A const& pA)const{return pA.a == a;} 
    bool operator!=(A const& pA)const{return pA.a != a;} 
    bool operator>(A const& pA)const{return pA.a > a;} 
    bool operator<(A const& pA)const{return pA.a < a;} 
}; 
int A::copies = 0; 


namespace std{ 
template<> 
class hash<A> 
{ 
public: 
    size_t operator()(A const& pA) const 
    { 
     return pA.a; 
    } 
}; 
} 


int main() 
{ 

    std::unordered_map<A, A> map; 
    std::unordered_set<A> set; 

    for(int i=0; i<1000000; ++i) 
    { 
     set.insert(A(i)); 
     map.insert(std::pair<A, A>(A(i), A(i))); 
    } 
    std::cout << A::copies << std::endl; 

    return 0; 
} 

Il costruttore di copie per set è stato chiamato 1 milione di volte - che significa che ogni oggetto è stato copiato sola volta (nel set). Per la copiatrice della mappa è stato chiamato 4 mln volte - 2 volte oggetto domestico (nota che la mappa ha bisogno di 2 oggetti A per ogni inserto). Inoltre quando eseguo il test in cui inserisco solo un oggetto (per i < 1), quindi copia construcotr è stato chiamato una volta per set e 4 volte per map.

Conclusioni: Sembra che il reshash e l'inserimento di oggetti non reallocino oggetti in unordered_set né unordered_map. Penso che sia vero perché non credo che non ci sia stato nemmeno un rifacimento per così tanti inserimenti. Il costruttore della copia è stato chiamato una volta per set (per copiare l'oggetto in un nodo impostato) - ovvio. Perché allora la copia di construcotr è stata chiamata 4 volte per ogni chiamata di inserimento mappa? La chiave della mappa è un oggetto A e anche il valore è un oggetto A. Gli oggetti sono stati creati e copiati in std :: pair (prime 2 copie) e poi la coppia è stata copiata nella mappa (2 altre copie) - Penso che sia come funziona.

Quindi sembra che gli oggetti nella mappa non ordinata e nel set non vengano mai riallocati in modo che puntatori e riferimenti rimangano validi ma probabilmente gli iteratori no - @Alok Salva risposta. Ho fatto questo test perché mi stavo chiedendo se le chiavi si riallocano quando si verifica rehash. @Alok Save ha scritto sugli elementi ma non sulle chiavi (o non ho capito correttamente la sua risposta e l'elemento significa valore e chiave).

Domanda: Lo standard dice qualcosa sulle chiavi (se non sono considerate come elementi)?

PS: Per test ho usato g ++ 4.8.