Sono membro di un sito web di codifica online e oggi, quando ho presentato una soluzione in C ++, ho visto che c'erano molte più risposte in C ++ che richiedevano molto meno tempo. Le soluzioni erano aperte, quindi ho proseguito con alcune di esse e ho trovato tutte utilizzando la struttura dati della mappa. Non riuscivo a capire dove esattamente ci vuole un vantaggio. Ho fatto qualche ricerca su google, ma non è stato convincente. Per favore aiuto.
map è un contenitore di tipo di dizionario abbastanza completo che offre numerosi vantaggi su < a href="http://www.sgi.com/tech/stl/List.html"> std::list (elenchi collegati) e std::vector (array). Sebbene non sia strettamente specificato, i vincoli prestazionali richiesti su una mappa impongono di implementarlo quasi come una sorta di albero binario autobilanciato. Quindi, se ti è stato utile ripensarci in questi termini, considera i vantaggi degli alberi binari su normali array / liste collegate se ne hai già appreso in passato.
Tempo di ricerca
Se sai che le tue chiavi (quello che stai usando per cercare i tuoi dati) rientrano in un intervallo intero molto ristretto, allora un array (o preferibilmente un vettore) è l'ideale se tutto quello che ti interessa è la ricerca. Puoi cercare con una chiave in tempo costante senza problemi.
Si rompe se lo spazio della chiave diventa troppo grande o non è un numero intero. Ovviamente non puoi avere un array che abbia un elemento memorizzato solo nello 0th slot e nel 2 ^ 32 spot senza sprecare tonnellate di memoria. Una mappa ti consente di mantenere prestazioni di ricerca ragionevoli ( O(log(n)) ), ma occupa solo 2 punti per archiviare la memoria. Una mappa consente anche di cercare su qualsiasi tipo che definisce < operator o specifica sulla mappa tramite un argomento modello come confrontare le chiavi. Così puoi avere una ricerca ragionevole sulle mappe di stringhe - > un altro valore Ad esempio, una mappa ti consente di fare map["Bob"] = 5; , ad esempio.
ordinato
mappa memorizza gli articoli in ordine di chiave. Quindi puoi scorrere tutti gli elementi in una mappa, dall'inizio alla fine, nell'ordine delle chiavi ordinate. Ovviamente puoi farlo con un array / vettore, tuttavia come detto in precedenza, una mappa ti consente di avere qualsiasi tipo di chiave arbitraria con qualsiasi ordine arbitrario definito.
Inserimento
Per inserire nel mezzo di un array / vettore devi spostare tutti gli elementi a sinistra. Per un array dinamico e un vettore devi ridimensionare il vettore, il che ti farà copiare l'intero array nella nuova memoria.
Una mappa ha un tempo di inserimento ragionevole (O(log(n))) .
Alternative w / differentoffoff
multimap è come una mappa ma consente alle chiavi di non essere uniche unordered_map è una mappa che non memorizza gli articoli in ordine, ma può fornire migliori prestazioni di ricerca se viene fornita una buona funzione di hash Per la maggior parte degli scopi le classi della libreria standard rischiano di sovraperformare qualsiasi struttura / contenitore / algoritmo di dati in modo rapido che si scriverà. Questo presuppone che tu scelga l'astrazione giusta (std :: vector e std :: list hanno diversi compromessi, per esempio). Un sacco di tempo e sforzi da parte di molte persone intelligenti hanno contribuito a rendere quelle librerie sia generiche che il più veloci possibile data la natura generica delle librerie.
Se hai un caso molto specifico che conosci molto bene e conosci anche le tue classi di librerie standard molto bene, potresti essere in grado di scrivere una classe personalizzata che superi il migliore equivalente standard per il tuo scopo specifico, limitato, ma una cosa del genere dovrebbe essere fatta solo quando la profilazione della tua applicazione dimostra la necessità di tale ottimizzazione.
Leggi altre domande sui tag c++ c data-structures map