Nächsten Punkt mit Untergrenze suchen ... aber Daten sind nicht sortiert

Question

Ich habe einen Vektor, der die Entfernung zu einem bestimmten Bezugspunkt entlang einer Linie speichert. Also möchte ich zum Beispiel den Index, wo die Entfernung 700 Meter oder der nächste Wert zu dieser Entfernung ist.

Ich habe angenommen, der Vektor ist sortiert, und verwendet lower_bound mit Erfolg.

Das Problem ist, dass im wirklichen Leben Fehler passieren, also kann ich nicht garantieren, dass ich immer einen sortierten Vektor habe, weil der Benutzer beim Speichern von Daten beispielsweise nicht der Zeile gefolgt ist.

Wie kann ich den nächsten Wert finden, wenn die Daten nicht sortiert sind?

Answer 1

Kopieren Sie Ihre vector in eine STL set und verwenden Sie dann die gleiche Logik wie Sie für Vektor für das Finden des Elements getan haben.

Answer 2

Sie können nicht, weil std::vector ein Sequenzcontainer ist. Sie müssen die Daten mit einem Sortieralgorithmus.

Answer 3

Sie können std::min_element in der Form mit drei Argumenten verwenden. Übergeben Sie einen Komparator, der true zurückgibt, wenn das erste Argument näher an der Zielentfernung (700 m) liegt als das zweite Argument. Dann ist das Ergebnis von min_element der Punkt, der dem Ziel am nächsten ist.

Natürlich ist dies asymptotisch langsamer als lower_bound, aber es ist asymptotisch schneller als der schlechteste Fall des Sortierens des Vektors. Wenn Sie den Vektor einmal sortieren und sich darauf verlassen können, dass er sortiert bleibt, während Sie nach dem nächsten Punkt in mehreren verschiedenen Entfernungen suchen, sollten Sie wahrscheinlich std::sort und std::lower_bound verwenden. Wenn das Auffinden des nächsten Punktes eine einmalige Operation ist, kann es besser sein, es langsam mit min_element zu machen.