Verkettete Liste - Entfernen von Elementen

Scorcher24

Grüss euch. Ich hab mir eine verkettete Liste in einer Klasse geschrieben, funktioniert soweit auch wunderbar.
Nur mit dem entfernen von Daten hab ich noch meine Probleme.
Hier erstmal die entsprechenden Daten für euch:

template <typename T>
class dtListData
{
public:
    inline dtListData()
    {
        m_data = NULL;
        m_next = NULL;
        m_prev = NULL;
        m_ordinal = 0;
    }

    inline ~dtListData()
    {
        dtDelete(m_data);
    }

    /** @brief Returns a Pointer to the Data of this Object. */
    inline T* getData()
    {
        return m_data;
    }

    /** @brief Returns the Ordinal Number */
    inline UINT getOrdinal()
    {
        return m_ordinal;
    }

    /** @brief Returns the next entry of the list */
    inline dtListData<T>* getNext()
    {
        return m_next;
    }

    /** @brief Returns the previous entry of the list */
    inline dtListData<T>* getPrevious()
    {
        return m_prev;
    }

private:
    UINT m_ordinal;
    T*   m_data;
    dtListData<T>* m_next;
    dtListData<T>* m_prev;

    friend dtList<T>;
};

ZUr Erklärung:
Das ist die Klasse die die tatsächlichen Daten erhält und dann im Speicher als Element abgelegt wird.
m_ordinal ist hierbei einfach eine Nummer die vergeben wird, um die Elemente nacher auf eine schnelle Weise zu identifizieren.
m_next ist ein Zeiger auf das nächste Element.
m_prev ist ein Zeiger auf der vorige Element.
Die 2 Zeiger sind nützlich um schneller durch die Liste zu iterieren. Ich hab in der Klasse dtList einen Zeiger auf die Liste, der sich nur bewegt, wenn gesucht wird. Ich entscheide dann einfach nach der OrdinalZahl ob ich nach vorne oder rückwärts suche... zumindest glaub ich, dass es schnell ist :D.

Hier jetzt die Listen-Klasse:

template <typename T>
class dtList
{
public:
    inline dtList()
    {
        [..]
    }

    inline ~dtList()
    {
        [..]
    }

    /** @brief Adds an Entry to the List
      * @param data A pointer to the Data
      * @return The ordinal number of the object.
      */
    inline UINT add(const T* data)
    {
        [..]
    }

    /** @brief Removes an Item by its ordinal number.
      * @param ordinal The item to remove by ordinal.
      * @bug After an element has been deleted, the pointers of
      * the prev. element still point to this element.
      */
    inline void remove(const UINT ordinal)
    {
        dtListData<T>* element = NULL;
        element = this->getListData(ordinal);

        if (element != NULL)
        {
            element->m_prev->m_next = element->m_next;
            element->m_next->m_prev = element->m_prev;
            delete element;
            m_size--;
        }
    }

    /** @brief Returns the First Node 
      *
      */
    inline dtListData<T>* getFirst() const
    {
        return m_first;
    }

    /** @brief Returns the Data of the named object.
      * @param ordinal The ordinal number of the object.
      * @return A pointer to the data or NULL if not found.
      */
    inline T* getData(const UINT ordinal) 
    {
        [..]
    }

    /** @brief Returns the Number of Nodes in the List
      * @return The size of the list. May be zero.
      */
    inline UINT getSize() const
    {
        return m_size;
    }

    /** @brief Returns the dtListData Element by ordinal Number
      * @param index The number of the node you search.
      * @param reset If you set this to true, the search will start from the first entry.
      */
    dtListData<T>* getListData(const UINT index, const bool reset = false)
    {
        [..]
    }

    /** @brief Searches for a node by data
      * @param A pointer to the Data searched.
      */
    inline dtListData<T>* search(const T* data)
    {
        [..]
    }

private:
    dtListData<T>* m_first;
    dtListData<T>* m_list;
    dtListData<T>* m_iterator;
    UINT m_size;   
};

