doppelt verkettete Liste - Ueberladung des Index-operators
-
Moeglichst viel.. Erstmal kommt die in Verbindung mit meiner Factory zum Einsatz und dann denke ich mal immmer wenn ich Sie brauche.
Ups, das wusste ich nicht. Hmm dann wirds halt keine reine Liste..
-
@GPC: Hast du mal nen Index-Op ueberladen, in nem Prog von dir?
-
PunI$0R schrieb:
Ups, das wusste ich nicht. Hmm dann wirds halt keine reine Liste..
Dann wird deine Liste lahm, das sähe dann wahrscheinlich so aus:
template<typename T> T& Liste<T>::operator[](int index) { ListNode<T> *node = head; for (int i=0;i!=index;++i) node = node->next; return node->get_value(); };Je mehr Elemente in der Liste, desto länger dauert der Spaß
//Edit: Im Ernst, nimm lieber Iteratoren.
-
Naja.. verdammt, stimmt im Grunde nich so doll..
Ich sollte nochmal drueber nachdenken//Edit Hab noch nie was mit nem Iterator gemacht..
-
Verkettete Liste is eh eigentlich relativ langsam aufgrund des nichtwahlfreien Zugriffs, weil wenn man ein bestimmtes Element sucht, muss man erst die komplette Liste bis zu diesem Element durchlaufen, also hat man damit Aufwand O(n)...Würde dafür besser nen Baum in Erwägung ziehen, da der mit O(log(n)) arbeitet
-
hmm, also mein Kollege hat eine super verkettete Listenklasse mit der er ne 60MB-txt Datei innerhalb kuerzester Zeit im Speicher hatte und das ohne viel Speicher drumrum zu verschwenden. Das war schon geil...
//Edit: wo finde ich was ueber Iteratoren..?
-
PunI$0R schrieb:
hmm, also mein Kollege hat eine super verkettete Listenklasse mit der er ne 60MB-txt Datei innerhalb kuerzester Zeit im Speicher hatte und das ohne viel Speicher drumrum zu verschwenden. Das war schon geil...
das Problem das angesprochen wurde bezieht sich auch nicht auf die grösse eines Elementes ,sondern auf die Anzahl der elemente. Stell dir vor du hast 600 000 elemente und willst ans 300 000ste ...
-
Ja, sry bin was schwer von Begriff, gerade
-
PunI$0R schrieb:
Ja, sry bin was schwer von Begriff, gerade
Die angesprochene Schwachstelle einer Liste ist die Tatsache, dass man durch die Elemente iterieren muss,um zu einem bestimmten element zu gelangen.
Wenn du also zu einem Element in der Mitte willst, musst du sie vom anfang bis zur mitte "durchlaufen". also ist die Zugriffszeit wie gesagt proportional zur Länge.
Sprich je länger die Liste, desto länger dauert der Zugriff...
-
Ja das war mir schon die ganze Zeit klar nur ich hab Vordens Beitrag nich so verstanden wie ers meinte
for(m_poObj = m_pofirstElement ; m_poObj ; m_poObj = m_poObj->poNext) {};Sowas aehnliches duerfte doch eigentlich schon gut schnell sein...?
//Edit: Klar bei 300000 Elementen kann es das auch nicht mehr..
-
Eine Liste ist auch dazu da, um schnell an beliebigen Positionen einfügen/löschen zu können, und soll keine Bäume(welcher Art auch immer) ersetzen um möglichst schnell zu suchen.
Btw. Wenn ich nen Iterator in der Mitte der Liste stehen hab, dann kann ich mit dem vor und zurück iterieren und hab somit relativ kurze Zugriffszeiten auf die Elemente in der Mitte! Es stimmt also nicht dass ich jedesmal über die komplette Liste drüber muss.
-
GPC schrieb:
Eine Liste ist auch dazu da, um schnell an beliebigen Positionen einfügen/löschen zu können, und soll keine Bäume(welcher Art auch immer) ersetzen um möglichst schnell zu suchen.
Btw. Wenn ich nen Iterator in der Mitte der Liste stehen hab, dann kann ich mit dem vor und zurück iterieren und hab somit relativ kurze Zugriffszeiten auf die Elemente in der Mitte! Es stimmt also nicht dass ich jedesmal über die komplette Liste drüber muss.
nee natürlich nicht jedes mal, aber es ist dennoch so, dass man um den iterator dorthinzubekommen,dennoch einmal bis dorthin durchlaufen muss.
Was den Einsatz von listen angeht, gebe ich dir natürlich volkommen recht, es ging mir nur darum es dem OP klarzumachen, da er es zu diesem Zeipunkt noch nicht zu wissen schien. Dem ist aber nicht so und von daher wohl allen beteiligten klar.