How to use a stack of pointers to arrays, and access two arrays in the same command?

Question

Just to be clear, this is for a homework assignment. I'm not asking for anyone to do it for me, I'm just stuck on a small portion of it.

I'm asked to implement mergesort, but each new array I make has to be placed in a stack of pointers. In the code below, I'm trying to split up an array recursively, then merge them together. My stack is named ptrs. The merge() function takes two sorted arrays and their sizes.

template <typename T>
T* MergeSort<T>::mergeSort(T arr[], int size) {

    int size1 = (int)size/2;
    int size2 = size - size1;

    //I'll have a base case to cover the arrays of size 1 or 2

    ptrs.push(new T[size1]);
    for(int i = 0; i < size1; i++) {
        ptrs.top()[i] = arr[i];
    }

    ptrs.push(new T[size2]);
    for(int i = 0; i < size2; i++) {
        ptrs.top()[i] = arr[i + size1];
    }

    return merge(mergeSort(TODO, size1), mergeSort(ptrs.top(), size2), size1, size2);

My problem is marked by my TODO. How can I access the first array, if the second one is now on the top of the stack?

ptrs is a stack of arrays of type T. In my tests, I've been using doubles. And the stack comes from std::stack. — user3448821, Mar 24 '14 at 13:56
stack is a poor choice of container here, may I suggest deque? With a deque, push becomes push_back, pop becomes pop_back, top becomes back, and second last element can be accessed with ptrs[ptrs.size()-2] — sp2danny, Mar 24 '14 at 14:03
Hm. That sounds like it could work. Unfortunately, the assignment is restricted to using a stack. Perhaps my code above is just using the wrong approach? — user3448821, Mar 24 '14 at 14:54
I just saw this comment, after writing my answer. But using a stack doesn't make sense to me. The stack's interface is designed to allow viewing or popping the top element only. You can only view the second if pop the first. But then you start realizing that you don't need a stack, only the two items. — iavr, Mar 24 '14 at 15:02

score 0 · Accepted Answer · edited May 23 '17 at 10:26

0

Why do you need a stack at all? Since you allocate two new arrays and copy the two portions of the input array, you can recurse on them directly:

T* left = new T[size1];
for(int i = 0; i < size1; i++) //...

T* right = new T[size2];
for(int i = 0; i < size2; i++) /...

T* left_sorted  = mergeSort(left,  size1);
T* right_sorted = mergeSort(right, size2);

Then merge, being careful to deallocate:

delete[] left;
delete[] right;

T* merged = merge(left_sorted, right_sorted, size1, size2);

delete[] left_sorted;
delete[] right_sorted;

return merged;

If this is allowed by the assignment, I would strongly recommend using std::vector instead of plain arrays + sizes. You could also consider in-place merge to avoid all those allocations.

edited May 23 '17 at 10:26

Community

1
1

answered Mar 24 '14 at 14:59

iavr

7,547
1
18
53

Though your way is not how I was allowed to do it, thanks for a working answer. It led me to my solution, which was to make array pointers and use them normally, but make sure to push anything I "new"ed before leaving the method. Then I let the destructor take care of my stack. – user3448821 Mar 26 '14 at 02:40
@user3448821 I trust your instructor has good reason for this :-) – iavr Mar 26 '14 at 02:44

How to use a stack of pointers to arrays, and access two arrays in the same command?

1 Answers1