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

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.