remove bei unsortierten vector

[Nexus]

seldon schrieb:

Geht es dir darum, eine Funktion zu haben, die entweder einen Verweis auf ein gefundenes Element oder einen direkt als "nicht gefunden" erkennbaren Wert zurückgibt?

Ja. Genau die gleiche Semantik wie bei std::find() , nur halt binäre statt lineare Suche. Die Anforderung ist dann eben nicht operator== , sondern operator< (oder ein Prädikat).

seldon schrieb:

Wenn du das allgemein formulieren willst, hast du das Problem, zu definieren, welches der 10 gleichwertigen Elemente, die hintereinander im Bereich liegen, genommen werden soll.

Nein, siehe Marthog. Oft ist man sowieso nur am Wert interessiert, wobei äquivalente Objekte gleich sind.

seldon schrieb:

Ich finde das eigentlich eine ganz elegante Lösung [...] und spezielle Schnittstellen, die im Einzelfall angenehmer zu benutzen sind, lassen sich auf dieser Basis trivial zusammenstellen.

Ich finds überhaupt nicht elegant, sowas Grundlegendes nicht fertig anzubieten. Wir haben so viele sinnlose Algorithmen wie std::remove_copy_if() oder std::find_if_not() , die sich von anderen nur durch eine Negation abheben, welche tatsächlich trivial mittels Lambda-Ausdrücken oder Adapterfunktoren implementierbar wäre.

Binäre Suche auf Anhieb richtig zu implementieren finde ich hingegen nicht trivial, auch mit gegebenen Funktionen nicht (in die man sich auch erst einlesen muss). Es ist nicht wahnsinnig schwierig, aber dann doch eine etwas andere Stufe als ein ! vor eine Bedingung zu setzen. Schlussendlich braucht man doch einiges an Zeit für eine Implementierung. Man will sich ja auch sicher sein, dass es funktioniert.

[huh]

Nexus schrieb:

Binäre Suche auf Anhieb richtig zu implementieren finde ich hingegen nicht trivial, auch mit gegebenen Funktionen nicht (in die man sich auch erst einlesen muss).

Also ich finde das dermassen trivial, dass ich mir gar nicht die Mühe mache, diese Funktion zu schreiben.

template<class ForwardIt, class T>
ForwardIt binary_find(ForwardIt first, ForwardIt last, const T& value)
{
    return std::lower_bound(first, last, value);
}

Oder, wenn < und == gegeben:

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

[camper]

huh schrieb:

Oder, wenn < und == gegeben:

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

oder richtig nur bezogen auf die Ordnungsrelation

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

[seldon]

Ich hätte das jetzt so aufgezogen:

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

Ändert aber nichts am grundsätzlichen Vorgehen.

[Nexus]

seldon schrieb:

Ich hätte das jetzt so aufgezogen

Ich glaube nicht, dass der Templateparameter Compare so hergeleitet werden kann.

Das meinte ich exakt mit nicht-trivial: huhs Version ist nicht generisch, hier muss man zuerst Compilerfehler beheben... Man kann also den Code nicht einfach hinschreiben und er funktioniert. Klar bringt man eine Implementierung zustande, aber man könnte sich mit einer Standardimplementierung unnötiges Rad-Neu-Erfinden sparen.

[seldon]

Nexus schrieb:

seldon schrieb:

Ich hätte das jetzt so aufgezogen

Ich glaube nicht, dass der Templateparameter Compare so hergeleitet werden kann.

Hab's grad ausprobiert; da hast du recht. Dafür muss man wohl überladen.

Nexus schrieb:

Das meinte ich exakt mit nicht-trivial: huhs Version ist nicht generisch, hier muss man zuerst Compilerfehler beheben... Man kann also den Code nicht einfach hinschreiben und er funktioniert. Klar bringt man eine Implementierung zustande, aber man könnte sich mit einer Standardimplementierung unnötiges Rad-Neu-Erfinden sparen.

Naja, wir reden hier trotz allem über einen Zweizeiler. Das ist nichts, was einen, wenn man vor einem Compiler sitzt und das irgendwo einbaut, länger als ein paar Minuten für braucht -- für mein Verständnis fällt das noch unter trivial. 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?

Natürlich könnte man viele solche Frontend-Funktionen einführen, aber man würde nie alles abdecken, was jemand gerne hätte. Und am Ende stünde man da wie PHP, mit zwanzig Fantastilliarden Funktionen in der Standardbibliothek, die alle das gleiche machen und durch die sich niemand mehr durchfindet. So spart man sich vielleicht ein paar Minuten Rad-neu-erfinden, hat aber ne halbe Stunde Rad-finden dafür. Und wenn man mal etwas will, was auch in all diesen Funktionen nicht vorhanden ist, hat man die paar Minuten noch zusätzlich drauf.

[Nexus]

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.

Das Problem ist ja nicht, dass wir in der C++-Standardbibliothek keine binäre Suche haben. Aber irgendjemand hatte die brilliante Idee, std::binary_search() für 95% der Fälle komplett nutzlos zu machen, indem bool zurückgegeben wird. Man fragt sich hier schon etwas, da so gut wie alle anderen Suchfunktionen einen Iterator auf das gefundene Element oder das Ende des Intervalls zurückgeben.

Sogar schon in C war man klüger und hat bsearch() einen Zeiger auf das gefundene Element zurückgeben lassen. Und C hat gerade mal zwei Algorithmen in der Standarbibliothek!

seldon schrieb:

Und kein find_first_not_of?

std::string hats

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

[seldon]

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.

[nwp3]

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.