如何动态分配一个全局 int*？

Question

我正在尝试用 C++ 编写合并排序代码，为了避免大量内存使用，我想将辅助向量声明为全局变量。你可能知道，使用全局变量策略 space 使用的是 O(1)，而使用另一个，它是 O(N logN) 。但是有一个小问题，我不知道将用于测试我的代码的向量的大小，所以我需要动态分配那个全局变量。

我已经试过这样做了：

这来自 .h 存档：

void mymergesort_recursive(std::vector<int> &v, SortStats &stats, int i = 0, 
                           int f = 0, bool nouveau = true);
int *aux = nullptr;

这来自 .cpp 存档：

void mymergesort_recursive(std::vector<int> &v, SortStats &stats, int i, 
                           int f, bool nouveau) {
    if (nouveau) {
        stats.recursive_calls = 1;
        f = int(v.size());
        // Allocates the variable aux according with the vector size. This makes a lot of memory economy.

        aux = new int[f];
    } else {
        ...
    }
    ...
}

其实我也试过这个：

aux = (int *)malloc(f * sizeof(int));

aux = static cast <int*>(malloc(f * sizeof(int)));

以及其他所有导致相同错误的尝试和错误可能性:-(

multiple definition of `aux'

我在这里的这个论坛中寻找了一些其他问题，但尽管有很多类似的问题，但我无法提取完全解决这个问题的解决方案。

我觉得已经把问题说清楚了，如果有什么不明白的，请追问。

Answer 1

错误是您在 header 上声明了一个变量。

在 header 你应该把

extern int* aux;

然后在一些 .cpp 中你应该输入：

int* aux= nullptr;

无论如何，你应该认真考虑而不是 int* aux 使用 std::vector<int> aux;。

它将为您保留元素的数量
空的时候几乎不会用space
它会根据需要增长。
你可以reserve内存在你使用它之前优化它。
您不需要调用 delete/free

Answer 2

使用全局辅助向量不会实现 O(1) 内存 space 开销，向量的大小将是您尝试的最大向量的大小排序（或者至少是聪明实现的一半），因此 O(N) space 开销。

此外，使用全局变量使代码不可重入，非线程安全，并在排序完成后保留开销。

这里有一个更好的方法：

编写一个递归 mergesort_helper 函数，在合并阶段使用此临时数组存储左侧子数组。
在 mergesort 函数中，分配一个大小为 (N + 1) / 2 的临时数组并将其传递给递归 mergesort_helper 函数。
释放临时数组
return 给来电者。

如何动态分配一个全局 int*？

How to allocate a global int* dynamically?

c++

global-variables

mergesort

multiple-definition-error