Concatenation of Strings C++

I recently came to know that the operator+ is overloaded in c++ to concatenate two strings but it is highly inefficient(Complexity: linear in terms of resulting string). I searched about it but could only found either the use of Ropes or operator +=. Is there any other way of joining two strings efficiently in C++ other than these 2?

1 Like

I am not very proficient in C++ , but I know that in C++ , strings are basically character arrays , thus when concatenating , all the characters of the second string would have to be copied over , making it O(N)

To make it O(1) , for storing strings simply use a linked list of characters and maintain variables for the start and end node of each linked list.

When concatenating , just join the start node of second string to the end node of first string , and call it a new string

I don’t know whether there is any library that has this implemented, although it should be pretty easy to implement by hand too

I hope I was of help :slight_smile:

your idea is good but there exists a ds called ropes which also do string concatenation very fast and there is internal library implementing that i was just refraining from studying ropes hoping that may be there is some other way to :slight_smile:

probably you are getting T.L.E in the 4th question of oct17 :stuck_out_tongue:

actually i was trying to submit for first subtask and + resulted a TLE for even first subtask and after changing it i got AC for 1st subtask

I Think How to rmove TLE for a live contest should not be discussed here .