3. Codereview meiner einfachen generischen Liste

Codereview meiner einfachen generischen Liste 


  • 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
  • 3

    Nachdem wir nun Iteratoren implementiert haben, haben wir schon einen Großteil geschafft. Allerdings tun die vom Compiler generierten Kopier-Operationen nicht das richtige. Die Regel der großen Drei besagt, dass wir den Kopierkonstruktor und Kopier-Zuweisungsoperator implementieren müssen, da wir einen Destruktor implementiert haben.

    Fangen wir mit dem Kopierkonstruktor an. Wir kopieren einfach jedes Element der Liste. Damit wir an den pos-Member des Iterators herankommen, erklären wir list zusätzlich als friend der Klasse iterator.

    list(list const& other)
	: size_(other.size_)
{
	first_.next = 0;

	for(iterator iter = other.begin(), curr = iterator(first_); iter != other.end(); ++iter, ++curr)
		new node(curr.pos, *iter);
}

    Jetzt fehlt nur noch der Zuweisungsoperator. Am einfachsten ist es, diesen über das "Copy & Swap" - Idiom zu implementieren. Siehe auch: http://en.wikibooks.org/wiki/More_C++_Idioms/Copy-and-swap

    Dafür brauchen wir eine Funktion, die *this mit einer andere Liste tauscht. Am einfachsten geht das, indem wir alle Knoten zwischen first und last der beiden Listen tauschen. Doch hier haben wir ein Problem: Das Tauschen lässt sich nicht effizient implementieren, da wird einen last-Knoten haben. Wir müssten die Liste bis zum letzten Element vor last durchgehen, um den Zeiger des Knotens auf das neue last setzen zu können. Wir kommen zu dem Entschluss, dass wir auf camper hätten hören sollen und bauen unsere Liste so um, dass das Ende durch einen next-Zeiger mit dem Wert 0 repräsentiert wird.

    Dazu sind lediglich ein paar Änderungen erforderlich. Als erstes entfernen wir den last-Knoten. Nun müssen wir nur alle Stellen korrigieren, an denen wir last verwendet haben. Als erstes wäre da der Konstruktor. Wir haben first_.next_ mit &last initialisiert, das ersetzen wir durch 0:

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

    Die zweite Stelle, an der wir last verwendet haben, ist die end()-Methode. Anstatt eines Iterators auf &last geben wir einen Iterator auf 0 zurück:

    iterator end()
{
	return iterator(0);
}

    War also doch nicht so schlimm, wie ursprünglich angenommen. Nun können wir unser swap() implementieren. Wir tauschen einfach die Knoten der Listen sowie die Größen:

    void swap(list& other)
{
	swap(first_.next_, other.first_.next_);
	swap(size_, other.size_);
}

    Damit wird der Zuweisungsoperator auch einfach:

    list& operator = (list other)
{
	swap(other);
	return *this;
}

    Der Vollständigkeit halber sollten wir noch eine freie Funktion zum Tauschen zweier Listen implementieren:

    template <typename T>
void swap(list<T>& first, list<T>& second)
{
	first.swap(second);
}

    In Teil 5 werden wir noch ein paar Konstruktoren und Methoden sowie ein paar typedefs hinzufügen.

    0
  • 3

    Vorhin schrieb ich, dass schon die meisten Standard-Algortihmen mit unserer Liste funktionieren. Manche Algorithmen setzen jedoch voraus, dass sowohl die Liste, als auch unsere Iterator-Klasse bestimmte Typen definiert.

    Die folgenden typedefs können wir in die Liste stecken.

    typedef T value_type;

typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;

typedef T& reference;
typedef T const& const_reference;

typedef T* pointer;
typedef T const* const_pointer;

    Für die typedefs im Iterator gibt es glücklicherweise eine Abkürzung in der STL. Mithilfe der Klasse iterator aus <iterator> können wir uns die Tipparbeit sparen. Dazu müssen wir unseren iterator nur von std::iterator ableiten.

    struct iterator : std::iterator<std::forward_iterator_tag, T>

    Das forward_iterator_tag gibt den Typen des Iterators an. Da wir eine einfach verkettete Liste haben, haben wir nur forward access.

    Da wir nun die ganzen typedefs haben, wäre es besser, überall im Code T durch das entsprechende typedef zu ersetzen.

    Damit kommen wir zu folgendem Code:

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

