如何实现子阵移位一位

Question

我们如何将数组成员移动一个位置？

例如，如果我们有一个包含一个空元素的n大小的数组，并且我们将所有元素向成员pos的右侧移动一个位置，我们可以将第n-1个成员复制到空元素中，以此类推。

代码：

#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;
    }
}

• 但是，难道我们不能通过某种方式，将整个子阵一起移动，将所有成员向右滑动一个吗？

• 我们也可以用向量来实现吗？向量会更有效还是更好的方式来实现这一目标？

Answer 1

首先，C++ 不支持可变长度数组（VLA）。尽管某些编译器有自己的支持 VLA 的语言扩展，但最好使用标准 C++ 功能。

所以而不是

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

最好写

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

一般来说，如果可能的话，最好使用标准算法而不是循环，因为这可以消除错误。

要在数组中插入一个值，pos 您可以使用以下方法，如演示程序所示。对于基本算术类型，您还可以使用标准 C 函数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;
}

它的输出是

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 

至于标准容器std::vector，它具有允许插入新元素的方法。然而与数组相比，这些方法会放大向量。

有以下std::vector 允许插入一个元素的方法。

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

在底层，向量的作用与数组相同，只是向量可以动态地扩大使用的内存。