Hartă (C++)

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 7 ianuarie 2021; verificările necesită 2 modificări .

map- o clasă de șablon standard a bibliotecii limbajului de programare C++, concepută pentru a implementa abstractizarea afișajului sub forma unui container asociativ ordonat . Declarația sa se află în spațiul de nume al fișierului antet <map> al bibliotecii STL [1] [2] [3] . În contextul accesului la elementele sale, o clasă este considerată o matrice asociativă , în care valorile cheie joacă rolul indicilor [4] , ceea ce face posibilă trasarea unei analogii cu un dicționar sau cu o carte de telefon . 5] . stdmap

Descriere

Elementele unei clase mapsunt perechi de chei și valorile lor corespunzătoare. Stocarea elementelor de clasă este mapimplementată într-o formă ordonată pe baza unui criteriu de sortare care se aplică prin valori cheie. Implicit, criteriul de sortare este stabilit de operatorul operator< [6] . Spre deosebire de un container set, o clasă mapoferă utilizatorului său operator [][1] . Pentru a controla gestionarea memoriei, este posibil să conectați versiuni personalizate ale alocatoarelor de memorie . Pentru implementarea practică a clasei , mapse folosesc de obicei arbori binari de căutare [7] .

Funcționalitate de bază

Metodele standard de clasă mappermit utilizatorului să efectueze operații de căutare, inserare și traversare într-un container într-un mod unificat. Pentru mulți dintre ei, este oferită interacțiunea cu iteratorii obișnuiți ai bibliotecii STL [8] .

Datorită structurii ordonate a containerului map, căutarea sau inserarea elementului dorit poate fi efectuată în timp logaritmic [9] .

Nume Funcții
size() Returnează numărul de elemente din container
empty() Returnează truedacă containerul este gol
find(k) Returnează un iterator care indică valoarea corespunzătoare valorii cheii k. Dacă nu există o astfel de valoare în container, atunci este returnat un iterator.end
operator[k] Returnează o referință la valoarea corespunzătoare cheii k. Dacă o astfel de cheie nu există, atunci este creată.
insert(pair(k,v)) Inserează o pereche în container (k,v), returnând adresa poziției sale
erase(k) Îndepărtează elementul cu cheia din containerk
erase(p) Îndepărtează din container elementul indicat de iteratorp
begin() Returnează un iterator la începutul containerului
end() Returnează un iterator la sfârșitul containerului

Note

  1. ↑ 1 2 Gregorie, 2018 , hartă și multihartă, p. 518.
  2. ↑ Van Weert, Gregorie, 2016 , Containere asociative ordonate, p. 71.
  3. ↑ Goodrich, Tamassia, Mount, 2011 , The STL map Class, p. 372.
  4. ↑ Litvinenko, 2005 , Harta Containerelor, Multimap, p. 198.
  5. ↑ Horton, Van Weert, 2018 , Hărți, p. 730.
  6. ↑ Litvinenko, 2005 , Harta Containerelor, Multimap, p. 195.
  7. ↑ Șablon de clasă std:map Arhivat la 30 ianuarie 2020 la Wayback Machine www.cplusplus.com
  8. ↑ Goodrich, Tamassia, Mount, 2011 , The STL map Class, p. 372, 373.
  9. ↑ Posch, Galowicz, 2018 , Cunoașterea noii semantici a indicii de inserare a std::map:insert, p. 524.

Surse