0

In Python, we can use ''.join() to concatenate a list of strings in O(n) time. Is there something similar in C++? If I was to use += to append, it could take up to O(n^2) time.

Remy Lebeau
  • 555,201
  • 31
  • 458
  • 770
Bjorn Lom
  • 1
  • 1
    In a word, no. C++ does not have a direct equivalent of `join()`, but it would not be difficult to code up something yourself manually, or else find an existing 3rd party implementation. – Remy Lebeau Oct 09 '21 at 01:25
  • 1
    If you look up "c++ join vector of strings" or "c++ join array of strings" you'll find some examples of how to implement it. – lurker Oct 09 '21 at 01:27
  • 1
    An important note is that C++ strings are mutable, and they provide a `reserve()` function in their interface to request increases in capacity. If sufficient memory is reserved, appending / concatenating can be done in linear time. Of course, this requires computing the amount of memory which needs to be reserved, which could end up being slower than just letting it auto-resize (if you're concerned, you should time it). – Alexander Guyer Oct 09 '21 at 01:32
  • @RemyLebeau how would I go about coding it up manually to be done in O(n)? – Bjorn Lom Oct 09 '21 at 01:35
  • Step 1: add up the sizes of the individual strings, Step 2: `reserve` enough space in the result string, Step 3: concatenate all the individual strings into the result string, Step 4: ???, Step 5: Profit. – Eljay Oct 09 '21 at 01:39
  • 1
    Does this answer your question? [String concatenation complexity in C++ and Java](https://stackoverflow.com/questions/15400508/string-concatenation-complexity-in-c-and-java) – Chris Oct 09 '21 at 01:42
  • When you use `+=`, if the `std::string` being appended to doesn't currently have sufficient capacity, it will tend to resize to at least double the capacity. Consequently, by the end of the appending, about half the text will have been copied zero or one times during resizing, a quarter one or two times, an eight two or three times, and so on - the average of 1/2*1 + 1/4*2 + 1/8*3 is constant, so the total time taken is O(n). See https://coliru.stacked-crooked.com/a/7b05189262597173 – Tony Delroy Oct 09 '21 at 01:48

0 Answers0