As I know that C++ only allows to add 2 strings together, i.e: s = s1 + s2
But I want to be able to add many strings together like:
s = s1 + s2 + s3 + s4 + .... + sn
How could I solve this problem? Can anybody help?
Thanks.
Why allocate a vector for the strings when they already exist in separate instances?
Billy ONeal
2010-02-20 03:23:18
@BillyONeal: Do they? Or is the OP getting them from some other source as `char*` and will also have to convert them?
Ignacio Vazquez-Abrams
2010-02-20 03:24:35
It doesn't matter, assuming one of the items is the standard string class. Operator + is defined for that class in both directions. I'm assuming that the OP isn't trying to sum up char * strings because then the simple case of s = s1 + s2 would also be invalid.
Billy ONeal
2010-02-20 03:27:32
+7
A:
First of all, you can do the +sn thing just fine. Though it's going to take exponential quadradic(see comments) time assuming you're using std::basic_string<t> strings on C++03.
You can use the std::basic_string<t>::append in concert with std::basic_string<t>::reserve to concatenate your string in O(n) time.
EDIT: For example
string a;
//either
a.append(s1).append(s2).append(s3);
//or
a.append("I'm a string!").append("I am another string!");
Billy ONeal
2010-02-20 03:21:57
It's not going to take exponential time, only quadratic. `append` will be faster, but in general quadratic anyway because it needs to reallocate form time to time. In the very most cases both methods won't be slow enough to be noticeable, though.
sth
2010-02-20 03:49:19
No, it is actually exponential, as R Samuel Klatchko's answer demonstrates. You add s1 and s2 together, then add the result to s3, then add the result to s4... etc. Each add adds the complete length of all the strings previous in the sequence. Therefore, given K strings of length N, you will have Sum_{i = 1}^{K}(Sum_{j=1}^{i - 1}(N) + N) which is exponential. `std::basic_string<t>::append` is linear if used with `std::basic_string<t>::reserve` as stated in my answer, because `std::basic_string<t>::reserve` guarantees no reallocation.
Billy ONeal
2010-02-20 04:00:44
Note: It's quadradic with respect to K in my above example, but exponential with respect to N, so we are both correct here if you look at the problem another way.
Billy ONeal
2010-02-20 04:15:01
@BillyONeal: Why would that be exponential? The sum you mention is equal to `(0*N + N) + (1*N + N) + (2*N + N) + ... + ((K-1)*N + N)` which equals `(1+2+...+(K-1)) * N + K*N` = `(K*(K-1)/2) * N + K*N` = `((K^2 + K) / 2) * N` = `O(K^2 * N)`. So it is quadratic in the number of parts `K`. In the number of characters in each part, `N`, it is linear.
sth
2010-02-20 04:16:02
About `append()`: I seem to have missed that you mentioned `reserve()`. Used with `reserve()` it is indeed linear.
sth
2010-02-20 04:23:00
OK. You win. Bill opens mouth, Bill inserts foot. Bill must go find where he read exponential time and never believe advice from said source again.
Billy ONeal
2010-02-20 04:45:23
@sth Even without reserving enough space, `append` takes linear amortized time which is way faster than quadratic
FredOverflow
2010-02-20 17:59:26
+2
A:
If your trying to append string objects of std::string class, this should work.
string s1 = "string1"; string s2 = "string2"; string s3 = "string3";
string s = s1 + s2 + s3;
OR
string s = string("s1") + string("s2") + string("s3") ...
Dave18
2010-02-20 03:27:14
+1 - Just keep in mind when you use `operator+(std::basic_string<t>, std::basic_string<t>)` you will incur exponential time in C++03. Using the `std::basic_string<t>::append` member function takes only linear time in comparison.
Billy ONeal
2010-02-20 03:28:54
I think string s = string("s1") + string("s2") + string("s3") ... is something that I'm looking for. I wonder why it works?
tsubasa
2010-02-20 03:46:05
Because you are when you use string(x), you invoke a constructor for the standard string class on x. You create a temporary string object which can then participate with it's operator+. (This sort-of works like a form of cast)
Billy ONeal
2010-02-20 03:53:08
@tsubasa: It's also enough if you just make sure the first item is a `string`, so `string("s1") + "s2" + "s3"` will also work. The reason is that normal string constants like `"s1"` are of type `const char*`, and you can't just add such pointers together. `string` objects on the other hand know how to add a `const char*` to form a new `string`. (Also: Nothing will use exponential time here, so don't worry too much about that)
sth
2010-02-20 03:54:51
@BillyONeal: are you sure it's exponential time? Look O(N^2) to me.
Steve Jessop
2010-02-20 11:44:51
@Steve: Yes, my bad, see comments on my answer. It won't let me edit that comment here. Not that quadratic time is a good thing here either.
Billy ONeal
2010-02-20 17:15:20
+3
A:
s = s1 + s2 + s3 + .. + sn;
will work although it could create a lot of temporaries (a good optimizing compiler should help) because it will effectively be interpreted as:
string tmp1 = s1 + s2;
string tmp2 = tmp1 + s3;
string tmp3 = tmp2 + s4;
...
s = tmpn + sn;
An alternate way that is guaranteed not to create temporaries is:
s = s1;
s += s2;
s += s3;
...
s += sn;
R Samuel Klatchko
2010-02-20 03:28:14
Martin York
2010-02-20 18:10:58
+2
A:
std::ostringstream is build for that, see example here. It's easy:
std::ostringstream out;
out << "a" << "b" << "c" << .... << "z";
std::string str( out.str());
Nikolai N Fetissov
2010-02-20 03:48:47
I would point out that using stringstream for appending strings is slower than just appending to a string. stringstream is great for converting things to strings, but if all you're doing is constructing strings from strings, then it's the less efficient way to do it. append() and += are the way to go.
Jonathan M Davis
2010-02-20 05:44:23
Actually, I wrote a test program for it recently and found that it took about 2 1/2 times as long to put strings together with stringstream than appending directly to a string - and that's _without_ getting the string out of the stringstream when you're done. That particular figure likely isn't generally accurate with varying circumstances and all that, but it was quite clear that constructing streams with stringstream is significantly slower than just appending to a string.
Jonathan M Davis
2010-02-20 11:08:07
Well I did some tests and found that though slightly slower, it was only 20% slower. Taking a string and adding 10 string with 10 characters onto it. Reset and repeat this a million times. The difference is 2 seconds (on my machine). Hardly even worth noticing as any processor stalls will knock that difference away immediately. The win for me on this is the lower overhead on the memory management system. Less calls to allocate space as the string stream has a relatively large buffer.
Martin York
2010-02-20 18:21:44
This is probably due to a particular implementation of internal string buffer management (exponential growth?) and string stream buffer management. Neither are guaranteed to behave one way or the other.
Nikolai N Fetissov
2010-02-20 20:42:52
@Nikolai True. If you really care and you want to be sure of which is faster for what you're doing, you need to profile it for the particular program that you're working on with the particular implementation that you're using. However, the general indications are that stringstream is likely to be slower, so I'd say to use string's append() or += unless you need stringstream for its particular abilities, or you really care about performance and have profiled your code and found that stringstream is better in your particular case.
Jonathan M Davis
2010-02-20 23:49:31