STL-kompatibler Iterator für eigene Datenstruktur



  • Hi,

    ich schreibe gerade einen Wrapper für eine C-Lib, die fleißig Linked Lists verwendet (natürlich eigene Implementation).

    Ich möchte um diese Linked Lists nun einen Wrapper bauen, so dass ich später z.B. mit std::find u.a. darauf zugreifen kann. Die zugrunde liegende LL ist bidirektional.

    Nun habe ich im Internet gesucht (und hier im Forum), wie man das am besten anstellt. Da scheinen sich aber die Meinungen zu unterscheiden, was nun richtig ist. Subclasse ich std::iterator? Schreibe ich einfach einen eigenen Iterator der alle nötigen Operatoren/Datentypen anbietet? Benutze ich boost? In mehreren Threads (bei Stack Overflow) habe ich gelesen, dass es nun out ist, std::iterator zu subclassen, warum hab ich nicht verstanden.

    Wie mache ich das nun richtig? Wie gesagt, Ziel ist es, via Wrapper die Linked List per STL-Algorithmen ansprechen zu können, zweites Ziel ist einfach, dass ich Zugriff auf die Datenstruktur in STL-gewohnten Methoden anbiete.



  • Welche weitere Erkenntnis hoffst du mit dieser Frage zu gewinnen?



  • manni66 schrieb:

    Welche weitere Erkenntnis hoffst du mit dieser Frage zu gewinnen?

    Diese Gegenfrage finde ich jetzt mal reichlich sinnlos und seine Frage legitim.

    Wenn ich spezielle iteratoren brauche benutze ich meistens boost::iostreams, weil nach C++ standard einen iterator zu bauen AFAIR eklig ist. Da gibts auch nen tut zu in der dokumentation.
    Warte aber nochmal andere Antworten ab.



  • Also ich hab jetzt für meinen Wrapper einfach wie gewohnt begin() und end() definiert sowie ein Memberklasse "iterator" die das kann, was ein Forward-Iterator laut Doku können muss.

    Ich kann jetzt wie gewünscht z.B. std::find() auf den Wrapper loslassen und das tut was es soll.

    Ob das jetzt der richtige Weg war, oder ob es überhaupt einen einzigen richtigen Weg gibt, weiß ich nicht. Das war die Frage, aber dass manni66 ein nutzloser Schwachkopf ist, war mir eigentlich schon bekannt.

    Vielleicht mag jemand anderes noch eine Bewertung abgeben, ob und wie man das korrekt löst.



  • .. mit boost::iterator ist das tatsächlich sehr einfach (wenn man weiß, wie's geht)
    Beispiel:

    #include <boost/iterator/iterator_adaptor.hpp>
    #include <algorithm>
    #include <cassert>
    #include <iostream>
    
    struct Node
    {
        Node* next;
        int i;
        double d;
    };
    
    class NodeIterator : public boost::iterator_adaptor< NodeIterator, Node*, Node, boost::forward_traversal_tag >
    {
    public:
        explicit NodeIterator( Node* ptr = nullptr )
            : iterator_adaptor_( ptr )
        {}
    
    private:
        friend boost::iterator_core_access;
    
        void increment()
        {
            assert( base() );
            base_reference() = base()->next;
        }
    };
    
    int main()
    {
        using namespace std;
        // C-Stuff
        Node a;
        a.i = 13; a.d = 3.14;
        Node b;
        b.i = 14; b.d = -0.009;
        a.next = &b;
        b.next = nullptr; // -> NIL
    
        // C++
        auto iNode = find_if( NodeIterator(&a), NodeIterator(), []( const Node& nd ) { return nd.d < 0.; } );
        if( iNode != NodeIterator() )
            cout << "Knoten " << iNode->i << " gefunden" << endl;;
        return 0;
    }
    

    siehe auch https://www.c-plusplus.net/forum/p2232768#2232768

    mit diesen beiden Funktionen

    NodeIterator begin( Node& nd )
    {
        return NodeIterator( &nd );
    }
    NodeIterator end( Node& /*nd*/ )
    {
        return NodeIterator();
    }
    

    kannst Du ab Zeile 42 noch etwas syntaktischen Zucker hinzufügen:

    auto iNode = find_if( begin(a), end(a), []( const Node& nd ) { return nd.d < 0.; } );
        if( iNode != end(a) )
            cout << "Knoten " << iNode->i << " gefunden" << endl;
    

    dann ginge auch:

    for( auto nd: a ) // alle Knoten ausgeben
            cout << "Knoten #" << nd.i << endl;
    

    Gruß
    Werner

    @Edit: hinzugefügt for( auto nd: a )



  • Vielen Dank, das sieht gut aus, dann schaue ich mir mal boost::iterator an!


Anmelden zum Antworten