String concatenation complexity in C++ and Java [duplicate]

Question

Consider this piece of code:

public String joinWords(String[] words) {     String sentence = "";     for(String w : words) {         sentence = sentence + w;     }     return sentence; } 

On each concatenation a new copy of the string is created, so that the overall complexity is O(n^2). Fortunately in Java we could solve this with a StringBuffer, which has O(1) complexity for each append, then the overall complexity would be O(n).

While in C++, std::string::append() has complexity of O(n), and I'm not clear about the complexity of stringstream.

In C++, are there methods like those in StringBuffer with the same complexity?

Answer 1

C++ strings are mutable, and pretty much as dynamically sizable as a StringBuffer. Unlike its equivalent in Java, this code wouldn't create a new string each time; it just appends to the current one.

std::string joinWords(std::vector<std::string> const &words) {     std::string result;     for (auto &word : words) {         result += word;     }     return result; } 

This runs in linear time if you reserve the size you'll need beforehand. The question is whether looping over the vector to get sizes would be slower than letting the string auto-resize. That, i couldn't tell you. Time it. :)

If you don't want to use std::string itself for some reason (and you should consider it; it's a perfectly respectable class), C++ also has string streams.

#include <sstream> ...  std::string joinWords(std::vector<std::string> const &words) {     std::ostringstream oss;     for (auto &word : words) {         oss << word;     }     return oss.str(); } 

It's probably not any more efficient than using std::string, but it's a bit more flexible in other cases -- you can stringify just about any primitive type with it, as well as any type that has specified an operator <<(ostream&, its_type&) override.