string switch

hiho

ich wollt mal in die runde fragen, wie ihr so string switches implementiert? fÃ¼r kleine strings / wenige fÃ¤lle kann man ja noch getrost if else ketten mit strcmp machen. aber was wenn es einige hundert werden, die auch noch oft abgefragt werden? ich habe das bislang oft mit unordered_map<string,function<void()>> gemacht, fand ich aber sehr hÃ¤sslich aus drei grÃ¼nden: 1. nutzt man eine variable um den code darzustellen, was sich falsch anfÃ¼hlt. der code sollte durch if else switch etc. dargestellt werden, nicht durch obskure tabellen die obskure funktionen enthalten. 2. man nutzt eine variable obwohl sich nie etwas daran Ã¤ndert. 3. new calls. alternativen?

mfg

achja, noch n nachteil: die hashes der strings werden zur laufzeit erst berechnet (=hoher initialaufwand) und die strings werden die ganze laufzeit des programs lang am leben gehalten.

hustbaer

(1): tut man irgendwie dauernd. finde ich nicht schlimm. und man muss es ja nicht "obskur" machen - man darf ja auch mal ausnahmsweise gute, verständliche variablen- und funktionsnamen verwenden.
(2): kannst du vermeiden wenn du wirklich willst, indem du ne unordered_map<string, int> verwendest und dann halt auf den int switch()ed.
(3) + "noch n nachteil": ist mir tendentiell wurst. gibt natürlich fälle wo es schwierig ist ein gutes zuhause für die map zu finden, so dass man sie nicht dauernd neu bauen muss, sie aber gleichzeitig nicht in teile rausgezogen wird die damit gar nix zu tun haben sollten - aber auch das lässt sich lösen wenn es wichtig ist.

was man ansonsten machen kann...
wenn die strings sich selten genug ändern, und es dir nicht zu viel aufwand ist kannst du das ganze in mehrere switch()es zerlegen. erstmal auf die länge und dann pro index wo es unterschiede geben kann. zum schluss noch 1x vergleichen um "was unbekanntes" fälle zu erkennen (ausgenommen fälle wo bereits jedes zeichen vorher geprüft wurde).
dann hast du wieder nur code, so wie du möchtest, und ne mehr oder weniger performante implementierung. wird aber sehr schnell sehr unübersichtlich. hab ich noch nie gemacht, ist mehr theoretisch.

oder du findest eine kollisionsfreie hash funktion für deine strings. dann kannst du hashen und brauchst pro case nur mit einem string zu vergleichen, nämlich dem bekannten. wenn ungleich, dann war es ein unbekannter. (also die konstenten strings hast du vorher gehashed, so dass du deren hashcode bei den "case"es direkt hinschreiben kannst.) mit c++17 sollte das mMn. sogar mit constexpr gehen, so dass du bei den case labels direkt hash("blah") schreiben kannst. damit wäre das wieder halbwegs schön zu schreiben und auch sichergestellt dass die hashfunktion kollisionsfrei ist -- denn sonst würde es nicht compilieren.
das sollte von der performance her nahe am optimum sein. hab ich auch noch nie gemacht, sehe aber keinen grund dagegen -- also gegen die constexpr variante. ausser natürlich wenn es der verwendete compiler nicht kann.

Columbo

mit c++17 sollte das mMn. sogar mit constexpr gehen, so dass du bei den case labels direkt hash("blah") schreiben kannst. damit wäre das wieder halbwegs schön zu schreiben und auch sichergestellt dass die hashfunktion kollisionsfrei ist -- denn sonst würde es nicht compilieren.

Das ist auch unter C++11 möglich. Wurde wiederholt im Forum demonstriert, auch von mir:

<a href= schrieb:

Arcoth">

5cript schrieb:

Aber vielleicht hat ja Arcoth noch eine Lösung, die mich umhaut

So etwas leider nicht, aber die Hashing Idee ist schon recht bekannt und wird i.d.R. so implementiert:

constexpr std::uint64_t fnv(const char* p, std::size_t len,
                            std::uint64_t h = 0xcbf29ce484222325) {
    return len == 0? h : fnv(p+1, len-1, (h ^ *p) * 0x00000100000001b3);
}

constexpr std::uint64_t operator "" _fnv( char const* str, std::size_t len ) {
    return fnv(str, len);
}

// [...]

    switch(fnv(str.data(), str.size()))
    {
        case "Hallo"_fnv:
            std::cout << "Welt!";
            break;
        case "Welt"_fnv:
            std::cout << "Hallo!";
            break;
        default:
            std::cout << "Nochmal probier'n!";
    }

Demo.

Edit: Was das Performance-Defizit der Map angeht, möchte ich natürlich auf die Stack-allozierenden Maps verweisen, wie die in Constainer. Den polymorphen Wrapper kann man ebenfalls optimieren, und sogar ohne jegliche Limitierungen: Schließlich ist die Größte der captures zur Compilezeit bekannt. Deshalb kann die kleinste ausreichende Zellengröße bestimmt werden. Ich würde diesen Weg natürlich trotzdem nur gehen, wenn die Zahl der Zweige so groß wird, dass der Komplexitätsvorteil den Overhead durch Indirektion und Kopie der captures kompensiert.

hustbaer

Ah, cool!