如何在不知道大小的情况下编写过程来修改动态数组的元素和大小

Question

以下是我最近参加的编程考试中的一个问题。我和其他学生都没有找到解决问题的方法。教授说这是可能的，但拒绝告诉我们解决方案是什么。问题：

编写一个标头为：

void ArrayUpdate( int ??? array, int ??? delAmount, int ??? addAmout)

• 该过程用于修改通过第一个参数传递的动态数组的元素。
• 该过程应从数组中删除第一个单元格的 delAmount。它还应该在数组的后面添加 addAmount 的元素，并从 std：：cin 读取整数。
• 需要更换或移除"???"。
• 方括号"[ ]"只能与新建或删除一起使用。
• 只能包括iostream和fstream。（另一个问题需要 fstream，所以这里可能不需要它。

Answer 1

• "该过程用于修改通过第一个参数传递的动态数组的元素。" 它没有说明数组是如何组织的。正如@user4581301建议的那样，第一个元素可能是数组的大小。换句话说，数组的第一个元素位于位置 1，而不是 0。这很可能是你老师的想法。目的是教你指针/引用和数组布局。

• 创建数组：

  void CreateArray( int*& array, int size )
  {
    array = new int[ size + 1 ];
    array[ 0 ] = size;
  }
  

  你可以使用int**而不是int*&，但它更难写入/读取。

• 检索大小：

  int ArraySize( int* array )
  {
    return *array;
  }
  

• 用法：

  int* array;
  CreateArray( array, 10 );
  //...
  for ( int i = 1; i <= ArraySize(array); ++i )
    // ...
  

• 函数签名：

  void ArrayUpdate( int*& array, int delAmount, int addAmout);
  

Answer 2

这是我对

这个问题的黑客削减。它与 ZDF 非常相似，但它将数组的capacity添加到簿记中，并通过为调用方提供指向数组中间而不是开头的指针来谎言和隐藏簿记。这允许用户将数组用作常规数组，但如果他们尝试自己delete数组，则会崩溃。

嵌入的评论，我认为需要更多的解释。

//Magic numbers are evil.
constexpr int bookkeeping = 2;
constexpr int sizeOff = -2;
constexpr int capOff = -1;
void ArrayUpdate( int *& array, int delAmount, int addAmount)
{
    int size;
    int capacity;
    // can't do jack with a non-existent array, so let's make sure we have one.
    if (array != nullptr)
    {
        size = *(array + sizeOff);
        capacity = *(array + capOff);
    }
    else
    {
        size = 0;
        capacity = 0;
    }
    if (delAmount > size) // can't delete more than we have.
    {
        delAmount = size; 
        // alternative: freak out here. Abort, throw exception, whatever
    }
    int * to; // track where data goes to
    int * temp; // location of new buffer, if resized
    bool resized;
    int newsize =size + addAmount - delAmount;
    if (newsize > capacity)
    { 
        capacity *=2;
        if (capacity < newsize)
        {
            capacity = newsize;
        }
        temp = new int[capacity+bookkeeping];
        to = temp + bookkeeping; // point to where we want data to go:
                                 // after the book-keeping.
        resized = true;
    }
    else
    {
        to = array;
        resized = false;
    }
    // use std::copy or memcpy here, but since we're not allowed the appropriate
    // headers, here comes ol' brute force!
    if (delAmount || resized) // need to copy old data around
    { 
        for (int index = delAmount; index < size; index++)
        {
            *to++ = *(array + index);
        }
    }
    // add new data
    for (int count = 0; count < addAmount; count++)
    {
        if (std::cin >> *to) // always test to make sure you got good input
        {
            to++;
        }
        else
        { // Bad input. Clean up
            std::cin.clear();
            // normally I'd use cin.ignore(numeric_limits<streamsize>::max(), 'n')
            // here to kill all the remaining user input, but no <limits>
            std::cin.ignore(1000, 'n');
            // might also want to just read and discard until you find the
            // first whitespace. That's can be done easily by >> to a std::string,
            // but no string header allowed. 
        }
    }
    if (resized)
    {
        if (array != nullptr) // normally deleting nullptr is safe, but not when
                              // you're going to modify it with an offset
        {
            delete[] (array - bookkeeping);
        }
        array = temp + bookkeeping; // array hides the extra book-keeping
        *(array + capOff) = capacity;
    }
    if (array != nullptr)
    {
        *(array + sizeOff) = newsize;
    }
}

没有经过详尽的测试。那里可能有一两个错误。

为了完整起见，下面是测试代码和一个自由数组例程：

void FreeArray(int * array)
{
    delete[] (array - bookkeeping);
}
void printarray(const int * array)
{
    int size;
    int capacity;
    if (array != nullptr)
    {
        size = *(array + sizeOff);
        capacity = *(array + capOff);
    }
    else
    {
        size = 0;
        capacity = 0;
    }
    std::cout << "Size: " << size <<"nCapacity: "<< capacity << 'n';
    for (int index = 0; index < size; index++)
    {
        std::cout << array[index] << ' ';
    }
    std::cout << std::endl;
}
int main()
{
    int * array = nullptr;
    printarray(array);
    ArrayUpdate(array, 5, 0);
    printarray(array);
    ArrayUpdate(array, 5, 5);
    printarray(array);
    ArrayUpdate(array, 5, 5);
    printarray(array);
    ArrayUpdate(array, 0, 5);
    printarray(array);
    ArrayUpdate(array, 5, 0);
    printarray(array);
}

Answer 3

如果"???"可以用你想要的任何内容替换，那么你可以将指向 int 的指针或指向 int 的指针传递给函数，等等......

因此，在处理内存管理或范围时，C++诀窍是存储 2 个指针，一个指向数组的开头，一个指向数组的末尾：

//a range:
int* limits[2];
int ** array = limits;

然后，如果您更改函数内范围的大小，则必须通过引用传递它：

void ArrayUpdate( int ** array, int delAmount, int addAmout){
   int* begin = array[0];
   int* end = array[1];
   //end so on
   }