Fibonaccizahlen, Iteratoren und andere Spielereien

[Werner Salomon]

Dieser Thread über Fibonaccizahlen motivierte mich zu folgendem Beitrag.

Fibonaccizahlen sind eine Folge von Zahlen; und Folgen kann man in C++ am ehesten durch Iteratoren ausdrücken. Also kann man sich einen Iterator vorstellen, der mit jedem Inkrementieren zur nächsten Fibonaccizahl springt.
Da muss man auch nicht alles selber schreiben, da boost.iterator_adaptor bereits das passende Werkzeug bereithält.

Heraus kommt:

#include <boost/iterator/iterator_adaptor.hpp>
#include <iostream>

namespace fibonacci
{
    template< typename T >
    class iterator : public boost::iterator_adaptor< 
        iterator< T >, // abgeleitete Klasse
        T, // Basis-Iterator (hier z.B. ein int)
        T, // Value: ist hier T (z.B. der int selbst); deshalb muss die Methode dereference() implementiert werden (s.u.)
        boost::forward_traversal_tag, // Bewegungsrichtung des Iterators
        T, // Referenztyp ist keine Referenz; d.h. -> input-iterator nur lesend
        int > // Differenztyp
    {
    public:
        friend class boost::iterator_core_access; // somit können increment() u.a private bleiben
        explicit iterator( T f_n_minus_1, T f_n )
            : iterator_adaptor_( f_n )
            , prev_( f_n_minus_1 )
        {}

    private:
        void increment()
        {   // --   Fibonacci-Schritt f_i+1 = f_i-1 + f_i
            const T tmp = prev_ + base();
            prev_ = base();
            base_reference() = tmp;
        }
        typename iterator_adaptor_::reference dereference() const
        {
            return base();
        }

        // --   Member
        T prev_; // vorhergehendes Fibonacci-Element
    };
}

.. und die Aufgabe mit der Ausgabe der 4-stelligen Fibonaccizahlen lässt sich damit elegant lösen:

int main()
{
    using namespace std;
    // --   gibt alle 4-stelligen Fibonaccizahlen aus
    for( fibonacci::iterator< int > fibo(1,0); *fibo < 10000; ++fibo )
        if( *fibo >= 1000 )
            cout << *fibo << " ";
    cout << endl;
    return 0;
}

Was hier fehlt ist ein Ende-Iterator. Eine Fibonaccifolge hat kein Ende - in unserer beschränkten Welt von short bis long ist natürlich irgendwann Schluss.
Ich löse das hier, indem ich eine Policy einführe, die angibt ob das Ende erreicht ist. Das Policy-Objekt ist ein Funktor, der in diesem Fall true liefert, wenn zwei Werte übergeben werden, deren Addition zu einem numerischen overflow führt. Dabei muss ich noch zwischen signed und unsigned unterscheiden:

#include <limits>
#include <type_traits> // std::enable_if<>, std::is_unsigned<> u.a.

template< typename T, typename Enabler = void >
struct overflow_plus;

template< typename T >
struct overflow_plus< T, typename std::enable_if< std::is_unsigned< T >::value >::type >
{
    bool operator()( T a, T b ) const
    {
        return a > std::numeric_limits< T >::max() - b;
    }
};
template< typename T >
struct overflow_plus< T, typename std::enable_if< std::is_signed< T >::value >::type >
{
    bool operator()( T a, T b ) const
    {
        return b >= T(0)? a > std::numeric_limits< T >::max() - b
            : a < std::numeric_limits< T >::min() - b;
    }
};

In der 2.Version muss dann noch die Abfrage auf 'Ende' beim Inkrementieren und auch beim Vergleich zweier Iteratoren implementiert werden:

#include <boost/iterator/iterator_adaptor.hpp>
#include <algorithm> // copy
#include <iostream>
#include <cassert>
#include <iterator> // std::ostream_iterator

// overflow-Policy (s.o.)

