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.


Log in to reply