std :: mappa e comportamento dei dati già inseriti

Question

std::map sposta valori già inseriti quando si inseriscono nuovi dati?

Answer 1

La mappa viene implementata come un albero e quando si inserisce un nuovo elemento, potrebbe essere necessario riequilibrare l'albero.

Questo valore non annulla qualsiasi iteratore o riferimento a elementi nell'albero. Questo bilanciamento viene effettuato tramite la manipolazione di puntatori, quindi non hai nulla di cui preoccuparti; i nodi stessi rimangono fermi.

Il bilanciamento comporta la modifica della struttura dell'albero dicendo ai nodi quali sono i loro figli, genitori e fratelli tramite i puntatori di riassegnazione, ma questo è un dettaglio di implementazione. Logicamente non è cambiato nulla.

Answer 2

Lo standard non richiede specifiche implementazioni del STL, solo il comportamento e le caratteristiche di runtime. Detto questo, una skip list o un albero è un'implementazione molto probabile di std :: map, quindi i collegamenti verranno aggiornati e l'ordine relativo cambierà, ma i dati reali non verranno spostati.

Answer 3

consideri un nodo tipico in lista doppiamente collegata:

template <class T> 
struct Node 
{ 
    Node* mPrevious; 
    Node* mNext; 
    T mValue; 
}; 

Quando si inserisce un nuovo nodo tra due esistenti, tutto ciò che dovete fare è un po 'ricablaggio.

void insert(Node* target, Node* newNode) 
{ 
    target->mPrevious->mNext = newNode; 
    target->mPrevious = newNode; 

    newNode->mPrevious = target->mPrevious; 
    newNode->mNext = target; 
} 

Il comportamento è simile con un std::map (o std::set, std::multimap o std::multiset poiché sono tutti implementati utilizzando la stessa struttura di base in generale).

Significa che qualsiasi iteratore che punta a un elemento esistente rimane anch'esso valido. Insisto sull'elemento esistente bit. L'iteratore restituito da end deve essere ricalcolato dopo l'inserimento o la rimozione ed è preferibile non essere memorizzato nella cache.

Answer 4

Lo standard C++ non determina l'implementazione di std::map solo il suo comportamento e l'efficienza. Le implementazioni sono autorizzate a spostare oggetti in giro; tuttavia, questo potrebbe essere inefficiente.

La maggior parte dei container std::map viene implementata utilizzando una struttura dati ad albero con collegamenti. Quando si inseriscono o riordinano gli elementi, i collegamenti vengono modificati, ma i dati non vengono spostati. Lo spostamento di elementi rallenterebbe il tempo di esecuzione di std::map.