Mehrfache Ersetung in strings

peterchen

Ich suche nach einem brauchbaren Algorithmus für mehrfache übersetzungen in einem String - d.h. ich habe z.B. eine map<string,string> mit Schlüsselwärtern und Ersetzungen.

Beispiel:

map["FOO"] = "Fehler-Objektorientiert)";
map["BAR"] = "Cash";

string s = "Hans FOOBAR";

multireplace(s, map);
assert(s == "Hans Fehler-ObjektorientiertCash");

die map kann evtl. recht lang werden, so daß ich nicht grad an jedem Zeichen auf alle strings prüfen möchte.

Randbedingungen:

Bei zwei Schlüsseln "FOO" und "FOOS" soll der länger erkannt werden (falls er paßt)
Schlüsselvergleich optional ohne Beachtung Groß/Kleinschreibung

Ideen oder Links?

Michael E.

for(map<string, string>::iterator iter = myMap.begin(); iter != myMap.end(); ++iter)
{
    string::size_type pos;
    while((pos = s.find(iter->first)) && pos != string::npos)
        s.replace(pos, iter->first.size(), iter->second);
}

[Edit] Zu den Randbedingungen:

Kannst du die Map nach der Schlüssellänge sortieren?
Das ist eklig Kann ich dir nicht sagen, welches der beste Weg ist.

.filmor

Eine klitzekleine Optimierung:

for(map<string, string>::iterator iter = myMap.begin(); iter != myMap.end(); ++iter)
{
    string::size_type pos = s.find(iter->first);
    while(pos != string::npos)
    {
        s.replace(pos, iter->first.size(), iter->second);
        pos = s.find(iter->first, pos + iter->first.size ());
    }
}

@peterchen: Wofür brauchst du das?! So wie du das schilderst scheint es mir ziemlich aufwendig zu programmieren, ist es das wert?

/edit: Zu 1.: Wenn du die Map an sich nicht umsortieren kannst/willst, ist vielleicht Boost.MultiIndex nützlich.

peterchen

Brauch' ich nicht zwingend - bzw. Brute Force ist in meinem Fall sicher ausreichend. (Anwendungsfall wäre Ersetzen von Umgebungsvariaben in einer befehlszeile - mein Ausgangspunkt war ähnlich).

Ich hab' geknobelt ob mir was fundamental besseres als "jeder string an jedem zeichen" einfällt, aber außer ein paar kleineren Optimierungen fällt mir nix ein.

2. sortierug der map ist egal (muß nicht mal eine map sein)

Mein Ansatz war etwas anders:

für alle zeichen ch in s
  in map: suche bereich aller strings die mit ch beginnen
    probiere alle strings im bereich

hat zwar eine binäre suche, fällt aber sofort auf linear zurück, wenn alle Schlüssel mit dem gleichen zeichen beginnen (was häufig sein wird).

Ich hab versucht, die map mit greater<> zu sortieren, damit längere strings zuerst kommen, aber dann bekomm ich mit lower_bound einen totalen Knoten im Kopf, scheint wohl nicht wirklich was zu nutzen.

Michael E. schrieb:

Das ist eklig

Aber nutzerfreundlich
Mein Ansatz war folgender: für "IgnoreCase" werden die Schlüsselstrings nach Lowercase umgewandelt (damit sie hintereinander liegen), und die vergleiche dann halt case insensitive (weil s nicht nach lowercase umgewandelt werden kann)

Naja, falls jemand noch eine Idee (oder einen link) hat

CStoll

Zu 1: Der Standardvergleich für Strings definiert eine lexikografische Ordnung (das bedeutet: wie im Wörterbuch) - wenn du etwas anderes benötigst, mußt du einen eigenen Vergleichs-Funktor schreiben.

Zu 2: Entweder du definierst dir eine Spezialisierung der basic_string für Case-Insensitive Strings (du kannst dir die aus meinem Artikel "Stringverarbeitung im C++" nehmen) oder du definierst einen Vergleichsfunktor, der Großschreibung ignoriert.