associative array (tsz. associative arrays)
std::map
és std::unordered_map
konténerekkel.
✅ Gyors keresés és beszúrás kulcs alapján
✅ Nincs szükség indexelésre, kulcs alapján érhetjük el az adatokat
✅ Ideális adatstruktúra, ha az adatokat egyedi kulcsokkal akarjuk elérni
std::map
– Rendezett asszociatív tömbA std::map
egy rendezett kulcs-érték párokat tároló konténer, amely piros-fekete fa (Red-Black Tree) struktúrát használ.
Tulajdonság | Leírás |
---|---|
Kulcs egyedi? | ✅ Igen |
Rendezett? | ✅ Igen, növekvő sorrendben |
Keresési idő | O(log n) |
Beszúrás/törlés idő | O(log n) |
std::map
használata#include <iostream>
#include <map>
using namespace std;
int main() {
map<string, int> diakok;
diakok = 90;
diakok = 85;
diakok = 78;
cout << "Anna pontszáma: " << diakok << endl;
// Összes elem bejárása
for (const auto &par : diakok) {
cout << par.first << ": " << par.second << endl;
}
return 0;
}
📌 Megjegyzések: - A kulcsok növekvő sorrendben tárolódnak. - A diakok
automatikusan beszúr egy új elemet, ha nem létezett korábban. - Az O(log n)
időbeli komplexitás a kereséshez és beszúráshoz megfelelő nagy adathalmazok esetén.
insert()
, erase()
és find()
használata#include <iostream>
#include <map>
using namespace std;
int main() {
map<string, int> diakok;
// Elem beszúrása insert() használatával
diakok.insert({"Dóra", 92});
diakok = 75;
// Elem törlése
diakok.erase("Erik");
// Elem keresése
auto it = diakok.find("Dóra");
if (it != diakok.end()) {
cout << "Dóra pontszáma: " << it->second << endl;
} else {
cout << "Dóra nincs a listában." << endl;
}
return 0;
}
📌 Fontos függvények: - insert({kulcs, érték})
– Új elem beszúrása (nem írja felül, ha már létezik). - erase(kulcs)
– Elem törlése kulcs alapján. - find(kulcs)
– Megkeresi az adott kulcsot, ha létezik (O(log n)
).
std::unordered_map
– Nem rendezett asszociatív tömbA std::unordered_map
egy hash tábla alapú asszociatív tömb, amely nincs rendezve, de gyorsabb keresést biztosít (O(1)
átlagos idővel).
Tulajdonság | Leírás |
---|---|
Kulcs egyedi? | ✅ Igen |
Rendezett? | ❌ Nem |
Keresési idő | O(1) átlagosan |
Beszúrás/törlés idő | O(1) átlagosan |
std::unordered_map
használata#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
unordered_map<string, int> diakok;
diakok = 90;
diakok = 85;
diakok = 78;
cout << "Anna pontszáma: " << diakok << endl;
for (const auto &par : diakok) {
cout << par.first << ": " << par.second << endl;
}
return 0;
}
📌 Megjegyzések: - Az unordered_map
nem garantálja a sorrendet. - Gyorsabb, mint a std::map
, mert hash tábla alapú (O(1)
keresés és beszúrás).
unordered_map
– Gyorsabb keresés#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
unordered_map<int, string> nevek;
nevek = "Anna";
nevek = "Béla";
nevek = "Csaba";
int id;
cout << "Add meg az ID-t: ";
cin >> id;
if (nevek.find(id) != nevek.end()) {
cout << "A keresett személy: " << nevek << endl;
} else {
cout << "Nincs ilyen ID!" << endl;
}
return 0;
}
📌 Az unordered_map
kiváló választás, ha nincs szükség rendezésre, és gyors keresés kell.
std::multimap
– Többször előforduló kulcsokA std::multimap
hasonló a std::map
-hez, de megengedi a duplikált kulcsokat.
Tulajdonság | Leírás |
---|---|
Kulcs egyedi? | ❌ Nem |
Rendezett? | ✅ Igen |
Keresési idő | O(log n) |
std::multimap
használata#include <iostream>
#include <map>
using namespace std;
int main() {
multimap<string, int> jegyek;
jegyek.insert({"Anna", 90});
jegyek.insert({"Béla", 85});
jegyek.insert({"Anna", 80}); // Anna kétszer szerepelhet!
for (const auto &par : jegyek) {
cout << par.first << ": " << par.second << endl;
}
return 0;
}
📌 Használat: - Kiváló több érték tárolására ugyanazzal a kulccsal (pl. egy diák több jegye).
std::unordered_multimap
– Hash alapú multitérképA std::unordered_multimap
egy hash tábla alapú multimap
, amely gyorsabb, de nem rendezett.
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
unordered_multimap<string, int> pontok;
pontok.insert({"Anna", 90});
pontok.insert({"Anna", 80});
pontok.insert({"Béla", 85});
for (const auto &par : pontok) {
cout << par.first << ": " << par.second << endl;
}
return 0;
}
📌 Ideális választás, ha gyors keresés kell, és megengedett a duplikált kulcs.
Konténer | Kulcs egyedi? | Rendezett? | Keresési idő |
---|---|---|---|
std::map
|
✅ Igen | ✅ Igen | O(log n) |
std::unordered_map
|
✅ Igen | ❌ Nem | O(1) (átlagosan) |
std::multimap
|
❌ Nem | ✅ Igen | O(log n) |
std::unordered_multimap
|
❌ Nem | ❌ Nem | O(1) (átlagosan) |
🚀 Ha gyors keresés kell, használj unordered_map
-ot, ha rendezés kell, map
-ot! 🚀