help with template mergesort function

Question

error C2065:'temp' : undeclared identifier

i know that for "temp" i need to declare the type that the array is like int temp[] but what if i don't know what it is.. it could be int or string or double.. how can i create a temp array not specifying what it should be

Here is my code:

template<class T>
void Mergesort(T& a, int first, int last);
template<class T>
void Merge(T& a, int first, int last);


int main()  
{
    int num;

    // Read in an array of strings
    cout << "How many words? ";
    cin >> num;
    Array<string> b(num);
    cout << "Enter the " << num << " words below:\n";
    for (int i=0; i<num ; i++)
     cin >> b[i];
    cout << "\nThank you!!\n";

    // Copy the original array and sort it using Quicksort
    Array<string> bq(b);
    Quicksort(bq, 0, num-1);
    cout << "\nElements sorted using quicksort:\n";
    for (int i=0; i<num ; i++)  
     cout << bq[i]<< " ";
    cout << "\n";

    // Print original list of elements.
    cout << "\nOriginal elements:\n";
    for (int i=0; i<num ; i++)  
     cout << b[i]<< " ";
    cout << "\n";

    // Copy original array and sort it using MergeSort
    Array<string> bm(b);
    Mergesort(bm, 0, num-1);
    cout << "\nElements sorted using mergesort:\n";
    for (int i=0; i<num ; i++)  
     cout << bm[i]<< " ";
    cout << "\n";


template<class T>
void Mergesort(T& a, int first, int last) 
{
    if (first < last) 
    {
        int mid = (first + last) / 2;
        Mergesort(a, first, mid);
        Mergesort(a, mid+1, last);
        Merge(a, first, last);
    }
}

template<class T>
void Merge(T& a, int first, int last) 
{
    int mid = (first + last) / 2;
    int one = 0, two = first, three = mid + 1;
    T *temp = new T[last];

    while (two <= mid && three <= last) // Neither sublist is done
        if (a[two] < a[three])          // Value in first half is smaller
      temp[one++] = a[two++];
        else                            // Value in second half is smaller
      temp[one++] = a[three++];
    while (two <= mid)                  // Finish copying first half
        temp[one++] = a[two++];
    while (three <= last)               // Finish copying second half
        temp[one++] = a[three++];   
    for (one = 0, two = first; two <= last; a[two++] = temp[one++]);
}

//ARRAY.h

using namespace std;

template<class T> class Array 
{
public:
    typedef T value_type;
    Array(int s);
    Array(int l, int h);

    Array(const Array& other);
    ~Array();

    T& operator[](int index);
    const T& operator[](int index) const;

    int get_size() const {return arraySize;}

private:
    int low;
    int high;
    int arraySize; //size of array
    int offset; //to adjust back to an index of zero
    T *array_;

    void Copy(const Array&);
};

Answer 1

temp is supposed to be an array of temporary items right? Well that sounds like you need to do something like:

typedef typename T::value_type U;
U *temp = new U[count];

don't forget to delete[] it when you are done!

Also, as a side note, the more c++-ish thing to do would be to use pointers/iterators. This way your algorithm will work with more types of containers, not just things that model an array.

Also, as Tim Sylvester suggested, you could use std::vector<U> temp(count) which will manage the memory for you.

Answer 2

In the context of a template function or class, the template parameters are "real" types. The type you want for temp is merely T*.

Update:

Since T is the array class not the element type, you actually want T::value_type* for temporary values.