namespace fibonacci
{
    template< typename T, typename EndPolicy = overflow_plus< T > >
    class iterator : public boost::iterator_adaptor< 
        iterator< T, EndPolicy >, // abgeleitete Klasse
        T, // Basis-Iterator (hier z.B. ein int)
        T, // Value: ist hier T (z.B. der int selbst); deshalb muss die Methode dereference() implementiert werden (s.u.)
        boost::forward_traversal_tag, // Bewegungsrichtung des Iterators
        T, // Referenztyp ist keine Referenz; d.h. -> input-iterator nur lesend
        int > // Differenztyp
    {
    public:
        friend class boost::iterator_core_access; // somit können increment() u.a private bleiben
        explicit iterator( T f_n_minus_1, T f_n, EndPolicy e = EndPolicy() )
            : iterator_adaptor_( f_n )
            , prev_( f_n_minus_1 )
            , end_condition_( e )
            , is_end_( false ) // der erste Iterator kann kein Ende-Iterator sein
        {}
        explicit iterator() // default iterator ist Ende-Iterator
            : iterator_adaptor_()
            , prev_()
            , end_condition_()
            , is_end_( true ) 
        {}

    private:
        void increment()
        {   // --   Fibonacci-Schritt f_i+1 = f_i-1 + f_i
            assert( !is_end_ );
            if( !(is_end_ = end_condition_( prev_, base() )) )
            {
                const T tmp = prev_ + base();
                prev_ = base();
                base_reference() = tmp;
            }
        }
        typename iterator_adaptor_::reference dereference() const
        {
            return base();
        }
        bool equal( const iterator& b ) const
        {
            return (is_end_ && b.is_end_)
                || (!is_end_ && !b.is_end_ && base() == b.base());
        }

        // --   Member
        T prev_; // vorhergehendes Fibonacci-Element
        EndPolicy end_condition_;
        bool is_end_; // true, wenn das 'Ende' erreicht ist
    };
}

Und die Ausgabe aller unsigend long Fibonaccis ist dann einfach:

int main()
{
    using namespace std;
    // --   gibt alle unsigend long Fibonaccizahlen aus
    copy( fibonacci::iterator< unsigned long >(1,0), fibonacci::iterator< unsigned long >(), ostream_iterator< unsigned long >( cout, " " ) );
    cout << endl;
    return 0;
}

Zum Schluss eine Spielerei mit strings. Außer #include <string> füge man statt main() folgendes ein:

struct GrossGenug
{
    explicit GrossGenug( std::size_t maxi = 0 ) : maxi_( maxi ) {}
    bool operator()( const std::string& a, const std::string& b ) const
    {
        return a.size() + b.size() >= maxi_;
    }
    std::size_t maxi_;
};

int main()
{
    using namespace std;
    copy( fibonacci::iterator< string, GrossGenug >("-","|", GrossGenug(80)), fibonacci::iterator< string, GrossGenug >(), ostream_iterator< string >( cout, "\n" ) );
    cout << endl;
    return 0;
}

Der Output ist:

|
-|
|-|
-||-|
|-|-||-|
-||-||-|-||-|
|-|-||-|-||-||-|-||-|
-||-||-|-||-||-|-||-|-||-||-|-||-|
|-|-||-|-||-||-|-||-|-||-||-|-||-||-|-||-|-||-||-|-||-|

weitere Ideen, Kommentare?

Gruß
Werner

[Sone]

Das hast du ja ein wenig von mir geklaut, die Idee mit dem Iterieren, nech :p
Aber schön gelöst

[Werner Salomon]

Sone schrieb:

Das hast du ja ein wenig von mir geklaut, die Idee mit dem Iterieren, nech :p

Sone - Du bist viel zu jung, als dass ich die Idee bei dir geklaut haben könnte

Sone schrieb:

Aber schön gelöst

Danke

[Sone]

Werner Salomon schrieb:

Sone schrieb:

Das hast du ja ein wenig von mir geklaut, die Idee mit dem Iterieren, nech :p

Sone - Du bist viel zu jung, als dass ich die Idee bei dir geklaut haben könnte

?
Hast du den Thread denn nicht aufmerksam gelesen? Das Ding das ich damals gebastelt hab'... sieh es dir nochmal an...

[nwp3]

Auch auf die Gefahr als Ignorant dazustehen: Du hast aus einem Dreizeiler eine über 100 Zeilen große C++-Bestie gemacht. Als Spielerei ganz nett, aber unverständlich bis zum geht nicht mehr. Daher frage ich mal direkt: Ist das für dich eine ernsthafte Lösung oder mehr fürs C++-Äquivalent zum IOCCC?

[nnI]

Stimmt leider. Dafür braucht man nur eine Rekursive Methode mit 3 Zeilen ... Informatik 1. Semester ...

[Shade Of Mine]

Sone schrieb:

