Как выделить глобальный int * динамически? - PullRequest
Новая
       9

Как выделить глобальный int * динамически?

0 голосов
/ 14 апреля 2019

Я пытаюсь сделать код сортировки слиянием в C ++, и чтобы избежать большого использования памяти, я хочу объявить вспомогательный вектор как глобальную переменную.Как вы, возможно, знаете, при использовании стратегии глобальных переменных используется пространство O (1) , а при использовании другого - O (N logN) * ​​1004 *.Но есть небольшая проблема, я не знаю размера векторов, которые будут использоваться для тестирования моего кода, поэтому мне нужно, чтобы эта глобальная переменная была динамически распределена.

Я уже пытался что-то сделатьвот так:

Это из архива .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)));

И другие возможности проб и ошибок, которые привели к одной и той же ошибке: - (

множественное определение `aux '

Я искал некоторые другие вопросы на этом форуме здесь, но, несмотря на множество подобных вопросов, я не смог найти решение именно этой проблемы.

Я думаю, что объяснилпроблема ясна, но если что-то неясно, пожалуйста, спросите.

Ответы [ 2 ]

0 голосов
/ 14 апреля 2019

Использование глобального вспомогательного вектора не приведет к O (1) накладным расходам памяти, размер вектора будет таким же, как у самого большого вектора, который вы пытаетесь отсортировать (или хотя бы вдвое меньше, чем при умномреализации), следовательно O (N) пробелы.

Кроме того, использование глобальной переменной делает код не реентерабельным, не ориентированным на многопотоковое исполнение и сохраняет издержки после выполнения сортировки.

Вот лучший подход:

  • написать рекурсивную mergesort_helper функцию, которая использует этот временный массив для хранения левого подмассива во время фазы слияния.
  • nmergesort функция, выделяет временный массив элементов размером (N + 1) / 2 и передает его рекурсивной функции mergesort_helper.
  • освобождает временный массив
  • и возвращает его вызывающей стороне.
0 голосов
/ 14 апреля 2019

Ошибка в том, что вы объявляете переменную в заголовке.

На заголовке нужно поставить 

extern int* aux;

А потом в какой-то .cpp вы должны положить: 

int* aux= nullptr;

В любом случае, вам следует серьезно подумать вместо int* aux использовать std::vector<int> aux;.

  • Он сохранит для вас количество элементов
  • Он не будет использовать почти пустое пространство, когда пуст.
  • Он будет расти по мере необходимости.
  • Вы можете reserve памяти, прежде чем использовать ее для оптимизации.
  • Вам не нужно будет звонить delete / free
...