3. Codereview meiner einfachen generischen Liste

Codereview meiner einfachen generischen Liste


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

    314159265358979 schrieb:

    struct const_iterator : std::iterator<std::forward_iterator_tag, value_type const>

    Das letzte const ist falsch. vector<const T>::value_type ist (wie bei allen STL-Iteratoren) nicht const T, sondern T. Daher müsstest du, wenn du kompatibel sein möchtest, das const entfernen.

    Wenn man danach googelt, findet man heraus, dass unser Werner das schon früher festgestellt hat.

    Im übrigen musst du nicht zwei (fast) identische Iteratoren schreiben, ein Iterator-Template und zwei typedefs einmal mit und einmal ohne const reichen auch.

    0
  • 3

    camper schrieb:

    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.

    Du nimmst mir echt alles vorweg 🤡
    Ja, ich habe daran gedacht. Aber für mich fällt das in die Kategorie "Optimierungen" und kommt daher ganz am Schluss.

    fackingstandard schrieb:

    314159265358979 schrieb:

    struct const_iterator : std::iterator<std::forward_iterator_tag, value_type const>

    Das letzte const ist falsch. vector<const T>::value_type ist (wie bei allen STL-Iteratoren) nicht const T, sondern T. Daher müsstest du, wenn du kompatibel sein möchtest, das const entfernen.

    Wenn man danach googelt, findet man heraus, dass unser Werner das schon früher festgestellt hat.

    Okay, das ist mir neu. Klingt meiner Meinung nach zwar nicht logisch, aber auch okay. Indem ich das const weglasse müsste das Problem ja behoben sein, oder?

    fackingstandard schrieb:

    Im übrigen musst du nicht zwei (fast) identische Iteratoren schreiben, ein Iterator-Template und zwei typedefs einmal mit und einmal ohne const reichen auch.

    Das hat mich selbst etwas gestört, sehe ich aber nicht wirklich als schlimm an. So auf die Schnelle fällt mir allerdings nicht ein, worauf man da sinnvoll parametrisieren soll.

    0
Anmelden zum Antworten