Binäre Suche: Ist meine Implementation korrekt und "idiomatisch"? (Iteratoren)



  • Unabhängig davon, dass man natürlich auf etablierte Bibliotheken zurückgreifen sollte, wenn möglich. v ist der (sagen wir: immer korrekt) vorsortierte "Heuhaufen", t ist die "Nadel".

    EDIT: Ich habe die bisher aufgezeigten Verbesserungen hineineditiert (Stand: nach zeropages zweitem Post).
    Ich vermute, begin und end sollten nicht by-reference übergeben werden, da Iteratoren kleine Objekte sind und die Funktion, die bsearch() aufruft, möglicherweise nicht will, dass die Iteratoren verändert werden.
    Tatsächlich merke ich auch, dass ich nicht auf Anhieb weiß, wie man std::vector hier zugunsten jedes möglichen Containers mit eingebautem (RA-)Iterator weggenerisiert. Wenn ich da nicht weiterkommen sollte (oder aber Ergebnisse vorweisen kann), melde ich mich noch einmal.

    #include <vector>
    
    template <typename T> bool
    bsearch(std::vector<T>::iterator begin, std::vector<T>::iterator end, const int t) {
        while(begin != end) {
            auto midpoint = begin + (end - begin) / 2;
            if(*midpoint == t)
                return true;
            else if(*midpoint > t)
                end = midpoint;
            else 
                begin = midpoint + 1;
        }
        return false;
    } 
    // [...]
    

    Für kleine Ganzzahlvektoren habe ich den Code getestet. Vor allem betreffs Zeile 6 frage ich mich allerdings z.B., ob für "sehr große" v irgendetwas schiefgehen könnte. Auch Kritiken des reinen Stils sind willkommen d.h. auch Vorschläge zu HIlfsmitteln in C++, die den Code noch vereinfachen.



  • Ganz kurz, was mir auf den ersten Blick nicht gefällt...

    • Warum ist v nicht const?
    • Man würde viel eher Iteratoren reingeben, keinen vector. Und dann das ganze gleich generisch schreiben, sonst macht es wenig Sinn.
    • Die zusätzlichen if Abfragen in > < finde ich sehr unschön.


  • Wozu brauchst Du überhaupt die zwei Zeilen 10 und 13?:

     if(begin + 1 == end) return false;
    

    Dein Algorithmus funktioniert auch, wenn Du die weglässt.



  • Zeile 14 musst Du noch korrigieren:

     begin = midpoint + 1;
    


    • Z. 10 ist tatsächlich Blödsinn. 13 dagegen ist, zumindest wenn man sonst nichts ändert, unabdingbar (ohne Z. 13 landet man ggf. in einer Endlosschleife, weil "begin = midpoint" nicht garantiert, dass der Iterator dadurch verschoben wird: ist nämlich end == begin + 1, so ist midpoint == begin, und damit ist garantiert vor und nach Z. 14 immer noch begin != end).

    fake edit: Stimmt -- mit begin = midpoint + 1 funktioniert es dann natürlich, und das ist die bessere Lösung.

    • v sollte tatsächlich const sein. Das war schlicht unaufmerksam.
    • Der Hinweis auf generische Programmierung ist berechtigt. -- Mir war bereits klar, dass man nicht nur ints sortieren kann (es geht mir hier eher um Anfängerfehler beim Iteratorengebrauch), sondern auch Objekte jeder Klasse mit totaler Ordnungsrelation; natürlich geht auch "template <typename T> bool bsearch(const std::vector<T>& v [usw.])".

    edit: Moment -- Du meinst dann natürlich wahrscheinlich auch generische Container.



  • @Shamshir sagte in Binäre Suche: Ist meine Implementation korrekt und "idiomatisch"? (Iteratoren):

    • v sollte tatsächlich const sein. Das war schlicht unaufmerksam.

    Ist jetzt aber nicht const, sondern eine Referenz.



  • Ja, ich meine, dass ich "const std::vector<T>&" hätte schreiben sollen. Ich war unaufmerksam, meinte ich damit.



  • Ahso, sorry, ich dachte, Du hattest inzwischen editiert.



  • Du hast deinen ursprünglichen Beitrag editiert, das macht es unübersichtlich. Ich hätts auch fast nicht gesehen.
    Den vector zu generalisieren ist eigentlich recht einfach, du machst einfach noch einen Template-Parameter für den Iterator Typ.

    template <typename Iter, typename T>
    

    Und der zweite Parameter der Funktion sollte dann natürlich vom Typ T und nicht int sein.



  • Ich beschloss zu editieren, nachdem zeropage anscheinend erwartet hatte, ich hätte den Code inzwischen editiert. Ich hatte daher vermutet, es wäre hier üblich, zu redigieren; vorher hatte ich darauf verzichtet. Tu ich dann auch in Zukunft wieder 🙃

    Ich verstehe, dass es eigtl. mehr Sinn ergibt, gleich den Iterator generisch darzustellen statt des Containers, das ist ja dann auch keine Schwierigkeit mehr.

    Aus irgendwelchen aus der Luft gegriffenen Gründen störte mich daran, dass man die Funktion bsearch() dann z.B. mit

    template <typename Iter, typename T> bool 
    bsearch(Iter begin, Iter end, const T& t) { /* ... */ }
    // ...dann irgendwann:
    std::vector<float> v = { /* ... */ };
    const int foo = 12;
    bsearch<std::vector<float>::iterator, int>(v.begin(), v.end(), foo)
    

    aufrufen konnte. Ich wollte also zur Kompilierzeit sicherstellen, dass der Container stets Elemente desselben Typs enthält, dem auch das gesuchte Objekt angehört. (Nebenbei: mit T jetzt natürlich by-reference.)

    Dummerweise scheiterte ich da an der Syntax des Headers bei verschachtelten Templates.

    template <typename Container template <typename T>> bool
    bsearch(Container<T>::iterator begin, /*...*/) // => Syntaxfehler!
    

    Bitter. Ich habe da noch einige andere Fehlkonstruktionen produziert und schließlich eingesehen, dass ich das Templateverschachteln syntaktisch eindeutig noch nicht durchschaut habe. Das Prinzip natürlich schon:

    bsearch :: (Ord a) => [a] -> a -> Bool 
    

    Ist doch alles ganz einfach. 👁 Spaß beiseite.

    Nach Recherche darüber, wie man Typen vergleicht und an den Typ eines dereferenzierten Iterators kommt, habe ich eine andere Lösung gefunden:

     static_assert(std::is_same<T, typename std::iterator_traits<Iter>::value_type>::value); 
    

    KISS. Das ginge natürlich auch mit dem Container sinngemäß. Dennoch wüsste ich gern, wie man dieses verschachtelte Template korrekt gebaut hätte.



  • @Shamshir sagte in Binäre Suche: Ist meine Implementation korrekt und "idiomatisch"? (Iteratoren):

    Dummerweise scheiterte ich da an der Syntax des Headers bei verschachtelten Templates.

    template <typename Container template <typename T>> bool
    bsearch(Container<T>::iterator begin, /*...*/) // => Syntaxfehler!
    

    Ich würde mich von dem mentalen Bild der Container-Klasse verabschieden, wenn es wirklich generisch werden soll. Das könnten auch nur zwei simple Pointer oder etwas völlig anderes sein, das überhaupt nichts mit Containern zu tun hat.

     static_assert(std::is_same<T, typename std::iterator_traits<Iter>::value_type>::value); 
    

    Das ist doch schon die richtige Richtung! Schliesslich interessiert dich doch nicht wirklich, ob der zu durchsuchende Bereich in einem Container liegt, sondern lediglich, welchen Typ die zurückgegebenen Elemente haben. Ein static_assert kann man hier machen, aber warum nicht gleich so:

    template <typename Iter> bool 
    bsearch(Iter begin, Iter end, const typename std::iterator_traits<Iter>::value_type& t) { /* ... */ }
    

    Dann muss der übergebene Wert nichtmal den exakt selben Typen haben, sondern es reicht bereits, wenn er in diesen implizit konvertierbar ist.

    Wenn dir das übrigens so wichtig ist, dass der Compiler hier frühzeitig sinnvolle Fehlermeldungen ausgibt, dann lohnt es sich vielleicht, auf einen Compiler umzusteigen, der bereits Concepts aus C++20 beherrscht. Da könnte man das z.B. so formulieren (mit Vorsicht übernehmen, ich bin da noch nicht so superfit drin):

    #include <iterator>
    #include <functional>
    
    template <std::random_access_iterator Iter>
    auto bsearch(Iter begin, Iter end, const std::iter_value_t<Iter>& t) -> bool 
        requires std::indirect_strict_weak_order<std::less<std::iter_value_t<Iter>>, Iter> { /* ... */ }
    

    Damit wäre abgedeckt, dass Iter ein Random Access Iterator ist, also Ausdrücke wie i + n zulässt (wie z.B. in Zeile 6 deines Codes), value dem von *i zurückgegebenen Typen enspricht und diese via std::less vergleichbar sind. Wenn ich nichts übersehen habe, dürfte das alles sein, was man für eine Binäre Suche braucht.

    KISS. Das ginge natürlich auch mit dem Container sinngemäß. Dennoch wüsste ich gern, wie man dieses verschachtelte Template korrekt gebaut hätte.

    Das "verschachtelte Template" hätte ich wohl gar nicht geschrieben, sondern das wahrscheinlich so gemacht (als Anregung):

    #include <utility>
    
    template <typename Iter>
    auto bsearch(Iter begin, Iter end, const decltype(*std::declval<Iter>())& t) -> bool { /* ... */ }
    

    Ohne std::iterator_traits<T>. So dürfte sehr wahrscheinlich auch das std::iter_value_t aus C++20 implementiert sein- Wie schon oben erwähnt, dich interessiert ja eigentlich nur der Typ von *i mit dem du letztendlich den Vergleich durchfürst - nicht was da in einem eventuellen Container steckt.



  • Orientiere dich am besten immer an der C++ Standard Library, d.h. hier also z.B. an std::find (Außer, daß du, so wie @Finnegan ja schon geschrieben hat, einen Random Access Iterator benötigst).
    Auch eine weitere Version mit der zusätzlichen Angabe eines UnaryPredicate wäre hier sinnvoll (auch als Übung).

    PS: Da fehlt noch ein typename:

    template <template <typename> class Container, typename T>
    bool bsearch(typename Container<T>::iterator begin, /*...*/)
    

    s.a. Typen, Nichttypen und Templates als Template-Parameter



  • @Shamshir sagte in Binäre Suche: Ist meine Implementation korrekt und "idiomatisch"? (Iteratoren):

    Nach Recherche darüber, wie man Typen vergleicht und an den Typ eines dereferenzierten Iterators kommt, habe ich eine andere Lösung gefunden:
    static_assert(std::is_same<T, typename std::iterator_traits<Iter>::value_type>::value);

    Ich finde das eher hinderlich.
    Wenn es nicht geht, gibt es (hoffentlich) einen Compilerfehler.

    Aber wenn es geht, ist es sehr praktisch.
    Stell dir vor, du hast einen vector<MyStruct> und MyStruct und int haben entsprechende Vergleichsoperatoren. Warum solltest du dann nicht einfach nach einem int suchen können?
    Sowas geht endlich auch (oft) in der STL.



  • Mal noch als Anmerkungen:
    Deine Sequenz ist ja sortiert, z.B. indem du std::sort aufgerufen hast? Dann sollte:

    • t vom Typ T sein und nicht int
    • die iteratoren random access Iteratoren sein, nicht vector Iteratoren
    • deine Suche nach t den operator< benutzen
    • deine Funktion optional eine Vergleichsfunktion/Comparator als Parameter entgegennehmen

    Bei nächsten Mal kannst du ja selbst in die Referenz der STL reinschauen, um auf sowas zu kommen.



  • Danke für eure Antworten! Was ein RA-Iterator ist, hatte ich bereits nachgeschlagen bzw. dass man ihn für Iteratorarithmetik unbedingt braucht. (http://www.cplusplus.com/reference/iterator/). Liefert es nicht ohnehin einen Compilerfehler, wenn man hier Iteratoren übergibt, die operator+/- nicht entsprechend ihres hiesigen Gebrauchs definieren?

    Der neue Code jedenfalls:

    template <class Iter, typename T = typename std::iterator_traits<Iter>::value_type> constexpr bool
    bsearch(Iter begin, Iter end, const T& t, std::function<bool(const T&, const T&)> lt = std::less<T>()) {
        while(begin != end) {
            auto half_pos = begin + (end - begin) / 2;
            if(lt(*half_pos, t))
                begin = half_pos + 1;
            else if(lt(t, *half_pos))
                end   = half_pos;
            else 
                return true;
        }
        return false;
    }
    

    Nun ist das Prädikat natürlich nicht unär. In Haskell wäre das zB (meines Wissens nach) derart möglich:

    bsearch :: (Ord a) => [a] -> (a -> Bool) -> Bool
    # (...Implementation...)
    # Aufruf dann: bsearch xs (<t) -- sucht nach t in xs
    

    Das ist auch in C++ kein Problem, man müsste nun aber statt t die anonyme Hilfsfunktion <t übergeben, und in C++ scheint mir das immer etwas mehr "boilerplate code" zu verlangen. Da fand ich es dann sinnvoller, mich an Finnegans Vorschlag mit std::less zu orientieren.

    e: declval/decltype habe ich auch zur Kenntnis genommen.



  • @Shamshir eine std::function ist hier aber unverhältnismässig teuer.



  • Was ist besser?



  • Informiere dich mal über das Stichwort "Funktor" bzw. "Funktionsobjekt", z.B. C++-Programmierung/ Die STL/ Funktionsobjekte, Funktionsobjekte in der C++-Standardbibliothek oder C++ Core Guidelines: Übergabe von Funktionsobjekten als Operationen .

    PS: Die Übergabe einer Funktion macht es ja unnötig, noch den Parameter const T& t zu übergeben, daher wird in der STL dafür dann auch nur UnaryPredicate und nicht BinaryPredicate verwendet - insbesondere in modernem C++ mittels Lambda-Ausdrücken recht elegant verwendbar.



  • @Th69 sagte in Binäre Suche: Ist meine Implementation korrekt und "idiomatisch"? (Iteratoren):

    Die Übergabe einer Funktion macht es ja unnötig, noch den Parameter const T& t zu übergeben, daher wird in der STL dafür dann auch nur UnaryPredicate und nicht BinaryPredicate verwendet

    std::lower_bound (die Binärsuche der STL) benutzt T und BinaryPredicate.



  • Ich meinte bei der oben von mir verlinkten find-Funktion.


Anmelden zum Antworten