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

Hallo,
ich suche nach dem effizientesten Weg, aus einem std::string der z.B. so aussieht:

a b  c   d e

einen std::string zu machen, der so aussieht:

a b c d e

Ich habe es zwar auch schon geschafft, nur ist meine Lösung so unglaublich langsam, dass ich mir denke, dass das niemals die Beste sein kann.
Bitte um Hilfe.
Danke!

Zeig mal deine Lösung

SeppJ

Eine sehr einfache Möglichkeit wäre es, einfach einen Stringstream und die Streamoperatoren zu benutzen. Das ist zwar sicherlich nicht die effizienteste Möglichkeit, aber es wird wird auch nicht spürbar langsam sein. Dafür braucht man sich aber wenig Gedanken um den eigentlichen Algorithmus machen, weil die Streamoperatoren alles für einen erledigen.

Michael E.

Ich denke, viel schneller als so wirst du es nicht hinbekommen:

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

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

int main()
{
	string foo = "a   b c  de  f";
	string::iterator newEnd = unique(foo.begin(), foo.end(), isDoubleSpace);
	foo.resize(newEnd - foo.begin());
	cout << foo;
}

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

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.

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

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

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.

Next Generation Hacker schrieb:

DAS ist am schnellsten
Viel Mist

In nem C++-Programm ein C-cast -> wenn dann const_cast!
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.
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() );
}

Release + Optimieruzngen kompilieren

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