Mergesort for strings

Question

I am new to C ++ programming and recently wrote a mergesort method to sort some arrays. For my personal test, it works great for integers and doubles. But when I try to sort the lines, it gives me a "semantic problem" error, which I am very confused about. Full code:

#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 in this "// * * ERROR LINE", for example:

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

What is this error talking about? How do I change the code?

Answer 1

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

You can use std::vector from them, i.e.

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

You can also make a t array of pointers (ie T* t[right-left+1]; and update the code accordingly).

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

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

Answer 2

You have a variable length array:

 T t[right-left+1]; 

This is an extension supported by your specific compiler, and not part of the C ++ standard. It does not work for complex object types such as std::string - hence the error message. You can replace it with vector :

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

The ideal idea is to use pointers better, though - copying std::string objects around is pretty heavyweight (i.e. intense, slow) ... you just want to keep track of which a[] elements are moved, rather than sorting the copies from them then copy them.