binary search with strcmp



  • In einer Liste befinden sich Namen die rein Alpabetisch sortiert sind. Die Namen sind in CamelCase geschrieben.
    Namen mit Underline kommen aber zuerst.

    mit einem bsearch und einer Methode als Übergabeparameter die einen strcmp durchführt sollte möglichst effizient nach einem Namen gesucht werden

    strcmp liefert mir dass der Underline "_" einen kleineren Wert hat als z.B. "a" oder auch "A" was nach der Alpabetischen Sortierung richtig ist.
    Nach der Ascii Tabelle kommt der Underline eigentlich nach dem großen "A" und vor dem kleinen "a".

    strcmp liefert mir aber zurück dass z.B. dass große T vor dem kleinen s kommt. Was wiederum der Ascii Tabelle entspricht aber nicht der reinen alpabetischen Sortierung.

    Beispiel:

    So ist die Sortierung

    _mno
    _klm
    abc
    def
    XYZ

    was auch der Sortierung im Windowsexplorer entsprechen würde.

    Strcmp liefert mir aber zurück dass XYZ der kleinere Wert ist als z.B. abc.

    _strcmpi hingegen sortiert case insensitive. Und sagt mir XYZ kommt nach abc. Was in meinem Fall passt. Allerdings liefert mir _strcmpi _mno kommt nach XYZ

    strcmp:
    -------
    _mno
    _klm
    XYZ
    abc
    def

    _strcmpi
    ----
    abc
    def
    XYZ
    _mno
    _klm

    Also die Frage: Gibt es eine string compare Funktion die die exakte Reihenfolge liefert wie die oben sortierte Liste.



  • Du möchtest also eine Funktion, die den String in Kleinbuchstaben vergleicht.

    Hast du dir mal den Code von strcmp angesehen?

    BTW: warum überhaupt C-Strings?



  • DirkB schrieb:

    BTW: warum überhaupt C-Strings?

    👍



  • nein möchte ich nicht. Wo steht das?
    Und wo steht dass ich nen CString verwende?



  • boster schrieb:

    Und wo steht dass ich nen CString verwende?

    Du benutzt eine Funktion um C-Strings zu vergleichen, ergo benutzt du C-Strings.



  • boster schrieb:

    nein möchte ich nicht. Wo steht das?

    '_' soll vor den Buchstaben einsortiert werden und die Groß-/Kleinschreibung ist egal.

    boster schrieb:

    Und wo steht dass ich nen CString verwende?

    strcmp (aus der Standard-Library) arbeitet nur mit C-Strings.

    Edit: Beachte den -
    Als C-String wird ein Nullterminiertes Char-Array verstanden. Eben ein String in C


  • Mod

    DirkB schrieb:

    Als C-String wird ein Nullterminiertes Char-Array verstanden. Eben ein String in C

    Mit Betonung auf 'kein String wie in C++'. Ich habe den Eindruck, dass dem Fragesteller gar nicht klar ist, dass Strings in C++ ganz anders gehen.



  • SeppJ schrieb:

    DirkB schrieb:

    Als C-String wird ein Nullterminiertes Char-Array verstanden. Eben ein String in C

    Mit Betonung auf 'kein String wie in C++'. Ich habe den Eindruck, dass dem Fragesteller gar nicht klar ist, dass Strings in C++ ganz anders gehen.

    Vor allem kein CString aus der MFC



  • Achso

    ich dachte ihr meint die Klasse CString.

    Also ist doch etwas anders als ich zuerst gedacht habe

    Ich habe zwei Systeme. In einem sind die Namen alle in Großbuchstaben

    _ABC
    ABC
    DEF
    GHI

    und die Namen mit den Underlines kommen am Anfang.

    In zweiten System sind die Namen in CamelCase und die Namen mit den Underlines kommen am Ende.

    abc
    DeF
    gHi
    _abc

    Ich denke hier ist es dann nicht möglich mit einer Routine beide Fälle zu behandeln ohne eine Fallunterscheidung zu machen.



  • boster schrieb:

    strcmp liefert mir dass der Underline "_" einen kleineren Wert hat als z.B. "a" oder auch "A" was nach der Alpabetischen Sortierung richtig ist.
    Nach der Ascii Tabelle kommt der Underline eigentlich nach dem großen "A" und vor dem kleinen "a".

    Das kann lt. Standard nicht sein. strcmp macht einen reinen Vergleich der Code-Werte der einzelnen Zeichen. Folglich kommt ein 'A':=0x65 vor einem '_':=0x95 - in folgendem Testprogramm ist das auch so:

    cout << strcmp("A egal","_egal was hier steht") << endl;
    

    liefert eine -1; heißt dass 'A'<'_' ist.

    boster schrieb:

    Und wo steht dass ich nen CString verwende?

    Nicht CString sondern C-Strings heißt [ char* ] - ohne C-String kein strcmp!

    boster schrieb:

    Also die Frage: Gibt es eine string compare Funktion die die exakte Reihenfolge liefert wie die oben sortierte Liste.

    Du kannst Dir eine beliebige Sortierung schnitzen, wenn Du statt C-Strings (s.o.) std::string und std::locale nebst std::collate benutzt. Geht im Prinzip so:

    #include <algorithm>
    #include <cassert>
    #include <iostream>
    #include <locale>
    #include <string>
    #include <vector>
    
    class StringCompare : public std::collate< char >
    {
    public:
        explicit StringCompare( std::size_t refs = 0 )
            : std::collate< char >( refs )
        {}
    
    protected:
        // liefert: t1<t2 := -1; t1==t2 := 0; t1>t2 := +1
        int do_compare( const char* low1, const char* high1, const char* low2, const char* high2 ) const
        {
            for( ; low1 != high1 && low2 != high2; ++low1, ++low2 )
            {
                if( less_c( *low1, *low2 ) )
                    return -1;
                if( less_c( *low2, *low1 ) )
                    return 1;
            }
            return low1 == high1? (low2 != high2? -1: 0) : 1;
        }
        string_type do_transform( const char* low, const char* high ) const
        {
            assert( ("not yet implemented",0) );
            return string_type();
        }
        long do_hash( const char* low, const char* high) const
        {
            assert( ("not yet implemented",0) );
            return 0;
        }
    
    private:
        bool less_c( char a, char b ) const
        {   // hier wird jetzt die Such- und Sortier-Reihenfolge festgelegt:
            if( b == '_' )
                return false;            // nichts ist kleiner als '_'
            if( a == '_' )
                return true;
    
            if( 'a' <= b && b <= 'z' )
            {
                if( !('a' <= a && a <= 'z') )
                    return false;       // !klein vor groß
            }
            else if( 'A' <= b && b <= 'Z' )
            {
                if( 'a' <= a && a <= 'z' )
                    return true;        // klein vor groß
            }
            return a < b;   // default;
        }
    };
    
    int main()
    {
        using namespace std;
        vector< string > vs( {  // nicht sortiert!
            "ABC", "abc", "_mno", "def_", "def",  "_klm", "XYZ"
        } );
        locale loc( locale(""), new StringCompare );
    
        sort( begin(vs), end(vs), loc );
        for( auto s: vs )
            cout << s << " ";
        cout << endl;
    
        cout << "\nFinde den Text, der als erster im 'Alphabet' nicht VOR dem Suchwort steht " << endl;
        for( string token; cout << "> ", cin >> token; )
        {
            auto i = lower_bound( begin(vs), end(vs), token, loc ); // das ist die binäre Suche!!
            cout << "next match: " << *i << endl;
        }
    
        return 0;
    }
    

    könnte dann im Dialog so aussehen:

    _klm _mno abc def def_ ABC XYZ

    Finde den Text, der als erster im 'Alphabet' nicht VOR dem Suchwort steht
    > ABC
    next match: ABC
    > daa
    next match: def

    Die Methode 'less_c' implementiert man am besten über eine Lock-Up-Table, das war mir aber i.A. zu aufwendig.

    Gruß Werner



  • boster schrieb:

    Ich denke hier ist es dann nicht möglich mit einer Routine beide Fälle zu behandeln ohne eine Fallunterscheidung zu machen.

    Ohne Fallunterscheidung nicht, aber mit einer collate-Klasse mit Schalter schon.



  • boster schrieb:

    Ich denke hier ist es dann nicht möglich mit einer Routine beide Fälle zu behandeln ohne eine Fallunterscheidung zu machen.

    strcmp ist kein Hexenwerk.
    Du kannst dir das auch leicht selber schreiben und vor dem Vergleichen die Zeichen in Klein- oder Großbuchstaben umwandeln.
    Je nachdem, welches Verhalten du wünscht. Auch einstellbar durch einen dritten Parameter.

    Aber ...
    ... die Strings von C++ (std::string) sind deutlich vielseitiger.



  • Also die Liste wird mir so geliefert und umsortieren sollte ich dringend vermeiden. Der Code arbeitet durchgehend mit char* also C strings.

    Also nun jedoch das darunter leigende System umgestellt wurde ist die GROSSSCHREIBUNG zur CamelCase Schreibweise gewechselt und die Sortierung mit den Underlines am Ende. Und mit dem vorhandenen Suchalgorithmus (bsearch und strcmp) wurden die Einträge nicht mehr alle gefunden,

    Mit dem umstellen auf _strcmpi hatte die Funktion wieder funktioniert. Allerdings nur für das neue System. Da das Programm aber beide Systeme unterstützen muss und die Liste wie gesagt nicht umsortiert werden darf, muss eine Fallunterscheidung her.



  • Dann mach dir eine eigene Funktion:

    #include <cctype>
    
    int str_icmp (const char *s1, const char *s2)
    {
      while (*s2 != 0 && tolower(*s1) == tolower(*s2))
        s1++, s2++;
      return (int) (tolower(*s1) - tolower(*s2));
    }
    

    Es wird als Kleinbuchstabe verglichen. Somit kommt '_' vor den Buchstaben (Zumindest bei ASCII)
    Und auch 'a' kommt vor 'B'



  • Hallo DirkB

    ja aber wie bereits erwähnt ist ja das nicht das Problem. Sondern dass ich entweder die '_' am Ende oder Amfang kommen.

    Also brauche ich eine Fallunterscheidung.



  • boster schrieb:

    Hallo DirkB

    ja aber wie bereits erwähnt ist ja das nicht das Problem. Sondern dass ich entweder die '_' am Ende oder Amfang kommen.

    Also brauche ich eine Fallunterscheidung.

    #include <cctype>
    int str_icmp (const char *s1, const char *s2, int underline_first)
    {
      if ( underline_first)
      {  while (*s2 != 0 && tolower(*s1) == tolower(*s2))
          s1++, s2++;
         return (int) (tolower(*s1) - tolower(*s2));
      } 
      else   
      {  while (*s2 != 0 && toupper(*s1) == toupper(*s2))
          s1++, s2++;
         return (int) (toupper(*s1) - toupper(*s2));
      } 
    }
    

    Hexenwerk.



  • boster schrieb:

    Also die Liste wird mir so geliefert und umsortieren sollte ich dringend vermeiden. Der Code arbeitet durchgehend mit char* also C strings.

    Also nun jedoch das darunter leigende System umgestellt wurde ist die GROSSSCHREIBUNG zur CamelCase Schreibweise gewechselt und die Sortierung mit den Underlines am Ende. Und mit dem vorhandenen Suchalgorithmus (bsearch und strcmp) wurden die Einträge nicht mehr alle gefunden, ..

    Sortieren ist nicht notwendig, es reicht aus, wenn der Comparator in lower_bound die aktuell Definition der Reihenfolge einhält. Also ist die Fallunterscheidung 'nur' dahingehend notwendig, das richtige Comparator-Objekt auszuwählen. (Im meinem Beispiel das locale ).

    Ob das Comparator-Objekt für die aktuelle Liste passt oder nicht, kann man sehr schnell mit adjacent_find heraus bekommen.


Log in to reply