STL-like iterator implementieren

[CStoll]

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).

[Simon2]

CStoll schrieb:

...die typsichen Operatoren ...

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

Gruß,

Simon2.

[phlox81]

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

[CStoll]

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>).

[Werner Salomon]

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

[Artchi]

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.

[phlox81]

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

[Werner Salomon]

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

[Werner Salomon]

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;}  // <---------------

[phlox81]

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