Mergesort for strings

Question

I am quite new for C++ programming, and recently wrote a mergesort method to sort some arrays. For my personal test, it works fine for integers and doubles. But when I try to sort strings, it gives me a "sematic issue" error which I am quite confused. The full code is:

#include <iostream>
#include <string>
using namespace std;

template<typename T>
class Sorting{
public:
static void merge(T* a, int left, int mid, int right){
    int i=left; int j=mid+1; int k=0;
    T t[right-left+1]; //****************ERROR LINE

    for(;i<=mid && j<=right;k++){
        if(*(a+i)<=*(a+j)){
            t[k]=a[i];
            i++;
        }
        else{
            t[k]=a[j];
            j++;
        }
    }

    for(;i<=mid;i++,k++) t[k]=a[i];

    for(;j<=right;j++,k++) t[k]=a[j];

    for(i=0;i<k;i++) a[left+i]=t[i];
}

//Mergesort top-level function. Left is starting index, right is ending index
static void mergesort(T* a, int left, int right){
    if(left>=right) return;
    int mid=left+((right-left)>>1);
    mergesort(a, left, mid);
    mergesort(a, mid+1, right);
    merge(a, left, mid, right);
}
};


int main(){
const int len=5; 
string ss[len]={
    "Yep",
    "Nope",
    "5",
    "2.5",
    "Stackoverflow"
};
double ar[len]={4.2, 3, 5.6, -15, 0};

Sorting<double>::mergesort(ar, 0, 4); for(int i=0; i<len;i++) cout<<ar[i]<<endl;
Sorting<string>::mergesort(ss, 0, 4); for(int i=0; i<len;i++) cout<<ss[i]<<endl;
return 0;
}

And I got a semantic error at that "//**ERROR LINE" like:

Variable length array of non-POD element type 'std::__1::basic_string<char>'

What is this error talking about? How should I modify my code?

Answer 1

In the error message, POD refers to plain old data type

You could use a std::vector of them, i.e.

   std::vector<T> t;
   t.resize (right-left+1);

You could also make t an array of pointers (i.e. T* t[right-left+1]; and update the code accordingly).

^{BTW, you are using variable length array, which is a GCC extension that some other compilers don't provide.}

But sorting is available in C++ standard library. You'll need to #include<algorithm> and use std::sort on standard C++ containers.

Answer 2

You have a variable length array:

T t[right-left+1];

This is an extension supported by your particular compiler, and not part of the C++ Standard. It doesn't work for complex object types like std::string - hence the error message. You could replace it with a vector:

std::vector<T> t(right - left + 1);

Basile's idea to use pointers is better though - copying std::string objects around is pretty heavyweight (i.e. memory intensive, slow)... you just want to keep track of which a[] elements to move, rather than sorting copies of them then copying them back.