template <typename T>
struct list
{
	typedef T value_type;

	typedef std::size_t size_type;
	typedef std::ptrdiff_t difference_type;

	typedef T& reference;
	typedef T const& const_reference;

	typedef T* pointer;
	typedef T const* const_pointer;

	struct node
	{
		node(node* prev, const_reference value)
			: next_(prev->next_)
			, value_(value)
		{
			prev->next_ = this;
		}

		node()
		{}

		node* next_;
		value_type value_;
	};

	struct iterator : std::iterator<std::forward_iterator_tag, value_type>
	{
		iterator(node* pos)
			: pos_(pos)
		{}

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

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

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

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

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

		const_pointer 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_ = 0;
	}

	list(list const& other)
		: size_(other.size_)
	{
		first_.next_ = 0;

		for(iterator iter = other.begin(), curr = iterator(first_); iter != other.end(); ++iter, ++curr)
			new node(curr.pos, *iter);
	}

	list& operator = (list other)
	{
		swap(other);
		return *this;
	}

	~list()
	{
		clear();
	}

	void swap(list& other)
	{
		swap(first_.next_, other.first_.next_);
		swap(size_, other.size_);
	}

	void push_front(const_reference 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;
	}

	size_type size() const
	{
		return size_;
	}

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

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

	iterator end()
	{
		return iterator(0);
	}

private:
	std::size_t size_;

	node first_;
};

template <typename T>
void swap(list<T>& first, list<T>& second)
{
	first.swap(second);
}

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());
}

    Leider habe ich gerade keine Zeit dafür, was ich noch schreiben wollte. Das folgt dann in Teil 6.

    0
  • C
    Mod

    314159265358979 schrieb:

    Dafür brauchen wir eine Funktion, die *this mit einer andere Liste tauscht. Am einfachsten geht das, indem wir alle Knoten zwischen first und last der beiden Listen tauschen. Doch hier haben wir ein Problem: Das Tauschen lässt sich nicht effizient implementieren, da wird einen last-Knoten haben. Wir müssten die Liste bis zum letzten Element vor last durchgehen, um den Zeiger des Knotens auf das neue last setzen zu können. Wir kommen zu dem Entschluss, dass wir auf camper hätten hören sollen und bauen unsere Liste so um, dass das Ende durch einen next-Zeiger mit dem Wert 0 repräsentiert wird.

    An die Implementierung hatte ich gar nicht gedacht, 0 hat noch einen anderen Vorteil: der end-Iterator (und damit jede beliebe Sequenz, wenn wir mal den vor-beginn-Iterator ignorieren) bleibt gültig trotz des swap. Damit sind die end-Iteratoren aller Listen identisch, eine Eigenschaft, die mit anderen Forward-Strukturen geteilt wird (man denke an streams).

    Nebenbei führt die Konstanz eines Iterators nicht dazu, dass sich der Typ der Referenz ändert. Wenn du const_iteratoren implementieren willst, wirst du einen eigenständigen Typ benötigen. Oft kann man const_iterator bauen und dann iterator davon ableiten und die entsprechenden Operatoren (mit ein paar unproblematischen const_casts) über die Basisklasse implementieren. Damit ist dann auch gleich die Konvertierung möglich.

    0
  • ?

    Fand den Thread bis jetzt sehr interessant. Man kann einen guten Einblick bekommen wie Andere an ein Problem heran gehen. Auch die Begründung der einzelnen Schritte find ich gut. Freue mich schon auf den nächsten Teil 🙂 .

    Nebenbei bemerkt hat sich in Zeile 98 ein Tippfehler eingeschlichen. Es fehlt das Underline nach 'next'.

    first_.next = 0;

    Lg Observer

    0
  • 3

    @camper: Dass ich einen eigenen const_iterator brauche, ist mir schon klar. Genau den wollte ich unter anderem jetzt implementieren 😉

    @Observer: Danke für den Hinweis. Freut mich, dass offenbar doch jemand hier mitliest.

    Wie oben schon gesagt, werden wir nun einen const_iterator implementieren. Ein const_iterator ist ein iterator, der die Elemente allerdings nicht verändern kann. Ich denke, ich muss dazu nicht mehr viel erklären, da der const_iterator dem iterator sehr ähnlich ist. Im iterator befand sich übrigens beim operator -> der Fehler, dass eine Dereferenzierung zu wenig war. Es muss natürlich "return &**this;" heißen.

    struct const_iterator : std::iterator<std::forward_iterator_tag, value_type const>
{
	const_iterator(node const* pos)
		: pos_(pos)
	{}

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

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

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

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

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

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

private:
	node const* pos_;
};

    Desweiteren fügen wir iterator einen Konvertierungsoperator zu const_iterator hinzu:

    operator const_iterator()
{
	return const_iterator(pos_);
}

    Wir könnten statt des Konvertierungsoperators natürlich auch const_iterator einen iterator-Konstruktor verpassen, was jedoch erfordern würde, dass const_iterator friend von iterator ist. Deshalb habe ich den Konvertierungsoperator gewählt.

    Nun haben wir zwar wunderschöne Iteratoren, aber wir können nur am Anfang der Liste einfügen und entfernen. Der nächste Schritt ist also, zwei Funktionen insert_after und erase_after zu implementieren. insert_after nimmt einen const_iterator, der die Position, nach der einefügt werden soll, angibt, sowie den einzufügenden Wert. Außerdem wird ein Iterator auf das neu eingefügte Element zurückgegeben. Diese Funktion ist relativ einfach geschrieben:

    iterator insert_after(const_iterator iter, const_reference value)
{
	node* temp = new node(const_cast<node*>(iter.pos_), value);
	++size_;
	return iterator(temp);
}

    Der const_cast hier ist deshalb erforderlich, weil wir nur einen const_iterator haben. Um eine Position anzugeben, reicht ein const_iterator aber völlig aus. Und da insert_after nonconst ist, wissen wir, dass wir den const_cast gefahrlos verwenden können.

    erase_after ist hier ziemlich ähnlich. Auch hier bekommen wir einen const_iterator als Positionsangabe und müssen einen const_cast verwenden. Wir geben einen Iterator auf das Element nach dem entfernten zurück.

    iterator erase_after(const_iterator iter)
{
	node* pos = const_cast<node*>(iter.pos_);
	node* temp = pos->next_;
	pos->next_ = temp->next_;
	--size_;
	delete temp;
	return iterator(pos->next_);
}

    Der Code für diese beiden Funktionen kommt uns ziemlich bekannt vor - er ist fast identisch mit dem von push_front und pop_front. Bevor wir push_front und pop_front über diese beiden Funktionen implementieren können, benötigen wir die Funktion before_begin(), die einen Iterator vor den Anfang der Sequenz liefert, also genau auf first_:

    iterator before_begin()
{
	return iterator(&first_);
}

    Damit können wir jetzt endlich push_front und pop_front wie folgt implementieren:

    void push_front(const_reference value)
{
	insert_after(before_begin(), value);
}

