C++ und generische Binärsuche

von Hubert Schmid vom 2012-02-05

Die Standardbibliothek von C++ enthält mehrere Algorithmen für die Binärsuche. Und es ist bereits eine Weile her, als ich mich ein wenig darüber geärgert habe, dass ich diese Algorithmen in einem Fall nicht einsetzen konnte. Das Ärgerliche daran war, dass es mit der konkreten Implementierung sehr wohl funktioniert hätte. Nur die Spezifikation hat diesen Fall nicht abgedeckt.

Ich habe mich in den letzten Tagen nochmals mit dem Thema auseinandergesetzt. Und dabei fand ich zwei Dinge besonders interessant: Erstens findet sich diese unnötige Einschränkung anscheinend in der meisten Literatur über Algorithmen. Und zweitens hat mich überrascht, dass C++ seit 2003 diese Einschränkung nicht mehr besitzt. Aber eins nach dem anderen. Und im folgenden versuche ich, die Situation schrittweise zu erklären.

Ein Algorithmus

Ich starte mit der Signatur einer Template-Funktion. Und da der Name zu diesem Zeitpunkt eher verwirren würde, nenne ich sie einfach foobar.

template <typename Iterator, typename Predicate>
auto foobar(Iterator first, Iterator last, Predicate&& predicate)
    -> Iterator;

Diese Funktion erwartet einen Bereich, der wie üblich durch zwei Iteratoren gegeben ist, sowie eine Prädikatsfunktion, die auf die Elements des Bereichs angewendet werden kann. Die Vorbedingung der Funktion ist, dass es einen Iterator i im Bereich [first,last] gibt, so dass predicate(*j) für alle Iteratoren j im Bereich [first,i) gilt, und !predicate(*j) für alle Iteratoren j im Bereich [i,last). Unter dieser Voraussetzung gibt die Funktion genau diesen Iterator i zurück.

Offensichtlich ist das Funktionstemplate std::partition aus der Standardbibliothek verwandt mit meinem Algorithmus. Die beiden Funktionen besitzen sogar die gleiche Signatur, aber wichtiger ist natürlich die semantische Verwandtschaft, die man beispielsweise im folgenden Code-Fragment erkennen kann.

auto i = std::partition(first, last, predicate);
auto j = foobar(first, last, predicate);
assert(i == j); // always true

Damit wollte ich vor allem zwei Dinge nochmals motivieren: Erstens ist die Spezifikation meines Algorithmus nicht willkürlich. Und zweitens ist mein Algorithmus verwandt mit der Partitionierung, die beispielsweise beim Quicksort-Algorithmus verwendet wird. Das könnte bereits auf einen Zusammenhang mit der Binärsuche hinweisen. Viel deutlicher wird der Zusammenhang allerdings, wenn man einen Blick auf die Implementierung wirft.

Eine Implementierung

template <typename Iterator, typename Predicate>
auto foobar(Iterator first, Iterator last, Predicate&& predicate)
    -> Iterator
{
    auto size = std::distance(first, last);
    while (size > 0) {
        auto half = size / 2;
        auto middle = std::next(first, half);
        if (predicate(*middle)) {
            first = std::next(middle);
            size -= half + 1;
        } else {
            size = half;
        }
    }
    return first;
}

Auf den ersten Blick sieht dieser Code dem Algorithmus für die Binärsuche sehr ähnlich. Denn er verwendet das gleiche Verfahren und halbiert den Suchbereich so lange, bis das gesuchte Element gefunden wird – beziehungsweise bis der Suchbereich leer ist.

Bei genauerem Hinsehen wird man vielleicht feststellen, dass es sich dabei tatsächlich um Binärsuche handelt – und zwar um eine sehr allgemeine – und zwar so allgemein, dass die meisten anderen Spezifikationen von Binärsuche ein Spezialfall dieser Implementierung darstellen. Interessant finde ich dabei insbesondere, dass die meisten anderen Implementierungen komplizierter und wesentlich restriktiver sind – und darüber hinaus noch eine Ordnungsrelation voraussetzen.

Ein Beispiel

Aber erstmal gehe ich einen Schritt zurück. Das folgende Beispiel zeigt, wie sich die klassische Binärsuche für einen aufsteigend sortierten std::vector<int> darauf abbilden lässt. Dabei verwende ich die Boost-Lambda-Bibliothek, um die Definition der Prädikatsfunktion einfach zu halten.

auto binary_search(const std::vector<int>& values, int value)
    -> bool
{
    using boost::lambda::_1;
    auto position = foobar(values.begin(), values.end(), _1 < value);
    return position != values.end() && *position == value;
}

