Doppelte (bzw. mehrfach) Vorkommende Leerzeichen in std::string löschen?

[unskilled]

foo.resize(newEnd - foo.begin());
->
foo.erase(newEnd, foo.begin());
;o)

bb

[EOP]

while( str.find( "  " ) != string::npos )
	std::replace( str.begin(), str.end(), "  ", " " );

Ungetestet.

[Michael E.]

unskilled schrieb:

foo.resize(newEnd - foo.begin());
->
foo.erase(newEnd, foo.begin());
;o)

bb

Verdammt, das spart bei mir ne Abfrage

void __CLR_OR_THIS_CALL resize(size_type _Newsize, _Elem _Ch)
{	// determine new length, padding with _Ch elements as needed
	if (_Newsize <= _Mysize)
		erase(_Newsize);
	else
		append(_Newsize - _Mysize, _Ch);
}

Das fällt wohl noch unter "nicht viel schneller"

[Blue-Tiger]

Da koennt man sich auch 'ne kleine RegEx basteln, bin aber grad zu faul mich durch die API zu wuehlen.

[Blue-Tiger]

#include <iostream>
#include <boost/regex.hpp>
#include <string>

using namespace std;
using namespace boost;

int main()
{
	string s1 = "a b  c d     e  f  ";
	string s2 = regex_replace(s1, regex("\\s+"), " ");
	cout << s2 << endl;
	return 0;
}

[Blue-Tiger]

hmm.... die Regex-Variante ist langsamer als Michael E.'s Variante. (Die von EOP funktioniert nicht).

#include <iostream>
#include <string>
#include <vector>
#include <boost/regex.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/foreach.hpp>
#define foreach BOOST_FOREACH

using namespace std;
using namespace boost;

bool isDoubleSpace(char first, char second)
{
	return first == second && second == ' ';
}

double meth1(vector<string> str)
{
	double start = time(0);
	foreach(string& s, str)
	{
		string::iterator newEnd = unique(s.begin(), s.end(), isDoubleSpace);
		s.erase(newEnd, s.begin());
		if (rand() == 42)
			cout << s << '\n';
	}
	double end = time(0);
	return end - start;
}

double meth2(vector<string> const& str)
{
	double start = time(0);
	const regex r("\\s+", regex::optimize);
	const string space = " ";
	foreach(string& s, str)
	{
		string s2 = regex_replace(s, r, space);
		if (rand() == 42)
			cout << s2 << '\n';
	}
	double end = time(0);
	return end - start;
}

int main(int argc, char** argv)
{
	if (argc < 3)
	{
		cerr << "usage: test stringlength nstrings [space-prob]\n";
		return 1;
	}

	unsigned strlen = lexical_cast<unsigned>(argv[1]);
	unsigned nstrings = lexical_cast<unsigned>(argv[2]);
	double space_prob = (argc == 4) ? lexical_cast<double>(argv[3]) : 0.5;

	vector<string> str;
	str.reserve(nstrings);
	for (unsigned i = 0; i < nstrings; ++i)
	{
		string tmp(strlen, 'a');
		for (unsigned j = 0; j < strlen; ++j)
		{
			if (rand() / (double) RAND_MAX < space_prob)
				tmp[j] = ' ';
		}
		str.push_back(tmp);
	}

	cout << "method 1: " << meth1(str) << '\n';
	cout << "method 2: " << meth2(str) << '\n';
	return 0;
}

tom@blulap:~$ g++ test.cpp -o test -lboost_regex -O2 -DNDEBUG
tom@blulap:~$ ./test 100 1000000
method 1: 3
method 2: 38
tom@blulap:~$ ./test 100 1000000 0.1
method 1: 2
method 2: 24
tom@blulap:~$ ./test 100 1000000 0.9
method 1: 2
method 2: 15
tom@blulap:~$ ./test 200 1000000 0.9
method 1: 10
method 2: 27

[Noob Otto]

Wow, ich hätte wirklich nicht gedacht, dass ein Gast so viele Antworten bekommt! Danke schon einmal bis hierhin! Auch wenn es ein wenig unfair den anderen gegenüber ist, danke ich Blue-Tiger für das Benchmark ganz besonders!

Mein Lösungsweg sah so aus:

//...
while((uiPosTemp = stTest.find(' ', uiPosTemp + 1)) != std::string::npos)
  stTest.replace(uiPosTemp, stTest.find_first_not_of(' ', uiPosTemp) - uiPosTemp, " ");
//...

Wie geschrieben, der tut's auch, ist aber unglaublich langsam und bremst das gesamte restliche Programm aus.

[Noob Otto]

Noch einmal wow, die Funktion von Michael E. ist weitaus schneller als meine eigene. Vielen, vielen Dank euch allen!!!

[Noob Otto]

... oder doch nicht? Wenn ich das, was Michael E. geschrieben hat, in eine Funktion packe und dann mit meiner Funktion vergleiche, ist meine schneller. Ich verstehe die Welt nicht mehr!

[EOP]

Diesmal etwas, das funktioniert:

string str = "a  b    c     d e  f   g  ";
size_t pos = 0;

while( (pos = str.find( "  ", pos )) != string::npos )
	str.erase( pos, 1 );

[SeppJ]

Zeig doch mal, wie du deine Zeitmessungen machst.

[Next Generation Hacker]

Noob Otto schrieb:

... oder doch nicht? Wenn ich das, was Michael E. geschrieben hat, in eine Funktion packe und dann mit meiner Funktion vergleiche, ist meine schneller. Ich verstehe die Welt nicht mehr!

