[C++/STL] Opslaan 'ruimtelijke' objecten in STL-containers

[MisterData]

Sinds een aantal maanden ben ik bezig met een programma waarin als belangrijk onderdeel een tijdbalk is verwerkt. Op deze tijdbalk staan verschillende sporen. Bepaalde sporen hebben weer dingen als blokjes, cues en weet ik veel wat voor items erop staan.

Nu zit ik me eigenlijk een beetje af te vragen wat nou het meest efficiënt is om die items in op te slaan: het is belangrijk dat ik snel kan zien welke items er op een bepaald tijdstip op de tijdbalk al dan niet aanwezig zijn, welke het dichtste bij zijn, en als het even kan wil ik er ook nog sequentieel dorheen lopen voor serialisatie later.

Nu kan ik het op een aantal manieren aanpakken. Hieronder de eerste manier, die ik nu gebruik en verder prima werkt:

C++:

struct Cue {
  Time _time;
  int _value;
};

std::vector<Cue> _cues;

Het nadeel is dat ik om te kijken welke cues er op een bepaald tijdstip 'in de buurt' zijn minstens alle elementen in de vector moet doorlopen. Een andere optie zou zijn geweest:

C++:

std::map<Time, int> _cues;

Hoewel je nu snel een cue op een bepaald tijdstip kunt ophalen, kun je niet snel (althans, zonder iterators zoals bij de vorige oplossing) zien welke cues in de buurt zijn. Daarnaast is het verplaatsen van een cue (met drag & drop bijvoorbeeld in de UI) niet makkelijk: als je een CUe verplaatst van t=x naar t=y dan moet je eerst de entry in de map van t=x verwijderen en vervolgens een nieuwe entry toevoegen.

Wat is de slimste manier om objecten in (indien mogelijk) STL-containers op te slaan bij dit soort structuren?

[Soultaker]

MisterData schreef op maandag 14 november 2005 @ 18:18:Nu zit ik me eigenlijk een beetje af te vragen wat nou het meest efficiënt is om die items in op te slaan: het is belangrijk dat ik snel kan zien welke items er op een bepaald tijdstip op de tijdbalk al dan niet aanwezig zijn, welke het dichtste bij zijn, en als het even kan wil ik er ook nog sequentieel dorheen lopen voor serialisatie later.

De set- en map-templates zijn daar juist bijzonder geschikt voor, omdat je ze gesorteerd kunt doorlopen, en je willekeurige waarden efficiënt kunt vinden, en je bovendien efficiënt waarden kunt toevoegen en verwijderen.

C++:

std::map<Time, int> _cues;

Hoewel je nu snel een cue op een bepaald tijdstip kunt ophalen, kun je niet snel (althans, zonder iterators zoals bij de vorige oplossing) zien welke cues in de buurt zijn.

Jawel, daarvoor zijn de lower_bound() en upper_bound() methodes, die een iterator naar respectievelijk de grootste kleinere en de kleinste grotere key opleveren. Die iterators zijn bidirectioneel dus je kunt dan zelf doorlopen tot je buiten het gewenste bereik komt.

Daarnaast is het verplaatsen van een cue (met drag & drop bijvoorbeeld in de UI) niet makkelijk: als je een CUe verplaatst van t=x naar t=y dan moet je eerst de entry in de map van t=x verwijderen en vervolgens een nieuwe entry toevoegen.

Dat klopt. Waarom is dat precies een bezwaar? (Als je ze in een gesorteerde vector zou stoppen, zou je immers ook opnieuw moeten sorteren.)

Denk er trouwens aan dat je met een std::map maar één gebeurtenis op een zeker tijdstip kunt hebben. Als je er meer wil moet je ofwel een multi_map gebruiken (die ook dubbele waarden toestaat) of een set<pair<Time,Whatever> >, waarmee je op eenzelfde tijdstip wel verschillende dingen kunt hebben, maar niet dezelfde.

[ Voor 7% gewijzigd door Soultaker op 14-11-2005 18:58 ]

[.oisyn]

multiset bestaat overigens ook

[Zoijar]

Boost.MultiIndex is ook een behoorlijk krachtige container die eigenlijk al het bovengenoemde combineert, plus extra's zoals hashing. TS kan eens naar de mogelijkheden hiervan kijken: http://www.boost.org/libs/multi_index/doc/index.html