Appending in front vs back of a string in C++

Question

In C++ vectors push_back() takes constant time, where as push_front() takes linear time. In regards to that I have some confusion regarding strings.

let string a be of length n and string b be of length m. Then what will be the time complexity of following operations :

1. a += b
2. a = b + a
3. a += 'x'
4. a = 'x' + a

according to my undersanding 1 and 3 should have constant time complexity.

Answer 1

Hmm...this seems to have a few problems.

std::vector has a push_back (which has amortized constant complexity), but doesn't have a push_front at all. std::list and std::deque both provide push_front, but for them it's constant complexity. You can add an item at the beginning of a vector using insert, which does have linear complexity though.

Getting to your individual examples (all relating to strings, not vectors):

a += b

I'd normally expect this to be O(m). C++ guarantees that strings are contiguous, so we need to copy the contents of b to the end of the previous contents of a.

If the string has to be reallocated, I'd expect to see amortized constant complexity, much like vector guarantees, but to the best of my recollection std::string doesn't actually require it.

a = b + a

I'd expect this to be O(n + m). It basically creates a new (temporary) string holding the contents of b followed by the contents of a, then assigns that temporary to a.

a += 'a'

I'd expect this to have amortized constant complexity, but (as outlined above) I don't believe it's guaranteed.

a = 'x' + a

I'd expect this to be linear on the length of a.