[C++11] Double Linked List

Übersicht Andere Dialekte Codearchiv

Neue Antwort erstellen

 

CO2

ehemals "SirMO"

Betreff: [C++11] Double Linked List

BeitragSo, Jun 05, 2016 17:56
Antworten mit Zitat
Benutzer-Profile anzeigen
Hallo Leute,

hier mal ein Include der dem ein oder anderen vielleicht das Leben erleichtert: Eine Double-Linked-List mit dynamischer Sortier- und Suchfunktion Code: [AUSKLAPPEN]
#pragma once
#include <utility>
#include <functional>

template <class T>
class CLinkedList
{
private:
   struct CListItem
   {
      CListItem *m_pNext;
      CListItem *m_pPrev;
      T         *m_pContent;
   };

   CListItem      *m_pFirst;
   CListItem      *m_pLast;
   unsigned int   m_iCount;
   bool           m_bDelete;

public:
   CLinkedList(bool bDelete = false)
   {
      this->m_pFirst = nullptr;
      this->m_pLast = nullptr;
      this->m_iCount = 0;
      this->m_bDelete = bDelete;
   }

   ~CLinkedList()
   {
      this->Clear();
   }

public:
   T *operator[](unsigned int index)
   {
      return GetAt(index);
   }

private:
   CListItem *GetAtTemp(unsigned int index)
   {
      if (index >= this->m_iCount)
         return nullptr;

      CListItem *pRetVal = this->m_pFirst;
      for (unsigned int x = 0; x < index; x++)
         pRetVal = pRetVal->m_pNext;

      return pRetVal;
   }

public:
   void Swap(unsigned int idx1, unsigned int idx2)
   {
      if (idx1 >= this->m_iCount || idx2 >= this->m_iCount)
         return;

      if (idx1 == idx2)
         return;

      CListItem *li1 = this->GetAtTemp(idx1);
      CListItem *li2 = this->GetAtTemp(idx2);
      if (li1 && li2)
         std::swap(li1->m_pContent, li2->m_pContent);
   }

   unsigned int GetCount()
   {
      return this->m_iCount;
   }

   void Add(T *newElem)
   {
      CListItem *pNewListItem    = new CListItem;
      pNewListItem->m_pContent   = newElem;

      if (m_iCount == 0)
      {
         m_pFirst                = pNewListItem;
         m_pLast                 = pNewListItem;
         pNewListItem->m_pNext   = m_pLast;
         pNewListItem->m_pPrev   = m_pFirst; 
      }
      else
      {
         pNewListItem->m_pPrev   = m_pLast;
         m_pLast->m_pNext        = pNewListItem;
         pNewListItem->m_pNext   = m_pFirst;
         m_pLast                 = pNewListItem;
      }

      m_iCount++;
   }

   T *GetAt(unsigned int index)
   {
      CListItem *pListItem = this->GetAtTemp(index);
      return (pListItem ? pListItem->m_pContent : nullptr);
   }

   void RemoveAt(unsigned int index)
   {
      if (index >= m_iCount)
         return;

      CListItem *pListItem = this->GetAtTemp(index);
      if (pListItem)
      {
         pListItem->m_pNext->m_pPrev = pListItem->m_pPrev;
         pListItem->m_pPrev->m_pNext = pListItem->m_pNext;

         if (m_pFirst == pListItem)
         {
            m_pFirst = pListItem->m_pNext;
            m_pLast->m_pNext = pListItem->m_pNext;
         }
         if (m_pLast == pListItem)
         {
            m_pLast = pListItem->m_pPrev;
            m_pFirst->m_pPrev = pListItem->m_pPrev;
         }

         if (m_bDelete)
            delete pListItem->m_pContent;

         delete pListItem;
         pListItem = nullptr;

         m_iCount--;
      }
   }

   void Clear()
   {
      for (int x = GetCount(); x >= 0; x--)
         this->RemoveAt(x);
   }

