0

我发现了 Timsort 的 Swenson 的 C 实现： https ://github.com/swenson/sort在较早的 SO 问题之一中提到。

我遇到了两个问题：

1）要使用它，我需要定义适合我想要排序的类型的 SORT_CMP 宏。我的类型被定义为（这里有点简化）：

typedef struct{
    int a;
    int b;
} MyType

我尝试定义： 

#define SORT_TYPE MyType
#define SORT_CMP(x,y) (x.a - y.a)

但我不断收到一个错误：“在不是结构或联合的东西中请求成员'a'”我认为也许 x 和 y 将是指针，但是：

#define SORT_CMP(x,y) (x->a - y->a)

也不行。你能帮我解决这个问题吗？我是 C 新手，可能缺少一些基本的东西。

2）有没有办法在 Visual Studio 中编译该代码？它使用来自较新的 C 标准的东西（比如块中间的声明）并且 cl.exe 不接受它。我使用 GCC (mingw) 编译它，但 mingw 的其余代码比 VC 慢 20%（使用 O2 或 O3 标志 vs lc.exe 使用 /Ox）所以我可以从使用 Timsort 而不是 stdlib qsort 中获得任何收益不会弥补的。Pelles 编译器也是如此。我的大部分数据都有很多部分排序的序列，排序需要大约 50% 的执行时间，所以我觉得假设我让它在 VC 中工作，这里有收获。

4

1 回答 1

2

您可以尝试在宏参数周​​围添加括号，如下所示：

#define SORT_CMP(x,y) ((x).a - (y).a)

该宏很可能与指向 SORT_TYPE 变量的取消引用指针一起使用：

SORT_TYPE * pMyTypeVar1, pMyTypeVar2;
...
SORT_CMP(*pMyTypeVar, *pMyTypeVar2);

如果宏参数周围的括号丢失，则预处理器会生成如下内容：

(*pMyTypeVar1.a - *pMyTypeVar2.a)

并且由于点运算符比星运算符绑定得更紧密，编译器会尝试找到a指针的成员，pMyTypeVar1而pMyTypeVar2这将不起作用。

按照建议使用括号将导致：

((*pMyTypeVar1).a - (*pMyTypeVar2).a)

这样编译器首先取消引用pMyTypeVar1，pMyTypeVar2最后能够找到 member a。

于 2012-06-12T17:55:33.773 回答