Wie kann ich am besten eine bestimmte Zeichenfolge in einem Vektor finden?

Question

Zum Beispiel. Ich habe eine gewisse Struktur:

s_Some{
  std::string lable;
  s_some_junk some_junk;
};

Und einen Vektor:

std::vector<s_Some> mSome;

Und dann fülle ich diesen Vektor mit einer Menge s_Somes.

Ich brauche einen Iterator für ein einzelnes s_Some in diesem Vektor zu finden, die eine bestimmte lable hat. Bisher habe ich einfach durch all diesen Müll iteriert und jede Tabelle mit der gewünschten Tabelle abgeglichen. Das sieht für mich ein bisschen blöd aus. Gibt es einen besseren Weg, dies zu tun?

Answer 1

Option 1) Wenn Sie gezwungen sind, den std::vector zu verwenden, aber sobald der Vektor gefüllt ist, bleibt er unverändert, dann könnten Sie den Vektor sortieren und die binäre Suche verwenden. Die einzigen Kosten wären dann das Sortieren und es entsteht kein zusätzlicher Overhead. Die Suchzeit ist logarithmisch O(logN).

Option 2) Wenn Sie die Freiheit haben, eine andere Datenstruktur zu wählen, dann sollten Sie die map (auch logarithmisch) oder unordered_map (erwartet O(1), schlimmstenfalls O(n)) verwenden.

Ich habe gerade bemerkt, dass Sie sagten, Sie wollten jedes Etikett mit dem gesuchten abgleichen. Daraus schließe ich, dass Sie doppelte Etiketten haben können. Dann für Punkt 2 verwenden entsprechende multi_map Container, während für Punkt 1 die Dinge ein bisschen chaotischer.

Answer 2

Wenn Sie nur wenige Male suchen müssen oder wenn Ihr Vektor bei jeder Suche wahrscheinlich einen anderen Inhalt hat, gibt es leider keine Alternative; Sie müssen den gesamten Vektor durchgehen.

Wenn sich Ihr Vektor jedoch nach der Erstellung nicht mehr ändern wird und Sie eine große Anzahl von Suchvorgängen durchführen müssen, tun Sie dies:

1. Sortiert den Vektor in aufsteigender Reihenfolge der Zeichenketten (d.h. so, wie sie im Wörterbuch stehen).
2. Wenn Sie so sortiert sind, verwenden Sie binärer Suchalgorithmus für alle Suchen.

Das wird viel schneller gehen.

Answer 3

Verwenden Sie eine

std::multimap< string, s_Some > mSome;

y

mSome.insert( std::make_pair( aSome.lable, aSome ) );

Finden Sie die erste Instanz des gewünschten Wertes von lable durch

mSome.find( lable_you_want );

Die nächste Instanz wird durch Inkrementieren des Iterators gefunden.

vgl. http://www.cppreference.com/wiki/stl/multimap/start

Das heißt, es sei denn, Sie müssen einen std::vector verwenden.

Answer 4

Sie können auch eine Karte de Verzeichnisse

Answer 5

Dazu können Sie den find_if-Algorithmus verwenden. Definieren Sie ein Prädikat etwas wie dieses:

struct isEqual
{
    isEqual(const std::string& s): m_s(s)
    {}
    bool operator()(S_Some& l)
    {
        return l.lable == m_s;
    }

    std::string m_s;
};

Und während der Suche können Sie

std::vector<S_Some>::iterator iter = std::find_if(mSome.begin(),
                                                  mSome.end(),
                                                  isEqual(std::string("AAAA"));