3. Codereview meiner einfachen generischen Liste

Codereview meiner einfachen generischen Liste

  • ?

    hmmmmm schrieb:

    Ne Liste mit Indexzugriff ist ziemlich abnormal

    Das ist dann keine Liste mehr, sondern ein array/vector :xmas1:

    0
  • V

    Das erste lement sollte den Index 0 haben, wie sonst überall in C auch üblich.

    Die leere Liste sollte keinen Knoten haben, sondern head sollte NULL sein.

    rc = remove(1); wird zu remove(1); Man muß Rückgaben nicht verarbeiten.

    delete (head); wird zu delete head; Die Klammen sind nutzlos und unüblich.

    Einige if-Abfragen können wegfallen.

    Viele while-Schleifen wären lieber for-Schleifen.

    Aus

    while ( tmp != NULL )
        {
            if ( v == tmp->value )
            {
                rc = true;
                break;
            }
            tmp = tmp->next;
        }

        return rc;

    wird

    while ( tmp != NULL )
        {
            if ( v == tmp->value )
            {
                 return true;
            }
            tmp = tmp->next;
        }

        return false;

    Diesen Trick oft verwenden. Das ist inzwischen nicht nur erlaubt (und widerspricht damit den Dogmen des Strukturierten Programmierens), sondern ist sogar erwünscht (und dann trotzdem noch schauen, ob es als for-Schleife hübsch wäre).

    0
  • ?

    Kann man sich nicht auch eine Iterator-Klasse mit überladenem Inkrement/Dekrement, Zuweisungs und Vergleichsoperatoren (== und <, dann std::rel_ops aus utility einbinden) überladen? Mach ich immer so :xmas1:

    0
  • U

    Hi an alle Rückmelder 🙂

    Nun ja, die Methoden waren eben vorgegeben. Daran konnte ich nichts anders machen. Hinsichtlich der Implementation habe ich Eure Anregungen gelesen und freue mich über die Hinweise.

    Grüße
    Uwe Homm

    0
  • K

    Was mir noch aufgefallen ist und bisher nicht genannt wurde: Namen wie __LISTE__ gehören zu den reservierten Namen, die man nicht benutzen sollte. Am besten man lässt alles bleiben, was zwei aufeinanderfolgende Unterstriche enthält oder mit einem Unterstrich gefolgt von einem Großbuchstaben beginnt.

    In echtem Code würde man so'was wie "contains" auch nicht anbieten. Dafür gibt es ja std::find aus <algorithm>. Gut, das erfordert natürlich Iteratoren. Und die würdest Du recht einfach mit Hilfe der Boost-Iterator-Bibliothek bauen können (unter Verwendung von boost::iterator_facade). Als Fingerübung ist das schonmal nicht schlecht. Aber man muss das Rad ja auch nicht neu erfinden; denn es gibt ja schon std::list mit einem schön ausgeklügeltem Interface.

    Ich sehe gerade noch remove(int pos). Das ist natürlich großer Käse. Der Parameter sollte hier ein Iterator sein.

    0
  • C
    Mod

    #7: __LISTE__ ist ein reservierter Bezeichner
    #10: NULL ist in <clocale>, <cstddef>, <cstdlib>, <cstring>, <ctime>, <cwchar> und ggf. <cstdio> zu finden
    #19: Da Element ohnehin eine private verschachtelte Klasse ist, scheint mir die Kombination alles private+friend überflüssig zu sein. Ein einfaches struct mit public Zugriff erfüllt den gleichen Zweck. Zweckmäßig wäre aber ggf. ein geeigneter Konstruktor, um das Listenelement gleich initialisieren zu können.
    #29: void in Funktionsparameterlisten ist in C++ überflüssig.
    #30: Dazu hat volkard schon etwas gesagt. Wenn schon ein dummy-Element benutzt werden soll, ist es i.d.R. empfehlenswert, dieses in das Klassenobjekt direkt einzubetten.
    #30: Die Verwendung der Initialisierungsliste ist zu empfehlen.
    #38: Hier wird Code dupliziert. Ein Aufruf von clearList ist empfehlenswert.
    #44: Ich vermisse einen Copy-Konstruktor und einen Zuweisungsoperator. Ein swap wäre auch nicht schlecht.
    #156: Hier wird ggf. der Wert eines nicht initialisierten Objektes zurückgegeben, das erzeugt undefiniertes Verhalten. rc sollte erst definiert werden, wenn es initialisiert werden kann. In dieser Zeile müsste return T(); stehen.

    Volkard hat noch ein paar mehr Tipps gegeben.
    Hier ein Beispiel, wie ein geeignet geschriebener Konstruktor für Element die Angelegenheit verweinfachen kann:

    struct Element
    {
        Element(const T& v, Element* next = NULL)
            : next(next), value(v)
        {}
        Element* next;
        T value;
    };
