std::multiset

Angol

Főnév

std::multiset (tsz. std::multisets)

1. (informatika) A std::multiset a C++ Standard Library (STL) egyik konténere, amely egy rendezett adatszerkezet, hasonló a std::set-hez, de azzal a fő különbséggel, hogy ugyanaz az elem többször is előfordulhat benne.

• Az elemek rendezetten tárolódnak (alapértelmezés szerint növekvő sorrendben).
• Minden elem többször is előfordulhat (ellentétben a std::set-tel, amely csak egyedi elemeket tárol).
• A háttérben egy kiegyensúlyozott bináris keresőfa (általában vörös-fekete fa) segítségével van implementálva.
• Az összes művelet (beszúrás, törlés, keresés) O(log N) időben fut.

---

1. std::multiset alapvető használata

Példa: std::multiset létrehozása és alapvető műveletek

#include <iostream>
#include <set>

int main() {
    std::multiset<int> ms;

    // Elembeszúrás
    ms.insert(5);
    ms.insert(1);
    ms.insert(3);
    ms.insert(5); // Ismétlődő elem
    ms.insert(2);
    
    // Kiírás (automatikusan növekvő sorrendben)
    std::cout << "Multiset elemei: ";
    for (int elem : ms) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // Adott elem megszámlálása
    std::cout << "5-ös előfordulások száma: " << ms.count(5) << std::endl;

    // Egy adott elem törlése (csak egy előfordulás törlése)
    ms.erase(ms.find(5));

    std::cout << "Egy 5-ös törlése után: ";
    for (int elem : ms) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

Kimenet:

Multiset elemei: 1 2 3 5 5 
5-ös előfordulások száma: 2
Egy 5-ös törlése után: 1 2 3 5

---

2. std::multiset műveletei és tulajdonságai

Művelet	Leírás
insert(value)	Elem beszúrása (duplikátumok megengedettek)
erase(value)	Minden előfordulás törlése egy adott értékből
erase(iterator)	Egy adott iterátorral megjelölt elem törlése (csak egy példányt töröl)
count(value)	Megszámolja, hogy egy adott elem hányszor fordul elő
find(value)	Visszaad egy iterátort az első előfordulásra (ha nincs, akkor end())
lower_bound(value)	Visszaadja az első olyan elemet, amely nem kisebb, mint a keresett érték
upper_bound(value)	Visszaadja az első olyan elemet, amely nagyobb, mint a keresett érték
equal_range(value)	Visszaad egy párt az adott elem első és utolsó előfordulásáról (lower_bound és upper_bound)

---

3. Specifikus keresések lower_bound és upper_bound használatával

A lower_bound(value) és upper_bound(value) függvények lehetővé teszik az elemek hatékony keresését és tartományok kijelölését.

Példa:

#include <iostream>
#include <set>

int main() {
    std::multiset<int> ms = {1, 2, 2, 2, 3, 4, 5, 5};

    // lower_bound: az első olyan elem, amely >= 2
    auto it1 = ms.lower_bound(2);
    std::cout << "Lower bound of 2: " << *it1 << std::endl;

    // upper_bound: az első olyan elem, amely > 2
    auto it2 = ms.upper_bound(2);
    std::cout << "Upper bound of 2: " << *it2 << std::endl;

    return 0;
}

Kimenet:

Lower bound of 2: 2
Upper bound of 2: 3

---

4. std::multiset összehasonlítása más konténerekkel

Konténer	Egyedi elemek?	Sorbarendezett?	Keresési idő
std::set	✔️ Igen	✔️ Igen	O(log N)
std::multiset	❌ Nem	✔️ Igen	O(log N)
std::unordered_set	✔️ Igen	❌ Nem	O(1) (átlagosan)
std::unordered_multiset	❌ Nem	❌ Nem	O(1) (átlagosan)

• Ha egyedi elemekre van szükség, használj std::set-et.
• Ha többször előforduló elemek is kellenek, std::multiset a megfelelő választás.
• Ha nem kell rendezés és inkább gyors keresés a cél, akkor std::unordered_multiset jobb lehet.

---

5. Példa egyedi használati esetre – Multiset frekvencia alapú törléssel

Tegyük fel, hogy van egy számhalmazunk, és azt szeretnénk, hogy ha egy elem többször szerepel, akkor csak egyet töröljünk belőle.

#include <iostream>
#include <set>

int main() {
    std::multiset<int> ms = {1, 2, 2, 3, 3, 3, 4, 5};

    std::cout << "Eredeti multiset: ";
    for (int elem : ms) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // Csak egy példány törlése a 3-asból
    auto it = ms.find(3);
    if (it != ms.end()) {
        ms.erase(it);
    }

    std::cout << "Egy 3-as törlése után: ";
    for (int elem : ms) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

Kimenet:

Eredeti multiset: 1 2 2 3 3 3 4 5
Egy 3-as törlése után: 1 2 2 3 3 4 5

---

Összegzés

• A std::multiset egy rendezett konténer, amely lehetővé teszi az ismétlődő elemek tárolását.
• Az O(log N) időkomplexitás miatt hatékony keresésre és beszúrásra alkalmas.
• Ha az egyedi elemek fontosak, akkor inkább std::set-et kell használni.
• A lower_bound és upper_bound segítségével hatékony tartománykeresést végezhetünk.

További információk

• std::multiset - Szótár.net (en-hu)
• std::multiset - Sztaki (en-hu)
• std::multiset - Merriam–Webster
• std::multiset - Cambridge
• std::multiset - WordNet
• std::multiset - Яндекс (en-ru)
• std::multiset - Google (en-hu)
• std::multiset - Wikidata
• std::multiset - Wikipédia (angol)