Wie man sieht steckt die ganze Magie in der verwendeten Prädikatsfunktion. Und die letzte Zeile der Funktion ist notwendig, weil foobar lediglich die Position des gesuchten Elements liefert, aber nicht die Information, ob es auch tatsächlich existiert.

Eine Spezialisierung

Das letzte Beispiel war sehr spezifisch. Daher möchte ich auch noch kurz zeigen, wie sich die anderen, generischen Funktionen zur Binärsuche aus der Standardbibliothek darauf abbilden lassen. Und zunächst definiere ich ein Hilfsfunktion, um Redundanzen zu vermeiden.

namespace detail
{
    // unnamed class because there is only one instance
    struct
    {
        template <typename Lhs, typename Rhs>
        auto operator()(Lhs&& lhs, Rhs&& rhs) const -> bool
        {
            // use perfect forwarding - just in case
            return std::forward<Lhs>(lhs) < std::forward<Rhs>(rhs);
        }
    } less;
}

Das Funktionsobjekt detail::less lässt sich mit zwei beliebigen Argumenten aufrufen und delegiert den Aufruf einfach an den Kleiner-Operator. Damit kann ich nun die beiden Funktionen std::lower_bound und std::upper_bound in wenigen Zeilen selbst implementieren. Und selbstredend sind diese Implementierungen bei einem üblichen, optimierenden Compiler genau so schnell wie die entsprechenden Funktionen aus der Standardbibliothek.

// replacement of std::lower_bound
template <typename Iterator, typename Value, typename Compare>
auto lower_bound(Iterator first, Iterator last, Value&& value, Compare&& compare = detail::less)
    -> Iterator
{
    using Type = decltype(*first);
    auto&& predicate = [&](const Type& arg) { return compare(arg, value); };
    return foobar(first, last, std::move(predicate));
}

// replacement of std::upper_bound
template <typename Iterator, typename Value, typename Compare>
auto upper_bound(Iterator first, Iterator last, Value&& value, Compare&& compare = detail::less)
    -> Iterator
{
    using Type = decltype(*first);
    auto&& predicate = [&](const Type& arg) { return !compare(value, arg); };
    return foobar(first, last, std::move(predicate));
}

Ein Irrtum

Wie gerade gesehen gibt es von der Funktion std::lower_bound praktisch zwei Varianten. Die erste Variante verwendet den Kleiner-Operator als Ordnungsrelation. Und falls man eine andere Ordnungsrelation benötigt, so kann man sie in der zweiten Variante explizit angegeben. Die ursprüngliche Dokumentation der STL spezifiziert das Verhalten der Funktion genau auf diese Weise. Und diese Definition findet sich auch im ersten Sprachstandard von C++ (1998) wieder.

Allerdings gibt es eine Reihe von interessanten Anwendungsfällen, die damit nicht abgedeckt werden können. Ein einfaches Beispiel dafür ist eine Sequenz von Kunden-Objekten (nach Kundennummer sortiert), in der nach einer speziellen Kundennummer gesucht wird. Und bereits daran scheitert die obige Definition, denn die Datentypen unterscheiden sich. Mit der Funktion foobar ist diese Aufgabe hingegen trivial lösbar.

Dieses Problem ist anscheinend mehreren Entwicklern aufgefallen. Und wenn ich das richtig gesehen habe, so wurde die Spezifikation der Funktion 2003 tatsächlich angepasst und gelockert. Die neue Definition verzichtet nun komplett auf Ordnungsrelationen und ist vergleichbar mit der Definition von foobar. Und zeigen lässt sich das am einfachsten, indem ich meine Funktion auf std::lower_bound zurückführe.

template <typename Iterator, typename Predicate>
auto foobar(Iterator first, Iterator last, Predicate&& predicate)
    -> Iterator
{
    using Type = decltype(*first);
    auto&& compare = [&](const Type& arg, int) { return predicate(arg); };
    return std::lower_bound(first, last, 0, std::move(compare));
}

Dabei wird der Funktion std::lower_bound das binäre Prädikat nur vorgegaukelt. Tatsächlich wird das zweite Argument nie verwendet und könnte von beliebigem Typ sein. Und auch wenn das Ganze ein wenig merkwürdig aussieht: Der Sprachstandard sichert das gewünschte Verhalten zu.

Eine Erkenntnis

Manchmal zweifle ich an der Sprache C++. Und dann überrascht sie mich wieder. Und manchmal vergeht dazwischen auch relativ viel Zeit. Abgesehen davon ist es schön zu sehen, dass mein ursprüngliches Problem mittlerweile gelöst ist, so dass ich nicht mehr selbst die Binärsuche implementieren muss – wobei es mir in diesem Fall Spass gemacht hat, und ich ein wenig überrascht war, wie viel einfacher das mit C++11 geworden ist.