Problem bei eigener LinkedList

Firefighter schrieb:

Danke Werner, aber duch diesen Codeabschnitt:
pToDel = prev->next;    // prev zeigt auf den Vorgänger
prev->next = pToDel->next;
Steige ich nicht so richtig durch, was machst du da genau? Speichertechnisch?

nach der ersten Zeile hat man folgende Situation:

prev           pToDel
    |              |
    v              v
 +-------+   +->+-------+   +->+-------+
 |  x0   |   |  |  x1   |   |  |  x    |
 | next------+  | next------+  | next---->...
 +-------+      +-------+      +-------+
                  ^
                 index (zu löschen)

und nach der zweiten Zeile:

+-----------------+
             |                 |
   prev      |    pToDel       |
    |        |     |           |
    v        |     v           v
 +-------+   |  +-------+   +->+-------+
 |  x0   |   |  |  x1   |   |  |  x    |
 | next------+  | next------+  | next---->...
 +-------+      +-------+      +-------+
                  ^
                 index (zu löschen)

.. mal selber; das übt

Gruß
Werner

Firefighter

Ahhh cool danke. Ich denke ich habe es jetzt so langsam geschnitten. Muss ja haufen malarbeit gewesen sein Danke nochmal

Firefighter

Mal so eine Frage nebenbei? Wie müsste denn bei der Klasse der Copyctor aussehen?? Kann ich da eventuell meinen [] operator nutzen oder muss ich da was beachten?

Firefighter schrieb:

Wie müsste denn bei der Klasse der Copyctor aussehen?? Kann ich da eventuell meinen [] operator nutzen oder muss ich da was beachten?

So weit ich das gesehen und Dein Konzept verstanden habe, läufst Du in dem operator[] in einer Schleife vom Anfang (first) bis zu i'ten Element.
Wenn Du nun den operator[] im Copy-Konstruktor einsetzt, so wurde Du bei 2 Elementen 3 mal durch diese Schleife im operator[] laufen. Bei 10 Elementen wären es 55 und bei 100 Elementen bereits über 5000 Durchläufe. Mit anderen Worten - Dein Copy-Konstruktor hätte die Komplexität O(n^2).

Das sollte man vermeiden. Also implementiere lieber eine Schleife mit 'Item* p; p = p-> next ..'.

Noch ein Tipp: Implemntiere auch eine swap-Methode für die LinkedList (das sollte trivial sein) und nutze im Zuweisungs-operator den Kopie-und-Swap-Trick.

LinkedList& LinkedList::operator=( const LinkedList& other )
{
  LinkedList temp(other);
  LinkedList::swap(temp);
  return *this;
}

Gruß
Werner

Firefighter

Das sollte man vermeiden. Also implementiere lieber eine Schleife mit 'Item* p; p = p-> next ..'.

wie meinst du das? Wie kann ich denn eine solche Schleife gestalten irgendwie muss ich ja mit dem Index arbeiten oder sehe ich das gerade falsch?
Aber die restlichen Tips waren sehr gut danke. wobei ich mir noch nicht 100% schlüssig bin wie ich die swap gestalten sollte

LordJaxom

Firefighter schrieb:

Das sollte man vermeiden. Also implementiere lieber eine Schleife mit 'Item* p; p = p-> next ..'.

wie meinst du das? Wie kann ich denn eine solche Schleife gestalten irgendwie muss ich ja mit dem Index arbeiten oder sehe ich das gerade falsch?

Du hast doch in der operator[]-Funktion eine Schleife, die vom ersten zum i'ten Element zählt. So eine Schleife ist gemeint, nur vom ersten bis zum letzten Element (Analogieübung: Ersetze i durch m_length-1 :D).

Zum Swap: Wenn Du den Inhalt zweier Listen tauschen möchtest, musst Du die Daten, die diese Liste verwaltet, tauschen. Die Daten innerhalb der Liste liegen als Zeiger auf das erste Element vor, also kann diese Tauschoperation sehr günstig erreicht werden.

Firefighter

Du hast doch in der operator[]-Funktion eine Schleife, die vom ersten zum i'ten Element zählt. So eine Schleife ist gemeint, nur vom ersten bis zum letzten Element (Analogieübung: Ersetze i durch m_length-1 :D).

Wenn ich das doch so mache, dann laufe ich ja jedesmal bis zum Ende durch und gebe das Letzte Element zurück? Stehe ich gerade aufem Schlauch?!

LordJaxom

Firefighter schrieb:

