C++ array_put()

Question

你好，我对 C++ 无限数组有疑问。这个 array_put() 函数通过创建新数组是增加数组大小的最佳方式吗？也许有比这更快的方法？ :(

我在用谁，对此不确定...

#include <windows.h>
#include <iostream>
#include <sstream>

using namespace std;

// ============================================================
//                       ALERT WINDOW
// ============================================================
void alert(string value, string title = "Warning")
{
    MessageBox(NULL, value.c_str(), title.c_str(), MB_OK);
}
// ============================================================


// ============================================================
//                     INTEGER TO STRING
// ============================================================
string integer_to_string(int value)
{
    ostringstream stream;
    stream<<value<<flush;

    return stream.str();
}
// ============================================================

// ============================================================
//                          ARRAY PUT
// ============================================================
typedef struct ARRAY{
    int* data;
    int length = 0;
} array;

void array_put(array &array_data, int value)
{
    int* new_array = new int[array_data.length+1];
    if (array_data.length != 0){new_array = array_data.data;}

    new_array[array_data.length] = value;

    array_data.data = new_array; array_data.length++;
}
// ============================================================


// ============================================================
//                ARRAY PRINT (REQ: ARRAY PUT)
// ============================================================
string array_print(array array_data)
{
    string out = "";
    out += "array_length: " + integer_to_string(array_data.length) + "\n";
    for (int i=0;i < array_data.length;i++)
    {
        out += "[" + integer_to_string(i) + "] = " + integer_to_string(array_data.data[i]) + "\n";
    }
    return out;
}
// ============================================================

int main()
{
    array array_data;
    array_put(array_data, 120);
    array_put(array_data, 170);

    string result = array_print(array_data);
    alert(result);

    return 0;
}

Answer 1

其他人已经指出了您代码中的错误，并指出您可能应该使用 vector 而不是自行开发的解决方案这一事实。但是，还没有人回答您的实际问题是否有更快的方法。

假设您通常向同一个数组添加多个元素，这确实不是最佳选择:按原样(更正错误后)，您将为每个额外的条目重新分配数组，完成之前复制所有数据存储。由于数据会随着每个元素的增加而增长，因此插入的复杂度是二次方的(必须制作的拷贝数与插入的元素数的平方成正比)，以及线性数量的昂贵的重新分配。

更好的策略是始终将一定数量的现有元素分配为新元素，并跟踪这些元素中有多少实际上是数组的一部分，以及有多少已经预先分配用于添加新元素之后。这减少了重新分配的次数越多，你的数组已经越大，并最终给你一个摊销常数复杂度(平均而言，要执行的拷贝数与你插入的元素数成正比)，以及对数的昂贵的重新分配。

的确，这正是 vector 所做的。