Výběr kontejneru – C / C++ – Fórum – Programujte.com

Navrhuji jednu aplikaci a není mi jasné, jaký kontejner z STL by byl pro daný úkon nejvhodnější;
V kontejneru by měly být uchovávány celočíselné indexy, ke kterým bude přiřazen ukazatel. S položkami v kontejneru potřebuji provádět tyto operace:
[seznam]Zcela nahodile k nim přistupovat[/seznam]
[seznam]Mazat je kdekoliv v kontejneru[/seznam]
[seznam]Přidávat nové; nezáleží jaký index jim bude přiřazen (tzn. pozřebuji nějak zjistit neobsazený index)[/seznam]
Mýmy favority jsou vector a mapa. U mapy nevím, jak rychlé je u ní mazání. Navíc nevím, jak bych získával nové indexy. U vectoru jsem zamýšlel položky v něm smazané nechávat; pouze přidávat na konec nové (volný index bych získal pomocí funkce size()). Bylo by to paměově náročnější; navíc by někdy bylo nutné vector stejně někde promazat, abych se vlezl do limitu (long) unsigned int.

Doufám, že chápete, co myslím. Jaký kontejner by jste zvolili vy? Děkuju za odpověď.

Čau,

osobně bych si udělal nějaký adapter(= vlastni definované rozhraní, ať případné změny neovlivní celý projekt) nad těmi kontejnery a v první implementaci prostě zkusil vector. A teprve až bych zjistil případné výkonostní problémy, tak bych se zamýšlel nad jiným kontejnerem(uvažoval jsi o hashovací tabulce?).

Původně jsem se zkoušení chtěl vyhnout; mít teoreticky základ. Teď s odstupem 3 dnů jsem dospěl k názoru, že metoda pokus-omyl bude nejlepší. Díky za odpověď

To yaqwsx : Záleží na tom co chceš, kolik prvků v kontejneru bude, jaká bude nejčastější operace atp.
Já osobně jsem tohle řešil pomocí mapy, kde klíč byl uint64_t, který jsem pokaždé zvyšoval při vkládání nového elementu, s tím, že dle mého rozboru (při maximální možné frekvenci vkládání a vybírání objektů) mi množina klíčů (2^64) dojde opravdu za dlouhý čas, který zaručeně přesahuje délku životnosti předpokládaného HW.

To voty : Počet prvků v kontejneru? Okolo 30-40tisíc. A frekvence vyjímaní bude různá; zhruba tak 50% prvků v kontejneru nezůstane déle než 0,5 sekundy a cca 5% se tam neohřeje ani na desetinu sekundy.

To yaqwsx : Tak je pěkné :) Ale pokud má v kontejneru být skutečně naráz 30 až 40 tisíc objektů, z nichž se každých 500 ms 50% protočí, tak se mi jako nejlepší jeví STL list, kde "indexem" bude iterator (doufám, že se nepletu a iterator u STL list zůstává platný i po operacích vkládání a vyjímání jiných prvků, když tak mne opravte).

To voty : jak zmenis list tak prestavaj iteratory platit.. pokud si pamatuju dobre

To voty : To KIIV : Pokud si pamatuji dobře, tak se zneplatní pouze iterátory za vyjmutým/vloženým prvkem. Ale i tak je to pro mě nepoužitelné.
Děkuji za úvahy a návrhy – rozhodl jsem se že půjdu cestou metody a omylu; jako první kandidáty mám mapy a vector.

To KIIV : Tak jsem to pro jistotu hledal a u Listu jsou iterátory stále platné, ať přidáváme jak přidáváme a mazání jedné položky listu zneplatní právě ten jeden iterátor, který položce odpovídá.