用于字符串的Mergesort

Question

我是C++编程的新手,最近写了一个mergesort方法来排序一些数组.对于我的个人测试,它适用于整数和双精度.但是当我尝试对字符串进行排序时,它会给我一个"语义问题"错误,我很困惑.完整的代码是:

#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;
}

我在"// **ERROR LINE"上遇到语义错误,如:

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

这个错误在谈论什么？我应该如何修改我的代码？

Answer 1

在错误消息中,POD指的是普通旧数据类型

你可以使用std::vector它们,即

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

您还可以创建t一个指针数组(即相应地T* t[right-left+1];更新代码).

^{顺便说一句,您使用的是可变长度数组,这是其他一些编译器不提供的GCC扩展.}

但是在C++标准库中可以进行排序.您需要在标准C++容器上#include<algorithm>使用std :: sort.

Answer 2

你有一个可变长度数组:

T t[right-left+1];

这是您的特定编译器支持的扩展,而不是C++标准的一部分.它不适用于复杂的对象类型std::string- 因此错误消息.您可以用以下代码替换它vector:

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

Basile使用指针的想法更好 - 复制std::string周围的对象非常重要(即内存密集,速度慢)...你只想跟踪a[]要移动的元素,而不是对它们的副本进行排序然后将它们复制回来.