verkettete Liste in C++ mit Iteratoren
-
Hallo Gemeinde,
mich interessiert weniger, wie das mit der Verkettung funktioniert, sondern wie man "modern" soetwas macht. Ich möchte also sowas machen:
#include <iostream> #include "list.h" int main() { List<int> l; l.append(0); l.append(1); List<int>::iterator it = l.begin(); List<int>::iterator endit = l.end(); while ( it != endit ) { std::cout << *it << "\n"; it = l.next(it); } return 0; } /* for ( List<int>::iterator it = l.begin(), endit=l.end(); it != endit; ++it ) std::cout << *it << "\n"; */Wie man an der Auskommentierung sieht, habe ich es mit der Incremtierung nicht hin gekriegt. Auserdem gibt es noch ein Bug am Ende der Liste, den finde ich aber noch.
Die entsprechende h - Datei sieht folgendermaßen aus:
template <typename T> class List { public: List() { _first = _last = 0; } void append(const T& t) { T* v = new T(t); iterator* i = new iterator; i->_data = v; i->_next = 0; if ( _first == 0 ) _first = i; else _last->_next = i; _last = i; } struct iterator { friend class List<T>; iterator() { _next = 0; _data = 0; } iterator(const iterator& i) { ~iterator() { delete _data; _data = 0; } T* operator->() const { return _data; } T& operator*() const { return *_data; } const bool operator!=(const iterator& i) { return compare(i) == false; } const bool operator==(const iterator& i) { return compare(i) == true; } const bool compare(const iterator& i) { if ( this==&i ) return true; else return false; } iterator* _next; T* _data; iterator& operator=(const List<T>::iterator& i) { _next = i._next; _data = i._data; return *this; } iterator& operator++() { iterator* t = this; if ( t->_next ) t = t->_next; return *t; } }; iterator& next(const iterator& i) { return *i._next; } iterator& begin() { return *_first; } iterator& end() { return *_last; } private: iterator* _first; iterator* _last; }Ich würde mich freuen, wenn mir jemanden helfen kann.
Ich vermute, es ist ein design - Fehler.Viele Grüße
uli3
-
Hallo uli3,
abgesehen davon, dass in Zeile 30 vor dem Destruktor ein '}' fehlt, brauchst Du in einer einfach verketteten Liste ein Knoten-Element welches den Datentyp und den Zeiger auf das nächste Element enthält. Du hast den Iterator dazu missbraucht. Das ist vielleicht nicht grob falsch, aber ziemlich unüblich.
Besser ist man definiert sich ein Knotenelement innerhalb der Liste - also:
template <typename T> class List { struct Node { Node* next_; T data_; }; public: // usw. private: Node* head_; // zeigt auf das erste Element oder auf 0 // optional (um ein append bzw. push_back zu ermöglichen): Node* back_; // zeigt in einer nicht leeren Liste auf das letze Element };Dann benötigst Du im Iterator nur einen Zeiger auf den aktuellen Knoten. Ich nenne ihn mal cur_ (current bzw. aktuell)
struct iterator { // .. private: Node* cur_; };(Bem.: der Underscore sollte nicht am Anfang stehen; darartige Namen sind für das System reserviert)
Mit begin zeigt cur_ auf das erste Element der Liste und mit end zeigt er auf 0.
Dann sieht operator++ so aus:iterator& operator++() { cur_ = cur_->next_; return *this; }Die Abfrage auf 0 ist unnötigt, da es nicht erlaubt ist den Ende-Iterator zu inkrementieren. Du kannst aber ein
assert( cur_ );spendieren, falls es aus Versehen doch passiert.
Auf den Rest solltest Du selber kommen; sonst frage noch mal nach.
Noch ein Tipp: benutze in jedem Konstruktor die Initialisierungsliste und versehe Node mit einem KonstruktorGruß
Werner
-
Hallo Werner,
danke für die rasche Antwort. Ich habe meine Implementation geändert.
Leider lässt sich unten stehender code nicht linken.
Kann mir jemand helfen?
Grüsse
uli3
g++ -v Using built-in specs. Target: i486-linux-gnu Configured with: ../src/configure -v --with-pkgversion='Debian 4.3.1-9' --with-bugurl=file:///usr/share/doc/gcc-4.3/README.Bugs --enable-languages=c,c++,fortran,objc,obj-c++ --prefix=/usr --enable-shared --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --enable-nls --with-gxx-include-dir=/usr/include/c++/4.3 --program-suffix=-4.3 --enable-clocale=gnu --enable-libstdcxx-debug --enable-objc-gc --enable-mpfr --enable-targets=all --enable-cld --enable-checking=release --build=i486-linux-gnu --host=i486-linux-gnu --target=i486-linux-gnu Thread model: posix gcc version 4.3.1 (Debian 4.3.1-9)make g++ -o testlist main.o node.o list.o main.o: In function `main': /home/uk/Daten/src/list2/main.cxx:6: undefined reference to `List<int>::List()' /home/uk/Daten/src/list2/main.cxx:7: undefined reference to `List<int>::append(int const&)' /home/uk/Daten/src/list2/main.cxx:8: undefined reference to `List<int>::append(int const&)' /home/uk/Daten/src/list2/main.cxx:10: undefined reference to `List<int>::iterator::operator*() const' /home/uk/Daten/src/list2/main.cxx:9: undefined reference to `List<int>::iterator::operator!=(List<int>::iterator const&)' /home/uk/Daten/src/list2/main.cxx:11: undefined reference to `List<int>::~List()' /home/uk/Daten/src/list2/main.cxx:11: undefined reference to `List<int>::~List()' main.o: In function `List<int>::begin()': /home/uk/Daten/src/list2/list.h:33: undefined reference to `List<int>::iterator::iterator(Node<int> const*)' main.o: In function `List<int>::end()': /home/uk/Daten/src/list2/list.h:37: undefined reference to `List<int>::iterator::iterator(Node<int> const*)' main.o: In function `List<int>::iterator::operator++()': /home/uk/Daten/src/list2/list.h:23: undefined reference to `Node<int>::setNext(Node<int> const*)' collect2: ld returned 1 exit status make: *** [testlist] Fehler 1Hier ist der kpmplette code
makefile
CPP = g++ COPTIONS = -pedantic -Wall -ggdb3 OBJS = main.o node.o list.o all : testlist main.o : main.cxx makefile $(CPP) $(COPTIONS) -c $< node.o : node.cxx node.h makefile $(CPP) $(COPTIONS) -c $< list.o : list.cxx list.h makefile $(CPP) $(COPTIONS) -c $< testlist : $(OBJS) makefile $(CPP) -o testlist $(OBJS) clean : @rm -f $(OBJS) testlist doxy : doxygen doxyfilenode.h
#ifndef NODE_H #define NODE_H template <typename T> class Node { public: Node(); Node(const T*, const Node<T>*); Node<T>* next() const { return _next; } void setNext(const Node<T>* next); T* data() const; void setData(const T*); private: Node<T>* _next; T* _data; }; #endifnode.cxx
#include "node.h" template <typename T> Node<T>::Node() { _data = 0; _next = 0; } template <typename T> Node<T>::Node(const T* data, const Node<T>* next) { _data = data; _next = next; } //template <typename T> Node<T>* Mode<T>::next() const //{ // return _next; //} // template <typename T> void Node<T>::setNext(const Node* next) { _next = next; } template <typename T> T* Node<T>::data() const { return _data; } template <typename T> void Node<T>::setData(const T* data) { return _data = data; }list.h
#ifndef LIST_H #define LIST_H #include "node.h" template <typename T> class List { public: List(); ~List(); void append(const T&); void append(const T*); void clear(); class iterator { public: iterator(); iterator(const Node<T>*); iterator(const Node<T>&); T& operator*() const; T* operator->() const; iterator& operator++() { _current->setNext(_current); return *this; } const bool operator!=(const iterator&); const bool operator==(const iterator&); private: Node<T>* _current; }; iterator begin() { return iterator(_first); } iterator end() { return iterator(_last); } private: Node<T>* _first; Node<T>* _last; }; #endiflist.cxx
#include "list.h" template <typename T> List<T>::List() { _first = 0; _last = 0; } template <typename T> List<T>::~List() { clear(); } template <typename T> void List<T>::clear() { } template <typename T> void List<T>::append(const T* t) { T* v = new T(t); Node<T>* node = new Node<T>(v, 0); if ( _first == 0 ) _first = node; else _last.setNext(node); _last = node; } //template <typename T> iterator List<T>::begin() //{ // return iterator(_first); //} // //template <typename T> iterator List<T>::end() //{ // return iterator(_last); //} // template <typename T> List<T>::iterator::iterator() { _current = 0; } template <typename T> List<T>::iterator::iterator(const Node<T>* node) { _current = node; } template <typename T> List<T>::iterator::iterator(const Node<T>& node) { _current = *node; } template <typename T> const bool List<T>::iterator::operator!=(const iterator& it) { return _current != ⁢ } template <typename T> const bool List<T>::iterator::operator==(const iterator& it) { return _current == ⁢ } template <typename T> T& List<T>::iterator::operator*() const { return _current.data(); } //template <typename T> iterator& List<T>::iterator::operator++() //{ // _current->setNext(_current); // return *this; //}main.cxx
#include <iostream> #include "list.h" int main() { List<int> l; l.append(0); l.append(1); for ( List<int>::iterator it = l.begin(), endit=l.end(); it != endit; ++it ) std::cout << *it << "\n"; return 0; }
-
Hallo uli3,
Bei templates ist die Trennung von Implementierung und Deklaration nicht zulässig. Der Code von list.cxx und node.cxx gehört mit in list.h bzw. node.h hinein oder Du inkludierst am Ende der H-Datei das passende .cxx-File. Im make kannst Du list.cxx und node.cxx entfernen - da ist es überflüssig.
Gruß
Werner
-
Hallo Werner,
ich habe jetzt die komplette Implementierung in die header genommen.
Es kommen trotzdem Fehler.Ich habe schonmal gesehen, dass template Klassen instanziert werden müssen.
Ich weis nicht wie das geht.
Viele Grüsse und vielen Dank
uli3
-
Das sind ganz normale Compilerfehler. Bisher kamen die deshalb nicht, weil list.cxx und node.cxx nicht instanziiert wurden. Die Instanziierung geschieht durch das 'List<int> l;' das reicht.
Unter anderen muss der Konstruktor von itertor einen nicht(!) const Pointer auf Node aufnehmen, sonst kann man später das Element ja nicht manipulieren.
iterator(/*const*/ Node<T>*);Der Konstruktor mit der Referenz auf Node ist dann überflüssig.
Beim Vergleich zweier Iteratoren müssen natürlich die Member und nicht der Member mit dem Zeiger auf den Iterator verglichen werden
template <typename T> const bool List<T>::iterator::operator!=(const iterator& it) { return _current != it._current; }Und Node sollte einen Element als Member aufnehmen nicht als Pointer - das macht doch nur Arbeit und ist fehlerträchtig.
template <typename T> class Node { // ... private: Node<T>* _next; T _data; // _data ist Member von Node };.. und weitere Compilerfehler - such' mal selber
Gruß
Werner
-
Hallo Werner,
danke für Deine Antwort.
Hier ein Prototyp:
list.h
#ifndef LIST_H #define LIST_H #include "node.h" template <typename T> class List { public: List() { _first = 0; _last = 0; } ~List() { clear(); } void append(const T& t) { append(&t); } void append(const T* t) { T* v = new T(*t); Node<T>* node = new Node<T>(v, 0); if ( _first == 0 ) _first = node; else _last->setNext(node); _last = node; } void clear() { } class iterator { public: iterator() { _current = 0; } iterator(Node<T>* node) { _current = node; } const T& operator*() const { return *(_current->data()); } const T* operator->() const { return _current->data(); } iterator& operator++() { _current = _current->next(); return *this; } const bool operator!=(const iterator& it) const { return _current != it._current; } const bool operator==(const iterator& it) const { return _current == it._current; } private: Node<T>* _current; }; iterator begin() { return iterator(_first); } iterator end() { return iterator(_last->next()); } private: Node<T>* _first; Node<T>* _last; }; #endifnode.h
#ifndef NODE_H #define NODE_H template <typename T> class Node { public: Node() { _data = 0; _next = 0; } Node(const Node* node) { _data = node->_data; _next = node->_next; } Node(const Node& node) { _data = node._data; _next = node._next; } Node(T* data, Node<T>* next) { _data = data; _next = next; } Node<T>* next() const { return _next; } void setNext(Node<T>* next) { _next = next; } const T* data() const { return _data; } void setData(const T* data) { _data = data; } private: Node<T>* _next; T* _data; }; #endiflist.cxx
#include "list.h"node.cxx
#include "node.h"main.cxx
int main() { List<int> l; l.append(0); l.append(1); l.append(2); l.append(3); l.append(4); l.append(5); l.append(6); l.append(7); l.append(8); l.append(9); for ( List<int>::iterator it = l.begin(), endit=l.end(); it != endit; ++it ) std::cout << *it << std::endl; return 0; }Jetzt geht es ans optimieren und implementieren der restlichen Funktionen.
Viele Grüße
und Danke
uli3
[cpp]
-
Ich würde dir noch empfehlen dir ein paar Gedanken zu machen über:
- Kopierkonstruktor
- Zuweisung
- Initialisierungsliste (bereits genannt)
- Freigeben von Speicher
...