Ugrás a tartalomhoz

associative container

A Wikiszótárból, a nyitott szótárból

Angol


Főnév

associative container (tsz. associative containers)

  1. (informatika) A C++ Standard Template Library (STL) részeként az asszociatív tárolók olyan adatszerkezetek, amelyek elemeket kulcs alapján tárolnak és gyors keresést, beszúrást, valamint törlést biztosítanak. Az asszociatív konténerek rendezetten vagy rendezetlenül tárolhatják az adatokat.


1. Associative konténerek típusai

A C++ STL négy fő asszociatív konténert biztosít:

Konténer Leírás Sorrend Duplikátumok
std::map Kulcs-érték párok tárolása Rendezett (kulcs szerint) Nem engedélyezett
std::multimap Kulcs-érték párok tárolása Rendezett (kulcs szerint) Engedélyezett
std::set Egyedi elemek halmaza Rendezett (elemek szerint) Nem engedélyezett
std::multiset Többször előforduló elemek halmaza Rendezett (elemek szerint) Engedélyezett

Ha a gyors keresés és beszúrás fontosabb, mint a rendezettség, akkor az unordered változatokat használjuk (std::unordered_map, std::unordered_set stb.).


2. std::map – Rendezett kulcs-érték tárolás

A std::map egy fából (általában Red-Black Tree) implementált kulcs-érték alapú tároló. Az elemek kulcs szerint rendezettek, és egy kulcs csak egyszer szerepelhet.

Példa – std::map használata

#include <iostream>
#include <map>

int main() {
    std::map<std::string, int> korok;

    // Kulcs-érték párok beszúrása
    korok["Anna"] = 25;
    korok["Béla"] = 30;
    korok["Csaba"] = 22;

    // Kiírás
    for (const auto& [nev, kor] : korok) {
        std::cout << nev << " -> " << kor << " év" << std::endl;
    }

    return 0;
}

Kimenet:

Anna -> 25 év
Béla -> 30 év
Csaba -> 22 év

🔹 A std::map automatikusan rendezi a kulcsokat (ábécérendben)!
🔹 Az operator[] segítségével könnyen hozzáadhatunk vagy módosíthatunk elemeket.

Keresés és törlés std::map esetén

if (korok.find("Anna") != korok.end()) {
    std::cout << "Anna életkora: " << korok["Anna"] << std::endl;
}

korok.erase("Béla"); // Béla törlése a térképből

🔹 find() ellenőrzi, hogy létezik-e a kulcs.
🔹 erase() törli a megadott kulcsot.


3. std::multimap – Többször előforduló kulcsok

A std::multimap hasonló a std::map-hoz, de ugyanaz a kulcs többször is szerepelhet.

Példa – std::multimap használata

#include <iostream>
#include <map>

int main() {
    std::multimap<std::string, int> diakJegyek;

    // Többször előforduló kulcsok
    diakJegyek.insert({"Anna", 5});
    diakJegyek.insert({"Béla", 4});
    diakJegyek.insert({"Anna", 3});

    for (const auto& [nev, jegy] : diakJegyek) {
        std::cout << nev << " kapott: " << jegy << std::endl;
    }

    return 0;
}

Kimenet:

Anna kapott: 3
Anna kapott: 5
Béla kapott: 4

🔹 Többször előfordulhat ugyanaz a kulcs.
🔹 insert() szükséges új kulcspárok beszúrására, mert operator[] nem támogatott.


4. std::set – Egyedi rendezett elemek

A std::set egy automatikusan rendezett gyűjtemény, amelyben minden elem egyedi.

Példa – std::set használata

#include <iostream>
#include <set>

int main() {
    std::set<int> szamok = {5, 3, 8, 1, 3, 5};

    // Kiírás (rendezett és egyedi elemek)
    for (int x : szamok) std::cout << x << " ";
    return 0;
}

Kimenet:

1 3 5 8

🔹 Az elemek egyediek és mindig rendezettek!
🔹 A duplikált elemek automatikusan eltűnnek.

Keresés std::set-ben

if (szamok.find(3) != szamok.end()) {
    std::cout << "A 3-as benne van a halmazban!" << std::endl;
}

5. std::multiset – Rendezett, de duplikált elemek engedélyezettek

A std::multiset hasonló a std::set-hez, de duplikált elemek is szerepelhetnek benne.

Példa – std::multiset használata

#include <iostream>
#include <set>

int main() {
    std::multiset<int> szamok = {5, 3, 8, 1, 3, 5};

    for (int x : szamok) std::cout << x << " ";
    return 0;
}

Kimenet:

1 3 3 5 5 8

🔹 Duplikált elemek megengedettek.
🔹 Mindig rendezett marad.


6. Összehasonlítás – Mikor melyik konténert használjuk?

Funkció std::map std::multimap std::set std::multiset
Rendezett? ✅ Igen ✅ Igen ✅ Igen ✅ Igen
Kulcs-érték párok? ✅ Igen ✅ Igen ❌ Nem ❌ Nem
Duplikáció engedélyezett? ❌ Nem ✅ Igen ❌ Nem ✅ Igen
Gyors keresés (O(log n)) ✅ Igen ✅ Igen ✅ Igen ✅ Igen
Legjobb használat Egyedi kulcsok, gyors keresés Többször előforduló kulcsok Egyedi elemek, gyors keresés Duplikált elemek kezelése


7. Alternatíva: unordered_map és unordered_set

Ha még gyorsabb keresésre van szükség, de nem fontos a rendezett sorrend, akkor használjuk a hash-alapú konténereket: - std::unordered_map - std::unordered_set

Ezek általában O(1) időben keresnek, míg az std::map és std::set O(log n) időt igényel. 🚀


Összegzés

✅ std::map – Egyedi kulcsok, automatikusan rendezett.
✅ std::multimap – Többször előforduló kulcsok, rendezett.
✅ std::set – Egyedi, rendezett elemek.
✅ std::multiset – Rendezett, de duplikált elemek is lehetnek benne.

Ha gyors keresés kell rendezés nélkül, használj unordered_map-ot vagy unordered_set-et! 🚀

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=associative_container&oldid=3499359”