3. Zeichenkette unterteilen

Zeichenkette unterteilen

  • X

    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 ?

    0 

  • #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;
}
    0
  • Mod

    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.

    0
  • W

    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

    0
  • X

    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 👍

    0

  • 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? )

    0
  • Mod

    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.

    0
  • ?
     

    boost::split(vector<string>, str, boost::is_any_of(" "));
    0

  • @Arcoth
    Delim delim, Comp comp
    =>
    Pred pred
    ?

    0
  • Mod

    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 von equal_to ist, und der Iterator ein Contiguous Iterator auf entsprechende Type, können wir die spezielle Implementierung anschmeißen.

    0

  • Ah OK 💡
    Die Optimierung hab' ich beim Überfliegen gesehen, aber nicht genauer angeguckt 🙂

    Und... 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 über std::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ür char gilt ja Strict Aliasing sowieso nicht. Aber was wenn man das selbe für wchar_t oder char16_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.

    0
  • Mod

    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.html

    Die 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.

    0
  • Mod

    Ach ja, und es sollte noch erwähnt werden, dass obiger Trick wahrscheinlich schon in ähnlicher Form in strchr eingebaut ist.

    0
Anmelden zum Antworten