remove bei unsortierten vector

[itterschwapp]

Den Algorithmus gibt es und er heisst iter_swap

std::iter_swap(iterator, --container.end());

Das pop_back musst du selber ausführen, denn kein Algorithmus aus der Standardbibliothek verändert den Container. Selbst unique verschiebt die überflüssigen Elemente nur an das Ende.

[seldon]

Es passt in das Iterator-Konzept nicht so recht rein, das die Algorithmen der Standardbibliothek verfolgen. Gegen das grundsätzliche Vorgehen spricht aber aus meiner Sicht nichts. Als Implementationsdetail würde ich vielleicht std::swap (bzw. using std::swap; und dann swap() ohne std::) verwenden statt std::move, damit alter Code nicht benachteiligt wird.

[Marthog]

dot schrieb:

Wäre nicht vielleicht std::unordered_set die bessere Wahl als std::vector?

unordered_set steht der Zugriff mit dem Wert im Mittelpunkt.
vector hat schon alles, was ich brauche, ich wunder mich nur, warum ich es bei dem doch sonst geschwindigkeitbedachten C++ und der umfassenden boost-library nicht gefunden habe.

seldon schrieb:

Es passt in das Iterator-Konzept nicht so recht rein, das die Algorithmen der Standardbibliothek verfolgen.

itterschwapp schrieb:

Das pop_back musst du selber ausführen, denn kein Algorithmus aus der Standardbibliothek verändert den Container.

iter_swap ist nicht ganz das, was ich suche, sondern eher so std::remove und std::remove_if, das alles durchsucht aber nicht alles verschoben wird, sondern nur ein bisschen vom Ende. Ich kenne das remove-erase-idiom und würde es auch dafür nutzen.
Ich frage ja genau deswegen nach, weil es meiner Ansicht nach prima zu den anderen Algorithmen passt und für bestimmte Zwecke schneller sein kann. Ich wunder mich halt nur und denke, den muss es doch irgendwo geben und ich übersehe ihn nur.

[itterschwapp]

Also wenn ich dich richtig verstehe:

template <typename Iter>
Iter unordered_remove_single(Iter elem, Iter end)
{
  *elem = move(*--end); // geht sowieso nicht exception-sicher
  //iter_swap(elem, --end); // C++03
  return end;
}

template <typename Iter, typename Pred>
Iter unordered_remove_if(Iter first, Iter last, Pred p)
{
  while (first != last)
    if (p(*first))
      last = unordered_remove_single(first, last);
    else
      ++first;
  return last;
}

template <typename Iter, typename T>
Iter unordered_remove_if(Iter first, Iter last, T const& value)
{
  return unordered_remove(first, last, [&](T const& x) { x == value; });
}

// löscht einzelnes Element
container.erase(unordered_remove_single(iterator, container.end()));

// löscht alle Elemente == 1
container.erase(unordered_remove(container.begin(), container.end(), 1), container.end());

[Nexus]

Gibt ein paar wichtige Sachen, die fragwürdig oder nicht umgesetzt sind. Was ich bis heute nicht verstehe, ist warum std::binary_search bool statt eines Iterators zurückgibt.

Übrigens: --container.end() setzt voraus, dass der von end() zurückgegebene Iterator keinen skalaren Typ hat -- was gerade bei std::vector nicht der Fall sein muss. Besser wäre std::prev(container.end()) .

[seldon]

Nexus schrieb:

Gibt ein paar wichtige Sachen, die fragwürdig oder nicht umgesetzt sind. Was ich bis heute nicht verstehe, ist warum std::binary_search bool statt eines Iterators zurückgibt.

Dafür gibt's ja std::lower_bound, std::upper_bound und std::equal_range.

Aber solche Dinge haben ein Stück weit immer historische Gründe. Irgendjemand hat das so gemacht, und bei der Standardisierung hat man es festgeschrieben, damit weniger bestehender Code auseinanderfliegt.

[Nexus]

seldon schrieb:

Dafür gibt's ja std::lower_bound, std::upper_bound und std::equal_range.

Die Antwort hab ich erwartet. Aber binäre Suche -- einen der grundlegendsten Algorithmen überhaupt -- gibts nicht, man muss sie sich aus anderen Algorithmen zusammenbasteln. Was dann trotzdem darauf hinausläuft, dass man sich ein neues Funktionstemplate definieren muss, wenn man den Code wiederverwenden will. Dann kann man gerade so gut alles von Grund auf schreiben, ist je nachdem sogar noch effizienter.

[seldon]

Äh...lower_bound, upper_bound und equal_range machen binäre Suche, wenn man ihnen Random-Access-Iteratoren gibt.

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

Ich finde das eigentlich eine ganz elegante Lösung, sich auf die mathematisch sauberen Begriffe zurückzuziehen. Der grundlegende Algorithmus ist damit vorhanden, und spezielle Schnittstellen, die im Einzelfall angenehmer zu benutzen sind, lassen sich auf dieser Basis trivial zusammenstellen.

[Marthog]

seldon schrieb:

Äh...lower_bound, upper_bound und equal_range machen binäre Suche, wenn man ihnen Random-Access-Iteratoren gibt.

Die Funktion std::find macht linear search nach einem element und gibt den iterator auf das erste gefundene zurück.
Es wäre nun logisch, bei binary_search das gleiche zu machen, nur halt mit binary search. Stattdessen wird aber nur über Erfolg und Misserfolg Bericht erstattet.
Noch besser wäre es natürlich, find auch linear_search zu nennen.

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