[c++][alg] pari, mape, paketi

da zadovoljimo nekatere bolj napredne uporabnike (a ne yeti? :p) iscem resitev za naslednji problem:
- imamo pare id, string
- ti pari so organizirani v pakete, recimo en paket vsebuje 100 takih parov
- pari se dinamicno ne bodo spreminjali, zato je za iskanje najbolj primeren kak map
- paketi se bodo dinamicno spreminjali, recimo enega umaknemo, drugega dodamo
- uporabnik, ki potrebuje string, ve samo za id, ne ve pa v katerem paketu se par dejansko nahaja, zato potrebujemo eno kombinirano mapo, ki vsebuje vse pare
- problem nastopi, ko moramo paket zbrisati, saj par potrebuje dodaten tag, ki mu pove v katerem paketu se nahaja, tako se pac moramo sprehoditi cez celotno mapo, zato da pare, ki niso vec potrebni, umaknemo

- ena resitev je, da vsak paket ima svoj map, vendar moras v najslabsem primeru, iti cez vse pakete/mape, to pa je po zacetnih izracunih, pocasneje od kombinirane mape z vsemi pari

alternative?

Za vsak paket imej seznam id-jev od parov id,string, ki so v tem paketu. Pri odstranitvi paketa iz skupne mape odstranis vse pare, ki imajo id v seznamu paketa:
foreach (id in paket.idList) skupnaMapa.Remove(id);

- ne rabis se sprehoditi po celi mapi (O(n)), ampak samo m-krat odstranis par iz mape (O = m*O(1), kjer je m velikost seznama id-jev paketa)

Se ena opcija: mapo parov id,string imej v vsakem paketu, zraven pa se imej eno mapo id,paket_id:
- brisanje vseh parov v paketu je enostavno - brises paket;
- dostop do stringa z id: preko mape id,paket_id dobis v katerem paketu se dolocen par id,string nahaja, potem pa iz tega paketa preberes ustrezen string.

@thomas
ne vem ce :)

sicer je header + data precej uporabna zadeva, ampak tuki res nekako ne vidim, zakaj bi bil to boljsi nacin. pakete rabim, saj nocem imeti vseh nalozenih naenkrat - potreba po modularnosti pac.