Wenn ich das doch so mache, dann laufe ich ja jedesmal bis zum Ende durch und gebe das Letzte Element zurück? Stehe ich gerade aufem Schlauch?!

Vielleicht: Ein Konstruktor gibt nichts zurück. Wir reden doch vom Copy-Konstruktor, oder?

EDIT:
Nochmal langsam: Du möchtest in einem Copy-Konstruktor an die einzelnen Elemente. Dein Vorschlag war, über den op[] an diese Elemente heranzugehen. Der Einwand war, dass das zu langsam sein könnte, weil dann für jedes Element von Anfang bis zum Element durchgezählt wird. Der Alternativvorschlag war, statt op[] eine Schleife zu verwenden, die wie die in op[] aufgebaut ist. Du solltest nicht op[] verändern.

Firefighter

Auch Von dem und von der Methode operator[] wie die besser gestaltet werden könnte

EDIT:Asso...ok dann muss ich das nochmal überarbeiten

LordJaxom

Achsooooo (siehe auch mein EDIT im Post oben).

Da kannst Du beruhigt sein: Bei einer verketteten Liste ohne zusätzlichen Verwaltungsschnickschnack kann der Indexoperator nicht besser implementiert werden. Deshalb bietet die Standardbibliothek auch keinen op[] für std::list an. Wenn Du sowas mit std::list nachbilden willst, muss auch durchgezählt werden.

Firefighter

Alles klar, danke dir Dann schmeiße ich mein operator[] raus, wenn er nicht mal in der std::list vorgesehen ist, brauche ich den erst recht nicht

Firefighter

Sorry ich brauche nochmal eure Hilfe bei der Swap Funktion, ich tue mich ein wenig Schwer mit dem Zeigerwirrwarr. Zurzeit sieht es so hier aus:

template<class T>
LinkedList<T>& LinkedList<T>::swap_list(const LinkedList& list)
{
    Item* temp = this->first;
    this->first = list->first;
    list->first = temp;

    return this;

}

Leider führt das nur zu Fehlern

drakon

Was für Fehler?

Das alleine kann ja schon nicht gehen.

return this;

Nutzt doch einfach std::swap:

template<class T>
LinkedList<T>& LinkedList<T>::swap_list(const LinkedList& list)
{
    std::swap (this->first, list.first);
    return *this;
}

Firefighter

hmm --.-- ich dummkopf, danke dir

camper

const ?

Firefighter

Habe ich mich auch gerade gefragt, weil mit const geht es leider nicht :(Und auch ohne Const kriege ich eine Segmentation Fault

camper

Firefighter schrieb:

Habe ich mich auch gerade gefragt, weil mit const geht es leider nicht

Darf ich das unter "Redewendungen, die ihr hasst" zitieren? :

Firefighter schrieb:

Und auch ohne Const kriege ich eine Segmentation Fault

Was heißt auch? Du kriegst den segfault auch mit const?

Firefighter

@camper:

Kannst du gerne zitieren wenn dich das glücklich macht Aber ich werde mich sofort selber schlagen, weil diese Aussage von mir sehr schwammig war

Nein mit const kriege ich keinen Segmentation Fault.Sondern einen Fehler welchen ich gerade nicht posten kann, da ich das Programm auf arbeit habe.

Firefighter

So da bin ich nochmal mit der Fehlermeldung welche auftritt wenn ich const wieder reinpacke:

D:\Coding\Cpp\LinkedList\LinkedList.h||In member function `LinkedList<T>& LinkedList<T>::swap_list(const LinkedList<T>&) [with T = int]':|

Ich hoffe ihr könnte mir weiterhelfen?
Entschuldigt bitte nochmal meine Ungenauigkeit in den vorherigen Posts.

LordJaxom

Firefighter schrieb:

D:\Coding\Cpp\LinkedList\LinkedList.h||In member function `LinkedList<T>& LinkedList<T>::swap_list(const LinkedList<T>&) [with T = int]':|

Ich hoffe ihr könnte mir weiterhelfen?

Wenn Du jetzt zu der Information, in welcher Funktion der Fehler aufgetreten ist, noch die eigentliche Fehlermeldung schreibst, dann ja :p

Ok, eigentlich brauche ich die garnicht, aber Du willst ja sicher auch lernen die Fehlermeldungen richtig einzuordnen. Das Problem ist, dass Du an einem konstanten Objekt nichts ändern kannst (logisch, oder?), also auch nichts tauschen. Da müssen wir an der non-const Version weiterforschen.