Обнаружено повреждение кучи сортировки слиянием

Question

Обнаружено повреждение кучи сортировки слиянием

Я пишу функцию, которая должна сортировать массив с помощью сортировки слиянием. Пока у меня есть две функции:

template <typename Item, typename SizeType>
void merge_sort(Item data[], SizeType size) {
SizeType size1, size2;
if(size > 1) {
size1 = size/2;
size2 = size - size1;
merge_sort(data,size1);
merge_sort((data+size1),size2);

merge(data,size1,size2);
}
}

а также:

template <typename Item, typename SizeType>
void merge(Item data[], SizeType size1, SizeType size2) {
Item* temp;
SizeType copied = 0;
SizeType copied1 = 0;
SizeType copied2 = 0;

temp = new Item[size1 + size2];

while(copied1 < size1 && copied2 < size2) {
if(data[copied1] < (data + size1)[copied2])
temp[++copied] = data[++copied1];
else
temp[++copied] = (data + size1)[++copied2];
}

while (copied1 < size1)
temp[++copied] = data[++copied1];
while (copied2 < size2)
temp[++copied] = (data + size1)[++copied2];

for(SizeType i = 0; i < size1 + size2; ++i)
data[i] = temp[i];
delete [] temp;
}

Однако, когда я пытаюсь запустить программу, я получаю сообщение об ошибке, в котором говорится, что куча повреждена после обычного блока, и что CRT обнаружил, что приложение записало в память после окончания буфера кучи. Может кто-нибудь объяснить, что это значит и как я мог это исправить?

0

c++heap heap-corruption merge mergesort

Решение

Другие решения

Вы подразумеваете, что ваши приращения будут пост-приращениями, а не пре-приращениями? Например:

    temp[copied++] = (data + size1)[copied2++];

С предварительным приращением, на первой итерации, когда copied2 было 0, вы получали доступ (data + size1)[1], когда copied2 достигает конца вашей выделенной памяти, вы получаете доступ к концу за концом.

Чтобы избежать этого, я рекомендую не иметь приращений в качестве подвыражений. Это может быть запутанным, чтобы написать а также читать.

2

если скопировано = 0 и скопировано1 = 0, тогда строка

temp [++ copied] = data [++ copied1];

будет производить

temp [1] = data [1];

потому что префикс ++ имеет самый высокий приоритет здесь

1

Источник

Accepted Answer

Вы увеличиваете, прежде чем использовать значения … так что в основном делает проверки устаревшими …

использование copied++ вместо.

Вам нужен оператор постинкремента, потому что если вы увеличиваете его перед использованием, вы выходите за пределы.
Операторы увеличения и уменьшения

2