remove bei unsortierten vector

Sone

Aber irgendjemand hatte die brilliante Idee, std::binary_search() für 95% der Fälle komplett nutzlos zu machen, indem bool zurückgegeben wird.

Ich konnte das zuerst nicht glauben, dachte du hast dich verschrieben... jetzt sitz' ich vor dem PC und staune einfach.

Bashar

Ich verstehe nicht, was es da zu staunen gibt. Man wollte halt kein unspezifiziertes Ergebnis wie bei bsearch im Falle mehrerer möglicher Ergebnisse. Das mag nicht die beste Entscheidung gewesen sein, aber so völlig abwegig wie ihr tut ist es auch wieder nicht.

Marthog

Bashar schrieb:

Man wollte halt kein unspezifiziertes Ergebnis wie bei bsearch im Falle mehrerer möglicher Ergebnisse.

Es ist aber nicht konsistent mit anderen Suchfunktionen.
Beim design sollte man schon darauf achten, ein einheitliches Interface zu haben und dabei würde sich doch anbieten, für linear und binary search ein gleiche Parameter und gleichen Rückgabewert anzubieten, damit einfach umbenennen reicht. Zudem sollten sie auch noch naheliegende Namen haben und da man meistens nach der Position sucht, ist es doch unnütz, dass die gleichnamige Funktion nur ein boolean zurückgibt.

knivil

Eure Probleme will ich mal haben. Benutzt einfach lower_bound und upper_bound! Gut, binary_search haette man weglassen koennen hat, man aber nicht. Desweiteren hat diese Funktion ihre Daseinsberechtigung beisielsweise bei der Berechnung von Schnittmengen oder was auch immer.

Nexus schrieb:

seldon schrieb:

Das Problem, was ich sehe, ist, dass man sich mit dieser Herangehensweise immer darüber beschweren kann, dass fast alles fehlt. Warum gibt es rotate und rotate_copy, aber kein rotate_n und rotate_copy_n? Und kein mismatch_end? Und kein find_first_not_of?

Ich kann mich nur wiederholen: Binäre Suche ist einer der grundlegendsten Algorithmen überhaupt. Darauf basieren etliche Datenstrukturen. Ich weiss nicht, wie du darauf kommst, das mit rotate_copy_n() zu vergleichen.

Binäre Suche ist, wie auch das Rotieren eines Bereichs, in der Standardbibliothek enthalten. Nur halt nicht mit dem genauen Frontend, was du dir vorstellst.

Haufenweise Frontend-Funktionen* für bestehende Algorithmen in die Standardbibliothek einzuführen, insbesondere, wenn deren Ergebnis nicht wohldefiniert ist, ist aus meiner Sicht nicht zielführend. Daher der Vergleich mit rotate_copy_n.

Zu deinem Fall würde ich Folgendes festhalten: Wenn du den Wert schon kennst und es nur darum geht, ob er in einem Bereich enthalten ist, reicht std::binary_search aus. Suchst du nach einem Objekt mit zusätzlichen Eigenschaften, hast du das Problem, welches von mehreren gleichwertigen Objekten gemeint ist. Ein bisschen Sinn ergibt es nur, wenn du vorher weißt, dass höchstens ein gleichwertiges Objekt im Container ist, oder wenn du mehrere gleichwertige Objekte im Container erwartest und es dir egal ist, welches du bekommst. Da du aber diese Fälle und alle anderen mit den bestehenden Funktionen abhandeln kannst, ist eine derart eingeschränkte Funktion aus meiner Sicht nicht notwendig. Eigentlich wäre schon std::binary_search aus meiner Sicht nicht notwendig; ich kann mich nicht entsinnen, sie jemals gebraucht zu haben. Aber da gibt es wohl historische Gründe, und immerhin ist das Ergebnis klar definiert.

Und wenn du es wirklich haben willst, ist in der Standardbibliothek alles enthalten, um das Problem mit zwei Zeilen Code zu erschlagen.

* Aus Gründen der Lesbarkeit mache ich hier keinen Unterschied zwischen Funktionen und Funktionsvorlagen. Eigentlich dreht sich hier alles um Funktionsvorlagen.

Also ich habe binary_search schon öfter benutzt. Immer wenn ich Mengen von Objekten habe eigentlich. Wenn Objekt in dieser Menge tue dies ansonsten was anderes. Das implementiere ich als

