2
{
   std::string s = "this is a string ";
   std::string res = std::string();
   int sLength = s.length();
   for(int i = 0; i < sLength; i++)
      res += s[i];
}

I would imagine this C++ is strictly linear in complexity (with regard to character allocation), as opposed to the quadratic complexity of the equivalent in C#.

However, the fact that in this case, memory is not allocated beforehand, are we actually looking at quadratic complexity as well ? If yes, would allocation of a char array help us to achieve linear complexity ?

7
  • 1
    I'm not sure I understand your question? Are you under the impression that each concatenation will force another allocation of size = previous_size + 1? That isn't how it works. May 22, 2015 at 14:40
  • 1. StringBuilder. 2. in C# this would take the same amount of memory. The GC will eat up all the extra alocations
    – AK_
    May 22, 2015 at 14:42
  • @CoryKramer I considered it as a possibility at least.
    – BuZz
    May 22, 2015 at 14:43
  • @AK_ so you're saying both C++ and C# implementation of this will be quadratic.
    – BuZz
    May 22, 2015 at 14:44
  • @Franklin No. both would be linear. for different reasons.
    – AK_
    May 22, 2015 at 14:45

2 Answers 2

2

You could achieve linear complexity by calling std::string::reserve. This would prevent re-allocations as the string grows:

std::string s = "this is a string ";
std::string res = "what is this? ";
res.reserve(s.length() + res.length());

for(int i = 0; i < s.length(); i++)
   res += s[i];

Obviously you wouldn't concatenate strings like that in real life.

1

According to cppr, adding a character to a string has constant complexity (although I think this carries an implicit "amortized", as for string::push_back).

So your code already has linear complexity.

If you care about the allocation cost and have an upper bound for the size beforehand, you can also just reserve enough space to avoid any reallocation and copying of the string. Then, not even a plain char buffer should beat your performance (significantly).

2
  • +1 ; thanks. so while both with/without "reserve" provide linear complexity, "reserve" would show a tiny practical improvement.
    – BuZz
    May 22, 2015 at 14:55
  • @Franklin If tiny or not is subject to measurement, but the complexity is the same.
    – Baum mit Augen
    May 22, 2015 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.