std::multiset (tsz. std::multisets)
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.std::set-tel, amely csak egyedi elemeket tárol).
std::multiset alapvető használata
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;
}
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
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)
|
lower_bound és upper_bound használatávalA 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.
#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;
}
Lower bound of 2: 2 Upper bound of 2: 3
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) |
std::set-et.std::multiset a megfelelő választás.std::unordered_multiset jobb lehet.
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;
}
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
std::multiset egy rendezett konténer, amely lehetővé teszi az ismétlődő elemek tárolását.std::set-et kell használni.lower_bound és upper_bound segítségével hatékony tartománykeresést végezhetünk.