   void SortEx(std::function<bool(T* left, T* right)> compare)
   {
      for (unsigned int n = m_iCount; n > 1; n--)
      {
         for (unsigned int i = 0; i < n - 1; i++)
         {
            if (compare(this->GetAt(i), this->GetAt(i + 1)))
               this->Swap(i, i + 1);
         }
      }
   }

   // Aufruf: Liste.SortM(&CKlasse::Membername, [true | false])
   template <class CLASS, class MEMBERTYPE>
   void SortM(MEMBERTYPE CLASS::*member, bool bUp)
   {
      if (bUp)
         SortEx([&](CLASS *left, CLASS *right){ return left && right && left->*member > right->*member; });
      else
         SortEx([&](CLASS *left, CLASS *right){ return left && right && left->*member <= right->*member; });
   }

   // Aufruf: Liste.SortF(&CKlasse::Membermethode, [true | false])
   template <class CLASS, class FUNCTIONRETURN>
   void SortF(FUNCTIONRETURN (CLASS::*func)(), bool bUp)
   {
      if (bUp)
         SortEx([&](CLASS *left, CLASS *right){ return left && right && (left->*func)() > (right->*func)(); });
      else
         SortEx([&](CLASS *left, CLASS *right){ return left && right && (left->*func)() <= (right->*func)(); });
   }

   T *FindEx(std::function<bool(T *cmp)> compare)
   {
      for (unsigned int x = 0; x < this->m_iCount; x++)
      {
         if (compare(GetAt(x)))
            return GetAt(x);
      }

      return nullptr;
   }

   // Aufruf: Liste.FindM(&CKlasse::Membername, Suchwert)
   template <class CLASS, class MEMBERTYPE>
   T* FindM(MEMBERTYPE CLASS::*member, MEMBERTYPE value)
   {
      return FindEx([&](CLASS *pCompare){ return pCompare && pCompare->*member == value; });
   }

   // Aufruf: Liste.FindF(&CKlasse::Membermethode, Suchwert)
   template <class CLASS, class FUNCTIONRETURN>
   T* FindF(FUNCTIONRETURN (CLASS::*func)(), FUNCTIONRETURN value)
   {
      return FindEx([&](CLASS *pCompare){ return pCompare && (pCompare->*func)() == value; });
   }
};


Und noch der Beispielcode dafür Code: [AUSKLAPPEN]
#include "stdafx.h"

#include "linkedlist.h"

class CFoo
{
public:
   int m_Bar;

public:
   CFoo(int val)
   {
      this->m_Bar = val;
   }

   int GetBar()
   {
      return m_Bar;
   }
};


int main()
{
   CLinkedList<CFoo> List(true);

   List.Add(new CFoo(4));
   List.Add(new CFoo(2));
   List.Add(new CFoo(5));
   List.Add(new CFoo(6));

   printf("Debug:\n");
   for (int x = 0; x < List.GetCount(); x++)
      printf("%d\n", List.GetAt(x)->m_Bar);
   printf("\n");

   List.SortM(&CFoo::m_Bar, true);

   printf("Debug:\n");
   for (int x = 0; x < List.GetCount(); x++)
      printf("%d\n", List.GetAt(x)->m_Bar);
   printf("\n");

   List.SortF(&CFoo::GetBar, false);

   printf("Debug:\n");
   for (int x = 0; x < List.GetCount(); x++)
      printf("%d\n", List.GetAt(x)->m_Bar);
   printf("\n");

   CFoo *pFoo = List.FindF(&CFoo::GetBar, 5);
   if (pFoo)
      printf("Gefunden (%d)!", pFoo->m_Bar);

   pFoo = List.FindM(&CFoo::m_Bar, 2);
   if (pFoo)
      printf("Gefunden (%d)!", pFoo->m_Bar);

   return 0;
}


Viel Spaß!

UPDATE: Bug gefixt, bei dem es zu einem Absturz kam, sobald man das erste Element gelöscht hat Embarassed
mfG, CO²

