Gegeben ein sortierter Vektor mit einer Anzahl von Werten, wie im folgenden Beispiel:
%Vor%Ich suche nach dem elegantesten Weg, um für jedes doppelte d die zwei Werte zu erhalten, die direkt neben ihm liegen. Zum Beispiel, wenn ich den Wert "45" verwende, möchte ich, dass "10" und "100" zurückgegeben werden.
Ich habe lower_bound und outer_bound gesucht, aber sie tun nicht, was ich will. Können Sie mir helfen?
EDIT: Ich habe mich entschieden, meinen eigenen Anser zu posten, da es sich um eine Zusammenfassung aller hilfreichen Antworten handelt, die ich in diesem Thread bekommen habe. Ich habe die Antworten gewählt, die meiner Meinung nach am hilfreichsten waren.
Danke allen,
Dave
Ich werde meinen eigenen Anser veröffentlichen und jemanden wählen, der mir geholfen hat, ihn zu erreichen, da ich das am Ende verwenden werde, und Sie haben mir alle geholfen, zu diesem Schluss zu kommen. Kommentare sind willkommen.
%Vor%Sie können beide Werte (falls vorhanden) in einem Aufruf mit equal_range () erfassen. Sie gibt ein std :: -Paar von Iteratoren zurück, wobei der erste Ort der erste und der zweite der letzte Ort ist, an dem Sie den übergebenen Wert einfügen können, ohne die Reihenfolge zu verletzen. Um Ihre Kriterien strikt zu erfüllen, müssten Sie den Iterator zuerst dekrementieren, nachdem Sie überprüft haben, dass er nicht mit dem Beginn des Vektors () übereinstimmt.
Sie können einfach eine binäre Suche verwenden, die in O (log (n)) läuft.
Hier ist ein Lua-Snippet (ich habe keine Zeit, es in C ++ zu tun, tut mir leid), was das tut, was Sie wollen, außer für Grenzbedingungen (die Sie sowieso nicht definiert haben):
%Vor%Es wird der Wert für die Suche über die Befehlszeile benötigt:
%Vor%Was ist, wenn (in Ihrem Fall) d kleiner ist als das erste Element oder mehr als das letzte? Und wie geht man mit negativen Werten um? Übrigens: Damit garantiert wird, dass dein "d" zwischen dem ersten und dem letzten Wert deines Vektors lebt, kannst du das so machen:
%Vor%Hier ist der Rest:
%Vor%Elegant genug? : /
Sie könnten in Ihrem Vektor nach Ihrem Wert suchen (der Ihnen sagen würde, wo Ihr Wert wäre, wenn er im Vektor wäre) und dann den Wert vor und nach diesem Ort zurückgeben. Wenn Sie also nach 45 suchen, würde es Ihnen sagen, dass es bei Index = 1 sein sollte und dann würden Sie 0 und 1 zurückgeben (abhängig von Ihrer Implementierung der Suche erhalten Sie entweder den Index des kleineren Werts oder den Index des größeren Werts. aber das ist leicht zu überprüfen mit ein paar Randbedingungen). Dies sollte in der Lage sein, in O (log n) zu laufen, wobei n die Anzahl der Elemente in Ihrem Vektor ist.
Ich würde so etwas schreiben, nicht testen, ob das kompiliert, aber Sie bekommen die Idee:
%Vor%Ich habe diese kleine Funktion geschrieben, die zu dem allgemeineren Fall passt, den Sie haben wollten. Ich habe es nicht vollständig getestet, aber ich habe einen kleinen Testcode (inklusive) geschrieben.
%Vor%Basierend auf dem Code, den tunnuz gepostet hat, haben Sie hier einige Verbesserungen bezüglich der gebundenen Überprüfung:
%Vor%Anwendungsbeispiel:
%Vor%Wenn Sie die Möglichkeit haben, eine andere Datenstruktur (kein Vektor) zu verwenden, würde ich eine B-Struktur vorschlagen . Wenn Ihre Daten unverändert sind, können Sie das Ergebnis in konstanter Zeit (logarithmische Zeit im schlimmsten Fall) abrufen.