How to shift chars in a character array without a temp?

Question

I'm wondering if there's any way to shift all characters from an index one position to the right, given that there is enough space allocated for it.

I got hints by my teacher that it can be done without an auxiliary variable and using the <cstring> library.

I tried:

#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    char str[100] = "Welcome to hell!";
    strcpy(str+4, str+3);
    cout << str; //Welccccccco hell!!
                 //Expected: Welccome to hell (to double the c so i can insert whitespace)
    return 0;
}

I know that this function works with pointers as parameters, so calling it with the same string can mess things up. But is it possible in a way? I found that strcpy(s+i, s+j) gives an unexpected result if i > j. Why? Also, what's the alternative?

Answer 1

As was mentioned in the comments, you get undefined behaviour when using strcpy with overlapping ranges.

From https://cplusplus.com/reference/cstring/strcpy/

...the size of the array pointed by destination shall be long enough to contain the same C string as source (including the terminating null character), and should not overlap in memory with source.

To see why this is an issue, we can look at some of the implementations of strcpy discussed in this question, and see that the code copies from the source buffer to the destination buffer until the null terminator character '\0' is reached. When calling strcpy(str+3, str+4), you are always copying the same character, then advancing and reading again the same character you just copied, so the null terminator is never reached.

Perhaps there is some difference or safety check in the implementation of strcpy you are using, as it does not overwrite the entire string, and stops after some time. Or perhaps this is the result of compiler optimizations, which are allowed to assume you don't do things the library functions say not to do (i.e. that your code does not invoke undefined behaviour).

It's not clear from your question whether your teacher suggests using other tools in <cstring> to write code to accomplish your goal, or whether your teacher thinks that there is an exact function which already does what you want.

I would suggest that rather than starting from the middle of the string, you start at the end, and move all characters down one, to leave the doubling you desire. If the purpose of doing this shift is always to insert a space, you could build this space insertion into the same function as well.

As an aside, if you are working in C++, it is typically best to avoid C-style strings unless absolutely necessary. You should instead prefer using the standard library's std::string.

Answer 2

strcpy(str+4, str+3); reads characters from str+3 until it finds a \0. However, it reads a character from one position then writes to the next position in the array, hence it never finds a \0. More formally, strcpy(str+4,str+3) invokes undefined behavior. Output of the code could be anything.

You can use std::reverse_copy that avoids the issue of reading the character that just has been overwritten by starting at the back:

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    char str[100] = "Welcome to hell!";
    std::copy_backward(str+3,str+std::strlen(str),str+std::strlen(str)+1);
    cout << str;
}

Live Demo

The 3 arguments are start of the source, str+3, end of the source, str+std::strlen(str), and end of the destination, end_of_source+1.

Answer 3

From cppreference

The behavior is undefined if the strings overlap.

Are you tied to using C-strings? Using std::string allows for this:

std::string string("Welcome to hell!");
std::cout << string.insert(3, " ");

To avoid copy of the whole sting on insertion, because more memory is needed, you may call reserve to tell the string how much space is needed in advance:

std::string string;
string.reserve(100);
string = "Welcome to hell!";

In case you cannot use std::string, the following function foes the trick:

void shift_right(char* const str, size_t from, size_t shift_amount) {
    const size_t size = std::strlen(str);
    for (unsigned i = size; i > from; --i) {
        str[i + shift_amount] = str[i];
    }
}

int main() {
    char str[100] = "Welcome to hell!";
    shift_right(str, 3, 1);
    std::cout << str;
}

Moving the elements starting from the back does not override the elements needed afterwards. Note size + shift_amount + 1 should be less than the whole char array. If you shift more than the size - from, then make sure that you fill the values, otherwise there may be a stray \0 or garbage in the middle of your string.

Answer 4

It you insist on doing it with <cstring> (to stay within the taught material for example), then:

memmove( str+4, str+3, sizeof(str) - 4);

or more generally:

memmove( str+n+1, 
         str+n, 
         sizeof(str) - n - 1);

Noting that that relies on str being an array rather than a pointer. Otherwise you need to know the actual string length:

memmove( str+n+1, 
         str+n, 
         strlen(str + n) );

but strlen() necessarily iterates the string to find the end, so there performance wise it may not be a good idea.