Suchen ein C ++ Vector zum ersten / letzten Auftreten eines Wertes

StackOverflow https://stackoverflow.com/questions/1649139

Frage

Ich versuche, die beste Methode zu erarbeiten, einen Vektor vom Typ „Tracklet“ suchen (eine Klasse ich mich gebaut habe) für eine ihrer Variablen, die die erste und die letzte Vorkommen eines bestimmten Wertes zu finden. Zum Beispiel habe ich die folgenden Klassen (für dieses Beispiel vereinfacht): 

class Tracklet {
    TimePoint *start;
    TimePoint *end;
    int angle;

    public:
        Tracklet(CvPoint*, CvPoint*, int, int);
}

class TimePoint {
    int x, y, t;

    public:
        TimePoint(int, int, int);
        TimePoint(CvPoint*, int);
        // Relevant getters and setters exist here   
};

Ich habe einen Vektor „vector<Tracklet> tracklets“ und ich brauche für alle tracklets mit einem gegebenen Wert von „t“ für das Ende Zeitpunkt zu suchen. Der Vektor wird in Bezug auf die Endzeit geordnet (d.h. tracklet.end->t).

Ich bin glücklich, einen Suchalgorithmus zu codieren, aber bin nicht sicher, welcher Weg mit ihm zu nehmen. Ich bin nicht sicher, binäre Suche geeignet wäre, wie ich es zu merken scheinen nicht unbedingt die erste finden. Ich dachte an einer Methode, wo ich binäre Suche verwenden, um einen Index eines Elements mit der richtigen Zeit zu finden, dann iteriert zurück, um die ersten zu finden und nach vorne die letzten zu finden. Ich bin sicher, dass es einen besseren Weg, als das, da es Binärsuchen O (log n) Abfälle durch Iterieren.

Hoffentlich macht Sinn: Ich kämpfte es ein bisschen zu erklären! Cheers!

War es hilfreich?

Lösung

Wenn der Vektor sortiert und enthält den Wert, std::lower_bound geben Ihnen einen Iterator auf das erste Element mit einem bestimmten Wert und std::upper_bound geben Ihnen einen Iterator auf ein Element nach dem letzten man den Wert enthält. Vergleichen Sie den Wert mit dem zurückgegebenen Elemente zu sehen, ob es in dem Vektor vorhanden ist. Beide Funktionen verwenden binäre Suche, so Zeit O (log N).

Zum Vergleich auf tracklet.end->t, zu verwenden: 

bool compareTracklets(const Tracklet &tr1, const Tracklet &tr2) {
    return (tr1.end->t < tr2.end->t);
}

und compareTracklets als vierte Argument übergeben lower_bound oder upper_bound

Andere Tipps

Ich würde nur benutzen find und

Eine binäre Suche scheint die beste Wahl hier, solange Ihr Vektor sortierten bleibt. Es ist im Wesentlichen identisch, Performance-weise, eine Suche in einer binären Baum-Struktur durchgeführt wird.

dirkgently bezeichnet zu einem süßen Optimierung Vergleich. Aber ich würde in der Tat keinen std::vector für diesen.

In der Regel, bei der Entscheidung, einen STL-Container zu verwenden, ich die Leistung Aspekt nicht wirklich in Betracht ziehen, aber ich habe seine Schnittstelle in Bezug auf die Art des Betriebes berücksichtigen mag ich nutzen. 

std::set<T>::find
std::set<T>::lower_bound
std::set<T>::upper_bound
std::set<T>::equal_range

Wirklich, wenn Sie eine geordnete Folge wollen, außerhalb eines Schlüssel / Wert-Setup ist std::set nur einfacher als jede andere zu verwenden.

  • Sie müssen sich keine Sorgen über zu einem ‚schlechten‘ Position Einfügen
  • Sie haben keine Probleme mit der Iteratoren Ungültigkeits beim Hinzufügen / Entfernen eines Elements
  • Sie haben integrierte Methoden für die Suche

Natürlich können Sie wollen auch Ihr Vergleichsprädikat wirklich glänzen (hofft der Compiler inlines die Operator () Implementierung), in jedem Fall.

Aber wirklich, wenn Sie nicht überzeugt sind, versuchen Sie einen Build mit einem std::vector und manuelle Einfügen / Suche (mit dem <algorithm> Header) und versuchen Sie einen anderen Build std::set verwendet wird.

Vergleichen Sie die Größe der Implementierungen (Anzahl der Zeilen Code), vergleichen, um die Anzahl der Fehler, vergleichen, um die Geschwindigkeit, und dann entscheiden.

Am häufigsten die ‚Optimierung‘ für Sie zielen darauf ist eigentlich ein Pessimierung , und in dieser raren Zeit ist es nicht, es ist einfach so kompliziert, dass es es nicht wert ist.

Optimierung :

  • nicht
  • Expert nur: Seien Sie nicht, wir meinen es
  

Der Vektor wird in Bezug auf Zeit bestellt

Die Startzeit oder die Endzeit?

Was mit einem naiven O falsch (n) suchen? Erinnern Sie sich nur suchen und nicht sortieren. Sie könnten einen sortierten Behälter als auch verwenden (wenn das nicht gegen das Grunddesign geht).

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top