multimap data type
Főnév
multimap data type (tsz. multimap data types)
- (informatika) A multimap (magyarul: többszörös leképezés, vagy „többértékű asszociatív tömb”) egy olyan asszociatív kollekció (abstract data type), amelyben egy kulcshoz több érték is tartozhat. Ez különbözik a hagyományos (egyszerű) map adattípustól, ahol minden kulcshoz pontosan egy érték tartozik.
Példa multimap-re:
{
"alma": [1, 2, 3],
"körte": [7],
"szilva": [4, 4]
}
Itt az “alma” kulcshoz három különböző érték tartozik, a “szilva” kulcshoz kétszer a 4-es érték.
2. Miért hasznos a multimap?
A multimap-ot akkor használjuk, ha ugyanaz a kulcs többször is előfordulhat a kollekcióban, és mindegyik előfordulásához külön érték társul. Például:
- Telefonkönyv: ugyanaz a név több telefonszámot is tartalmazhat.
- Indexelés: egy szó több helyen is előfordulhat egy könyvben, mindegyik előfordulást tárolni akarjuk.
- Csoportosítás: embereket csoportosítunk azonos kulcsok alapján (pl. évfolyam, város stb.), ahol egy kulcshoz több személy tartozik.
3. Multimap ADT – főbb műveletek
A multimap ADT tipikus műveletei:
| Művelet | Leírás |
|---|---|
Create() |
Üres multimap létrehozása |
Insert(m, kulcs, érték) |
Új (kulcs, érték) pár hozzáadása |
Erase(m, kulcs) |
Összes ilyen kulcs törlése |
Erase(m, kulcs, érték) |
Csak adott érték törlése a kulcs alól |
Find(m, kulcs) |
Az összes érték listázása, amely a kulcshoz tartozik |
Count(m, kulcs) |
Hány érték tartozik egy kulcshoz |
Contains(m, kulcs) |
Van-e ilyen kulcs |
Size(m) |
Összes (kulcs, érték) pár száma |
IsEmpty(m) |
Üres-e a multimap |
Clear(m) |
Multimap kiürítése |
Iterate(m) |
Sorba veszi az összes (kulcs, érték) párost |
4. Matematikai háttér
Formálisan a multimap reláció (nem függvény): f: KULCS → ÉRTÉKLISTA Tehát minden kulcshoz egy (lehet üres vagy többszörös) értéklista tartozik.
5. Implementációs lehetőségek
5.1. Vektoros tárolás
- Az összes (kulcs, érték) párt egy vektorban vagy listában tároljuk.
- Gyors beszúrás, de keresés lassú lehet.
5.2. Map of lists (szótár-lista)
- Egy normál map, ahol minden kulcshoz egy listát (vektort) rendelünk:
std::map<Key, std::vector<Value>> - Előnye: gyors keresés kulcs alapján, gyors beszúrás egy kulcshoz.
5.3. Multimap mint standard konténer
- C++ STL:
std::multimap<Key, Value>Egyes megvalósításokban a kulcs-érték párok rendezett (fa) struktúrában vannak. Egy kulcs többször is szerepelhet, minden előfordulás külön páros.
5.4. Hash alapú multimap
std::unordered_multimap(C++11-től) Kulcs hash-elés, gyors műveletek.
6. Multimap a gyakorlatban (C++ példák)
6.1. std::multimap használata
#include <iostream>
#include <map>
#include <string>
int main() {
std::multimap<std::string, int> m;
m.insert({"alma", 1});
m.insert({"alma", 2});
m.insert({"alma", 3});
m.insert({"körte", 7});
m.insert({"szilva", 4});
m.insert({"szilva", 4});
// Összes "alma"-hoz tartozó érték kiíratása:
auto range = m.equal_range("alma");
for(auto it = range.first; it != range.second; ++it)
std::cout << it->first << ": " << it->second << std::endl;
}
6.2. std::map<Key, std::vector<Value>> alternatíva
#include <map>
#include <vector>
#include <string>
std::map<std::string, std::vector<int>> m;
m["alma"].push_back(1);
m["alma"].push_back(2);
// stb.
7. Összehasonlítás: multimap vs map
- map: Minden kulcshoz csak egy érték tartozhat (az új beszúrás felülír).
- multimap: Minden kulcshoz több érték is tartozhat (többszörös előfordulás).
- Implementáció: A multimapben a kulcsok akár azonosak is lehetnek, mindegyik külön (kulcs, érték) párként tárolódik.
8. Tipikus felhasználási területek
- Indexek, fordított szótárak, csoportosítások, adatbázis-szerű leképezések, keresések, logfájl elemzés, keresőmotorok indexelése, nyelvi feldolgozás, események több eseményhez való hozzárendelése stb.
9. Előnyök és hátrányok
Előnyök:
- Kulcshoz több érték rendelhető.
- Jól csoportosíthatók vele adatok.
- Közvetlenül támogatott C++ STL-ben.
Hátrányok:
- Egyedi értékek listázása nem egyszerű (ha csak egy példány kell).
- Néha redundancia, ha az értékeket csak egyszer akarjuk tárolni.
10. Alternatívák
- Map of sets: Ha egy kulcshoz minden érték csak egyszer szerepelhet:
std::map<Key, std::set<Value>> - Unordered_multimap: Ha a sorrend nem számít, gyorsabb műveletekhez.
11. Összefoglalás
A multimap egy fontos absztrakt adattípus, amely lehetővé teszi, hogy egy kulcshoz több értéket rendeljünk. Számos gyakorlati alkalmazásban elengedhetetlen, például ahol csoportosítás, gyakoriság vagy többértékű hozzárendelés szükséges. Implementálható standard könyvtári osztályokkal vagy egyedi módon is.
- multimap data type - Szótár.net (en-hu)
- multimap data type - Sztaki (en-hu)
- multimap data type - Merriam–Webster
- multimap data type - Cambridge
- multimap data type - WordNet
- multimap data type - Яндекс (en-ru)
- multimap data type - Google (en-hu)
- multimap data type - Wikidata
- multimap data type - Wikipédia (angol)