std :: map partielle Übereinstimmung für den Schlüssel
Habe ich eine std::map, und ich will die Suche nach einem Schlüssel mit einem substring. Für exampe
#include <iostream>
#include <map>
#include <string>
using namespace std;
typedef std::map<std::string, std::string> TStrStrMap;
typedef std::pair<std::string, std::string> TStrStrPair;
int main(int argc, char *argv[])
{
TStrStrMap tMap;
tMap.insert(TStrStrPair("John", "AA"));
tMap.insert(TStrStrPair("Mary", "BBB"));
tMap.insert(TStrStrPair("Mother", "A"));
tMap.insert(TStrStrPair("Marlon", "C"));
return 0;
}
Möchte ich, um die Suche für die position hält, dass der substring "Marl" und nicht "Marlon". Ist es möglich? Wie?
EDIT: keine boost-Bibliotheken!
InformationsquelleAutor der Frage cateof | 2012-02-19
Du musst angemeldet sein, um einen Kommentar abzugeben.
Können Sie nicht effizient Suche nach substring, aber Sie können für Präfix:
Diese Drucke:
InformationsquelleAutor der Antwort Branko Dimitrijevic
Wenn Ihr substring ist ein Präfixwie in Ihrem Beispiel, können Sie
lower_bound
zu suchen"Marl"
.Diese funktioniert nicht bei nicht-Präfix Teilstrings: im Allgemeinen Fall, Suche eine Karte nicht viel anders ist, suchen andere Container.
InformationsquelleAutor der Antwort dasblinkenlight
Suche nach einem substring des Schlüssels in einer map-haben Sie keine Wahl aber entweder eine neue Karte auf eine Besondere Art von Schlüssel-Typ, oder suchen Sie Ihre Karte in O(n).
std::map
verwendet (standardmäßig)operator<()
für die Bestellung von Schlüsseln und für die Suche und das vergleichen Funktion fürstd::string
ist eine einfache lexikographische vergleichen.Wenn Sie eine neue Karte erstellen, die auf eine spezielle Taste geben, die
operator<()
vergleichen auf basis einer Teilzeichenfolge beachten Sie, dass dies auch Auswirkungen auf die Entscheidung, ob ein neues element einfügen, wäre ein Duplikat. In anderen Worten, eine solche Karte nur Elemente, die keine Teilstrings voneinander.O(n) Suche praktisch bedeutet, dass Sie verwenden
std::find()
über die Karte, mit ein benutzerdefiniertes Prädikat, das dauert einstd::pair<std::string,std::string>
und gibt true zurück, wenn das zweite element des Paares ist eine Teilzeichenfolge der ersten.InformationsquelleAutor der Antwort wilhelmtell
InformationsquelleAutor der Antwort Armen Tsirunyan