STL-like iterator implementieren



  • Hallo,

    Ich interessiere mich für STL konforme Iteratoren, bzw. wie man diese schreibt.
    Ich brauche einen Iterator der als Interface auf einem anderen aufsetzt, und gewisse Dinge evtl. Protokolliert.
    Für den Anfang möchte ich einen "Counting Iterator" implementieren, der immer die genaue Position kennt:

    template<class Iterator>
    struct CountingIterator : Iterator // z.B. hier, ist Ableitung sinnvoll bzw. vorgesehen?
    {
    // und hier, gibt es virtuelle Methoden die Ich überladen muss, oder reichen die diversen operatoren (--,++,etc)
    }
    

    Gibt es irgendwo ein Tutorial oder Artikel zu dem Thema?
    Wo finde ich genauere Infos zum Iteratorinterface der STL?

    mfg.

    phlox



  • Für STL-Iteratoren gibt es keine Basisklasse. Das Interface ist rein syntaktisch festgelegt. Ein bidirektionaler Iterator etwa muß op++, op-- und op* implementieren. Zusätzlich natürlich noch Gleichheit/Ungleichheit, Zuweisung und Copy-Ctor.



  • Die Iteratoren haben keine virtuellen Methoden, nur die typischen*e* Operatoren (in meinem Magazin-Artikel "Aufbau der STL - Teil 3" hast du eine Liste, was du brauchst). Übrigens solltest du so einen Hilfs-Iterator nicht per Ableitung einbinden, sondern per Komposition - nimm dir an std::reverse_iterator ein Beispiel (Ableitung wird spätestens dann problematisch, wenn du einen die Position in einem Array mitschreiben willst - dessen Iterator ist ein einfacher Zeiger).



  • CStoll schrieb:

    ...die typsichen Operatoren ...

    Classic C++: Für "typsicher" und "typisch" braucht man keine getrennten Worte mehr. 😉

    Gruß,

    Simon2.



  • CStoll schrieb:

    Die Iteratoren haben keine virtuellen Methoden, nur die typsichen Operatoren (in meinem Magazin-Artikel "Aufbau der STL - Teil 3" hast du eine Liste, was du brauchst). Übrigens solltest du so einen Hilfs-Iterator nicht per Ableitung einbinden, sondern per Komposition - nimm dir an std::reverse_iterator ein Beispiel (Ableitung wird spätestens dann problematisch, wenn du einen die Position in einem Array mitschreiben willst - dessen Iterator ist ein einfacher Zeiger).

    Ok, Ableitung ist damit recht sinnlos.
    Komposition heisst dann nichts anderes, als das mein Iterator nur die Aufrufe an diesen weiterleitet, und evtl. vorher entsprechende Checks durchführt?
    Wäre dies dann die Implementation?:

    template<typename Iterator>
    class CountingIterator : public iterator<bidirectional_iterator_tag,void,void,void,void>
    {
    protected:
      Iterator& it;
      unsigned int count;
    public:
      explicit CountingIterator(Iterator& i) : it(i),count(0) {}
    
      // Wertzuweisung *it=x
      CountingIterator & operator=(const typename Iterator::value_type& val )
      {
        *it = val;
        return *this;
      }
    
      //Dereferenzierung
      CountingIterator& operator*() {return *this;}
    
      //Inkrement
      CountingIterator & operator++() {count++; it++; return *this;}
      CountingIterator & operator++(int) {count++; ++it; return *this;}
      CountingIterator & operator--() {count--; it--; return *this;}
      CountingIterator & operator--(int) {count--; --it; return *this;}
    };
    

    Beim Op* bin ich mir noch nicht sicher, wie ich das an den unterliegenden Iterator weiterleite...

    phlox



  • Simon2 schrieb:

    CStoll schrieb:

    ...die typsichen Operatoren ...

    Classic C++: Für "typsicher" und "typisch" braucht man keine getrennten Worte mehr. 😉

    Das kommt davon, wenn man sich zu stark bemüht, grammatisch korrekt zu schreiben - die wenigen überlebenden Tipfehler fallen besonders stark auf 😃

    Edit @phlox: Ja, Komposition bedeutet, daß du alle Operationen an einen Member weiterleitest. Aber diese Implementierung funktioniert vermutlich nicht - zumindest die Präfix-Operatoren haben die falsche Semantik (und operator->() fehlt).

    Wie ich schon sagte - schau dir mal std::reverse_iterator<> an, um Anregungen zu holen (zu finden in der <utility>).



  • Hallo phlox,

    Die erste Adresse für die Info was ein Iterator ist, ist natürlich der C++-Standard Kapitel 42.1 Iterator requirements.
    Außerdem findest Du bei boost einiges darüber. Mit den boost.operators kannst Du leicht eigene Iteratoren bauen und mit [boost.iterators](file:///H:/Toolkit/boost_1_34_0/libs/iterator/doc/index.html) hast Du ein ganzes Iterator construction framework.

    Wie CStoll bin auch ich der Meinung, dass Ableitung von einem existierenden Iterator der falsche Weg ist. Eine Komposition wäre hier angebracht.

    Anbei ein kleines Beispiel mit einem Output-Iterator - das ist aber auch der einfachste ...

    #include <iostream>
    #include <iterator> // ostream_iterator
    #include <algorithm> // copy
    #include <boost/operators.hpp> // output_iterator_helper
    
    template< typename I, typename V >
    class CountOut : public boost::output_iterator_helper< CountOut< I, V > >
    {
    public:
        explicit CountOut( I base ) : m_cnt( 0 ), m_base( base ) {}
        CountOut& operator*()
        {
            return *this;
        }
        CountOut& operator++()
        {
            ++m_base;
            ++m_cnt;
            return *this;
        }
        CountOut& operator=( const V& value )
        {
            *m_base = value;
            return *this;
        }
    
        int count() const { return m_cnt; }
    
    private:
        int m_cnt;
        I m_base;
    };
    template< typename V, typename I >
    CountOut< I, V > make_countout( I i )
    {
        return CountOut< I, V >( i );
    }
    
    int main()
    {
        using namespace std;
        const char arr[] = "Hallo Welt";
        int anz = copy( arr, arr + sizeof(arr)/sizeof(*arr) - 1,
            make_countout< char >( ostream_iterator< char >( cout, "." ) ) ).count();
        cout << "\n" << anz << " mal ein Zeichen mit '.' geschrieben" << endl;
        return 0;
    }
    

    Gruß
    Werner



  • Ja, ein Itertaor ist ja letztendlich auch nur ein Pointer. Man muß eigentlich nur daran denken, die Pointer-Schnittstellen (Operatoren) zu implementieren.

    Es gibt aber von Boost auch das Iterator Construction Kit. 😉



  • Die Boostsachen sehen interessant aus, leider hab ich gerade nicht soviel Zeit mich auch noch in sowas einzulesen 😉

    Mein aktueller Iterator sieht so aus:

    template<typename Iterator>
    class CountingIterator : public std::iterator<typename std::iterator_traits<Iterator>::iterator_category,
    		      typename std::iterator_traits<Iterator>::value_type,
    		      typename std::iterator_traits<Iterator>::difference_type,
    		      typename std::iterator_traits<Iterator>::pointer,
                  typename std::iterator_traits<Iterator>::reference>
    {
    protected:
      Iterator& it;
      unsigned int count;
    public:
        typedef typename std::iterator_traits<Iterator>::reference   reference;
        typedef typename std::iterator_traits<Iterator>::pointer     pointer;
      explicit CountingIterator(Iterator& i) : it(i),count(0) {}
    
      // Wertzuweisung *it=x
      CountingIterator & operator=(const typename Iterator::value_type& val )
      {
        *it = val;
        return *this;
      }
    
      //Dereferenzierung
      //CountingIterator& operator*() {return *this;}
      reference operator*(){Iterator tmp = it;
    	return *--tmp;}
    
      bool operator!=(const CountingIterator& ci){return it != ci.it;}
    
      //Inkrement
      CountingIterator & operator++() {count++; it++; return *this;}
      CountingIterator & operator++(int) {count++; ++it; return *this;}
      CountingIterator & operator--() {count--; it--; return *this;}
      CountingIterator & operator--(int) {count--; --it; return *this;}
      unsigned int Getcount()const{return count;}
    };
    

    Problem jedoch ist, das bei:

    int main()
    {
    	std::string str = "This is a test for the Counting Iterator";
    	std::string::iterator beg,end;
    	beg = str.begin();
    	end = str.end();
    	CountingIterator<std::string::iterator> cbeg(beg),cend(end);
    	for(;cbeg != cend;cbeg++)
    	{
    	    std::cout << *cbeg << " " << cbeg.Getcount() << std::endl;
        }
    	return 0;
    }
    

    ...er 1 Element zu früh aufhört...
    Woran liegt das?

    phlox



  • phlox81 schrieb:

    Wäre dies dann die Implementation?:

    template<typename Iterator>
    class CountingIterator : public iterator<bidirectional_iterator_tag,void,void,void,void>
    {
    

    zum einen solltest Du hier std:: benutzen, da dies sicher in einer H-Datei steht und dort using namespac std nicht angebracht ist und das void,void,void,.. ist so nur für einen Output-Iterator zulässig, aber nicht für einen bidirectional iterator.

    phlox81 schrieb:

    public:
      CountingIterator & operator=(const typename Iterator::value_type& val )
    

    hier muss es

    CountingIterator & operator=(const typename std::iterator_traits< Iterator >::value_type& val )
    

    heißen (mit const) sonst kannst Du hier nicht den Returnwert einer Funktion (z.B. begin()) übergeben. Konsequenterweise darf der Member 'it' dann keine Referenz sein.

    phlox81 schrieb:

    CountingIterator & operator=(const typename Iterator::value_type& val )
    

    korrekt wäre hier

    CountingIterator & operator=(const typename std::iterator_traits< Iterator >::value_type& val )
    

    phlox81 schrieb:

    //Dereferenzierung
      CountingIterator& operator*() {return *this;}
    

    Ist nur ok für Output-Iteratoren nicht für bidirektionale Iteratoren

    phlox81 schrieb:

    //Inkrement
      CountingIterator & operator++() {count++; it++; return *this;}
      CountingIterator & operator++(int) {count++; ++it; return *this;}
      CountingIterator & operator--() {count--; it--; return *this;}
      CountingIterator & operator--(int) {count--; --it; return *this;}
    };
    

    Die In/Dekrentoperatoren mit (int) müssen heißen

    CountingIterator operator++(int) { CountingIterator tmp( *this ); this->operator++(); return tmp;}
    

    außerdem reicht es in jedem Fall den prefix-++-operator von 'it' zu benutzen.

    Gruß
    Werner



  • phlox81 schrieb:

    ...er 1 Element zu früh aufhört...
    Woran liegt das?
    phlox

    wahrscheinlich daran:

    phlox81 schrieb:

    //Dereferenzierung
      //CountingIterator& operator*() {return *this;}
      reference operator*(){Iterator tmp = it;
    	return *--tmp;}  // <---------------
    


  • Jo, das war noch ein C&P Error 🙂 Jetzt klappts.


Log in to reply