void pop_front()
{
	erase_after(before_begin());
}

    Und wenn wir schon dabei sind, Iterator-Funktionen zu basteln, können wir auch gleich die restlichen begin/end-Funktionen für const_iterator sowie .front() schnitzen:

    const_iterator before_begin() const
{
	return const_iterator(&first_);
}

const_iterator cbefore_begin() const
{
	return before_begin();
}

const_iterator begin() const
{
	return const_iterator(first_.next_);
}

const_iterator end() const
{
	return const_iterator(0);
}

const_iterator cbegin() const
{
	return begin();
}

const_iterator cend() const
{
	return end();
}

reference front()
{
	return *begin();
}

const_reference front() const
{
	return *begin();
}

    Worauf mich niemand hingewiesen hat: Der Kopierkonstruktor funktioniert so ja überhaupt nicht. 😉
    Also schnell eine richtige Implementierung zusammenbauen:

    list(list const& other)
	: size_(other.size_)
{
	first_.next_ = 0;

	for(const_iterator iter = other.begin(), curr = cbefore_begin(); iter != other.end(); ++iter, ++curr)
		insert_after(curr, *iter);
}

    In Teil 7 werden wir weitere Memberfunktionen implementieren, bevor wir uns dann in Teil 8 an Allokatoren wagen.

    0
  • C
    Mod

    Hast du noch vor, ein nodebase einzuführen? Das dummy-T in der Liste ist ja nicht so toll. Dann würdest du dir den node-Defaultkonstruktor sparen können und kannst mit Ts ohne Defaultkonstruktor umgehen.

    0
Anmelden zum Antworten