Yocker
  1. Yocker
  3. Qual è il modo più veloce per cambiare una chiave di un elemento all’interno di std :: map
Intereting Posts
Le intestazioni di condivisione di risorse incrociate possono autorizzare l’accesso IFRAME X-Domain? Come applicare le wavelet Gabor a un’immagine? Socket.io con nginx Kit Sprite e colorWithPatternImage come ottenere l’ultimo carattere di una stringa? salva l’output html della pagina dopo l’esecuzione del javascript della pagina Ottenere gli ultimi n elementi di un vettore. C’è un modo migliore rispetto all’utilizzo della funzione length ()? Mercuriale: rami nominati rispetto a più archivi Formattazione delle date MM / GG / AAAA nella casella di testo in VBA Eccezione non gestita di riferimento metodo Java 8 Come aggiungere il riconoscimento vocale al progetto Unity? + – qual è il punto? Come aggirare il limite della class case di Scala di 22 campi? three.js impostare e leggere il vettore di immagine della fotocamera Organizzazione, dove dovrei inserire le domande più comuni quando si utilizza Entity Framework Code First?

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.