What is the fastest way to reverse a c-string, in place in c++?

Question

What's the fastest way to reverse a c-string, in place in c++ using only the library? In particular, are there any methods that require less than O(strlen) time?

since you have to move (and therefore read) all chars (except possibly one), how could it not be O(strlen)? — Mitch Wheat, Feb 05 '13 at 02:16
There's a [question on SO](http://stackoverflow.com/questions/14664510/access-violation-writing-location) which shows some C++ code for reversing a C string in situ. Just don't call the function with a string literal, that's all. — Jonathan Leffler, Feb 05 '13 at 02:19
Is there a need to reverse a C-string besides programming projects? — Thomas Matthews, Feb 05 '13 at 02:20
Yes: `std::string str = "my string"; auto reversed = str.rbegin();` It's O(1)!!!1 — Seth Carnegie, Feb 05 '13 at 02:21
If a `reverse_iterator` is an acceptable result, and the length happens to be known beforehand, you can do it in O(1). Otherwise, this is nonsense. — Potatoswatter, Feb 05 '13 at 02:22
@Seth, useful to know but that's actually not a C string :-) — paxdiablo, Feb 05 '13 at 02:22
@paxdiablo You're right. We should start calling C-strings "badstrings" to stigmatise people who use them. The idea is sound though, since `string` is just a wrapper around a C-string. — Seth Carnegie, Feb 05 '13 at 02:26
Related: http://stackoverflow.com/questions/2197412/reverse-c-style-string-c, http://stackoverflow.com/questions/198199/how-do-you-reverse-a-string-in-place-in-c-or-c — jogojapan, Feb 05 '13 at 04:20

score 5 · Answer 1 · answered Feb 05 '13 at 02:16

5

There cannot possibly be a method to reverse a string of length n in less than O(n) time. By definition of "reversing", every character has to be read at least once.

answered Feb 05 '13 at 02:16

us2012

16,083
3
46
62

2

Well, not a nice way that's compatible with normal C strings, but you could create a special String class that has an isReversed flag and keeps pointers to both ends of the string. Then add string operations which could check the flag and decide which bytes to work with. – MindJuice Feb 12 '14 at 22:29

score 3 · Answer 2 · answered Feb 05 '13 at 02:17

3

I doubt it's possible with less than O(N) complexity. Given how C strings are defined (NUL terminated) you can't even find the final element of the string with less than O(N) complexity, so it's hard to imagine actually doing anything with it with lower complexity.

As far as how you do it, the usual is to swap the first element with the last, second with second to last, and so on.

To achieve something faster than linear, you'll probably need to start by storing the length of the string. Then instead of actually reversing it at all, you'd (for example) set a flag to specify starting from the end. This would allow constant complexity "reversal". This is fairly easy to manage in C++, where you can "protect" the storage, and overload operators to provide access in the direction you want.

answered Feb 05 '13 at 02:17

Jerry Coffin

476,176
80
629
1,111

Can you explain on how you get sublinear complexity with your method? OP's requirement was "reverse the string in place". Even if he doesn't necessarily need to overwrite the old string with the reverse, but just 'extract' the reverse, it will be `O(N)`. The only possibility for going sublinear that I see is if you only need the last `k` characters, in which case you can go `O(k)` if you know the length in advance. – us2012 Feb 05 '13 at 02:23
@us2012: He is describing a reverse iterator. – jxh Feb 05 '13 at 02:25
1

And what I'm trying to say is that while a reverse iterator can be acquired in `O(1)`, you haven't done anything useful once you've acquired it. To do stuff with your required output (the reversed string), you have to in/decrement it and read the characters. I feel that selling this solution as `O(1) string reversal` is creative marketing at least :) – us2012 Feb 05 '13 at 02:27
@us2012 to do anything useful with a string that really has been reversed, you must also in/decrement it and read the characters. There's no difference except one is faster. – Seth Carnegie Feb 05 '13 at 02:30
@Seth True, but doesn't change overall complexity. All I'm trying to say is that *to do anything useful with it, complexity will be linear*. – us2012 Feb 05 '13 at 02:38
@us2012 except If you reverse it and then use it, you're multiplying your work by a factor of two, iterating the string twice instead of once. Using a reverse iterator is exactly the same as passing a pointer to the end of the string and changing every `++` or `+=` to a `--` or `-=` in the algorithm magically without modifying the code. It's as efficient as _not reversing it_, except you have to get a pointer to the end. – Seth Carnegie Feb 05 '13 at 02:39
@Seth I know. I think we're just talking about different things. I am only trying to address the issue of the complexity of the algorithm, and a factor of two on top of an `O(n)` algorithm doesn't change it, it's still `O(n)`. – us2012 Feb 05 '13 at 02:43
@us2012 yeah definitely, I think we are on different tracks, English is a complicated language. I was just meaning that in real life, the coefficient of `n` does matter, so that while 2n and 10^50n are both O(n), I'd rather use the former in my code. – Seth Carnegie Feb 05 '13 at 02:46
@us2012 wait, are we talking about the complexity of the reversal of the string? If so, the reverse iterator is O(1) and the real reversal is O(n), no? – Seth Carnegie Feb 05 '13 at 02:47
@Seth Yes. That is all I have been trying to say: Getting the iterator O(1), actually doing something with the reversal O(n). I apologize if my slightly convoluted way of phrasing it caused all this confusion. Btw, +1 for Jerry's answer as the reverse iterator is obviously a very useful tool in the real world. – us2012 Feb 05 '13 at 02:49

paxdiablo · Answer 3 · 2013-02-05T02:33:38.793

3

There's no way to do it in better than O(n) time since you have to touch each character at least once.

So something like:

void reverseString (char *s) {
    char t, *d = &(s[strlen (s) - 1]);
    while (d > s) {
        t = *s;
        *s++ = *d;
        *d-- = t;
    }
}

is probably about as efficient as you're going to get in standard C++.

Now there are ways to improve this if you're allowed to impose extra information, to the point where you could amortise the cost to less than O(n), depending on your access patterns.

By that, I mean keep a reversed string and dirty flag along with the original string.

if you try to access the reversed string when the flag is dirty, calculate the reversal, set the flag to clean and return the calculated/stored reversal. Cost is O(n).
if you try to access the reversed string when the flag is clean, just return the calculated/stored reversal. Cost is O(1).
if you ever change the original string, set the flag to dirty. Cost is O(1).

If you access the reversed string more often than you change the original string, the cost reduces below the simplistic "calculate the reversed string every time" method.

edited Feb 05 '13 at 02:33

answered Feb 05 '13 at 02:26

paxdiablo

854,327
234
1,573
1,953

If you trust `std::reverse`, you can do `std::reverse(s, s+strlen(s));` – jxh Feb 05 '13 at 02:31
@user315052, I have no reason _not_ to trust it but it's still an O(n) operation. – paxdiablo Feb 05 '13 at 02:35
Is this supposed to be d > s? – Bob John Feb 05 '13 at 03:14
Also, I was curious about reversal of the words, not individual letters. – Bob John Feb 05 '13 at 03:16
@Bob, yes it is supposed to be `d > s`. `s` is the start of the string, `d` is the end. You swap, then you increment `s` and decrement `d` until they meet or cross. And there's _nothing_ in your question about swapping words, rather it's just about reversing a string, which is very much a char-by-char operation. If you want to ask a question about swapping words, I suggest you ask another one. But check first, I'm pretty certain you'll find something. – paxdiablo Feb 05 '13 at 03:25

What is the fastest way to reverse a c-string, in place in c++?

3 Answers3