iterator für eigenen container



  • hallo zusammen,

    ich versuche einer eigenen klasse einen iterator hinzuzufügen. allerdings klappt dies im moment noch nicht so richtig. ich habe ne menge gelesen, aber bei weiten nicht alles verstanden. daher hoffe ich hier rat zu bekommen. 🙂

    die klasse von mir ist im wesentlichen ein wrapper für std::vector, soll dies aber eigentlich verbergen. zunächst einmal die signatur der klasse, mit iterator. ich vermute mal, schon hier ist nicht alles so, wie man es sonst so macht.

    template <typename T>
            class List {
            public:
    
                List();
                virtual ~List();
    
            //gekürzt
    
            protected:
    
                typedef std::vector<T> TList;
                TList queue;
    
            public:
    
                class iterator : public std::iterator<std::forward_iterator_tag, T>{
                public:
    
                    iterator(const unsigned int aIndex, const TList & l);
                    T & operator*();
                    iterator & operator++(); // prefix
                    iterator operator++(int); //postfix
                    bool operator !=(const iterator & other) const;
    
                private:
                    unsigned int index;
                    TList & itQueue;
                };
    
                iterator begin();
                iterator end();
    
            };
    

    Wenn ich weiter unten die einzelnen Methoden implementieren will, bekomme ich bei:

    template <typename T>
       List<T>::iterator &  //<<---- Fehlerstelle
       List<T>::iterator::operator++() { // prefix
          ++index;
          return *this;
       }
    

    Den Fehler:

    error: expected constructor, destructor, or type conversion before ‘&’ token
    

    Könnt ihr mir einen Tipp geben was ich falsch mache?

    Vielen Dank.

    sven



  • typename List<T>::iterator&
    


  • ah vielen dank! deswegen wohl auch immer die typedefs in den beispielen? versteh. ist der iterator in der klasse eigentlich an der richtigen stelle, oder definiert man ihn normalerweise anders/woanders?

    der konstruktor sollte dann wohl auch eher so aussehen:

    iterator(const unsigned int aIndex, TList & l);
    

    oder?

    sven_



  • sven_ schrieb:

    deswegen wohl auch immer die typedefs in den beispielen? versteh.

    typedef != typename
    typename braucht man wenn man dem compiler klar machen will, dass ein bezeichner ein typ ist. wenn man das nicht tut, dann geht der compiler von einer instanz aus (wenn man auch enum-labels als kontante instanzen von z.b. ints sieht). der compiler erkennt ja eigentlich selbst ob ein bezeichner von einem typen stammt oder nicht, nicht aber wenn es sich um einen verdeckten abhängigen namen handelt. verdeckt weil der name im klassentemplate drin ist und abhängig weil der name von der instanziierung des klassentemplates abhängt.

    sven_ schrieb:

    ist der iterator in der klasse eigentlich an der richtigen stelle, oder definiert man ihn normalerweise anders/woanders?

    sieht nicht verkehrt aus, würde ich auch so machen.

    sven_ schrieb:

    der konstruktor sollte dann wohl auch eher so aussehen:

    iterator(const unsigned int aIndex, TList & l);
    

    oder?

    das top-level-const beim index-parameter ist unnötig. ob das ziel der referenz const-qualifiziert ist ist davon abhängig, ob es ein iterator oder ein const-iterator sein soll. (einfach ein klassentemplate machen und dann wahlweise mit <T, TList> oder mit <const T, const TList> füttern)

    ausserdem zweifle ich deinen ansatz ein wenig an: du musst nicht wissen auf welchen container sich der iterator bezieht (ausser du willst range-checks oder sonst was machen, wozu du wissen über den container brauchst). bei vectoren kannst du einfach einen zeiger auf das element machen, bei listen auf den knoten, bei bäumen auf das blatt / auf den knoten. das setzt afaik aber eine etwas schwächere kapselung voraus indem du den container und den iterator zu freunden machst.



  • vielen dank für deine antwort. fast alles verstanden, außer:

    ausserdem zweifle ich deinen ansatz ein wenig an: du musst nicht wissen auf welchen container sich der iterator bezieht (ausser du willst range-checks oder sonst was machen, wozu du wissen über den container brauchst). bei vectoren kannst du einfach einen zeiger auf das element machen, bei listen auf den knoten, bei bäumen auf das blatt / auf den knoten. das setzt afaik aber eine etwas schwächere kapselung voraus indem du den container und den iterator zu freunden machst.
    

    meinst du ich soll statt der gesamten queue nur ein T* über geben und den begin iterator mit &queue[0] initialisieren, oder wie? funktioniert dann ein t++ korrekt in der operator++() methode?



  • ja, so meine ich das (bei fortlaufendem speicher wie std::vector). würde etwa so aussehen: (ungetestet und nur kurz hingewurstelt, sicherlich voller fehler, geht aber nur ums prinzip)

    template<typename T> // Vielleicht auch eigenen Allocator erlauben?
    class Wrapper
    {
    	//...
    
    	template<typename U>
    	class BasicIterator : public std::iterator<std::forward_iterator_tag, U>
    	{
    		pointer MyTarget;
    
    		friend class Wrapper<T>;
    
    		explicit BasicIterator(pointer Target)
    			: MyTarget(Target)
    		{
    		}
    
    	public:
    		// ...
    
    		BasicIterator& operator++()
    		{
    			++this->MyTarget;
    			return *this;
    		}
    	};
    
    public:
    	typedef T ValueType;
    	typedef BasicIterator<T> Iterator;
    	typedef BasicIterator<const T> ConstIterator;
    
    	//...
    
    	ConstIterator Begin() const
    	{
    		return ConstIterator((*this)[0]);
    	}
    	Iterator Begin()
    	{
    		return Iterator(const_cast<ValueType*>(&*static_cast<Wrapper const*>(this)->Begin()));
    	}
    };
    


  • ich muß nochmal nachfragen.

    beim umbauen der lösung in deine richtung bin ich nun so weit gekommen:

    template <typename T>
            class List {
            public:
    
                template <typename L>
                class Iterator : public std::iterator<std::forward_iterator_tag, L> {
    
                    L pos;
    
                    friend class List<L>;
    
                    explicit Iterator(L aPos):pos(aPos){};
    
                public:
    
                    T & operator*();
    //
                    Iterator<L> & operator++(){}; // prefix
                    Iterator<L> operator++(int){ throw 0; }; //postfix
    //
                    bool operator !=(const Iterator<L> & other) const {
                        return false;
                    }
    //                bool operator ==(const iterator & other) const;
    
                private:
    //                unsigned int index;
    //                TList & itQueue;
                };
    
                typedef Iterator<T * > iterator;
                typedef Iterator<const T *> const_iterator;
    
                iterator begin();
    };
    

    Implementiere ich zB. den operator* so inline:

    T & operator*(){ 
    ... 
    }
    

    gehts, versuche ich aber die implementierung nach unten zu verlegen, in form von:

    template <typename T, typename L>
            T & //<<<--- fehler
            List<T>::Iterator<L>::operator*() {
                //todo
                throw 0;
            }
    

    bekomme ich als Fehler:

    error: too few template-parameter-lists
    

    Was mache ich den noch falsch, bzw. habe ich falsch verstanden?



  • 1. erst arbeitest du so, als wäre L der wert-typ. dann müsste pos aber ein zeiger auf L sein.

    1. friend class List<L>; wird möglicherweise nicht funktionieren da die const-qualifizierte version des iterators einem typen (List<const T>) die freundschaft erlaubt, der gar nie benutzt wird und verweigert sie dem typen, der die freundschaft braucht (List<T>).

    3. operator* muss L& zurückgeben, sonst ist das konzept mit den wahlweise konstanten iteratoren dahin.

    4. ausserhalb der klasse definieren würde man den operator afaik so:

    template<typename T>
    template<typename L>
    L& List<T>::Iterator<L>::operator*()
    {
        // TODO
        throw 0;
    }
    

    ps.: wenn du das mit dem externen definieren der übersichtlichkeit wegen machst: viele moderne IDEs (so auch vs) unterstützen das zusammenklappen von codeblöcken. damit sparst du viel fleissarbeit und kannst dich aufs wesentlichere konzentrieren.



  • Hallo asfdlol,

    also erst einmal riesigen dank für deine Hilfe, fast ist es geschafft.! Zu den Punkten:

    1. Hat ich erst so, hab's dann auf falsch geändert. Gute frage warum. 🙂
    2. Stimmt, übersehen.
    3. Darauf hätte man auch allein kommen können, peinlich peinlich. Lustig finde ich da ja jetzt die Signatur in der Definition:
    template <typename T>
            template <typename L>
            typename List<T>::template Iterator<L>
            List<T>::Iterator<L>::operator++(int) {...}
    

    Das ist doch mal übersichtlich. 😉

    Zum IDE Thema. Ich nutze Netbeans und liebe dies. Das Code- und Commentfolding kann es auch, aber komischerweise nur in den CC Datein, bzw. unten in der Definition bei der h-Datei. Wenn die Methode direkt in der Deklaration auch definiert wird, dann unterstützt er das einklappen nicht. Ich finde es aber auch nicht schlimm. A) sieht die Deklaration sauberer aus, und 😎 lernt man dann wie hier wieder was dazu. 😃

    Lange rede kurzer sind, es klappt mit einem normalen iterator, aber beim const_iterator bekomme ich:

    conversion from ‘List<int>::Iterator<int>’ to non-scalar type ‘List<int>::Iterator<const int>’ requested
    

    Wenn ich:

    List<int> l;
    l.add(1);
    l.add(5);
    l.add(9);
    l.add(3);
    
    List<int>::const_iterator it = l.begin();
    

    versuche.

    Noch nen tip dazu??

    sven



  • List<T>::begin() scheint 2x überladen zu sein (so sollte es zumindest sein). einmal const-qualifiziert und einmal nicht. bei der nicht-konstanten liste wird das nicht-konstante begin aufgerufen was einen nicht-konstanten iterator zurückgibt.
    lösung (wenn mich nicht alles täuscht): (ungetestet!)

    // Wenn kein C++11 unterstützt ist:
    template<typename T>
    struct RemoveConst
    {
    	typedef T Type;
    };
    template<typename T>
    struct RemoveConst<const T>
    {
    	typedef T Type;
    };
    
    // Ansonsten einfach #include <type_traits>
    
    template<typename U>
    class BasicIterator : public std::iterator<std::forward_iterator_tag, U>
    {
    	pointer MyTarget;
    
    	// ...
    
    public:
    	BasicIterator(BasicIterator<typename RemoveConst<U>::Type> const& Rhs) // Wichtig: Impliziter Konstruktor!
    		: MyTarget(Rhs.MyTarget)
    	{
    	}
    
    	// ...
    };
    


  • ok ok,ich versteh was es mache soll, aber klappen tut es nicht. 😞

    ich nutze c++11, und habe daher meine definitionen so angepasst:

    template <typename L>
                class Iterator : public std::iterator<std::forward_iterator_tag, L>{
                    L * pos;
                    friend class List<T>;
                    explicit Iterator(L * aPos);
                public:
                    Iterator( Iterator<typename remove_const<L>::type > const & other)::pos(other.pos){}
    //...
    };
    

    Dies ergibt bei mir:

    error: template argument 1 is invalid
    List.h: In constructor ‘List<T>::Iterator<L>::Iterator(const int&)’:
    List.h:85: error: request for member ‘pos’ in ‘other’, which is of non-class type ‘const int’
    

    Da noch nen Tip??? 😞
    Ich weiß schon, warum ich bisher nen großen Bogen um Iteratoren gemacht habe. 😕



  • mh,

    sollte es nur ein inklude problem gewesen sein???? so kompiliert es:

    Iterator( Iterator<typename std::remove_const<L>::type > const & other):pos(other.pos){
                    }
    

    Man (oder ich) beachte das std::remove_const! 😃 😃

    ist damit der fall wohl geschlossen, was?



  • im ersten post hast du auch zwei doppelpunkte bei der initialisierungsliste!



  • ah, wie haben die sich den dahin geschmuggelt? im code standen die nicht. witzig.

    however, vielen dank für die hilfe! war ne super sache von dir. hätte ich allein nicht gewuppt bekommen! danke schön. 😃

    es grüßt der sven


Anmelden zum Antworten