Рассмотрим этот фрагмент кода:
public String joinWords(String[] words) {
String sentence = "";
for(String w : words) {
sentence = sentence + w;
}
return sentence;
}
При каждой конкатенации создается новая копия строки, так что общая сложность O(n^2)
. К счастью, в Java мы могли бы решить это с помощью StringBuffer
, которая имеет сложность O(1)
для каждого добавления, тогда общая сложность будет O(n)
.
Пока в С++, std::string::append()
имеет сложность O(n)
, и я не понимаю сложность stringstream
.
В С++ существуют ли методы типа StringBuffer
с такой же сложностью?