Hast du den Thread denn nicht aufmerksam gelesen? Das Ding das ich damals gebastelt hab'... sieh es dir nochmal an...

Also ich sehe da keine Aehnlichkeit.

[cooky451]

nnI schrieb:

Stimmt leider. Dafür braucht man nur eine Rekursive Methode mit 3 Zeilen ... Informatik 1. Semester ...

Fail! Abgesehen davon, dass die rekursive Variante hier so ziemlich das dümmste ist was man in C++ (und in den meisten anderen Sprachen) machen kann, ist z.B. das Ausgeben der Zahlen von n! bis m! grundsätzlich wesentlich teurer mit deiner 3-Zeilen Variante. (Oder du hast deine Ausgabe direkt im Algorithmus drin, was natürlich auch schwachsinnig ist.) Und Overflow-Protection hast du da auch nicht drin, von einer auswählbaren Policy mal ganz zu schweigen. Man mag darüber streiten ob man das nicht auch ohne boost implementieren hätte können, aber die Iteratorvariante mit dem Schulaufgaben-Dreizeiler zu vergleichen, zeugt einfach nur von völliger Ahnungslosigkeit.

[dodapisa]

Werner Salomon schrieb:

Fibonaccizahlen sind eine Folge von Zahlen; und Folgen kann man in C++ am ehesten durch Iteratoren ausdrücken.

Damit triffst du genau meinen Nerv. So interpretiert ermöglicht das Iteratorenkonzept eine funktionale Programmierung mit Lazy Evaluation.

Werner Salomon schrieb:

Was hier fehlt ist ein Ende-Iterator. Eine Fibonaccifolge hat kein Ende - in unserer beschränkten Welt von short bis long ist natürlich irgendwann Schluss.
Ich löse das hier, indem ich eine Policy einführe, die angibt ob das Ende erreicht ist.

Das gefällt mir weniger. Es ist mMn nicht die Aufgabe eines Iterators herauszufinden, ob er am Ende ist oder nicht. Keep Iterators Simple, Stupid (oder so).
Dein Design funktioniert auch nur halb. Ich sehe zumindest keine Lösung mit deinem Iterator, die die 4-stelligen Fibonaccizahlen ausgibt und ohne Schleifen auskommt.
Eine unendliche Folge ist kein Weltuntergang, der ostream_iterator hat auch kein Ende. Dummerweise gibt es nur einen Algorithmus in der Standardbibliothek, der unendliche Input-Iteratoren erlaubt, copy_n . Deshalb habe ich mir ein copy_until geschrieben und damit kann das Problem ähnlich kurz gelöst werden:

int main()
{
  /*
    // --   gibt alle 4-stelligen Fibonaccizahlen aus
    for( fibonacci::iterator< int > fibo(1,0); *fibo < 10000; ++fibo )
        if( *fibo >= 1000 )
            cout << *fibo << "\n";
  */
  fibonacci_iterator<long> it(0, 1);
  copy_until<fibonacci_iterator<long>&>(it, [](long i){return i<1000;}, discard_iterator{});
  copy_until(it, [](long i){return i<10000;}, std::ostream_iterator<long>(std::cout, "\n"));

  /*
    // --   Spielerei mit strings
    copy( fibonacci::iterator< string, GrossGenug >("-","|", GrossGenug(80)), 
          fibonacci::iterator< string, GrossGenug >(),
          ostream_iterator< string >( cout, "\n" ) );
  */
  copy_until(fibonacci_iterator<std::string>("-", "|"),
             [](std::string const& s){ return s.size() < 80; },
             std::ostream_iterator<std::string>(std::cout, "\n"));
}

Zeile 10 ist im Prinzip ein find_if , nur ohne End-Iterator. Anstatt ein infinite_find_if zu schreiben, habe ich mich für einen discard_iterator entschieden. In Zeile 22 spare ich mir etwas Boilerplate für [c]GrossGenug[c]. Weil dein Iterator bei mir nicht kompiliert (vielleicht habe ich eine zu alte Boost-Version), habe ich ihn in begrenzterer Form noch einmal geschrieben.

template< typename T >
struct fibonacci_iterator : std::iterator<std::input_iterator_tag, T> {
  T curr, prev;
public:
  fibonacci_iterator( T f_n_minus_1, T f_n ) : curr(f_n), prev(f_n_minus_1) {}

