std::list Implementierung
-
Guten Tag,
Ich habe versucht eine std::list zu implementieren, soweit funktioniert auch alles und kommt der Geschwindigkeit der std::list recht nahe.
Allerdings bin ich mir sicher, dass da noch Optimierungsmöglichkeiten sind, und falls doch ein Fehler da sein sollte, den ich übersehen habe, wäre es super, wenn man mir auch diesen zeigen könnte
Code: http://codepad.org/C97mUMna
Feedback bitte
-
Ich ueberpruefe keine 600 Zeilen Code!
-
War klar, dass sowas kommt. Spar dir bitte den Kommentar und überlies es einfach. Danke.
-
@314159265358979: Bist du sicher, dass jeder deinen Realnamen wissen sollte?
-
Ist mir relativ egal
-
314159265358979 schrieb:
Feedback bitte
Ich hab's nur überflogen. Sieht gut aus auf den ersten Blick. Mir ist jetzt nur aufgefallen, dass sich ein iterator bei Dir nicht in einen const_iterator konvertieren lässt. Vielleicht bekommst Du die Redundanz bzgl const_iterator + iterator auch noch reduziert. Die Unterschiede zwischen den beiden könnte man vielleicht per Template-Parameter erschlagen. Ich definiere eigene Iteratoren eher selten. Von daher habe ich da keine reifen Tipps parat. Mit Boost.Iterator kann man sich vielleicht auch noch etwas Tipparbeit sparen.
-
314159265358979 schrieb:
Feedback bitte
Du verwendest einige Features von C++0x. Das verhindert zumindest, dass ich das hier mal eben übersetzen kann.
Du verwendest zwei Anker-Knoten first und last. Meines Erachtens ist nur ein Ankerknoten notwendig, der auf sich selbst zeigt, falls die Liste leer ist.
wenn schon C++0x dann fehlt der Zuweisungsoperatoren mit der doppelten Referenz (&&)
Die Algorithmen unique und reverse sind meines Erachtens überflüsig, das selbe leistet auch std::unique mit anschließendem erase, bzw. std::reverse.
Im Konstruktor von ListNode kann man prev und next nicht mitgeben. Wenn Du noch einen hinzufüst, so würde sich das List::init erledigen.
Was macht emplace? soll das ein insert sein?
Gruß
Werner
-
Werner Salomon schrieb:
Du verwendest zwei Anker-Knoten first und last. Meines Erachtens ist nur ein Ankerknoten notwendig, der auf sich selbst zeigt, falls die Liste leer ist.
Ist nötig für die Iteratoren
Werner Salomon schrieb:
wenn schon C++0x dann fehlt der Zuweisungsoperatoren mit der doppelten Referenz (&&)
Der wurde mit Absicht weggelassen, operator = (List) kann beides leisten.
Werner Salomon schrieb:
Die Algorithmen unique und reverse sind meines Erachtens überflüsig, das selbe leistet auch std::unique mit anschließendem erase, bzw. std::reverse.
Die Liste orientiert sich an der std::list, daher sind alle Funktionen der Standardliste vorhanden
Werner Salomon schrieb:
Im Konstruktor von ListNode kann man prev und next nicht mitgeben. Wenn Du noch einen hinzufüst, so würde sich das List::init erledigen.
Kann man machen, mir gefällts so besser
Werner Salomon schrieb:
Was macht emplace? soll das ein insert sein?
emplace ist wie insert, gibt aber die Konstruktor-Argumente an die ListNode weiter, die sie an das Objekt weitergibt
-
314159265358979 schrieb:
Werner Salomon schrieb:
Du verwendest zwei Anker-Knoten first und last. Meines Erachtens ist nur ein Ankerknoten notwendig, der auf sich selbst zeigt, falls die Liste leer ist.
Ist nötig für die Iteratoren
die brauchen auch nur einen. end() zeigt auf den einen ungültigen Knoten der den Ring schließt, und begin() zeigt auf den ersten Knoten dahinter.
//edit block entfernt, mach nen post draus...ihr seid zu schnell .
-
Wie auch immer, ist so einfacher zu implementieren.
-
314159265358979 schrieb:
Werner Salomon schrieb:
Du verwendest zwei Anker-Knoten first und last. Meines Erachtens ist nur ein Ankerknoten notwendig, der auf sich selbst zeigt, falls die Liste leer ist.
Ist nötig für die Iteratoren
Nö - begin() zeigt auf das erste Element und end() auf den Anker. Ein zweiter Anker ist unnötig.
314159265358979 schrieb:
Werner Salomon schrieb:
Im Konstruktor von ListNode kann man prev und next nicht mitgeben. Wenn Du noch einen hinzufüst, so würde sich das List::init erledigen.
Kann man machen, mir gefällts so besser
Ist aber bestimmt 'ne halbe nano-Sekunde langsamer, da prev und next zwei mal initialisiert werden. Außerdem geht bei mir immer die gelbe Warnleuchte an, wenn ich init() lese
Gruß
Werner
-
Werner Salomon schrieb:
Nö - begin() zeigt auf das erste Element und end() auf den Anker. Ein zweiter Anker ist unnötig.
Siehe erste Seite
Werner Salomon schrieb:
Ist aber bestimmt 'ne halbe nano-Sekunde langsamer, da prev und next zwei mal initialisiert werden. Außerdem geht bei mir immer die gelbe Warnleuchte an, wenn ich init() lese
Der Compiler müsste das doch eigentlich wegoptimieren können, oder?
-
(war vorher ein edit, aber ihr postet zu schnell):
Ws mich stört:
Was ich an der std::list niemals mochte war, dass für jedes neue Element new aufgerufen wurde. in der std::list wurde das noch durch einen Allokator gelöst an dem man selbst rumpfuschen konnte, hier geht das nicht. Besser wäre es(meiner Meinung nach), wenn die Liste den Speicher immer Blockweise allokieren würde. Dann muss man sich nicht schlagen, wenn man regelmäßig Elemente aus der Liste entfernen/einfügen muss...
-
otze schrieb:
(war vorher ein edit, aber ihr postet zu schnell):
Ws mich stört:
Was ich an der std::list niemals mochte war, dass für jedes neue Element new aufgerufen wurde. in der std::list wurde das noch durch einen Allokator gelöst an dem man selbst rumpfuschen konnte, hier geht das nicht. Besser wäre es(meiner Meinung nach), wenn die Liste den Speicher immer Blockweise allokieren würde. Dann muss man sich nicht schlagen, wenn man regelmäßig Elemente aus der Liste entfernen/einfügen muss...Auf Allokatoren habe ich der Einfachheit halber bewusst verzichtet
-
314159265358979 schrieb:
Feedback bitte
Warum eigentlich?
-
Werner Salomon schrieb:
314159265358979 schrieb:
Feedback bitte
Warum eigentlich?
Weil ich wissen möchte, ob noch jemandem etwas auffällt, das total falsch oder schöner/besser/schneller zu lösen ist. Bin halt ein Perfektionist
-
Neben der fehlenden iterator -> const_iterator Konvertierung ist mir noch etwas aufgefallen. Du verwendest überall Schleifen der Art
for (auto&& iter = list.begin(); iter != list.end(); ++iter) ...wobei hinter dem auto ein && sitzt. Das ist aber eigentlich überflüssig. list.end() wird (logisch) auch jedes Mal aufgerufen.
Und ich sehe gerade noch, dass der Selbstzuweisungstest beim operator=(List) nicht nötig ist.
-
krümelkacker schrieb:
Neben der fehlenden iterator -> const_iterator Konvertierung ist mir noch etwas aufgefallen.
Wäre es ratsamer in iterator einen operator const_iterator() zu definieren, oder dem const_iterator einen iterator-Konstrukor zu geben?
krümelkacker schrieb:
wobei hinter dem auto ein && sitzt. Das ist aber eigentlich überflüssig.
Was zur Folge hat, dass der Returnwert gemoved wird. Dass das wenig bringt, ist mir klar.
krümelkacker schrieb:
list.end() wird (logisch) auch jedes Mal aufgerufen.
Natürlich könnte ich die Schleife so umschreiben:
for(auto&& iter = list.begin(), end = list.end(); iter != end; ++iter) ...Aber kann der Compiler das nicht von selbst optimieren?
krümelkacker schrieb:
Und ich sehe gerade noch, dass der Selbstzuweisungstest beim operator=(List) nicht nötig ist.
Danke, habe ich übersehen
-
314159265358979 schrieb:
Weil ich wissen möchte, ob noch jemandem etwas auffällt, das total falsch oder schöner/besser/schneller zu lösen ist. Bin halt ein Perfektionist
Warum lehnst du dann alle verbesserungs vorschlaege ab?
-
Shade Of Mine schrieb:
314159265358979 schrieb:
Weil ich wissen möchte, ob noch jemandem etwas auffällt, das total falsch oder schöner/besser/schneller zu lösen ist. Bin halt ein Perfektionist
Warum lehnst du dann alle verbesserungs vorschlaege ab?
Tue ich doch gar nicht, vielleicht habe ich mich schlecht ausgedrückt, ich möchte es erstmal bei der vorhandenen Funktionalität belassen
