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?

This sounds like a job for [`std::rotate`](http://en.cppreference.com/w/cpp/algorithm/rotate) — NathanOliver, Jan 11 '16 at 13:05
@Borgleader Nope. I did just watch a talk of his not too long ago though. — NathanOliver, Jan 11 '16 at 13:15
If you do many insert/erase in the middle use std::list. See http://stackoverflow.com/questions/471432/in-which-scenario-do-i-use-a-particular-stl-container — Support Ukraine, Jan 11 '16 at 13:30
@StillLearning most of the time `std::vector<>` outperforms `std::list<>`, even when that contradicts intuition. See https://www.youtube.com/watch?v=YQs6IC-vgmo — cdonat, Jan 11 '16 at 13:41
@cdonat - In case you have many insert/erase randomly distributed in a large container (e.g. 1.000.000 elements) , a list will out perform vector. — Support Ukraine, Jan 11 '16 at 14:19
@StillLearning Have you watched the video I have linked? Bjarne Stroustrup explains, why even in such cases vectors outperform lists most of the time. It is about predictable memory access patterns and linear search for the position to insert in linked lists. — cdonat, Jan 11 '16 at 14:27
@cdonat - Better than that. I just tried inserting (one-by-one) 10.000 ints in the middle of a container with 1.000.000 elements. Tried both list and a vector. List is much faster. Used g++ 4.8.1 and -O3. — Support Ukraine, Jan 11 '16 at 14:50
@StillLearning have you searched the position for insertion before measuring? If you would have watched the video, you'd know, that the operations on lists are dominated by sequential searches for positions to insert, or erase. — cdonat, Jan 11 '16 at 14:53

Vlad from Moscow · Accepted Answer · 2016-01-11T14:04:12.030

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.

Thank you! Actually it was a school assignment and we had to use loops. Are vector approaches to such situations better? — Max Payne, Jan 11 '16 at 14:44
@Tim If the array is not large and you need a fixed number of elements then it is better to use an array. Otherwise use std::vector. Take into account that it is even better to use container std::array instead of an ordinary array. — Vlad from Moscow, Jan 11 '16 at 14:58

How to implement shifting of sub-array one position

1 Answers1