Finden Sie alle Strings (nicht-niedriger ASCII) beginnend mit einem Präfix in einem geordneten STL-Container

Question

Ich habe einen großen STL-Container von std::string (Hunderttausende von Einträgen). Ich benutze gerade eine vector, aber ich bin glücklich, mich zu ändern. Die Inhalte sind alphabetisch sortiert und bestehen aus alphabetischen Kleinbuchstaben a-z plusñ.

Ich versuche, eine Funktion zu implementieren, die eine const std::string& prefix empfängt und ein Paar Iteratoren zurückgibt, wobei einer auf das erste Element zeigt, das mit einem solchen Präfix beginnt, und das andere auf den letzten verweist. Wenn keine Zeichenfolgen den Kriterien entsprechen, geben Sie zwei identische Iteratoren zurück. Ich brauche Effizienz beim Nachschlagen, weil der Vektor sehr groß ist, also möchte ich ihn für eine binäre Suche verwenden.

Ich denke, std::lower_bound ist, was ich suche, aber ich vermisse eine Funktion zu vergleichen std::string s, die mit der spanischen ñ umgehen kann.

Answer 1

Sie können den gesamten Bereich der gleichen Werte mit std::equal_range erhalten. Sie erhalten ein Paar Iteratoren, einen am Anfang und einen nach dem Ende des Bereichs, wenn mindestens eine übereinstimmende Zeichenfolge in der Sammlung vorhanden ist. Wenn die Zeichenfolge nicht vorhanden ist, gibt es zwei gleiche Iteratoren an der ersten Stelle unmittelbar nach der Position, zu der die Zeichenfolge gehören würde, wenn sie vorhanden wäre.

Vorausgesetzt, dass Sie nur eine identische Teilzeichenfolge suchen, sollte ein normaler String-Vergleich (der ersten N Zeichen) gut funktionieren. Wenn Sie zum Beispiel Dinge wie ein Paar Eingabestrings unterstützen und alle Eingaben zwischen ihnen finden möchten, mussten Sie von (say) "m *" bis "o *" (mit Ihren "ñ *" - Strings) suchen so behandelt werden, als ob sie zwischen den beiden kämen), dann müssten Sie ein bisschen schicker werden (das Übliche besteht dann darin, eine Kollationstabelle mit dem Zeichencode als Index und der relativen Reihenfolge als Wert an jeder Position zu erstellen).