  fibonacci_iterator& operator++() {
    std::tie(curr, prev) = std::make_tuple(curr+prev, curr); return *this; }
  fibonacci_iterator operator++(int) { auto t=*this; ++*this; return t; }
  T operator *() { return curr; }
};

struct discard_iterator : std::iterator<std::output_iterator_tag, void, void, void, void> {
  discard_iterator& operator++(   ) { return *this; }
  discard_iterator& operator++(int) { return *this; }
  discard_iterator& operator *(   ) { return *this; }
  template <typename T> void operator=(T) { }
};

template< typename InputIt, class Pred, typename OutputIt>
OutputIt copy_until(InputIt first, Pred pred, OutputIt result)
{
  while (pred(*first))
    *result++ = *first++;
  return result;
}

[blubblub]

cooky451 schrieb:

nnI schrieb:

Stimmt leider. Dafür braucht man nur eine Rekursive Methode mit 3 Zeilen ... Informatik 1. Semester ...

Fail! Abgesehen davon, dass die rekursive Variante hier so ziemlich das dümmste ist was man in C++ (und in den meisten anderen Sprachen) machen kann, ist z.B. das Ausgeben der Zahlen von n! bis m! grundsätzlich wesentlich teurer mit deiner 3-Zeilen Variante. (Oder du hast deine Ausgabe direkt im Algorithmus drin, was natürlich auch schwachsinnig ist.) Und Overflow-Protection hast du da auch nicht drin, von einer auswählbaren Policy mal ganz zu schweigen. Man mag darüber streiten ob man das nicht auch ohne boost implementieren hätte können, aber die Iteratorvariante mit dem Schulaufgaben-Dreizeiler zu vergleichen, zeugt einfach nur von völliger Ahnungslosigkeit.

Was soll denn die Ausgabe der Fibonaccizahlen anderes sein, als eine Schulaufgabe?

[CJosef]

Werner Salomon schrieb:

weitere Ideen, Kommentare?
Gruß
Werner

Ja.
Kommentar: Blähware!
Idee: beschränke dich aufs Notwendige und mach da keinen Hermann Werner draus!
Gruß
Josef

[DasErinnertMichAnEtwas]

Die Homor Seite des Forums geht nicht mehr, aber ich habs trotzdem mit google noch gefunden
http://www.c-plusplus.net/evolution.htm

Irgendwo zwischen Stufe 5: Erfahrener Softwareentwickler und Stufe 6: Chefentwickler

[Sone]

Shade Of Mine schrieb:

Sone schrieb:

Hast du den Thread denn nicht aufmerksam gelesen? Das Ding das ich damals gebastelt hab'... sieh es dir nochmal an...

Also ich sehe da keine Aehnlichkeit.

lol, auch nicht, dass meins iterierbar ist? Dann musst du schon blind sein, Shade, und das bist du nicht...

P.S.: Wegen der Ähnlichkeit: Es ging nicht darum, wie das ganze implementiert wird. Klar, seine Lösung sieht ganz anders aus.

[Cyres]

Sone schrieb:

Shade Of Mine schrieb:

Sone schrieb:

Hast du den Thread denn nicht aufmerksam gelesen? Das Ding das ich damals gebastelt hab'... sieh es dir nochmal an...

Also ich sehe da keine Aehnlichkeit.

lol, auch nicht, dass meins iterierbar ist? Dann musst du schon blind sein, Shade, und das bist du nicht...

P.S.: Wegen der Ähnlichkeit: Es ging nicht darum, wie das ganze implementiert wird. Klar, seine Lösung sieht ganz anders aus.

Soviel ich weiß, hast du die Iteratoren nicht erfunden und dass man Folgen als Iteratoren gut abbilden kann, ist jedem bekannt, der etwas von Informatik versteht.

[Shade Of Mine]

Sone schrieb:

P.S.: Wegen der Ähnlichkeit: Es ging nicht darum, wie das ganze implementiert wird. Klar, seine Lösung sieht ganz anders aus.

Deine Loesung ist eine vorberechnete Sequence.
Werner Salomon Loesung ist ein iterator.

Natuerlich kann man aus einem iterator eine Sequence machen und eine Sequence iterieren - aber der grundlegende Ansatz ist komplett verschieden.

Werner Salomon berechnet on the fly die naechste Zahl und kann somit unendlich fibonacci Zahlen generieren - waehrend du alle Zahlen in einem Bereich berechnest und in einen Container steckst.

Das sind absolut unterschiedliche Sachen.