[...]
    void add(const T& v){
        head->next = new Element(v, head->next);
        ++count;
    };
    0 

  • T remove(unsigned int pos){ 

         //1. Fall: Die Position gibt es nicht oder die Liste ist leer 
         if ( pos > count || count==0 ) 
             return rc; 

         //2. Fall: Das erste LE entfernen 
         if ( pos == 1) 
         { 
             // ...
             return rc; 
         } 

         //3. Fall: LE irgendwo in der Mitte 
         if ( pos > 1 ) 
         { 
             // ...
             return rc; 
         } 
     };

    Das ist Käse.

    Erstmal ist der Fall pos == 0 nicht abgedeckt.
    Und dann schreibt man exklusiv-oder Bedingungen üblicherweise mit "if-else-if". Und wenn es eine letzte Bedingung gibt, die "den ganzen Rest" einschliesst, dann schreibt man einfach nur mehr "else".
    Sieht dann so aus:

    T remove(unsigned int pos){ 
         if (pos == 0)
             return T(); // fehler irgendwie behandeln
         else if (pos > count)  // das || count == 0 können wir uns sparen
             return T(); // fehler irgendwie behandeln
         else if (pos == 1) 
         { 
             return WasAuchImmer; 
         } 
         else
         { 
             return WasAuchImmerAnderes; 
         } 
     };

    Und wenn du dann noch bei 0 zu zählen anfängst, wie schon vorgeschlagen wurde, wird die Funktion noch einfacher.

    0
  • ?

    hustbaer schrieb:

    Erstmal ist der Fall pos == 0 nicht abgedeckt.

    Wie mich das aufregt!! Es ist viel schöner, wenn du

    if(!pos)

    statt

    if(pos == 0)

    schreibst. :xmas1:

    0
  • ?

    camper schrieb:

    #19: Da Element ohnehin eine private verschachtelte Klasse ist, scheint mir die Kombination alles private+friend überflüssig zu sein. Ein einfaches struct mit public Zugriff erfüllt den gleichen Zweck. Zweckmäßig wäre aber ggf. ein geeigneter Konstruktor, um das Listenelement gleich initialisieren zu können.

    Ich würde ja gleich noch einen Destruktor setzen :xmas1:

    struct Element 
  { 
    // Konstruktor

    ~Element(){
      delete next;
    }

    Element* next; 
    T value; 
  };

    Dann vereinfacht sich der Destruktor der Liste zu:

    ~Liste(){
  delete head;
}

    Aber Achtung beim Löschen eines Elementes aus der Liste, nicht das man sich dann die Liste komplett löscht 😉

    0

  • Hacker schrieb:

    hustbaer schrieb:

    Erstmal ist der Fall pos == 0 nicht abgedeckt.

    Wie mich das aufregt!! Es ist viel schöner, wenn du

    if(!pos)

    statt

    if(pos == 0)

    schreibst. :xmas1:

    Ich hoffe das war ein Scherz.
    Dinge die ganz Klar "Nummern" sind, prüfe ich *nie* mit "!".

    Wenn es ein int-Cookie ist, wo der Wert Null "nix" bedeutet, dann OK. Wenn es ein Zeiger oder Handle ist OK. bool sowieso. Auch Dinge wie Timer-IDs etc. Alles wo "0" halt heisst "hier ist nix", und andere Werte keine Bedeutung haben, ausser halt irgendwas zu referenzieren.

    Aber nen Index mit "!" zu prüfen. Alter Schwede, wenn ich sowas wo lese geht mir der Hut hoch.
    Das ist fast so schlimm wie if (v.size() + 1 > n) und Dergleichen.

    0
  • 3

    Was deine Memberfunktionen angeht, kann ich nur sagen, dass das alles eher nach einem Vector/Array klingt, als nach einer Liste. Die Funktionsnamen klingen auch sehr nach Java, wobei die Liste in Java einfach komplett falsch designt ist.

    Ich hab hier mal eine Liste implementiert, du kannst sie ja zur Not selbst erweitern um die gefragten Funktionen, auch, wenn das schwachsinnig ist.

    Wir fangen an mit einer Liste, wo alles public ist. Um Kapselung kümmern wir uns später.

    template <typename T> // Ob typename oder class ist grundsätzlich egal, ich bevorzuge typename, weil es meine Intention, einen beliebigen Typen zuzulassen, besser ausdrückt.
