Re: perl-like string concatenation
* Christof Warlich:
Alf P. Steinbach schrieb:
*However*, adopting string concatenation as an idiomatic way to build
strings is IMHO ungood because it easily leads to O(n^2) behavior,
e.g. for adding in things in a loop.
Instead I prefer to overload operator <<, C++ "output", to a string,
modifying the string. This works well even with a temporary e.g.
foo( string().append("") << blah << 42 << gnurk );
and if that first sub-expression is defined as a macro TEMP_STR
foo( TEMP_STR << blah << 42 << gnurk );
and even better if it's defined as three- or four-line class
foo( TempStr() << blah << 42 << gnurk );
without the O(n^2) behavior so common in scripting languages.
Did I get you right that you are suggesting something like this, i.e
returning a reference to a string instead:?
template<typename T> string &operator<<(string &x, T y) {
ostringstream tmp;
tmp << x << y;
x = tmp.str();
return x;
}
Not quite.
You have to specialize for various types, especially char const*.
Otherwise you're incurring a heck of an overhead of the ordinary sort, as you're
doing.
And you have to absolutely avoid copying the lhs string, otherwise you're
incurring the O(n^2) algorithmic overhead, which you're also doing, which means
that this implementation is not just inefficient but /incorrect/ wrt. to goal.
But apart from the extreme inefficiency of that concrete implementation, and
apart from it's incorrectness, then yes, sort of. :-)
It avoids creating a new string over and over again when being used in a
loop, so it should run faster. But a quick test did not show a big
difference:
#include <string>
#include <iostream>
#include <sstream>
using namespace std;
template<typename T> string &operator<<(string &x, T y) {
ostringstream tmp;
tmp << x << y;
x = tmp.str();
return x;
}
template<typename T> string operator&(const string &x, T y) {
ostringstream tmp;
tmp << x << y;
return tmp.str();
}
int main(void) {
int i;
string tmp;
for(i = 0; i < 30000; i++) {
tmp = tmp << i << ";";
This should just be
tmp << i << ";".
}
cout << tmp << endl;
tmp = string();
for(i = 0; i < 30000; i++) {
tmp = tmp & i & ";";
}
cout << tmp << endl;
return 0;
}
Compiled with gcc, both loops seem to run more or less equally long.
See above.
I leave re-testing with that fix (removing incorrect usage), plus a fix of the
earlier mentioned incorrectness of operator<< implementation, to you. ;-)
And my first solution had the advantage that the source string remains
unmodified.
That's not an advantage, it's a disadvantage. With the "&" operator above you
don't have a choice about whether to create a new string or not, you always have
to create a new string. With the "<<" above the client code can choose in each
case -- and as mentioned, when it's used correctly it avoids that dreaded
O(n^2) behavior (there's no way to guard against silly client code, though).
Cheers & hth.,
- Alf
--
Due to hosting requirements I need visits to <url: http://alfps.izfree.com/>.
No ads, and there is some C++ stuff! :-) Just going there is good. Linking
to it is even better! Thanks in advance!