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

Mechanics

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

TGGC

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.

Shamshir

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.

Shamshir

Was ist besser?

Th69

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.

Th69

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

Shamshir

Unabhängig von der STL-Praxis kann man natürlich lower_bound als Binärsuche auch mit unärem Prädikat und übergebener (ggf. anonymer) Funktion bauen (und überhaupt jede Binärsuche zu jedem unären Prädikat p, deren "Heuhaufen" die Bedingung erfüllt, dass es darin ein x gibt mit p(x) => p(y) für alle y > x):

template <class Iter, class UnaryPredicate> constexpr bool
bsearch(Iter begin, Iter end, UnaryPredicate p) {
    if(begin == end) throw /* ... */;  // s. Anm.
    while(begin + 1 != end) {
        auto half_pos = begin + (end - begin) / 2;
        if(p(*half_pos))
            end   = half_pos;
        else
            begin = half_pos + 1;
    } return p(*begin);
}
// ...
const int c = -3; // z.B.
if(bsearch<std::vector<int>::iterator>(v.begin(), v.end(), [](const int& a) { return c < a; })
    std::cout << c << " ist untere Schranke für v" << std::endl;

So kurz/elegant wie in Haskell finde ich das C++-Lambda hier aber wirklich nicht, "boilerplate" eben. Direkt c als drittes Argument übergeben zu können, fände ich auch nicht schlecht.
Was ich außerdem gern wüsste, ist, wie man hierbei UnaryPredicate fest an Funktionen bindet, die wirklich bool zurückgeben müssen, nicht nur irgendetwas implizit in bool Konvertierbares (oder ist das wieder übertriebene Vorsicht?).
Da kannte ich dummerweise nur std::function (und C-artige Funktionspointer, die mir erst recht unangebracht scheinen), und aus den von Th69 gegebenen Links ist mir das nicht klargeworden (wiewohl sie trotzdem hilfreich waren).

EDIT: Hier würde ich übrigens den Rückgabetyp nicht mehr als bool belassen wollen, weil ich bei begin == end eigtl. weder true noch false zurückgeben will, wenn die Prädikate beliebig sind (wer weiß, was der Anwender erwartet hat), aber throw ist auch nicht gerade fantastisch für denjenigen Anwender, der sich um den Fall begin == end überhaupt nicht kümmern will. Besser wäre wohl (-1, 0, 1) als Bild.

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

So kurz/elegant wie in Haskell finde ich das C++-Lambda hier aber wirklich nicht,

Lass <std::vector<int>::iterator> weg, dann wird's kürzer

hustbaer

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

Was ich außerdem gern wüsste, ist, wie man hierbei UnaryPredicate fest an Funktionen bindet, die wirklich bool zurückgeben müssen, nicht nur irgendetwas implizit in bool Konvertierbares (oder ist das wieder übertriebene Vorsicht?).

Du kannst ein static_assert() reinschreiben in dem du prüfst ob der Returntyp bool ist. Sowas in der Art:

template <class Pred>
void fun(Pred p)
{
    static_assert(std::is_same<decltype(std::declval<Pred>()()), bool>::value, "meh");
}

Alternativ könntest du die Bedingung auch mit enable_if verwenden.
Nur wieso solltest du das machen wollen?

Da kannte ich dummerweise nur std::function (und C-artige Funktionspointer, die mir erst recht unangebracht scheinen), und aus den von Th69 gegebenen Links ist mir das nicht klargeworden (wiewohl sie trotzdem hilfreich waren).

Ich glaube std::function tut nicht was du denkst. Das:

int foo();
std::function<bool()> f = foo;

...funktioniert nämlich wunderbar, weil es std::function auch reicht dass der Wert implizit konvertierbar ist.