I have searched different ways of concatenating strings in C++ and I found std::stringstream and std::string as possible options. However, I could not find a time complexity for the concatenation operations for both stringstream and string. What is the time complexity of string concatenation in C++. Moreover, what are the time complexities for converting to string in both std::stringstream and std::string in C++. Is it possible to append strings in 0(1) time in C++? Thank you for your time.

  • 2
    The 'time-complexities' are of the same order O(N). But adding two std::string objects together will be a great deal faster than using std::stringstream. – Richard Hodges Jul 30 '17 at 11:53
  • Think about it: you can't go sub-linear because of copying required; it goes one char at a time. You cannot also go super-linear, because there are no nested loops during concatenation. Hence, O(n+m) is the only thing that's left. – dasblinkenlight Jul 30 '17 at 11:54
  • std::stringstream however is much better at converting to strings right? – Vishwa Patel Jul 30 '17 at 11:55
  • Converting a string to a string? – user2672107 Jul 30 '17 at 12:03
  • no so if I have an int then is a std::stringstream better at converting the int to a string or not? – Vishwa Patel Jul 30 '17 at 12:05

Both are unspecified, but you can guess at linear complexity (create new buffer, copy the chars to the new buffer).

  • No but in C++ you can just append to both std::string and std::stringstream so in that case would it still be linear complexity? – Vishwa Patel Jul 30 '17 at 11:57
  • @VishwaPatel yes. Both are doing almost the same thing, probably the stringstream needs 2 copies but it's still linear time. – amchacon Jul 30 '17 at 11:59
  • So would it be efficient to use std::string for appending and std::stringstream for converting to strings? – Vishwa Patel Jul 30 '17 at 12:02
  • @VishwaPatel std::string to appending string-string and std::stringstream for "complex" appends (like string-integer, string-float). – amchacon Jul 30 '17 at 12:04
  • Thanks a lot @amchacon – Vishwa Patel Jul 30 '17 at 12:05

Your Answer

