Iterator für eine einfach verkettete List



  • Ich habe noch nie einen Iterator selbst geschrieben und würde gerne wissen, ob meine implementation für eine einfach verkettete Liste richtig ist:

    #ifndef LINKED_LIST_H
    #define LINKED_LIST_H
    
    #include <memory>
    #include <stdexcept>
    #include <cassert>
    #include <algorithm>
    #include <iterator>
    
    template<typename T>
    class LinkedList
    {
    	private:
    		struct Node
    		{
    			T data;
    			std::unique_ptr<Node> next;
    		};
    
    	public:
    		class Iterator : public std::iterator<std::forward_iterator_tag, Node*>
    		{
    			public:
    				Iterator()
    					: m_ptr(nullptr)
    				{}
    
    				Iterator(Node* ptr)
    					: m_ptr(ptr)
    				{}
    
    				Iterator(const Iterator& iter)
    					: m_ptr(iter.m_ptr)
    				{}
    
    				Iterator& operator=(Iterator iter)
    				{
    					if(this != &iter)
    					{
    						swap(*this, iter);
    					}
    
    					return *this;
    				}
    
    				~Iterator()
    				{}
    
    				Iterator& operator++()
    				{
    					m_ptr = m_ptr->next.get();
    
    					return *this;
    				}
    
    				Iterator& operator++(int unused)
    				{
    					LinkedList ret(*this);
    					m_ptr = m_ptr->next.get();
    
    					return ret;
    				}
    
    				T& operator*() const
    				{
    					return m_ptr->data;
    				}
    
    				T* operator->() const
    				{
    					return &m_ptr->data;
    				}
    
    				friend void swap(Iterator& lhs, Iterator& rhs)
    				{
    					std::swap(lhs.m_ptr, rhs.m_ptr);
    				}
    
    				friend bool operator==(const Iterator& lhs, const Iterator& rhs)
    				{
    					return lhs.m_ptr == rhs.m_ptr;
    				}
    
    				friend bool operator!=(const Iterator& lhs, const Iterator& rhs)
    				{
    					return !(lhs == rhs);
    				}
    
    			private:
    				Node* m_ptr;
    		};
    
    	public:
    		LinkedList();
    
    		LinkedList(const LinkedList& ll);
    
    		LinkedList& operator=(const LinkedList& ll);
    
    		~LinkedList();
    
    		void append(T data);
    
    		std::size_t getSize() const;
    
    		T get(std::size_t pos) const;
    
    		void clear();
    
    		bool isEmpty() const;
    
    		void erase(std::size_t pos);
    
    		T& operator[](std::size_t pos);
    
    		const T& operator[](std::size_t pos) const;
    
    		Iterator begin();
    
    		Iterator end();
    
    	private:
    		std::unique_ptr<Node> m_root;
    
    		std::size_t m_size;
    };
    

    Sollte bei dem Operator ++ eine Exception geworfen werden wenn m_ptr == nullptr?

    Ist der operator->() falsch implementiert? Ich habe kein Beispiel dafür gefunden.

    Fehlt eine Funktion die ich bereitstellen müsste? - Ich habe mich an diesem Post orientiert.


  • Mod

    Was mir beim Durchlesen auffällt, ohne Gewähr auf Vollständigkeit:

    • Das zweite Templateargument für std::iterator sollte T sein.
    • Beim Testen habe ich "Iterator" spontan erst einmal falsch geschrieben, weil es in der Standardbibliothek immer "iterator" heißt.
    • Offensichtlich hast du noch gar nicht selber getestet, einige Funktionen compilieren nicht, wenn man sie instantiiert. Du musst bei Templates die Funktionen auch wirklich mal benutzen, sonst wird der Code gar nicht richtig geprüft.
    • Ist der Konstruktor in Zeile 28 nötig? Soll der öffentlich zugänglich sein?
    • Ist der selbstgeschriebene Zuweisungoperator nötig?
    • Ist der selbstgeschriebene Kopierkonstruktor nötig?
    • Ist der selbstgeschriebene Destruktor nötig? Der ist ja sogar leer!
    • Zeile 58 überdenkst du besser noch einmal.
    • Wenn man unbenutzten Parametern keinen Namen gibt, beschwert sich der Compiler auch nicht über unbenutzte Variablen.
    • Der Operator-> sieht auf den ersten Blick korrekt aus.
    • Es ist üblich, != von == abzuleiten.
    • Ist die selbstgeschriebene swap-Funktion nötig?
    • Bei ungültigen Operationen würde ich einfach knallhart Nichts machen. Wenn jemand nullptr dereferenzieren möchte, soll er doch.
    • Wie ich subtil angedeutet habe, hast du eher viel zu viele Funktionen definiert. Deine Funktionen sind schließlich (zurecht) identisch mit dem, was sonst automatisch generiert würde.
    • In der gleichen Schiene: Braucht deine LinkedList einen selbstgeschriebenen Destruktor? ISt ein Operator[] wirklich sinnvoll? Ist erase via Index wirklich sinnvoll? Ebenso get und alle anderen Indexzugriffe, die ich eventuell übersehen habe.
    • Vielleicht orientierst du dich erst einmal lieber an der Schnittstelle von std::list, welche Operationen sinnvoll sind und welche nicht. std::list sollte als doppelt verkettete Liste etwas mehr können als deine Liste (beispielsweise wird ein erase bei dir schwer), nicht umgekehrt.
    • const_iterator?


  • Vielen Dank für die ausführliche Antwort. Ich habe nur noch zwei Fragen, wenn ich den Konstruktor aus Zeile 28 privat mache, oder sogar lösche, wie kann ich dann LinkedList::begin() implementieren? Die zweite Frage ist, wie schreibe ich am besten einen const_iterator? Ich wollte eigentlich etwas in dieser Richtung machen:

    template<typename T>
    class LinkedList
    {
    ...
        using iterator = Iterator<T>;
        using const_iterator = Iterator<const T>
    }
    

    Aber das klappt nur wenn ich Iterator ausßerhalb der LinkedList definiere. Die zweite Möglichkeit die ich im Internet gefunden habe, ist const_iterator auch als Klasse zu schreiben und von std::iterator<std::forward_iterator_tag, const Node> zu erben.

    Der Rest deiner Kritik ist mir einleuchtend und ich werde sie bei meinen std::list Klon berücksichtigen. 👍


  • Mod

    liste schrieb:

    Vielen Dank für die ausführliche Antwort. Ich habe nur noch zwei Fragen, wenn ich den Konstruktor aus Zeile 28 privat mache, oder sogar lösche, wie kann ich dann LinkedList::begin() implementieren?

    friend ist dein Freund.

    liste schrieb:

    Die zweite Frage ist, wie schreibe ich am besten einen const_iterator? Ich wollte eigentlich etwas in dieser Richtung machen:

    template<typename T>
    class LinkedList
    {
    ...
        using iterator = Iterator<T>;
        using const_iterator = Iterator<const T>
    }
    

    Aber das klappt nur wenn ich Iterator ausßerhalb der LinkedList definiere. Die zweite Möglichkeit die ich im Internet gefunden habe, ist const_iterator auch als Klasse zu schreiben und von std::iterator<std::forward_iterator_tag, const Node> zu erben.

    Ein Fehler der gerne gemacht wird.

    Der value_type eines const_iterators unterscheidet sich nicht von dem eines normalen (mutable) Iterator.
    Selbst std::iterator_traits<const T*>::value_type ist T und nicht etwa const T.

    Ausserdem sollte ein iterator konvertierbar zu const_iterator sein.


Log in to reply