Grosse if-Abfrage ersezten durch schoenen design



  • Hallo Leute,

    ich habe eine laengere if-Abfrage die so aussieht:

    if(str!="X" && str!="Z" && str!="ZX" && str!="BX" && str!="VX" && str!="QX")
    {
    .
    .
    .
    }
    

    In Zukunft wird die if-Abfrage erweiterst d.h. es koennen z.B noch mehr && str!="BN" hinzukommen. Wie kann ich die if Abfrage nun durch einen Algorithmus aus der STL ersetzen. Ich habe mir gedacht ich speichere all die strings in einem vector:

    std::vector<std::string>check_strs;
    check_strs.push_back("X");
    check_strs.push_back("Z");
    check_strs.push_back("ZX");
    check_strs.push_back("BX");
    check_strs.push_back("VX");
    check_strs.push_back("QX");
    
    std::vector<std::string>::const_iterator i = std::...(check_strs.begin(),check_strs.end(),funktor(str));
    
    if(i==check_strs.end())
    {
    .
    .
    .
    }
    

    Welchen Algorithmus muss ich verweden? Oder gibt es noch einen anderen Weg das elegant zu loesen?

    Besten Dank
    🙂



  • Mit C++11 wirds einfach:

    std::vector<std::string> check_strs
    { "X", "Z", "ZX", "BX", "VX", "QX" };
    
    std::string str; // Dein Test-String!
    if( std::find( check_strs.begin(), check_strs.end(), str ) == check_strs.end() )
    {
        //...
    }
    

    Mit C++98 musst du statt std::vector ein C-Array nehmen (für die Listen-Initialisierung) und entsprechend umbauen.

    (Ungetestet!)



  • Wenn STL dann wohl eher unorderd_set oder set und die Funktion count.



  • Gut, das geht natürlich auch.



  • manni66 schrieb:

    Wenn STL dann wohl eher unorderd_set oder set und die Funktion count.

    Noch viel besser wäre ein sortiertes Array mit std::binary_search .



  • Vielen Dank fuer die vielen Hinweise!
    Ich werde find verwenden.
    Ist binary_search mit dem sortierten Array schneller?



  • LeeVanCleef schrieb:

    Ist binary_search mit dem sortierten Array schneller?

    Es muss nur maximal log2(n) Vergleiche machen. In deinem Fall maximal 3 statt maximal 6 Vergleiche. Wenn die Anzahl Elemente grösser wird, zahlt sich das immer mehr aus.

    std::set muss zwar auch nur maximal 3 Vergleiche machen, aber der restliche Overhead ist immens grösser, so dass ich vermute, dass hier std::find sogar schneller ist.

    Und du kannst auch normale Arrays nehme, weshalb Sone hier std::vector verwenden will, verstehe ich nicht.



  • Bei so kurzen Containern ist der Overhead der linearen Suche aber nicht besonders groß verglichen zum Aufwand, die Liste erst noch zu sortieren. Ja, man kann sie gleich sortiert schreiben, aber da schleciht sich viel zu schnell ein Fehler sein, außerdem möchte man sie aus semantischen Gründen vielleicht lieber in einer anderen Reihenfolge pflegen.

    Die bisherigen Codes haben nämlich eine Schwachstelle: der vector (oder was auch immer für einen Container man wählt) wird jedesmal neu angelegt, müsste also auch jedesmal neu sortiert werden. Meine Lösung sähe im ersten Wurf vermutlich so aus:

    template <class T, class SortedContainer>
    bool isInSortedList(T&& val, SortedContainer const& container)
    {
      return std::binary_search(std::begin(container), std::end(container), val) != std::end(container);
    }
    // ...
    
    const static auto sorted_check_strs = []() {
      std::vector<std::string> vec 
        {"X", "Z", "ZX", "BX", "VX", "QX"};
      std::sort(begin(vec), end(vec));
      return vec;
    }();
    
    std::string str = /* ... */;
    if( isInSortedList(str, sorted_check_strs) )
    {
        //...
    }
    

    ggf. kann man aus dem Lambda auch noch eine eigene Funktion machen, um die Funktion nicht mit der Erzeugung der sortierten Liste zu überladen:

    const static auto sorted_check_strs = makeSortedList<std::vector>
      ({"X", "Z", "ZX", "BX", "VX", "QX"});
    
    std::string str = /* ... */;
    if( isInSortedList(str, sorted_check_strs) )
    {
        //...
    }
    


  • Es besteht auch die Möglichkeit, die Liste mit Template Metaprogramming zu sortieren und dann sortiert ins Datensegment des Programmes zu speichern. Leider ist es in pre C++14 etwas mühsam, Strings als Templateparameter zu übergeben.

    Kellerautomat hat hier mal einen TMP-Sortieralgorithmus für Strings gepostet.


Anmelden zum Antworten