我正在尝试在C++中执行合并排序代码，并且为了避免大量内存使用，我想将辅助向量声明为全局变量。您可能知道，使用全局变量策略时，使用的空间是 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)));
以及其他导致相同错误的尝试和错误可能性：-(
"辅助"的多重定义
我在这里的论坛中寻找了一些其他问题，但是尽管有很多类似的问题，但我无法找到解决这个问题的方法。
我认为已经清楚地解释了问题，但如果有什么晦涩难懂的地方，请问。
错误是您在标头上声明了一个变量。
在标题上，您应该输入
extern int* aux;
然后在某些.cpp中，您应该输入：
int* aux= nullptr;
无论如何，您应该认真考虑而不是int* aux使用std::vector<int> aux;。
- 它将为您保留元素的数量
- 它空时几乎不会使用任何空间。
- 它将根据需要增长。
- 您可以在使用内存进行优化之前
reserve内存。 - 您无需致电
delete/free
使用全局辅助向量不会实现O(1) 内存空间开销，向量的大小将是你尝试排序的最大向量的大小(或者至少是聪明实现的一半)，因此O(N)空间开销。
此外，使用全局变量会使代码不可重入、非线程安全，并在排序完成后保留开销。
这是一个更好的方法：
- 编写一个递归
mergesort_helper函数，该函数在合并阶段使用此临时数组来存储左侧子数组。 - 在
mergesort函数中，分配一个大小(N + 1) / 2元素的临时数组，并将其传递给递归mergesort_helper函数。 - 释放临时阵列
- 返回到呼叫者。