How to implement shifting of sub-array one position

Question

How can we shift array members one position?

For example, if we have n sized array with one empty element, and we shift all elements to right of a member pos by one position, we can copy n-1th member into the empty element, and so on.

code:

#include <iostream>

using namespace std;

// we take the position of insertion, then right shift all elements
// then insert the required number

int main() {
    int n = 10;
    int list[n];

    cout << "Enter " << n-1  << " elements:\n";

    for( int i = 0; i < n-1; ++i) {
        cin >> list[i];
    }

    int pos, num;

    cout << "Position ( start: 1 ): ";
    cin >> pos;

    if( pos < n && pos >= 0 ) {
        cout << "No. to be inserted: ";
        cin >> num;

        for( int i = n-2; i >= pos-1; --i) {
            list[i+1] = list[i];
        }
        list[pos-1] = num;

        for( int i = 0; i < n; ++i) {
            cout << list[i] << ' ';
        }

        return 0;
    }
}

• But can we not, by some means, shift the whole sub-array in one go, sliding all members right by one?

• Also can we implement this with vectors? And will vectors be more efficient or better way to achieve this?

Answer 1

First of all C++ does not support Variable Length Arrays (VLAs). Though some compilers have their own language extensions that support VLAs it is better to use standard C++ features.

So instead of

int main() {
    int n = 10;
    int list[n];
    //...

it is better to write

int main() {
    const int n = 10;
    int list[n];
    //...

Also in general it is better to use standard algorithms instead of loops where it is possible becasue this allows to eliminate errors.

To insert a value in your array in position pos you could use the following approach as shown in the demonstrative program. For fundamental arithmetic types you could use also standard C function memmove.

#include <iostream>
#include <algorithm>
#include <iterator>

int main()
{
    const size_t N = 10;

    for ( size_t i = 0; i < N; i++ )
    {        
        int a[N] = { 0 };

        auto pos = std::next( std::begin( a ), i );            
        std::copy_backward( pos, std::prev( std::end( a ) ), std::end( a ) );
        *pos = i + 1;

        for ( int x : a ) std::cout << x << ' ';
        std::cout << std::endl;
    }

    return 0;
}

Its output is

1 0 0 0 0 0 0 0 0 0 
0 2 0 0 0 0 0 0 0 0 
0 0 3 0 0 0 0 0 0 0 
0 0 0 4 0 0 0 0 0 0 
0 0 0 0 5 0 0 0 0 0 
0 0 0 0 0 6 0 0 0 0 
0 0 0 0 0 0 7 0 0 0 
0 0 0 0 0 0 0 8 0 0 
0 0 0 0 0 0 0 0 9 0 
0 0 0 0 0 0 0 0 0 10 

As for the standard container std::vector then it has methods that allow to insert new elements. However compared with arrays these methods will enlarge the vector.

There are the following methods of the std::vector that allow to insert one element.

iterator insert(const_iterator position, const T& x);
iterator insert(const_iterator position, T&& x);

Under the hood the vector does the same job as arrays except that the vector can enlarge dynamically the used memory.