string effizient splitten



  • Hi,

    wie kann ich folgende funktion optimieren? ich will folgenden string: "5.1+" in 5,1,+ oder "4.5.5*" in 4,5,5,* splitten...

    #include <iostream>
    #include <string>
    #include <vector>
    #include <string.h>
    using namespace std;
    
    // i want to use multiple delimiters (these are: '.' '+' '*')
    void tokenize(const std::string& str, const char* delim, std::vector<std::string>& lst) {
        if (str.empty()) {
            return;
        }
    
        char* dup = strdup(str.c_str());
        char* tok = strtok(dup, delim);
        uint8_t len = 0;
    
        while (tok != NULL) {
        	len = strlen(tok);
    
        	if ((tok[len-1]) == '*' || 
        	    (tok[len-1]) == '+') {
        		lst.push_back(std::string(strndup(tok, len-1)));
        		lst.push_back(std::string(strndup(tok+1, 1)));
        	}
        	else {
            	lst.push_back(std::string(tok));
        	}
            tok = strtok(NULL, delim);
        }
        free(dup);
    }
    
    int main() {
    	// your code goes here
    
    	std::vector<std::string> tokList;
    	tokenize("5.1+", ".", tokList);
    
    	for (auto tok : tokList) {
    		cout << tok << " ";
    	}
    
    	return 0;
    }
    


  • ein paar infos:
    const std::string& str kann '+' und '*' haben, diese sollen als token im vector erhalten bleiben.

    const std::string& str kann nur max ein '+' oder '*' am ende des strings haben...


  • Mod

    mike1 schrieb:

    const std::string& str kann nur max ein '+' oder '*' am ende des strings haben...

    Also letztes Zeichen angucken, ggf. als Token erkennen, danach den Rest mit den Standardmethoden an '.' splitten?



  • Ist das ne Hausaufgabe?

    Wenn nicht, dann nimm einfach den Boost.Tokenizer, damit splittst du was auch immer in 4 wohlformatierten Zeilen.

    Ich behaupte mal, die von Boost haben das auch sauber implementiert, habe es natürlich nicht getestet.



  • ich habs nun so geloest, muss noch testen obs einen bug gibt:

    void tokenize(const std::string& str, const char* delim, std::vector<std::string>& lst) { 
        if (str.empty()) { 
            return; 
        } 
    
        char* dup = strdup(str.c_str()); 
        char* tok = strtok(dup, delim); 
        uint8_t len = 0;
    
        while (tok != NULL) { 
            len = strlen(tok);
    
            // teste letztes zeichen
            if ((tok[len-1]) == '*' || 
                (tok[len-1]) == '+') {
                if (len == 1) {
                	lst.push_back(std::string(tok));
                    break;
                }
                else {
                	lst.push_back(std::string(strndup(tok, len-1))); 
                	lst.push_back(std::string(strndup(tok+len-1, 1)));
                }
            } 
            else { 
                lst.push_back(std::string(tok)); 
            } 
            tok = strtok(NULL, delim); 
        } 
        free(dup); 
    }
    

  • Mod

    Wenn man in C++ Stringoperationen macht und dabei
    a) string.h/cstring bemüht
    oder
    b) free benutzt

    Dann ist da etwas ganz grundsätzlich falsch.



  • der hintergrund strdup, strtok zu verwenden war speed (ich kann da auch falsch liegen). ich weiss nicht wie viel overhead eine c++ version da hat...


  • Mod

    mike1 schrieb:

    der hintergrund strdup, strtok zu verwenden war speed (ich kann da auch falsch liegen). ich weiss nicht wie viel overhead eine c++ version da hat...

    Garantiert weniger Overhead¹, als zuerst wild unnötige Kopien zu erzeugen.

    ¹: Womöglich sogar negativen, weil C-Strings teilweise sogar weniger effizient sind, da sie weniger Verwaltungsinformation tragen. Typisches Extrembeispiel wäre strlen vs length.


  • Mod

    Wie waers mit

    #include <iostream>
    #include <string>
    
    #include <boost/container/static_vector.hpp>
    
    template<typename T, std::size_t N = 256>
    using svector = boost::container::static_vector<T, N>;
    
    svector<std::string> split(std::string const& s) {
        svector<std::string> vec{{}};
        for (auto c : s) 
            switch(c) {
                case '+': case '-': case '*': case '/': vec.push_back({c});
                case '.': vec.emplace_back(); break;
                default: vec.back() += c;
            }
        if (vec.back().empty()) vec.pop_back();
        return vec;
    }
    
    int main()
    {
        auto x = split("5.1*7");
        for (auto y : x) std::cout << y << ' ';
    }
    

    Natuerlich hoffen wir auf SSO bei den strings; lieber waere mir natuerlich eine static_string Klasse, aber das gibt es leider nicht in Boost AFAIK (wobei ich das in constexpr implementiert habe).



  • Hi Arcoth,

    fuer

    split("*")
    

    musste ich noch ein if hinzufuegen:

    if (vec.front().empty()) vec.erase(vec.begin());
    

    ...was bei einem vector nicht effizient ist...

    was ist der unterschied zwischen dem static_vector and std::vector? ...static_vector uses "static allocation", heisst das der vector allokiert den vector mit max capacity von 256 und der vector hat eine fixe groesse? dh der static vector wird nie mehr reallokiert, wenn man z.b. elemente loescht?

    #include <iostream> 
    #include <string> 
    #include <vector>
    #include <boost/container/static_vector.hpp> 
    
    template<typename T, std::size_t N = 256> 
    using svector = boost::container::static_vector<T, N>; 
    
    svector<std::string> split(const std::string& s) { 
        svector<std::string> vec{{}};
    
        for (auto c : s) {
            switch(c) { 
                case '+': case '-': case '*': case '/': vec.push_back({c});
                case '.': vec.emplace_back(); break;
                default: vec.back() += c;
            }
        }
        if (vec.front().empty()) vec.erase(vec.begin());
        if (vec.back().empty()) vec.pop_back();
        return vec; 
    }
    
    int main() 
    { 
        auto x = split("5.1*"); 
        for (auto y : x) std::cout << y << ' ';
    
        std::cout << std::endl;
    
        x = split("*");
        for (auto y : x) std::cout << y << ' ';
    
        std::cout << std::endl;
    
        x = split("3+"); 
        for (auto y : x) std::cout << y << ' ';
    
        std::cout << std::endl;
    
        x = split("1*"); 
        for (auto y : x) std::cout << y << ' ';
    
        std::cout << std::endl;
    
        x = split("1.2.3"); 
        for (auto y : x) std::cout << y << ' ';
    }
    


  • mike1 schrieb:

    Hi Arcoth,

    fuer

    split("*")
    

    musste ich noch ein if hinzufuegen:

    if (vec.front().empty()) vec.erase(vec.begin());
    

    ...was bei einem vector nicht effizient ist...

    was ist der unterschied zwischen dem static_vector and std::vector? ...static_vector uses "static allocation", heisst das der vector allokiert den vector mit max capacity von 256 und der vector hat eine fixe groesse? dh der static vector wird nie mehr reallokiert, wenn man z.b. elemente loescht?

    Auch beim std::vector wird beim löschen eines elements keine reallokation gemacht.
    Das einzige was passiert das alle elemente, welche sich nach dem gelöschten Element befinden, werden um eine Position verschoben um die Lücke zu schließen.



  • @firefly: das kostet aber recht viel zeit?

    was ist der unterschied zwischen dem static_vector and std::vector? ...static_vector uses "static allocation", heisst das der vector allokiert den vector mit max capacity von 256 und der vector hat eine fixe groesse? dh der static vector wird nie mehr reallokiert, wenn man z.b. elemente hinzufuege/loesche?




Log in to reply