Constant time string reversal with smart strings?

Question

In C, instead of keeping track of only the length of the string, what if we keep track of its direction as well? For example, if str = "hello" was laid out in memory (as given by malloc), we would say it has a positive direction (+1) and therefore pass +1 into function arguments. Instead of taking O(n) to reverse this string, we can now just say rev = str[size - 1] with direction -1 and it is therefore treated differently. I realize the null termination might bring up some issues but given that we have the string length and the starting character in memory we do not need to care about the null termination (correct me if I'm wrong).

Is this a viable option if string reversal is critical in a program? Can someone give me a reason why I should not do this? Has anyone heard or seen this?

Sorry if my formatting is off, this is one of my first time posting. Thanks in advance!

Answer 1

I'm pretty sure that in order to reverse a string, you are going to have to copy the string in some way. Outside of some sort of MMU trick where the system's memory reading is reversed at the addressing level, this necessitates having to traverese the string at least once. Even if copying 4/8/16+ bytes at a time, this is still a linear operation.

Now, if you can just read the string in place, in reverse (using a special iterator or something), then perhaps you could consider this an O(1) operation, provided that this special iterator is also O(1).