Prepend std::string

Question

What is the most efficient way to prepend std::string? Is it worth writing out an entire function to do so, or would it take only 1 - 2 lines? I'm not seeing anything related to an std::string::push_front.

Solution 1

There actually is a similar function to the non-existing std::string::push_front, see the below example.

---

Documentation of std::string::insert

#include <iostream>
#include <string>

int
main (int argc, char *argv[])
{
  std::string s1 (" world");
  std::string s2 ("ello");

  s1.insert (0,     s2); // insert the contents of s2 at offset 0 in s1
  s1.insert (0, 1, 'h'); // insert one (1) 'h'        at offset 0 in s1

  std::cout << s1 << std::endl;
}

output:

hello world

---

Since prepending a string with data might require both reallocation and copy/move of existing data you can get some performance benefits by getting rid of the reallocation part by using std::string::reserve (to allocate more memory before hand).

The copy/move of data is sadly quite inevitable, unless you define your own custom made class that acts like std::string that allocates a large buffer and places the first content in the center of this memory buffer.

Then you can both prepend and append data without reallocation and moving data, if the buffer is large enough that is. Copying from source to destination is still, obviously, required though.

---

If you have a buffer in which you know you will prepend data more often than you append a good alternative is to store the string backwards, and reversing it when needed (if that is more rare).

Solution 2

myString.insert(0, otherString);

Let the Standard Template Library writers worry about efficiency; make use of all their hours of work rather than re-programming the wheel.

This way does both of those.

As long as the STL implementation you are using was thought through you'll have efficient code. If you're using a badly written STL, you have bigger problems anyway :)

Solution 3

If you're using std::string::append, you should realize the following is equivalent:

std::string lhs1 = "hello ";
std::string lhs2 = "hello ";
std::string rhs = "world!";

lhs1.append(rhs);
lhs2 += rhs; // equivalent to above
// Also the same:
// lhs2 = lhs2 + rhs;

Similarly, a "prepend" would be equivalent to the following:

std::string result = "world";
result = "hello " + result;
// If prepend existed, this would be equivalent to
// result.prepend("hello");

You should note that it's rather inefficient to do the above though.

Solution 4

There is an overloaded string operator+ (char lhs, const string& rhs);, so you can just do your_string 'a' + your_string to mimic push_front.

This is not in-place but creates a new string, so don't expect it to be efficient, though. For a (probably) more efficient solution, use resize to gather space, std::copy_backward to shift the entire string back by one and insert the new character at the beginning.

View more solutions

Comments

[Mike Bailey]

Any reason you can't do something like s = a + s?

[Ankit]

What do u mean by prepend? Is it what @MikeBantegui has mentioned? or you are trying to do something else?

[GWW]

Prepending to a string is not going to be efficient, perhaps it may be better to append to the string and reverse it when you are finished?

[Lightness Races in Orbit]

@GWW: Is that really more efficient?

[Lightness Races in Orbit]

Do you mean prepend to a std::string? Then prepend what?

[GWW]

@TomalakGeret'kal: Every time you prepend I'm assuming the whole string has to be moved over using some sort of memcpy operation.

[Lightness Races in Orbit]

@GWW: Yea, probably; once. How's that worse than looping through the original string and copying data one byte at a time? I'm not aware of a low-level API function to reverse the data in a block of memory.

[GWW]

@TomalakGeret'kal: Sorry, I have explained myself poorly. I meant if the poster is repeatedly prepending to the string it may be more efficient to instead append and then reverse the string after all of the appends have finished.

[Lightness Races in Orbit]

@GWW: OK. It's still unlikely; you'd be better off knowing how many new characters you need, and just perform them all at the same time in a single string. Reversing is unlikely to give you anything. Especially since you'd have to pre-reverse the original string too.

[Filip Roséen - refp]

You should not use std::string::resize to "gather more space", the function will make the internal buffer bigger if required, that's true. But it will also pad the current string with char()'s (also known as NULL (ie. the value 0). See this codepad paste for a demonstration.

[Don Reba]

I also want to add that if you need to prepend a string with multiple items, you can avoid quadratic-time performance by first appending the items and then rotating them to the front using std::rotate from <algorithm>.

[Ben Voigt]

An inefficient algorithm can't be rescued by a smart implementation.

[underscore_d]

Does anyone know why this answer was downvoted? Are its claims incorrect somehow? What are we, readers 5 years in the future, meant to infer from unexplained downvotes? That helps no one. Can someone elaborate, at long last?

[amon]

@underscore_d As mentioned in another answer, using operator+ will have to create a copy of the string. In contrast, using insert() can operate in-place (well, after possibly reallocating the string buffer). This doesn't matter for these small examples, but it might matter for huge strings. With C++11, it is also possible to say "result = "hello " + std::move(result)` in order to avoid the copy.

[underscore_d]

@amon Thanks! That seems obvious now, after 2 years of further learning and you pointing it out, but it was still worth having actually stated. The move() trick is one that I use sometimes for convenience, but does C++ actually guarantee anywhere that will be optimised by using .insert(), or is that just something library implementors can do if they're clever? I assumed the latter.