struct list
{
	struct node
	{
		node* next;
		T value;
	};

	std::size_t size; // std::size_t ist ein typedef aus <cstddef> und wird gerne für Größenangaben verwendet. size_t ist immer ein unsigned Datentyp, meist unsigned long long int.

	node first;
	node last;
};

    Ich speichere hier 2 Knoten. Der Grund ist, dass ich mich dadurch bei allen Operationen nur noch zwischen zwei Knoten befinde. Damit fallen alle Sonderfälle weg, was unseren Code erheblich einfacher und noch dazu flotter macht. Eine leere Liste besteht also aus zwei miteinander verketteten Knoten.

    Als Nächstes sollten wir node einen Konstruktor verpassen. Im Konstruktor übergeben wir den Knoten, an dem eingefügt werden soll. Der neue Knoten hängt sich dann selbstständig ein. Außerdem müssen wir noch den Wert des Elements übergeben.

    node(node* prev, T const& value)
	: next(prev->next)
	, value(value)
{
	prev->next = this;
}

    Jetzt wirds Zeit, auch der Liste einen Konstruktor zu verpassen. Den Destruktor heben wir uns erstmal für später auf.

    list()
	: size(0)
{
	first.next = &last; // Wir verketten den ersten mit dem letzten Knoten und haben nun eine leere Liste.
	// Manch einer mag hier auf die Idee kommen, ein "last.next = 0" hinzuzufügen. Dies ist jedoch nicht erforderlich, da wird diesen Zeiger nie anrühren!
}

    Leider haben wir jetzt ein neues Problem: Unsere Knoten-Klasse hat keinen Default-Konstruktor. Also schnell einen bauen, er tut einfach gar nichts. Auch hier brauchen wir die Zeiger nicht 0-setzen.

    node()
{}

    Zeit, eine erste Memberfunktion hinzuzufügen. Ich halte mich hier an die STL und bastle als erstes eine push_front Funktion. Sie fügt ein Element am Anfang der Liste ein, also immer genau nach first.

    void push_front(T const& value)
{
	new node(&first, value);
	++size; // Das erhöhen der Größe geschieht nach dem new, damit die Größe auch stimmt, falls new bad_alloc wirft, weil nicht mehr genug Speicher da ist.
}

    Zeit, unsere Liste zu testen! Wir erstellen ein kleines Testprogramm, das die Zahlen von 1 bis 20 einfügt und danach über die Liste iteriert und alle Elemente ausgibt.

    #include <iostream>
#include <cstddef>

template <typename T>
struct list
{
	struct node
	{
		node(node* prev, T const& value)
			: next(prev->next)
			, value(value)
		{
			prev->next = this;
		}

		node()
		{}

		node* next;
		T value;
	};

	list()
		: size(0)
	{
		first.next = &last;
	}

	void push_front(T const& value)
	{
		new node(&first, value);
		++size;
	}

	std::size_t size;

	node first;
	node last;
};

int main()
{
	list<int> l;

	for(int i = 1; i <= 20; ++i)
		l.push_front(i);

	for(list<int>::node* p = l.first.next; p != &l.last; p = p->next)
		std::cout << p->value << ' ';
}

    20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

    Es funktioniert! 🤡

    Weiter gehts dann in Teil 2 mit pop_front und geeignetem Destruktor. Außerdem werden wir erste Mühen in Kapselung stecken.

    0
  • C
    Mod

    0
  • 3

    Machen wir gleich weiter mit pop_front. pop_front löscht das erste Element aus der Liste und verringert damit die Größe der Liste um eins. Nichts leichter als das.

    void pop_front()
{
	node* temp = first.next; // Zu löschenden Knoten zwischenspeichern
	first.next = temp->next; // Zweiten Knoten als ersten einhängen
	--size; // Diesmal müssen wir die Größe vor dem delete erniedrigen. Das Element wurde ja schon entfernt, bevor delete eine Exception werfen könnte.
	delete temp; // Knoten löschen
}

    Bevor wir uns an einen Destruktor für die Liste wagen, kapseln wir erstmal den size-Member. Die STL bietet uns 2 Funktionen, die mit size in Zusammenhang stehen: .size() und .empty(). Was die Funktionen tun, sollte selbsterklärend sein. Das Problem mit .size() ist, dass wir unseren Member bereits size genannt haben. Ich versuche mir gerade die Konvention anzugewöhnen, allen Membervariablen einen _ nachzustellen. Wir machen das hier nun auch einfach so und benennen size in size_ um, alle anderen Membervariablen natürlich auch so.

    bool empty() const // Die Funktion verändert das Objekt nicht, also markieren wir sie als const
{
	return size_ == 0;
}

