suche void stripTrailingSpaces(char* str);



  • volkard schrieb:

    suche gute implemetierung zu

    void stripTrailingSpaces(char* str);
    

    hintergrund: hatte heute ein vorstellungsgespräch, wo der chef das fragte. ich hab nen falschen mist abgeliefert. aber auch nach mehrminütigem nachdenken nachträglich war es nicht trivial.

    Definiere gut.

    Mein anderthalbster Versuch brachte dies (der aller erste Versuch kam mit nur einer Zusweisung von 0 aus, dummerweise an der falschen Stelle).

    void stripTrailingSpaces(char* str)
    {
        assert(str);
        char* end = str + strlen(str);
        while (end != str && *(--end) == ' ')
            *end = 0;
    }
    

    Aber es ist spät, ich habe gerade ein hartes Fußballtraining hinter mir, die Chancen stehen also nicht schlecht, dass ich mich hier gerade nur zum Deppen mache 🙂



  • Toll. 7 Minuten nachgedacht und damit schon wieder viel zu spät 😃



  • Hallo,

    nicht so toll wie Humes, aber just for fun mal gemacht:

    void stripTrailingSpaces(char *str) {
    	char* end = str+strlen(str);
    	reverse(str, end);
    	fill_n(str, find_if(str, end, bind2nd(not_equal_to<char>(), ' ')) - str, '\0');
    	reverse(str, end);
    }
    

    Eine andere Moeglichkeit, die mir grad noch einfaellt, wo Hume doch erwaehnte,
    dass man ja lediglich an einer Stelle des Strings ein Nullterminierungszeichen
    plazieren muss, is aber boese, falls entsprechendes nicht gefunden wird:

    void stripTrailingSpaces(char *str) {
    	char* end = str+strlen(str);
    	reverse(str, end);
    	*(find_if(str, end, bind2nd(not_equal_to<char>(), ' '))-1) = '\0';
    	reverse(str, end);
    }
    

    Aber mir gefallen die zwei 'reverse()'-Aufrufe nicht so und rfind_if gibt es
    leider nicht in der stl :). Naja, hoffe ich hab hier jetzt keine Fehler drinne,
    habs ausprobiert und es hat gefunzt. Aber Humes Loesung ist bestimmt die, die
    am ehesten gefragt ist ;). So, jetzt geh ich schlafen...muss morgen arbeiten.

    mfg
    v R



  • Oder vielleicht doch vorwärts suchen?

    void stripTrailingSpaces(char* str)
    {
    	assert(str);
    	char* lastNonSpace = str;
    	do
    	{	
    		while (*str && *str != ' ') ++str;
    		lastNonSpace = str;
    		while (*str == ' ') ++str;
    	}while(*str);
    	*lastNonSpace = 0;	
    }
    


  • @Volkard
    Oder bin ich jetzt voll in die Falle getappt, weil ich nicht vorher gefragt habe ob str nicht zufällig auch ein Multi-Byte-Character-String sein könnte?



  • HumeSikkins schrieb:

    Definiere gut.

    korrekt, verständlich und performant.



  • HumeSikkins schrieb:

    Oder vielleicht doch vorwärts suchen?

    void stripTrailingSpaces(char* str)
    {
    	assert(str);
    	char* lastNonSpace = str;
    	do
    	{	
    		while (*str && *str != ' ') ++str;
    		lastNonSpace = str;
    		while (*str == ' ') ++str;
    	}while(*str);
    	*lastNonSpace = 0;	
    }
    

    und du hast echt nicht meinen rechner geknackz und den variablennamen abgeguckt? ich bin auf das hier gekommen.

    void stripTrailingSpaces(char* str){
    	char* lastNonSpace=NULL;//assume no non-space character
    
    	char* pos=str;//pos runs through the string
    	while(*pos!='\0'){
    		if(*pos!=' ')
    			lastNonSpace=pos;//and finds the last non-space character
    		++pos;
    	}
    
    	if(lastNonSpace!=NULL)//if there is a last non-space
    		*(lastNonSpace+1)='\0';//the cut directly after it
    	else//if only space characters
    		*str='\0';//cutcomplete string
    }
    


  • @virtuell Realisticer
    Statt der reverse-Aufrufe würde ich eher reverse_iteratoren benutzen:

    void stripTrailingSpaces(char* str)
    {
        typedef reverse_iterator<char*> RIT;
        RIT end(str-1);
        RIT it = std::find_if(RIT(str+strlen(str)), end, bind2nd(not_equal_to<char>(), ' '));
        if (it != end) *it.base() = 0;
    }
    

    und du hast echt nicht meinen rechner geknackz und den variablennamen abgeguckt?

    Nicht das ich wüsste 😉

    korrekt, verständlich und performant.

    Hm. Leider passen die drei mal wieder nicht so gut zusammen.
    Die "ersetze-von-hinten-alle-Spaces-durch-0"-Methode ist imo am Natürlichsten und gewinnt damit in der Kategorie Verständlichkeit.
    Dafür hat sie aber (bei C-Strings) Worst-Case O(n^2).
    Die "Spule-vor-bis-zum-letzten-nicht-Space-Char" ist deutlich komplizierter, theoretisch aber performanter.



  • HumeSikkins schrieb:

    Die "ersetze-von-hinten-alle-Spaces-durch-0"-Methode ist imo am Natürlichsten und gewinnt damit in der Kategorie Verständlichkeit.
    Dafür hat sie aber (bei C-Strings) Worst-Case O(n^2).

    Aber nur wenn man das Ende jedesmal neu sucht, sonst ist es linear.



  • Ponto schrieb:

    HumeSikkins schrieb:

    Die "ersetze-von-hinten-alle-Spaces-durch-0"-Methode ist imo am Natürlichsten und gewinnt damit in der Kategorie Verständlichkeit.
    Dafür hat sie aber (bei C-Strings) Worst-Case O(n^2).

    Aber nur wenn man das Ende jedesmal neu sucht, sonst ist es linear.

    Wieso? Ich brauch einmal n für strlen und einmal n für das Rückwärtssuchen (worst-case: nur Leerzeichen). Wo ist mein Denkfehler?



  • Ok. Danke. Jetzt ist mein Gehirn wieder an. 2n != n^2 😃 😉



  • HumeSikkins schrieb:

    Wieso? Ich brauch einmal n für strlen und einmal n für das Rückwärtssuchen (worst-case: nur Leerzeichen). Wo ist mein Denkfehler?

    2n2n und nicht n2n^2



  • HumeSikkins schrieb:

    @virtuell Realisticer
    Statt der reverse-Aufrufe würde ich eher reverse_iteratoren benutzen:

    void stripTrailingSpaces(char* str)
    {
        typedef reverse_iterator<char*> RIT;
        RIT end(str-1);
        RIT it = std::find_if(RIT(str+strlen(str)), end, bind2nd(not_equal_to<char>(), ' '));
        if (it != end) *it.base() = 0;
    }
    

    Ah, sowas hat mir gefehlt. Die muss ich in der STL-Doku wohl uebersehen haben.
    Thx fuer Code, sieht doch gleich viel schoener aus :).

    mfg
    v R



  • virtuell Realisticer schrieb:

    HumeSikkins schrieb:

    @virtuell Realisticer
    Statt der reverse-Aufrufe würde ich eher reverse_iteratoren benutzen:

    void stripTrailingSpaces(char* str)
    {
        typedef reverse_iterator<char*> RIT;
        RIT end(str-1);
        RIT it = std::find_if(RIT(str+strlen(str)), end, bind2nd(not_equal_to<char>(), ' '));
        if (it != end) *it.base() = 0;
    }
    

    Ah, sowas hat mir gefehlt. Die muss ich in der STL-Doku wohl uebersehen haben.
    Thx fuer Code, sieht doch gleich viel schoener aus :).

    mfg
    v R

    trotzdem noch unglaublich unschön



  • kotz schrieb:

    trotzdem noch unglaublich unschön

    Da gebe ich dir in diesem Fall recht. Verwendet man allerdings statt
    des bind2nd(not_equal_to<char>(), ' ')-Monsters einen hübschen boost-Lambda-Ausdruck a la:

    RIT it = std::find_if(RIT(str+strlen(str)), end, _1 != ' ');
    

    dann passt's auch mit der Schönheit.



  • HumeSikkins schrieb:

    RIT end(str-1);
    

    sind diese zeigervergleiche erlaubt? ich meine, weil str-1 ja nicht gerade im gemeinsam mit dem rest allokierten bereich liegt. oder gab es diese verwirrung nur bei < und nicht bei != ?

    Hm. Leider passen die drei mal wieder nicht so gut zusammen.
    Die "ersetze-von-hinten-alle-Spaces-durch-0"-Methode ist imo am Natürlichsten und gewinnt damit in der Kategorie Verständlichkeit.
    Die "Spule-vor-bis-zum-letzten-nicht-Space-Char" ist deutlich komplizierter, theoretisch aber performanter.

    jo. aber zum glück ist normalerweise eine sehe verständliche auch lösung sehr performant (und kann höchstens von lösungen getoppt werden, die den zehnfachen umfang haben).
    edit: um genau zu sein: die zeigerarithmetik bei str-1 ist undefined.



  • volkard schrieb:

    edit: um genau zu sein: die zeigerarithmetik bei str-1 ist undefined.

    So wäre es wohl richtig:

    void stripTrailingSpaces(char* str)
    {
        typedef reverse_iterator<char*> RIT;
        RIT rbegin(str+strlen(str));
        RIT rend(str);
    
        RIT it = std::find_if(rbegin, rend,  bind2nd(not_equal_to<char>(), ' '));
       *it.base() = 0;
    
    }
    

Anmelden zum Antworten