vector<Object> menge; //oder auch array<Object>
...
sort(menge.begin(), menge.end());
...
if (binary_search(menge.begin(), menge.end(), objekt){
    //ein Iterator ist unnötig, ich kenne objekt schon
    tuwas(objekt);
}

Das Argument der Nutzlosigkeit könnte man auch für deque bringen, das braucht man praktisch nie, aber wenn doch, dann ist man froh, dass es da ist.

TNA

Für den Fall, dass man nicht weiß ob sich der Wert im Container befindet und man gegebenenfalls die Stelle haben will, empfiehlt Scott Meyers equal_range anstatt lower_bound da bei lower_bound die Überprüfung, ob das Objekt tatsächlich gefunden wurde, im allgemeinen sehr komplex ist.

camper

TNA schrieb:

Für den Fall, dass man nicht weiß ob sich der Wert im Container befindet und man gegebenenfalls die Stelle haben will, empfiehlt Scott Meyers equal_range anstatt lower_bound da bei lower_bound die Überprüfung, ob das Objekt tatsächlich gefunden wurde, im allgemeinen sehr komplex ist.

Macht wenig Sinn, da sich so die effektive Komplexität (worst case) verdoppelt. equal_range macht ja im Grunde nichts anderes als sowohl lower_bound als auch upper_bound aufzurufen.

Etwas anderes ist nat. wenn man vorhat, über alle äquivalenten Elemente zu iterieren (was der Regelfall sein dürfte, wenn nicht bloss ein Element existieren kann). In diesem Fall ist equal_range sicher besser.

im allgemeinen sehr komplex

wurde oben schon gezeigt. Hält sich in Grenzen.

knivil

Das Argument der Nutzlosigkeit könnte man auch für deque bringen, das braucht man praktisch nie, aber wenn doch, dann ist man froh, dass es da ist.

Nein, alle meine Messagequeues sind Decks.

TNA

camper schrieb:

TNA schrieb:

Für den Fall, dass man nicht weiß ob sich der Wert im Container befindet und man gegebenenfalls die Stelle haben will, empfiehlt Scott Meyers equal_range anstatt lower_bound da bei lower_bound die Überprüfung, ob das Objekt tatsächlich gefunden wurde, im allgemeinen sehr komplex ist.

Macht wenig Sinn, da sich so die effektive Komplexität (worst case) verdoppelt. equal_range macht ja im Grunde nichts anderes als sowohl lower_bound als auch upper_bound aufzurufen.

Ist das tatsächlich so implementiert? Kann ich mir nicht vorstellen. Wenn man die lower_bound schon hat, dürfte sich die upper_bound doch viel schneller finden lassen, wenn das intelligent implementiert ist.

camper schrieb:

im allgemeinen sehr komplex

wurde oben schon gezeigt. Hält sich in Grenzen.

Ich sehe nicht wo das mal komplett richtig gemacht wurde. Korrekterweise müsste man zuerst prüfen, ob der Iterator auf ein gültiges Element zeigt, und falls ja, dieses auf Äquivalenz (abgesehen von Spezialfällen wo Equivalenz und Gleichheit zusammenfallen) prüfen und zwar mit der Vergleichsfunktion des Containers.

camper

TNA schrieb:

Ich sehe nicht wo das mal komplett richtig gemacht wurde. Korrekterweise müsste man zuerst prüfen, ob der Iterator auf ein gültiges Element zeigt, und falls ja, dieses auf Äquivalenz (abgesehen von Spezialfällen wo Equivalenz und Gleichheit zusammenfallen) prüfen und zwar mit der Vergleichsfunktion des Containers.

Dann hast du sicher seldons Code einfach nicht gesehen. Nochmal mit trivialer Korrektur

template<typename ForwardIt, typename T>
ForwardIt binary_find(ForwardIt first, ForwardIt last, T const &value)
{
  first = std::lower_bound(first, last, value);
  return first != last && !(value < *first) ? first : last;
}

template<typename ForwardIt, typename T, typename Compare>
ForwardIt binary_find(ForwardIt first, ForwardIt last, T const &value, Compare comp)
{
  first = std::lower_bound(first, last, value, comp);
  return first != last && !comp(value, *first) ? first : last;
}

Edit: es ist nicht möglich, den < Fall über std::less zu implementieren, sofern value_type des Iterators und T nicht übereinstimmen. Es könnten ja assymetrische Überladungen des < Operators existieren, die zu benutzen wären.