std::lower_bound und std::finden Sie auf einem einfachen array

Möchte ich std::algorithm Wann immer ich kann auf normalen arrays. Jetzt habe ich 2 Zweifel; angenommen, ich will std::lower_bound was passiert, wenn die Wert, die ich als argument nicht gefunden?

int a[] = {1,2,3,4,5,6};
int* f = std::lower_bound(a,a+6,20);

Das Ergebnis habe ich beim drucken *f 20.

Das gleiche passiert, wenn ich std::find.

int a[] = {1,2,3,4,5,6};
int* f = std::find(a,a+6,20);

Das Ergebnis habe ich beim drucken *f 20.

  1. Ist es immer der Fall, dass der Rückgabewert ist das ursprüngliche argument
    wenn diese nicht gefunden wird?
  2. In Bezug auf Leistung std::lower_bound führt besser von std::find da es implementiert eine binäre Suche Algorithmus. Wenn das array groß sagen max 10 Elemente, könnte std::finden Sie besser? Hinter den kulissen std::lower_bound ruft std::advance und std::distance ..vielleicht kann ich Sie retten, auf diese Anrufe?

Vielen Dank

AFG

Das Ergebnis haben Sie 20? Du meinst f? Oder *f? Wenn es f, das ist irrelevant, und unwahrscheinlich. Wenn es *f sollten Sie nicht dereferenzieren von f gibt.
Ich korrigiere meine Frage "das Ergebnis habe ich beim drucken *f", 20. Gibt es trotzdem, um zu testen, ob das element wurde nicht in den unteren Schranke/finden Ergebnis?
Über Ihre Leistung zu Fragen: Was wollen Sie erreichen? Sie scheinen, zu verzichten Verwendung von STL-Containern, während zur gleichen Zeit, die Verwendung von STL-Funktionen und sich Gedanken über Ihre Komplexität. Ich bin neugierig.
Test: if (f == a+6)
Wenn bei diesem test ist sicher, auch wenn für arrays vergeben stack ich erwarte gute Leistungen, die Nutzung dieser Nutzung. Vielen Dank.

InformationsquelleAutor Abruzzo Forte e Gentile | 2012-06-01

  1. 16

    Das Ergebnis habe ich 20. (Später bearbeitet werden, um: Das Ergebnis habe ich beim drucken *f 20.)

    Nein, das Ergebnis, das Sie bekommen, ist a+6. Dereferncing aufruft, die nicht definiertes Verhalten. Es könnten 20 ausgeben, es könnte Druck "Shirley MacLaine", oder es könnte die Luft zu sprengen Ihr Auto.

    Ist es immer der Fall, dass der Rückgabewert ist das ursprüngliche argument, wenn diese nicht gefunden wird?

    Den return-Wert immer die 2. argument in Ihrem Fall, weil 20 ist größer als jeder andere Wert im array. Wenn der Wert nicht gefunden wird, aber kleiner als einige vorhandene Wert, der Rückgabewert zeigt auf das nächst größere Element.

    Vom cppreference.com, ist der Rückgabewert von std::lower_bound ist "iterator zeigt auf das erste element, das nicht weniger als value oder last wenn kein solches element gefunden ist."

    In Bezug auf Leistung ...

    Messen. Keine anderen Ratschläge hier, die aufstehen wird, um Ihre tatsächliche empirische Evidenz.

    Hinter den kulissen std::lower_bound ruft std::advance und std::distance ..vielleicht kann ich Sie retten, auf diese Anrufe?

    Fast gar nicht. Diese Aufrufe sind fast sicher optimiert in Ihrem Fall um eine einzige (oder sehr wenige) Anweisungen.

    InformationsquelleAutor Robᵩ

  2. 6

    In Ihrem Beispiel müssen Sie nicht dereferenzieren f, weil es gleich a+6. Haben Sie sowieso, Sie sind also in UB Gebiet, aber ich nehme an, dass der Wert von 20 zufällig auf dem stack unmittelbar nach dem array a.

    Es ist wahr, dass für genügend kleine arrays, lineare Suche schneller als die binäre Suche. 10 "kleine", nicht "groß". Wenn Sie ein Programm, das macht eine Menge der Suchanfragen in kleine arrays sind, können Sie jeder Zeit ein-und sehen.

    Sollte es im Grunde kein Aufwand für std::advance und std::distance - jeder halbwegs kompetenter C++ - compiler inline alles, und Sie werden wiederum in Zeiger die addition und die Subtraktion.

    InformationsquelleAutor Steve Jessop

  3. 6

    Gibt es einen signifikanten Unterschied zwischen den Iteratoren zurückgegeben lower_bound und find. Wenn lower_bound nicht finden, das Element, wird es wieder der iterator, wo das Element eingefügt werden soll, behalten Sie die Sortierreihenfolge. Wenn find nicht finden, das Element, wird es wieder das Ende-iterator (D. H. das zweite argument find). In Ihrem Beispiel, da Sie versuchen, etwas zu finden, über das Ende des Arrays, beide geben die gleiche iterator - aber das ist ein völliger Zufall.

    InformationsquelleAutor Mark Ransom

  4. 1

    Könnten Sie die folgende Implementierung

    int a[] = {1,2,3,4,5,6};

    int f = lower_bound(a,a+6,20)-a;

    Nun, wenn 20 vorhanden ist, im array wird zurückgegeben, der index des Elements im array a (0-basierte Indizierung verwendet). Wenn 20 nicht vorhanden ist, in das array, wird es wieder 6 d.h. die Länge des Arrays.

    Im schlimmsten Fall wird der Punkt gesucht werden, an (n-1) - te index [wenn n die Größe des Arrays]. Dann f n-1.

    f werden n oder gleich der Größe des Arrays nur, wenn das Element gesucht wird, ist nicht in dem array.

    Hoffe, es beantwortet deine Frage.

    InformationsquelleAutor Ankit Kumar

Schreibe einen Kommentar