mercredi 4 mai 2016

Merge sort algoritm using array on std::unique_ptr

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