Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 <

000
31.12.2007, 01:17 Uhr
banshee

hallo,

bevor ich mir mit einer eher ungünsitgen Implementation ins Bein schieße, wollte ich erstmal klären, was die beste für mein Problem ist:

- ich hab eine variable Anzahl an Objekten, für die ich aber eine Obergrenze definieren kann
- jedem dieser Objekte möchte ich eine feste ID zuweisen und darüber auch zugreifen können
- ich möchte beliebige Objekte löschen können

Ich hab jetzt an 3 Sachen gedacht:
1) Eine verkettete Liste, Problem => konstanter ID-Zugriff
2) Ein Array, das ich nach einem Löschvorgang einfach nach unten verschiebe => IDs passen nach ersten Löschvorgang nicht mehr zu den Feldindizes
3) Ein Array, das bei jedem Einfügevorgang von vorne bis hinten durchlaufe und die nächste freie Stelle suche, Problem => langsam

Kann mir da jemand einen kleinen Tipp geben?

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
31.12.2007, 01:40 Uhr
0xdeadbeef
Gott
(Operator)

Das Problem aus 2) hast du bei 1) auch, allerdings wäre da zusätzlich noch die Laufzeitkomplexität des Zugriffs linear (nicht konstant).

Denkbar wäre, zusätzlich zu einem konstanten Array noch eine queue mit IDs zu halten - beim Einfügen halt eine ID aus der queue nehmen, beim Löschen die ID des gelöschten Objektes hinten an die queue anhängen. Damit erreichst du eine konstante Laufzeitkomplexität bei der ID-Auswahl. Abhängig davon, wie frei du bei der Vergabe der IDs bist, böte sich aber u.U. auch eine Hashmap an.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ C / C++ (ANSI-Standard) ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: