binary search with strcmp
-
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
-
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
GHIund 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
_abcIch 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: defDie 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 daslocale
).Ob das Comparator-Objekt für die aktuelle Liste passt oder nicht, kann man sehr schnell mit
adjacent_find
heraus bekommen.