Die Funktion remove() ist das Problem.
Das entfernen und freigeben des Speichers funktioniert soweit, nur zeigt der m_next und m_prev Zeiger des vorigen bzw nächsten Objekts immer noch auf das gelöschte Objekt... Wie schreibe ich das jetzt um, damit die Zeiger nicht auf die entfernten Zeiger zeigen, sondern wirklich auf die Zeiger der nächsten Objekte? Oder steckt der Design-Fehler tiefer?
Danke euch
rya.

crashterpiece

mal grundsätzlich das prinzip

wenn z der zeiger auf das zu löschende element ist

z->next->prev = z->prev
z->prev->next = z->next
delete z

mal es dir auf, dann wirds verständlich

*D*Evil

1. Designfehler: Guck dir mal das Iterator-Pattern an
2. Designfehler: Initialisierungsliste
(3. Designfehler: Orientier dich mal an die Std. Funktionen/Templates)
4. Was ist denn dtDelete?

Scorcher24

@crashinterpiece
mach ich doch so...:
element->m_prev->m_next = element->m_next;
Vom vorherigen Objekt nehm ich den next-Pointer und leg ihn auf das element nach dem zu löschenden Element.

element->m_next->m_prev = element->m_prev;
Vom nächsten Object nehm ich den prev.-Pointer und leg ihn auf das element vor dem zu löschenden Element.

Danach lösch ich das Element. Trotzdem zeigen die Zeiger alle auf NULL, obwohl die elemente davor und danach im Speicher vorhanden sind.

@evil:
zu 2:
Was meinst du damit?

zu 4:
dtDelete ist einfaches Makro:

#define dtDelete(ptr) if (ptr != NULL) delete ptr; ptr = NULL;

rya.

hustbaer

Er meint du sollst eine Initialisierungsliste (initializer list) verwenden:

//inline dtListData()
//{
//    m_data = NULL;
//    m_next = NULL;
//    m_prev = NULL;
//    m_ordinal = 0;
//}
//->
inline dtListData() : 
    m_data(NULL),
    m_next(NULL),
    m_prev(NULL),
    m_ordinal(0)
{
}

Ist aber in dem Fall nicht wichtig. Wichtig ist dass man die Syntax kennt und weiss was der Unterschied ist, damit mans verwenden kann wenn man es braucht (z.B. wenn man Klassen als Member verwenden will die keinen Default Constructor haben, oder const Member).

Weiters:

//#define dtDelete(ptr) if (ptr != NULL) delete ptr; ptr = NULL;
#define dtDelete(ptr) delete ptr; ptr = NULL; // das if braucht man nicht, delete ist OK mit null pointern

hustbaer

p.S.: nochwas: wenn du macros hast die wie Funktionen aufzurufen sind ist es gut wenn du die so schreibst:

#define foo(p) do { delete p; p = 0; } while(0)

Dann funktionieren nämlich u.A. solche Konstrukte wie erwartet:

#define foo(p) do { delete p; p = 0; } while(0)

void bar(int* p)
{
    if (blubb())
        foo(p);
}

Scorcher24

Ach das meinte er... die Mitglieder werden alle auf 0 initialisiert. Das ist bei mir fix drin :D. Wie man sieht hab ich den Konstruktor mit [...] ja auch weggekürzt. Also keine Panik :).
Aber ob classptr(NULL) oder classptr = NULL sollte doch egal sein oder?
Weil der Compiler spuckt ja keine ne Warnung aus. Und der MSVC-Compiler is eigentlich recht pingelig.

#define dtDelete(ptr) delete ptr; ptr = NULL; // das if braucht man nicht, delete ist OK mit null pointern

DAS wusste ich nicht... danke.
rya.

CStoll

Scorcher24 schrieb:

Aber ob classptr(NULL) oder classptr = NULL sollte doch egal sein oder?
Weil der Compiler spuckt ja keine ne Warnung aus. Und der MSVC-Compiler is eigentlich recht pingelig.

Für so triviale Objekte wie Zeiger ist es egal, ob du sie per Initialisierungsliste oder im Ctor-Rumpf auffüllst. Aber bei "größeren" Objekten macht es schon einen Unterschied (in der Laufzeit), ob sie erst default-initialisiert und anschließend überschrieben oder gleich mit dem endgültigen Wert gefüllt werden.
(und dann gibt es noch Referenzen, const-Member und Klassen ohne Default-Ctor - die nur über die Initialisierungsliste vorbelegt werden können)

btw, im Dtor ist es doch egal, wohin dein Zeiger hinterher zeigt - im nächsten Arbeitsschritt wird der sowieso pulverisiert (sprich: anstelle deines Makros reicht ein einfaches delete m_data; aus). Und anstelle des Zeigers würde ich lieber den Wert im Listenelement speichern.

Simon2

hustbaer schrieb:

p.S.: nochwas: wenn du macros hast die wie Funktionen aufzurufen sind ist es gut wenn du die so schreibst:
#define foo(p) do { delete p; p = 0; } while(0)
Dann funktionieren nämlich u.A. solche Konstrukte wie erwartet:
#define foo(p) do { delete p; p = 0; } while(0)

void bar(int* p)
{
    if (blubb())
        foo(p);
}

Interessanter Tipp !!

Würde es nicht reichen, einen eigenen Scope aufzumachen (ohne das do/while) ? Mir fällt jetzt spontan kein Beispiel ein, wo es das nicht das.

Gruß,

Simon2.

(D)Evil schrieb:

2. Designfehler: Initialisierungsliste

Was hat das denn mit Design zu tun?

CStoll

Nein, würde nicht reichen - versuch' doch mal sowas:

#define remove(x) {delete x;x=0;}

if(bed)
  remove(ptr);
else
  cout<<"Ich lebe noch";

Zur Erklärung: Nach dem Präprozessor bleibt davon:

if(bed)
{ delete ptr;ptr=0; }
;
else
  cout<<"Ich lebe noch";

-> der Inhalt des Makros wird als Anweisung im if-Zweig eingetragen, das anschließende Semikolon ergibt eine leere Anweisung - und das else steht plötzlich alleine im Raum.

PS: In C++ würde ich gar kein Makro verwenden, sondern lieber

template<typename T>
void dtDelete(T*& ptr)
{
  delete ptr;
  ptr=0;
}

Scorcher24

Danke für die netten Tips Aber hat jemand eine Lösung für das eigentliche Problem?
Zur Wiederholung:
Nach dem Löschen eines Elements und dem "Umbiegen" der Zeiger, zeigen diese immer noch auf das gelöschte Element... komischerweise.
rya.

CStoll

Das sollten sie aber eigentlich nicht mehr - hast du mal im Debugger verfolgt, was tatsächlich unterwegs passiert?

Scorcher24

Habs jetzt mehrfach durch den Debugger gejagt -> selbes Problem.
Hab dann mal die DLL komplett neu gebaut und den Client -> Problem verschwunden..^^
Ich schätze da war mal wieder der Wurm drin.. trotzdem danke.
rya.

CStoll

Scorcher24 schrieb:

Habs jetzt mehrfach durch den Debugger gejagt -> selbes Problem.

Du solltest nicht nur das Ergebnis im Debugger beurteilen, sondern den Ablauf mal im Detail verfolgen (um zu sehen, wann welche Variablen den Wert verändern)

Hab dann mal die DLL komplett neu gebaut und den Client -> Problem verschwunden..^^
Ich schätze da war mal wieder der Wurm drin.. trotzdem danke.
rya.

Die Liste war in einer DLL? Da könnte es auch sein, daß du mit einer veralteten Version gearbeitet hast.