map și unordered_map: ordine și costul căutării
Alege un dicționar după operațiile necesare. Separă ordinea cheilor de căutarea prin hash și diferențiază costul mediu de garanția în cel mai rău caz.
În acest material
Un dicționar asociază fiecărei chei o valoare. În C++, map și unordered_map oferă această idee, dar organizează cheile diferit. Alegerea nu trebuie redusă la afirmația că unul este întotdeauna mai rapid decât celălalt.
Ordinea este parte din contract
std::map păstrează cheile într-o ordine definită de comparator. Parcurgerea obișnuită vizitează elementele în acea ordine. Operații precum căutarea unei margini după o cheie se potrivesc acestei organizări.
std::unordered_map organizează cheile printr-o funcție hash, care calculează o valoare folosită pentru distribuirea lor în grupuri interne. Ordinea parcurgerii nu este ordinea numerică sau alfabetică și nu trebuie folosită ca o astfel de garanție.
Mediu și cel mai rău caz
Pentru map, operațiile obișnuite de căutare, inserare și ștergere după cheie au un număr logaritmic de pași de structură în numărul elementelor. Costul comparării cheilor contează separat, mai ales când cheile sunt texte lungi.
Pentru unordered_map, căutarea are în mod obișnuit cost mediu constant în numărul elementelor, dar cel mai rău caz poate fi liniar. Coliziunile apar când chei diferite ajung în același grup hash. Nu transforma garanția medie într-o promisiune pentru orice intrare.
Map parcurge cheile în ordinea comparatorului. Unordered_map nu garantează ordinea numerică; căutarea are cost mediu constant, dar poate fi liniară în cel mai rău caz.Mărește schema ↗
Citirea poate modifica dicționarul
Operatorul de indexare cu o cheie absentă poate introduce o intrare nouă cu valoare inițializată implicit. Pentru un dicționar de frecvențe întregi, aceasta poate fi exact intenția când incrementezi frecvența.
Dacă vrei doar să verifici existența fără modificare, folosește o operație de căutare potrivită, precum find, și compară rezultatul cu end. Altfel, simpla verificare poate mări numărul cheilor și poate schimba rezultatele unor parcurgeri ulterioare.
Alege după cerința concretă
Dacă trebuie să afișezi cheile sortate, map oferă direct această ordine. Dacă ordinea nu contează și urmărești frecvențe, unordered_map poate fi potrivit, dar memoria, distribuția cheilor și limitele problemei trebuie evaluate.
Pentru un domeniu mic de valori întregi, un tablou de frecvență poate fi mai simplu decât ambele. Nu introduce un dicționar doar fiindcă este disponibil în bibliotecă. Reprezentarea bună folosește informațiile despre date și operații.
Continuă cu frecvențele, structurile STL și complexitatea.
Întrebări frecvente
Care este diferența dintre map și unordered_map?
map păstrează cheile ordonate după comparator. unordered_map organizează cheile prin dispersie, fără o ordine de parcurgere sortată garantată. Alegerea depinde de operațiile necesare.
Are unordered_map mereu căutare O(1)?
Nu. Complexitatea uzuală este medie O(1), dar cazul nefavorabil poate fi liniar, în funcție de distribuția cheilor și coliziuni. Nu confunda media cu o garanție pentru fiecare operație.
Când este potrivit map?
Când ai nevoie de chei în ordine, căutări de frontiere sau operații logaritmice garantate pentru organizarea sa. Dacă ordinea nu contează, compară costurile reale înainte să alegi containerul.