DAS ist am schnellsten

#include <iostream>
#include <string>
using namespace std;

void remove_spc (char *s) {
   char *t = s;
   char l = 0;
   while (*s) {
      if (*s != ' ' || l != ' ')
         *t++ = *s;
      l = *s++;
   }
   *t = 0;
}

int main (void)  {
   string a = "a  b    c     d e  f   g  ";
   char *p = (char*)a.c_str();
   remove_spc (p);
   a = p;
   cout << a;
}

[Michael E.]

Da wäre ich wirklich mal auf ein Benchmark gespannt Denn mein Code macht im Prinzip nichts anderes, aber ich denke, die Standardalgorithmen werden sehr gut auf den jeweiligen Compiler hinoptimiert sein.

[nervösling]

Next Generation Hacker schrieb:

DAS ist am schnellsten

Viel Mist

1. In nem C++-Programm ein C-cast -> wenn dann const_cast!
2. Ist das echt böse! Du verändeeerst einen (nicht zu Unrecht) privaten Member, ohne auf andere Spezialitäten Rücksicht zu nehmen. z.B.
3. Du veränderst die Länge des strings!!! Woher weißt du, dass nicht intern eine Länge mitgespeichert wird?!?

Du machst zwar später eine Zuweisung - aber muss ja nicht immer hinhauen...
Lass die string-Klasse implizit geshared sein (k.A. wie der deutsche Begriff dafür ist...).
Da wird der data-pointer einfach ins neue Objekt gesetzt, eine Kopie des Arrays findet erst satt, wenn das Objekt über die public-Funktionen verändert wird. Deine Methode verhindert ein korrektes Handling dieses Mechanismus!!!

doIt( const std::string& str) {
    boeseFktDieStrAendert( (char*)str.c_str() );
}

[WelcomeToTheJungle]

Release + Optimieruzngen kompilieren

[Next Generation Hacker]

Michael E. schrieb:

Da wäre ich wirklich mal auf ein Benchmark gespannt

#include <iostream>
#include <string>
#include <algorithm>
#include <windows.h>
using namespace std;

void remove_spc (char *s) {
   char *t = s;
   char l = 0;
   while (*s) {
      if (*s != ' ' || l != ' ')
         *t++ = *s;
      l = *s++;
   }
   *t = 0;
}

char *hacker()  {
   static char a[100];
   strcpy (a, "a  b    c     d e  f   g  ");
   remove_spc (a);
   return a;
}

bool isDoubleSpace(char first, char second)
{
    return first == second && second == ' ';
}

string michael()
{
    string foo = "a  b    c     d e  f   g  ";
    string::iterator newEnd = unique(foo.begin(), foo.end(), isDoubleSpace);
    foo.resize(newEnd - foo.begin());
    return foo;
}

int main () {
   UINT32 t1, t2;
#define COUNT 1000000   

   t1 = GetTickCount();
   for (int s=0; s<COUNT; s++)
      hacker();
   t1 = GetTickCount() - t1;

   t2 = GetTickCount();
   for (int s=0; s<COUNT; s++)
      michael();
   t2 = GetTickCount() - t2;

   cout << t1 << endl;
   cout << t2 << endl;
}

Visual Studio, Release:
Hacker 141 ms
Michael 780 ms

Visual Studio, Debug:
Hacker 858 ms
Michael 26364 ms

[freaky]

Next Generation Hacker schrieb:

Visual Studio, Debug:
Hacker 858 ms
Michael 26364 ms

26Sekunden? Was hast du solange im Debug getrieben?

[volkard]

Iteratorchecks auch im Release ausmachen.

[Michael E.]

Na wir wollen doch fair bleiben und deiner Version auch mal das Erzeugen eines std::strings beibringen (so wie es gefordert war):

#include <iostream>
#include <string>
#include <algorithm>
#include <windows.h>
using namespace std;

void remove_spc (char *s) {
   char *t = s;
   char l = 0;
   while (*s) {
      if (*s != ' ' || l != ' ')
         *t++ = *s;
      l = *s++;
   }
   *t = 0;
}

string hacker()  {
	string a = "a  b    c     d e  f   g  ";
	char* p = (char*)a.c_str();
   remove_spc (p);
   a = p;
   return a;
}

bool isDoubleSpace(char first, char second)
{
    return first == second && second == ' ';
}

string michael()
{
    string foo = "a  b    c     d e  f   g  ";
    string::iterator newEnd = unique(foo.begin(), foo.end(), isDoubleSpace);
    foo.resize(newEnd - foo.begin());
    return foo;
}

int main () {
   UINT32 t1, t2;
#define COUNT 1000000  

   t1 = GetTickCount();
   for (int s=0; s<COUNT; s++)
      hacker();
   t1 = GetTickCount() - t1;

   t2 = GetTickCount();
   for (int s=0; s<COUNT; s++)
      michael();
   t2 = GetTickCount() - t2;

   cout << t1 << endl;
   cout << t2 << endl;
}

Ergebnis (VS 2008 Release, volle Optimierung):
687 (deins) gegen 579 (meins)

[Next Generation Hacker]

Michael E. schrieb:

Na wir wollen doch fair bleiben und deiner Version auch mal das Erzeugen eines std::strings beibringen (so wie es gefordert war):
...
Ergebnis (VS 2008 Release, volle Optimierung):
687 (deins) gegen 579 (meins)

Und die Moral von der Geschicht: Wenns schnell sein soll, nimm std::string nicht.