Sprachen: BlitzMax, C, C++, C#, Java
Hardware: Windows 7 Ultimate 64-Bit, AMX FX-6350 (6x3,9 GHz), 32 GB RAM, Nvidia GeForce GTX 750 Ti
  • Zuletzt bearbeitet von CO2 am Mo, Jun 06, 2016 7:53, insgesamt 2-mal bearbeitet

Xeres

Moderator

BeitragSo, Jun 05, 2016 18:19
Antworten mit Zitat
Benutzer-Profile anzeigen
~VERSCHOBEN~


Ich verstehe von C++ nicht genug um den Beitrag zu bewerten.
Was mir auffällt ist, das die Funktionen und deren Parameter nicht Kommentiert sind.
Win10 Prof.(x64)/Ubuntu 16.04|CPU 4x3Ghz (Intel i5-4590S)|RAM 8 GB|GeForce GTX 960
Wie man Fragen richtig stellt || "Es geht nicht" || Video-Tutorial: Sinus & Cosinus
T
HERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)
 

CO2

ehemals "SirMO"

BeitragSo, Jun 05, 2016 21:39
Antworten mit Zitat
Benutzer-Profile anzeigen
Huch, bin ich im falschen Unterforum gelandet... Danke für's verschieben Wink

Die Dokumentation über die Methoden und deren Parameter habe ich im Angesicht der Größe des Codes vernachlässigt. Sollte eigentlich größtenteils selbsterklärend sein.
mfG, CO²

Sprachen: BlitzMax, C, C++, C#, Java
Hardware: Windows 7 Ultimate 64-Bit, AMX FX-6350 (6x3,9 GHz), 32 GB RAM, Nvidia GeForce GTX 750 Ti

Thunder

BeitragMo, Jun 06, 2016 0:53
Antworten mit Zitat
Benutzer-Profile anzeigen
Ich nehme an, das ist ein Lernprojekt von dir? Denn wenn man etwas sinnvolles machen will, sollte man zu std::list greifen, oder besser std::vector.

Wenn es dich interessiert, ich habe Mal darüber gesehen und schreibe was mir so aufgefallen ist. Ich hab aber nicht ganz genau geschaut (nur syntaktisch - den Code nicht wirklich nachvollzogen, ausgenommen die einfachen Methoden).

Fehler?

1. Zuweisungen in ifs
Code: [AUSKLAPPEN]
         if (m_pFirst = pListItem) // = statt ==
         {
            m_pFirst = pListItem->m_pNext;
            m_pLast->m_pNext = pListItem->m_pNext;
         }
         if (m_pLast = pListItem)  // = statt ==
         {
            m_pLast = pListItem->m_pPrev;
            m_pFirst->m_pPrev = pListItem->m_pPrev;
         }


Falls gewünscht, wird es üblicherweise doppelt geklammert:

Code: [AUSKLAPPEN]
if((m_pLast = pListItem){ ...


2. Signedness: GetCount() liefert int, aber die Variable m_iCount, die zurückgeliefert wird, ist unsigned int.

Stil (wichtig)

1. CLinkedList, CListItem? Ich bin ja nicht so, aber ich denke dass einige C++ Programmierer dich nicht ernst nehmen, wenn du dich an Java Konventionen hältst.

2. üblicherweise (in den Standard Containern) sind Längen bzw. Indizes vom Typ size_t statt unsigned int.

3. Mehrere public/private/protected Labels sind unüblich (afaik) und machen den Code weniger leicht zu lesen.

4. Kein Copy-Konstruktor? Move-Konstruktor wäre natürlich auch fein, aber das ist etwas schwieriger.

Stil (weniger wichtig)

1. operator[] liefert Zeiger zurück. Also bei einer CLinkedList<int> bekomme ich bei dir ein int*. Bei Standard Containern bekommt man int&. Aber im Prinzip dokumentiert das der Code eh.
Aber ich schätze Mal, du wolltest auf diese Weise den Exceptions entfliehen.

2. Du hast ein paar schöne Gelegenheiten, auto zu verwenden, nicht genutzt Very Happy beispielsweise:
Code: [AUSKLAPPEN]
for (auto x = GetCount(); x >= 0; x--)  // auto statt int
         this->RemoveAt(x);
OpenSource FTW! -- GPL ist restriktiv -- verwendet MIT oder BSD Lizenzen
Meine Sachen: https://github.com/chtisgit
 

CO2

ehemals "SirMO"

BeitragMo, Jun 06, 2016 7:53
Antworten mit Zitat
Benutzer-Profile anzeigen
Hallo Thunder.

Vielen Dank für dein Code-Review Wink

Hier mal ein paar Rechtfertigungen und Einsichten:
1. Zuweisungen in Ifs: An der Stelle ist mein Code natürlich Cappes, das soll ein Vergleich sein. Ich update das im Original-Post.
2. Das mit GetCount() ist mir aufgefallen und bereits geändert, der Code im Original-Post wird abgeändert.
3. size_t kann man natürlich nehmen, muss man aber nicht. Ich habe es lieber solche Sachen in den Standard-Typen zu machen, statt in typedefs oder anderen Klassen oder Strukturen.
4. Den kann ich noch nachziehen, habe ich für das Beispiel jedoch nicht gebraucht. (Wo wir bei der Beantwortung deiner ersten Frage wären: Ich nehme an, das ist ein Lernprojekt von dir? - Eher weniger. Ein Freund hatte mich darum gebeten, es ging prinzipiell um die Nutzung der std::function<>()-Parameter. Deshalb ist die Klasse auch nur rudimentär umgesetzt (Was auch den fehlenden Copy-Konstruktor erklärt))

Stil (II):
1. Jep, exakt.
2. auto finde ich persönlich eher unprofessionell: Wenn ich weiß, welchen Datentyp ich brauche, wieso sollte ich dem Compiler freistellen irgendeinen zu nutzen?
mfG, CO²

Sprachen: BlitzMax, C, C++, C#, Java
Hardware: Windows 7 Ultimate 64-Bit, AMX FX-6350 (6x3,9 GHz), 32 GB RAM, Nvidia GeForce GTX 750 Ti

Thunder

BeitragMo, Jun 06, 2016 18:01
Antworten mit Zitat
Benutzer-Profile anzeigen
CO2 hat Folgendes geschrieben:
3. size_t kann man natürlich nehmen, muss man aber nicht. Ich habe es lieber solche Sachen in den Standard-Typen zu machen, statt in typedefs oder anderen Klassen oder Strukturen.


size_t ist standard Wink
Siehe: http://stackoverflow.com/quest...ize-t-in-c

Zitat:

2. auto finde ich persönlich eher unprofessionell: Wenn ich weiß, welchen Datentyp ich brauche, wieso sollte ich dem Compiler freistellen irgendeinen zu nutzen?


Er nutzt ja dann nicht irgendeinen, sondern evaluiert die rechte Seite der Zuweisung (dann weiß er den Typ von dem was rechts steht), und auf Basis von einigen Regeln leitet er einen Typen für das neu definierte Objekt ab - das ist wohldefiniert Very Happy

Wenn du auto x = GetCount(); definierst und GetCount() liefert int, dann kriegt x den Typ int, wenn es unsigned int liefert, bekommt x den Typ unsigned int. Das bedeutet weniger Code umschreiben bei einer Typ-Umstellung.

Die primäre Rechtfertigung ist: Der Compiler weiß den Typen eh und dem Programmierer kann der Name (des Typen) eigentlich egal sein, er muss nur wissen, wie er mit ihm umgehen muss (Methoden etc).

Aber ich verstehe es auch, wenn man auto nicht unbedingt verwenden will.
Einen so großen Anhänger wie mich kenne ich noch nicht...
Ich finde es aber schön, dass C++ jetzt nicht mehr so aussehen muss wie vor 20 Jahren.
OpenSource FTW! -- GPL ist restriktiv -- verwendet MIT oder BSD Lizenzen
Meine Sachen: https://github.com/chtisgit
 

CO2

ehemals "SirMO"

BeitragMo, Jun 06, 2016 18:09
Antworten mit Zitat
Benutzer-Profile anzeigen
Hallo Thunder,

ok, übergeredet, schreibe meinen Code zu size_t um, siehe Original-Post Very Happy
EDIT: Einmal geschaut, was size_t wirklich ist und ich zitiere die Code-Stelle Code: [AUSKLAPPEN]
typedef unsigned int     size_t;
Daraus folgt: Ohne es zu wissen alles richtig gemacht, also warum ändern?

Bei dem auto bleibe ich skeptisch: Auf der einen Seite ist es durchaus richtig, dass man nicht 1000 Stellen im Code abwandeln muss, wenn sich ein Datentyp ungünstig ändert. Auf der anderen Seite ist es aber auch unschön und kann bestimmt unübersichtlich werden, wenn man 1000 x auto benutzt, statt konkreter Datentypen. Plus wenn sich der Datentyp drastisch ändert, beispielsweise von int auf double muss man ohnehin alle Stellen überprüfen, die die entsprechende Variable nutzen. Jetzt könnte man sagen, dass sich ein Datentyp nicht so drastisch ändern kann, weil man vorher ja alles durchgeplant hat. Wenn man das sagt, sollte man auch beachten, dass wenn man int in unsigned int ändert, auch keinen Plan vorher hatte.

C++ vor 20 Jahren: Man musste dem C++ vor 20 Jahren jedoch lassen, dass es noch nicht ganz so weit gewachsen war. Das Problem an C++ ist sein hoher Bekanntheitsgrad: Viele wollen viel aus der Sprache rausholen, raus kommt eine unübersichtliche Sonderzeichenschlacht (wenn man sich beispielsweise Templates, oder wie oben std::function()s anschaut).
mfG, CO²

Sprachen: BlitzMax, C, C++, C#, Java
Hardware: Windows 7 Ultimate 64-Bit, AMX FX-6350 (6x3,9 GHz), 32 GB RAM, Nvidia GeForce GTX 750 Ti

Thunder

BeitragMo, Jun 06, 2016 19:08
Antworten mit Zitat
Benutzer-Profile anzeigen
Hinter dem typedef steckt der Grund, dass du ja <cstdlib> inkludierst und von dort bekommst du das typedef für size_t.
Jetzt kann aber die stdlib.h bzw stddef.h von Platform zu Platform unterschiedlich sein.
Zitat:
size_t (unsigned __int64 or unsigned integer, depending on the target platform)

Microsoft: https://msdn.microsoft.com/en-...b6b3k.aspx
Auf 32 bit PC war int ja 4 byte groß. Microsoft hat auf 64 bit int 4 byte groß belassen (afaik), während Linux auf 8 byte gegangen ist.
D.h. das size_t ist eine Abstraktion für die Benutzer der Standard Library. btw. ich habe vor kurzem etliche int Variablen im BlitzMax Compiler als size_t deklariert (wegen dieser Sache).

auto: ja bei primitiven Datentypen kommt der Nutzen nicht so hervor.
Ich finde es aber ziemlich hilfreich, also ich kann dem Compiler sagen: gib der Variablen genau den Typen des Ausdrucks, den ich dir gebe.
Vielleicht solltest du darauf verzichten, Code von mir zu lesen, wenn dir auto nicht gut bekommt Very Happy
OpenSource FTW! -- GPL ist restriktiv -- verwendet MIT oder BSD Lizenzen
Meine Sachen: https://github.com/chtisgit

Neue Antwort erstellen


Übersicht Andere Dialekte Codearchiv

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group