std::size_t size() const // Auch hier const nicht vergessen
{
	return size_;
}

    Damit könnten wir schon einen Destruktor implementieren, allerdings implementiere ich zuerst .clear(), welche wir dann einfach im Destruktor aufrufen können. clear leert, wie der Name schon sagt, die komplette Liste.

    void clear()
{
	// Wenn wir das so machen, ist es langsamer, als einfach alle Knoten direkt zu löschen, da pop_front noch Zeiger umhängt. Ich vernachlässige diesen Overhead fürs erste.
	while(!empty())
		pop_front();
}

    Nun ist der Destruktor der Liste auch nicht mehr schwer:

    ~list()
{
	clear();
}

    In Teil 3 gehts dann weiter mit Iteratoren, damit wir auch first und last private machen können und ein STL-Interface haben.

    0
  • 3

    Was bringt uns der beste Container, wenn wir uns als Benutzer mit Internas wie einer Knoten-Klasse herumschlagen müssen? Jetzt ist es an der Zeit, Iteratoren für unsere Liste zu implementieren. Ein Iterator ist einem Zeiger sehr ähnlich: Er lässt sich mit ++ erhöhen und mit * kommen wir an das Element. Der -> Operator funktioniert ebenfalls ähnlich einem Zeiger. Mehr zu Iteratoren findest du hier.

    Die Iterator-Klasse stecken wir auch einfach in die Listen-Klasse hinein.

    struct iterator
{
	iterator(node* pos)
		: pos_(pos)
	{}

	iterator& operator ++ () // Präfix-Inkrement
	{
		pos_ = pos_->next_; // Wenn der User ++ schreibt, gehen wir einfach zum nächsten Knoten.
		return *this;
	}

	iterator operator ++ (int) // Postfix-Inkrement
	{
		iterator temp(*this);
		++*this;
		return temp;
	}

	T& operator * () // non-const Version
	{
		return pos_->value_;
	}

	T const& operator * () const // const-Version
	{
		return pos_->value_;
	}

	T* operator -> () // Auch hier wieder eine non-const Version...
	{
		return &*this;
	}

	T const* operator -> () const // ... und eine const-Version
	{
		return &*this;
	}

	friend bool operator == (iterator const& first, iterator const& second)
	{
		return first.pos_ == second.pos_;
	}

	// Eigentlich müsste man den Kollegen gar nicht zum Freund erklären, aber damit man ihn ins selbe Arbeitszimmer setzen kann, machen wir eine Ausnahme.
	friend bool operator != (iterator const& first, iterator const& second)
	{
		return !(first == second);
	}

private:
	node* pos_; // Ein Iterator speichert sich den Knoten, an dem er sich gerade befindet.
};

    Falls du hier mit fragendem Gesicht vor dem Bildschirm sitzt: In diesem Artikel wird auf die Überladung von Operatoren eingegangen.

    Damit der User sich nun auch Iteratoren holen kann, müssen wir ihm die Funktionen begin() und end() zur Verfügung stellen. begin() gibt einen Iterator auf das erste Element (also das Element nach first_) zurück, end() einen Iterator eins hinter das letzte Element, also auf last_.

    iterator begin()
{
	return iterator(first_.next_);
}

iterator end()
{
	return iterator(&last_);
}

    Damit können wir first_ und last_ private machen und die Liste wieder einmal testen. Wir nehmen den Code von letztem mal her und ändern die Ausgabeschleife wie folgt ab:

    for(list<int>::iterator iter = l.begin(); iter != l.end(); ++iter)
	std::cout << *iter << ' ';

    Wir können jetzt sogar schon einige STL-Algorithmen mit unserer Liste verwenden. Wie wäre es mit dem Durchschnitt aller Werte?

    std::cout << std::accumulate(l.begin(), l.end(), 0) / static_cast<double>(l.size());

    std::accumulate aus dem Header <numeric> addiert alle Werte, danach teilen wir durch die Anzahl.

    Unser Code dürfte nun in etwa so aussehen:

    #include <iostream>
#include <numeric>
#include <cstddef>

template <typename T>
struct list
{
	struct node
	{
		node(node* prev, T const& value)
			: next_(prev->next_)
			, value_(value)
		{
			prev->next_ = this;
		}

		node()
		{}

		node* next_;
		T value_;
	};

	struct iterator
	{
		iterator(node* pos)
			: pos_(pos)
		{}