[derzweizeiler]

for (int i=0,f[2]={0,1};f[i%2]<=9999;++i,f[i%2]=f[0]+f[1])
    if (f[i%2]>999) std::cout << f[i%2] << '\n';

[Sone]

Was mir gerade auffällt: Ich weiß, es passt nicht zum Iteratoren-Modell von C++, aber wie wäre denn ein Java-like Iterator? Einer, der eine Methode hasMore() bereitstellt?
Das wäre doch einfacher als deine Policy.

nwp3 schrieb:

Auch auf die Gefahr als Ignorant dazustehen: Du hast aus einem Dreizeiler eine über 100 Zeilen große C++-Bestie gemacht. Als Spielerei ganz nett, aber unverständlich bis zum geht nicht mehr. Daher frage ich mal direkt: Ist das für dich eine ernsthafte Lösung oder mehr fürs C++-Äquivalent zum IOCCC?

Wenn du mich meinst: Spielerei natürlich ^^

[Werner Salomon]

Zunächst dachte ich ja da meldet sich keiner mehr, aber jetzt sieht's schon gut aus

Da Sone hier wohl den meisten Raum einnimmt

Sone schrieb:

Hast du den Thread denn nicht aufmerksam gelesen? Das Ding das ich damals gebastelt hab'... sieh es dir nochmal an...

Welcher Thread - gibt es da einen Link? Was hast Du gebastelt, was soll ich mir ansehen?

