c++ - 如何实现子数组移位一位

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

• 但是我们不能通过某种方式一次性移动整个子数组，将所有成员逐一移动吗？

• 我们也可以用 vector 来实现吗？ vector 是否会更有效或更好来实现这一目标？

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 那么它有允许插入新元素的方法。但是与数组相比，这些方法会放大 vector 。

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

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

在引擎盖下， vector 做与数组相同的工作，除了 vector 可以动态扩大使用的内存。