		iterator& operator ++ ()
		{
			pos_ = pos_->next_;
			return *this;
		}

		iterator operator ++ (int)
		{
			iterator temp(*this);
			++*this;
			return temp;
		}

		T& operator * ()
		{
			return pos_->value_;
		}

		T const& operator * () const
		{
			return pos_->value_;
		}

		T* operator -> ()
		{
			return &*this;
		}

		T const* operator -> () const
		{
			return &*this;
		}

		friend bool operator == (iterator const& first, iterator const& second)
		{
			return first.pos_ == second.pos_;
		}

		friend bool operator != (iterator const& first, iterator const& second)
		{
			return !(first == second);
		}

	private:
		node* pos_;
	};

	list()
		: size_(0)
	{
		first_.next_ = &last_;
	}

	~list()
	{
		clear();
	}

	void push_front(T const& value)
	{
		new node(&first_, value);
		++size_;
	}

	void pop_front()
	{
		node* temp = first_.next_;
		first_.next_ = temp->next_;
		--size_;
		delete temp;
	}

	bool empty() const
	{
		return size_ == 0;
	}

	std::size_t size() const
	{
		return size_;
	}

	void clear()
	{
		while(!empty())
			pop_front();
	}

	iterator begin()
	{
		return iterator(first_.next_);
	}

	iterator end()
	{
		return iterator(&last_);
	}

private:
	std::size_t size_;

	node first_;
	node last_;
};

int main()
{
	list<int> l;

	for(int i = 1; i <= 20; ++i)
		l.push_front(i);

	std::cout << std::accumulate(l.begin(), l.end(), 0) / static_cast<double>(l.size());
}

    In Teil 4 werden wir uns um etwas kümmern, das wir in unserem Eifer ganz vergessen haben: Die großen Drei!
    Allerdings ist es schon spät, daher folgt Teil 4 möglicherweise erst Morgen 😉

    0
  • C
    Mod

    Wozu genau brauchst du den last-Node? Wenn der unitialisiert bleibt, und du lediglich &last benutzt, um das Ende zu bestimmen, hättest du die Liste genauso gut mit 0 terminieren können.

    0
  • 3

    Jetzt wo du es sagst - Du hast Recht, der last-Knoten ist natürlich unnötig. Gewohnheit von doppelt verketteten Listen 🤡
    Wenn ich jetzt aber alles umbaue, ist die Gefahr, dass sich ein Fehler einschleicht, ziemlich hoch, daher lasse ich es nun so.

    0

  • camper schrieb:

    Wozu genau brauchst du den last-Node?

    Ich denke nen Sentinel verwenden ist gar nicht unüblich bei verketteten Listen.
    Macht die Implementierung von end() und operator ++ einfacher.

    In Teil 4 werden wir uns um etwas kümmern ...

    Those who can...

    0

  • Der Kopierkonstruktor und Zuweisungsoperator fehlen.

    0
  • ?

    Ich sehe keinen Vorteil mit dem first Node direkt in der Liste. Nur weil du keine vernünftige Fehlerabfrage machst, heißt das nicht, dass sie nicht nötig wäre. Probiere etwa mal auf einer leeren Listen ein pop_front(). Dann zerschießt es dir die ganze Liste. Und pop_front() ist die einzigste Funktion, die tatsächlich eine Fallunterscheidung braucht.

    0
  • 3

    DocShoe schrieb:

    Der Kopierkonstruktor und Zuweisungsoperator fehlen.

    -->

    314159265358979 schrieb:

    In Teil 4 werden wir uns um etwas kümmern, das wir in unserem Eifer ganz vergessen haben: Die großen Drei!

    bmario_ schrieb:

    Nur weil du keine vernünftige Fehlerabfrage machst, heißt das nicht, dass sie nicht nötig wäre. Probiere etwa mal auf einer leeren Listen ein pop_front(). Dann zerschießt es dir die ganze Liste. Und pop_front() ist die einzigste Funktion, die tatsächlich eine Fallunterscheidung braucht.

    -->

    n3290 schrieb:

    void pop_front();
    Effects: erase_after(before_begin())

    -->

    n3290 schrieb:

    iterator erase_after(const_iterator position);
    Requires: The iterator following position is dereferenceable. Effects: Erases the element pointed to by the iterator following position.
    Returns: An iterator pointing to the element following the one that was erased, or end() if no such element exists.
    Throws: Nothing.

    Und damit ist der Benutzer dann selbst schuld, wenn er auf einer leeren Liste pop_front() aufruft. Man könnte natürlich asserts einbauen.

    0
Anmelden zum Antworten