Meine älteste Datei, hier auf dem PC, an dem ich gerade sitze, die eine Fibonacciiterator-Implementierung enthält, hat einen Zeitstempel von 2008 - und das war lange nicht die erste. Ich glaub' das habe ich mal für eine Project-Euler-Aufgabe gemacht. Da warst Du (Sone) noch nicht mal hier im Forum registriert.
Und die Idee so etwas in einen Iterator zu pressen, haben sicher schon viele gehabt - sogar Sone (wie's aussieht).

CJosef schrieb:

Blähware!
Idee: beschränke dich aufs Notwendige und mach da keinen Hermann Werner draus!

Vielleicht hätte ich noch ein paar einleitende Worte spendieren sollen.
Zunächst mal ist das hier eine Spielerei - zumal mit der Anwendung auf Fibonaccizahlen. Natürlich kann man es reduzieren

nnI schrieb:

Dafür braucht man nur eine Rekursive Methode mit 3 Zeilen

auch ohne Rekursion käme man mit weniger als 3 Zeilen hin. Aber darum ging es gar nicht.

Motivation 1 war einfach mal zu zeigen, es geht.

Motivation 2 ist auch zu zeigen, wie (und dass!) man das Iterieren kapseln kann (in einem Iterator - wie sinnig). Außer iterieren wird in dem hier vorliegenden Beispiel nicht viel gemacht - die Zahl wird schlicht ausgegeben. Deshalb kommt das hier auch nicht so raus, wo da der Vorteil sein soll - mea culpa.
Aus meiner beruflichen Praxis sind mir aber ad hoc zwei Fälle bekannt, wo iterieren und bearbeiten des aktuellen Elements ein etwas chaotischer Code von mehreren tausend Zeilen geworden sind. Spitzenreiter war eine for-Schleife mit knapp 1000 Zeilen, die gespickt war mit Fallunterscheidungen und Funktionsaufrufen, die sowohl die Iteration, als auch die Bearbeitung betrafen. Dieser Code wurde nur noch von zwei Leuten gleichzeitig bearbeitet, da man Angst hatte, dass einer allein vielleicht etwas übersieht. Ich hatte irgendwann mal entschieden, alles weg zu werfen und neu zu schreiben (mit Iterator) - ich habe es nie bereut - ganz im Gegenteil.

cooky451 schrieb:

Man mag darüber streiten ob man das nicht auch ohne boost implementieren hätte können, aber die Iteratorvariante mit dem Schulaufgaben-Dreizeiler zu vergleichen, zeugt einfach nur von völliger Ahnungslosigkeit.

cooky451 scheint ähnlich gelagerte Fälle zu kennen.
Darüber hinaus ist es nämlich in vielen Fällen der Praxis gar nicht offensichtlich, dass überhaupt eine Iteration vorliegt (wie z.B. bei einer Zahlenfolge).

Motivation 3 war zu zeigen, wie es mit boost.iterator geht. Hat man die Auswahl der Template-Argumente erst mal überstanden, dann ist der Rest fast geschenkt. Find' ich persönlich einfach mal cool - das ist genau dass was Bjarne Stroustrup mit Spaß an der Programmierung meint. Ob man das im Einzelfall auch einsetzt oder nicht, sollte natürlich von anderen Kriterien abhängen - aber in einem Forum wie hier ist das doch ein lohnendes Thema - IMHO.

:xmas2: Werner

(to be continued)

[Sone]

Gut gut, war auch nur eine Vermutung. :xmas2:
(Mit "den Thread" meinte ich den Thread den du im ersten Post verlinkt hast. Da habe ich auch was iterierbares gebastelt, dachte du hast die Idee genommen und was schöneres draus gemacht, war offensichtlich nicht der Fall)

[Werner Salomon]

Hallo dodapisa,

Danke für Deinen Beitrag

dodapisa schrieb:

Es ist mMn nicht die Aufgabe eines Iterators herauszufinden, ob er am Ende ist oder nicht. Keep Iterators Simple, Stupid (oder so).

das ist die Frage, im Grunde tut das doch jeder Iterator irgendwie. Allen voran die istream- und istreambuf-Iteratoren. Der istream_iterator versucht in seiner operator++-Methode ein weiteres Element zu lesen. Er merkt sich (muss sich merken) wenn das schief geht. Und damit wird er dann zum Ende-Iterator.
Weiter sind mir auch Implementierungen von Iteratoren Assoziativer Container (map, set, etc.) bekannt, die ganz klar im operator++ feststellen - ich bin am Ende und ein interner Zeiger bekommt dann einen definierten Wert, der identisch ist, mit dem des Ende-Iterators.

dodapisa schrieb:

Dein Design funktioniert auch nur halb. Ich sehe zumindest keine Lösung mit deinem Iterator, die die 4-stelligen Fibonaccizahlen ausgibt und ohne Schleifen auskommt.

Zwei Vorschläge dazu:

typedef fibonacci::iterator< int, function< bool( int, int ) > > Fibo;
    copy( find_if( Fibo( 1,0, []( int prev, int fn )->bool { return prev + fn >= 10000; } ), Fibo(), []( int fn )->bool { return fn >= 1000; } ), Fibo(),
        ostream_iterator< int >( cout << "Die 4-stelligen Fibonaccizahlen lauten: ", " " ) );
    cout << endl;

und

auto _4stellig = []( int fn )->bool { return fn >= 1000 && fn < 10000; };
    copy( boost::make_filter_iterator( _4stellig, fibonacci::iterator< int >(1,0) ), boost::make_filter_iterator( _4stellig, fibonacci::iterator< int >() ),
        ostream_iterator< int >( cout << "Die 4-stelligen Fibonaccizahlen lauten: ", " " ) );
    cout << endl;

dodapisa schrieb:

Eine unendliche Folge ist kein Weltuntergang, der ostream_iterator hat auch kein Ende.

Der ostream_iterator ist ein Outputiterator und der Fibonacci-Iterator ist ein Inputiterator. Das gilt für alle Zahlenfolgen-Iteratoren.
Für einen Outputiterator ist z.B. ein ==-Operator gar nicht gefordert, da ein Algorithmus (z.B. copy) den aktuellen Outputiterator nie auf Ende abfragt. damit ist auch kein Ende-Iterator erforderlich. Inputiteratoren ohne Ende gehen nur mit den *_n-Algorithmen - außer copy_n fällt mir i.A. gar keiner ein.
D.h. ohne Endeiterator müsste man auf die ganzen schönen Vorteile der Algorithmen verzichten.

dodapisa schrieb:

Dummerweise gibt es nur einen Algorithmus in der Standardbibliothek, der unendliche Input-Iteratoren erlaubt, copy_n . Deshalb habe ich mir ein copy_until geschrieben und damit kann das Problem ähnlich kurz gelöst werden: ...

So was wie until-Algorithmen hatte ich auch schon mal im Focus. Aber außer bei Project-Euler (alles geht bis unendlich) hatte ich dafür praktisch keine Verwendung.

dodapisa schrieb:

Weil dein Iterator bei mir nicht kompiliert (vielleicht habe ich eine zu alte Boost-Version), habe ich ihn in begrenzterer Form noch einmal geschrieben.

Ich benutze VS10 mit boost 1.48 - was benutzt Du?

Gruß
Werner