Yocker
  1. Yocker
  3. Qual è il modo più veloce per cambiare una chiave di un elemento all’interno di std :: map
Intereting Posts
Come fare un editor di tabelle JComboBox ha il design di un ordinario JComboBox? Quando passi “questo” come argomento Differenza di rendering alfa tra OpenGL e WebGL Come e perché installo una macchina di compilazione C #? Controlla se esiste una tabella SQL Come posso organizzare un numero arbitrario di ggplot usando grid.arrange? Come disabilitare la casella di controllo di un nodo TreeView di WinForms? java.net.SocketException: Il software ha causato l’interruzione della connessione: recv failed Flag Perl -pe, -pi, -p, -w, -d, -i, -t? In che modo Task diventa un int? Errore durante l’utilizzo tranne in una query matrice a lunghezza fissa typedef Google map guida il codice sorgente della direzione per il loro esempio? Come posso trovare il metodo che ha chiamato il metodo corrente? Come copi il contenuto di un array in un file std :: vector in C ++ senza eseguire il loop?

Qual è il modo più veloce per cambiare una chiave di un elemento all’interno di std :: map

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:

  1. attraversa l’albero tre volte (+ saldo) anziché due (+ saldo)
  2. un’altra copia non necessaria del valore
  3. deallocazione non necessaria e quindi riallocazione di un nodo all’interno dell’albero

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:

  1. trova il nodo nell’albero di cui voglio cambiare la chiave.
  2. staccare se dall’albero (non rilasciare)
  3. riequilibrare
  4. cambia la chiave all’interno del nodo staccato
  5. reinserire il nodo nell’albero
  6. riequilibrare

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.