Capisco le ragioni per cui non si può semplicemente fare questo (riequilibrare e cose):
iterator i = m.find(33); if (i != m.end()) i->first = 22;
Ma finora l’unico modo (lo so) per cambiare la chiave è quello di rimuovere il nodo dall’albero e poi inserire il valore con una chiave diversa:
iterator i = m.find(33); if (i != m.end()) { value = i->second; m.erase(i); m[22] = value; }
Questo mi sembra piuttosto inefficiente per più motivi:
Trovo che l’allocazione e la deallocazione siano le peggiori da quelle tre. Mi manca qualcosa o c’è un modo più efficiente per farlo?
AGGIORNAMENTO: Penso che, in teoria, dovrebbe essere ansible, quindi non credo che cambiare per una diversa struttura dei dati sia giustificato. Ecco lo pseudo algoritmo che ho in mente:
In C ++ 17, la nuova funzione map::extract
ti consente di cambiare la chiave.
Esempio:
std::map m{ {10, "potato"}, {1, "banana"} }; auto nodeHandler = m.extract(10); nodeHandler.key() = 2; m.insert(std::move(nodeHandler)); // { { 1, "banana" }, { 2, "potato" } }
Ho proposto il tuo algoritmo per i contenitori associativi circa 18 mesi fa qui:
http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#839
Cerca il commento contrassegnato: [2009-09-19 Howard aggiunge:].
All’epoca eravamo troppo vicini a FDIS per considerare questo cambiamento. Comunque penso che sia molto utile (e tu apparentemente sei d’accordo), e mi piacerebbe farlo entrare in TR2. Forse potresti aiutare trovando e notificando al tuo rappresentante nazionale C ++ che questa è una funzionalità che vorresti vedere.
Aggiornare
Non è sicuro, ma penso che ci siano buone probabilità di vedere questa funzionalità in C ++ 17! 🙂
Puoi omettere la copia di valore ;
const int oldKey = 33; const int newKey = 22; const iterator it = m.find(oldKey); if (it != m.end()) { // Swap value from oldKey to newKey, note that a default constructed value // is created by operator[] if 'm' does not contain newKey. std::swap(m[newKey], it->second); // Erase old key-value from map m.erase(it); }
Non puoi.
Come hai notato, non è ansible. Una mappa è organizzata in modo da poter modificare il valore associato a una chiave in modo efficiente, ma non viceversa.
Dai un’occhiata a Boost.MultiIndex, e in particolare alle sezioni del contenitore standard di emulazione . I contenitori Boost.MultiIndex presentano un aggiornamento efficiente.
Le chiavi nelle mappe STL devono essere immutabili.
Sembra che forse una struttura dati o strutture diverse potrebbero avere più senso se si ha una tale volatilità sul lato chiave dei propri abbinamenti.
Dovresti lasciare l’allocazione all’allocatore. 🙂
Come dici tu, quando la chiave cambia ci potrebbe essere molto ribilanciamento. È così che funziona un albero. Forse 22 è il primo nodo nell’albero e 33 l’ultimo? Cosa sappiamo?
Se evitare le allocazioni è importante, forse dovresti provare un vettore o una deque? Si allocano in blocchi più grandi, quindi risparmiano sul numero di chiamate all’allocatore, ma potenzialmente sprecano memoria. Tutti i contenitori hanno i loro compromessi e spetta a te decidere quale ha il vantaggio principale di cui hai bisogno in ogni caso (supponendo che sia importante).
Per i più avventurosi:
Se sai per certo che il cambio della chiave non influisce sull’ordine e non commetti mai, mai un errore, un piccolo const_cast ti permetterebbe comunque di cambiare la chiave.