Zeichenkette unterteilen
-
Hallo ,
Der folgende Code unterteilt eine gegebene Zeichenkette in mehrere Zeichenketten, die durch einen bestimmten "Unterteiler" in Anfänglicher gekennzeichnet sind, z.B. "Hallo+dies+ist+ein+Test+". Anschließend werden sie in einem gegebenen Vektor gespeichert.void subdivideString(std::string string, std::vector<std::string>& strings, std::string divider) { auto it = string.find(divider); auto itr = 0; while (it != string.npos) { std::string substring = string.substr(itr, it - itr); strings.emplace_back(substring); itr = (it + 1); it = string.find(divider, itr); } }
Ist der Code so akzeptabel oder gibt es eine bessere Möglichkeit dieses Ziel zu erreichen ?
-
#include <vector> #include <string> #include <sstream> std::vector< std::string > tokenize( std::string const & src, char delim ) { std::vector< std::string > tokens; std::string token; std::stringstream ss{ src }; while( std::getline( ss, token, delim ) ) tokens.push_back( token ); return tokens; }
-
Akzeptabel, aber was mir direkt auffällt sind zwei Dinge:
1. Ist es Absicht, dass der letzte Token nicht Teil der Ausgabe ist, wenn der String nicht auf dem Trennwort endet?
2. Der Code hat ein merkwürdiges Verhalten bei Trennworten mit mehreren Buchstaben. Der erste, und nur der erste, Buchstabe des Trennwortes wird aus dem nächsten Token entfernt. Ich denke, dies ist keine Absicht. Entweder soll doch wohl das Trennwort höchsten einen Buchstaben haben (also vom Typ char sein) oder aber der Code muss angepasst werden, um mit einer beliebigen Länge des Trennwortes klar zu kommen.Von der technischen Seite her, würde ich mir den Umweg über die substring-Variable sparen. Sollte zwar wegoptimiert werden, aber der Code wäre auch nicht unleserlicher, würde man dies einfach weglassen.
Ich sähe es lieber, wenn man durch die Funktion nicht auf einen vector festgenagelt würde. Nimm besser einen beliebigen Iterator als Argument.
-
was SeppJ mit 'beliebigen Iterator' meint, ist IMHO wohl sowas:
#include <set> #include <string> #include <sstream> #include <iterator> // inserter, back_inserter #include <iostream> template< typename Out > void tokenize( std::string const& src, char delim, Out out ) { std::istringstream ss{ src }; // (i)stringstream reicht, mehr braucht es nicht for( std::string token; std::getline( ss, token, delim ); ) *out++ = token; } int main() { using namespace std; set< string > tokens; // Der Aufrufer entscheidet über den Typ des Containers tokenize( "Hallo+dies+ist+ein+Test", '+', inserter( tokens, begin(tokens) ) ); for( auto& tok: tokens ) cout << tok << endl; return 0; }
.. wobei sich bei diesen Dingen jedesmal die Frage stellt:
Wo kommt der Text ursprünglich her? Stand er womöglich in einer Datei?Gruß
Werner
-
Vielen Dank für die schnellen Antworten .
Das Wort "delimiter" hör ich zum ersten Mal. Auch der der insert_iterator ist mir neu ! Scheint, dass ich noch einiges zu lernen habe .Lg,
Lukas
-
Werner Salomon schrieb:
// ... template< typename Out > void tokenize( std::string const& src, char delim, Out out ) { std::istringstream ss{ src }; // (i)stringstream reicht, mehr braucht es nicht for( std::string token; std::getline( ss, token, delim ); ) *out++ = token; } // ...
. o O ( Wie langs wohl noch dauert bis ich auf Anhieb auf die wirklich, wirklich eleganten Lösungen komm? )
-
Swordfish schrieb:
. o O ( Wie langs wohl noch dauert bis ich auf Anhieb auf die wirklich, wirklich eleganten Lösungen komm? )
Ich finde seine Lösung nicht besonders hübsch.
Schließlich möchte eine gute Bibliothek so abstrakt wie möglich operieren. Folgendes wäre also mein Vorschlag:
#include <experimental/string_view> #include <iterator> // traits #include <utility> // pair #include <functional> // equal_to namespace ste = std::experimental; namespace detail { template <typename ForwardIt, typename Func, typename Delim, typename Comp> void foreachSplit(ForwardIt first, ForwardIt last, Func f, Delim delim, Comp comp) { using traits = std::iterator_traits<ForwardIt>; auto it = first; while (first != last) { if (comp(*first, delim)) { if (it != first) f(it, first); it = ++first; } else ++first; } if (it != last) f(it, last); } } template <typename ForwardIt, typename OutputIterator, typename Delim, typename Comp> void split(ForwardIt first, ForwardIt last, OutputIterator out, Delim delim, Comp comp) { detail::foreachSplit(first, last, [&] (auto... its) {*out++ = std::make_pair(its...);}, delim, comp);} template <typename ForwardIt, typename OutputIterator, typename Delim> void split(ForwardIt first, ForwardIt last, OutputIterator out, Delim delim) { split(first, last, out, delim, std::equal_to<>{});} template <typename CharT, typename OutputIterator, typename Traits> void splitString(CharT const* first, CharT const* last, OutputIterator out, CharT delim, Traits) { auto fun = [&] (auto l, auto r) {*out++ = ste::basic_string_view<CharT, Traits>(l, r-l);}; detail::foreachSplit(first, last, fun, delim, Traits::eq); } template <typename CharT, typename OutputIterator> void splitString(CharT const* first, CharT const* last, OutputIterator out, CharT delim) { splitString(first, last, out, delim, std::char_traits<CharT>{});} #include <iostream> #include <vector> int main() { { int arr[] {1, 2, 3, 4, 3, 5, 9, 4, 1, 2, 4}; std::vector<std::pair<int*, int*>> vec; split(std::begin(arr), std::end(arr), std::back_inserter(vec), 4); for (auto& p : vec) { for (auto i = p.first; i != p.second; ++i) std::cout << *i << ' '; std::cout << '\n'; } } { char const str[] = "Hallo+dies+ist+ein+Test"; std::vector<ste::basic_string_view<char>> vec; splitString(std::begin(str), std::end(str)-1, std::back_inserter(vec), '+'); for (auto& p : vec) std::cout << p << '\n'; } }
Demo.
Allerdings ist das performance-mäßig nicht optimal. Wenn wir den nächsten Delimiter im Falle eines byte-großen, trivial vergleichbaren Objektes finden möchten, können wir einen kleinen Trick anwenden (welcher sich auf
__int128
ausweiten lässt):bool has_zero_byte(std::uint64_t v) { return (v - 0x0101010101010101ull) & ~v & 0x8080808080808080ull;} bool has_byte(std::uint64_t x, unsigned char n) { return has_zero_byte(x ^ (~0ull/255 * n));} /* Requires: - p is properly aligned for an object of type uint64_t, - p points to byte k of an object of size at least, k+sizeof(uint64_t), and - the sizeof(uint64_t) bytes starting at k contain a valid value representation for uint64_t. */ std::uint64_t qword_from( char const* p ) { return *std::launder(reinterpret_cast<std::uint64_t*>(p)); } char const* find_next(char const* s, std::size_t len, char c) { void* p = s; std::size_t space = len; if (auto p = std::align(alignof(std::uint64_t), len, &p, space)) // ... }
Ist IIRC nicht in Implementierungen gängig.
-
boost::split(vector<string>, str, boost::is_any_of(" "));
-
@Arcoth
Delim delim, Comp comp
=>
Pred pred
?
-
hustbaer schrieb:
@Arcoth
Delim delim, Comp comp
=>
Pred pred
?Die von mir aufgezeigte (ziemlich effektive) Optimierung kann so nicht durchgeführt werden, da das Prädikat bei trivialem Vergleich irgendein Lambda sein wird. Die Idee ist ja, dass wir die Signatur so allgemein halten wie möglich, ohne Effizienz für die beliebtesten Anwendungsfälle einzubüßen: Wenn
Comp
eine Spezialisierung vonequal_to
ist, und der Iterator ein Contiguous Iterator auf entsprechende Type, können wir die spezielle Implementierung anschmeißen.
-
Ah OK
Die Optimierung hab' ich beim Überfliegen gesehen, aber nicht genauer angegucktUnd... was genau macht
std::launder
?
Was ich meine mir dazu korrekt ergoogelt zu haben: Man kann damit Strict Aliasing aushebeln. Also memcpy() nen POD irgendwo hin und dann Zugriff überstd::launder
und kein Problem mehr mit Strict Aliasing.
Was mir aber nicht klar ist, ist ob es danach noch OK ist den selben Speicherbereich mit einem anderen Typ anzusprechen.In deinem Beispiel vermutlich wurscht, da der andere Typ
char
ist, und fürchar
gilt ja Strict Aliasing sowieso nicht. Aber was wenn man das selbe fürwchar_t
oderchar16_t
machen möchte?p.S.: Ich hab' mich schon gefragt ob ich der einzige bin der es beknackt findet dass es keine Strict Aliasing Umfahrungsstrasse in C++ gibt. Wobei ich dabei eher an spezielle Hilfsfunktionen wie dein
qword_from
gedacht hätte -- bloss halt als Template.
-
hustbaer schrieb:
Und... was genau macht
std::launder
?P0137 formalisiert den Begriff des Zeigens, nach welchem ein (gecasteter) Zeiger auf ein altes Objekt nicht verwendet werden darf, um auf ein neues Objekt neuen Typs zuzugreifen, das in der selben memory location residiert. Der Grund für diese Regelung liegt in einer Optimierung: Der Wert eines Zeigers kann zurückverfolgt werden, um ggf. zu folden. Der Optimizer wird versuchen, zu beweisen, dass der Wert des Pointees zwischenzeitlich nicht modifiziert wurde. Das kann nur durch bestimmte glvalues geschehen; im folgenden Beispiel ist das nicht der Fall:
int i = 0; int* p = &i; float* fp = (float*)p; new (fp) float(1); // fp darf i nicht aliasen, daher ist dies keine vom Optimizer registrierte Modifizierung int j = *p; // UB float f = *fp; // UB! f == 0 ist möglich
Nun scheint es, dass ich
launder
leider missverstanden habe - meine Anwendung ist nämlich völliger Unsinn: http://www.open-std.org/pipermail/ub/2016-February/000565.htmlDie korrekte Variante meiner Funktion ist der momentan undefinierte Einsatz von
memcpy
, der bald definiert wird:std::uint64_t qword_from( char const* p ) { std::uint64_t u; std::memcpy(&u, p, sizeof u); return u; }
(Generiert übrigens tatsächlich auch nur einen
movq
! Und führt in diesem Fall gar zu effizienterem Code, da es das Ausrichten überflüssig macht )Jacksonville ist gerade am Laufen (hat heute begonnen). Dos Reis wird dort am Dienstag eine verfeinerte Variante seines Papers N3751 vorstellen, welches die
memcpy
Regeln in [basic.types]/2 und /3 auf unterschiedliche Typen ausweitet. Das ist ein ziemlich wichtiger Schritt in die richtige Richtung.Was mir aber nicht klar ist, ist ob es danach noch OK ist den selben Speicherbereich mit einem anderen Typ anzusprechen.
Einen Speicherbereich mit einem vom aktuellen Objekt abweichenden Typen anzusprechen ist generell Blödsinn; siehe der verlinkte Thread. Es geht, bis auf wenige Ausnahmen (wie e.g. structs mit common initial sequences und die bekannten Alias ausnahmen), nicht gut, da TBAA da grundsätzlich Schwierigkeiten bereitet (und gleichzeitig unverzichtbar ist).
p.S.: Ich hab' mich schon gefragt ob ich der einzige bin der es beknackt findet dass es keine Strict Aliasing Umfahrungsstrasse in C++ gibt. Wobei ich dabei eher an spezielle Hilfsfunktionen wie dein
qword_from
gedacht hätte -- bloss halt als Template.Nein, ganz und gar nicht. Obiges kann man aber in ein Funktionstemplate auslagern. Womöglich kann da was standardisiert werden, ich schau nach Jacksonville nach.
-
Ach ja, und es sollte noch erwähnt werden, dass obiger Trick wahrscheinlich schon in ähnlicher Form in
strchr
eingebaut ist.