I'm trying to make merge sort algorithm using array allocated on std::unique_ptr.
When I run application it usually breaks and returns 0xC0000005.
When I'm running it with debugger (form Code::Blocks IDE) it doesn't break , but some of data on result array are negative witch isn't correct(input array contains random value form 0 to 100).
I think some of memory is freed before I wanted, but all memory management is done by std::unique_ptr and in only using smart pointers to access dynamic memory.
Is it possible that std::move does not transfer ownership immediately, or is it something different?
I'm using: void mergeSort(SmartPtrArray<T>& array_before)
to run merge sort.
Here is fragment of my code:
template <typename T>
struct SmartPtrArray
{
SmartPtrArray() {}
SmartPtrArray(int i): array(new T[i]), amount(i) {}
std::unique_ptr<T[]> array;
int amount;
};
namespace SortingAlgoritms
{
template <typename T>
void merge(SmartPtrArray<T>& array_a, SmartPtrArray<T>& array_b, SmartPtrArray<T>& result_array)
{
if(result_array.array != nullptr)
result_array.array.release();
std::unique_ptr <T[]> tmp (new T [array_a.amount+array_b.amount]);
result_array.array = std::move(tmp);// now result_array is only pointer with ownership
result_array.amount= array_a.amount + array_b.amount;
if(array_a.array[array_a.amount-1] <= array_b.array[0])//1 case
{
for(auto i = 0; i < array_a.amount; i++)
result_array.array[i] = array_a.array[i];
for(auto i = array_a.amount; i < ( array_a.amount + array_b.amount ); i++)
result_array.array[i] = array_b.array[i - array_a.amount];
}
else //2 case
{
auto j = 0;
auto i = 0;
for(i = 0; i <= array_a.amount; i++)
{
while(j < array_b.amount && array_b.array[j] <= array_a.array[i])
{
result_array.array[i+j] = array_b.array[j];
j++;
}
result_array.array[i+j] = array_a.array[i];
}
while(j < array_b.amount && array_b.array[j] <= array_a.array[i-1])
{
result_array.array[i+j] = array_b.array[j];
j++;
}
}
}
template <typename T>
void mergeSort(SmartPtrArray<T>& array_before, SmartPtrArray<T>& result, int begin, int end)
{
SmartPtrArray<T> tmp_left;
SmartPtrArray<T> tmp_right;
int break_point=(end+begin)/2;;
if(end-begin > 1)
{
mergeSort(array_before, tmp_left, begin, break_point);
mergeSort(array_before, tmp_right, break_point, end);
merge(tmp_left, tmp_right, result);
}
else
{
if(result.array!=nullptr)
result.array.release();
SmartPtrArray<T> tmp(1);
tmp.array[0] = array_before.array[begin];
result.array=move(tmp.array);
result.amount=1;
}
}
template <typename T>
void mergeSort(SmartPtrArray<T>& array_before)
{
SmartPtrArray<T> tmp_left;
SmartPtrArray<T> tmp_right;
int break_point=array_before.amount/2;
if(array_before.amount!=1)
{
SmartPtrArray<T> result;
mergeSort(array_before, tmp_left, 0, break_point);
mergeSort(array_before, tmp_right, break_point, array_before.amount);
merge(tmp_left, tmp_right, result);
if(array_before.array!=nullptr)
array_before.array.release();
array_before=std::move(result);
}
}
}
Aucun commentaire:
Enregistrer un commentaire