为什么qsort（）没有返回值？

我是C++程序员，但大部分时间只是为了好玩，我试图在C中进行一些通用编程。特别是，我实现了一个通用的排序算法。我的函数的签名是为什么qsort（）没有返回值？

int sort(void *data, 
     size_t num_elems, 
     size_t elem_size, 
     int (*cmp)(const void*, const void*))

当我在标准库相比，这qsort()，我发现我的不同功能，qsort()没有返回值。由于对数组进行排序总是需要交换元素，因此实现需要临时存储大小为elem_size。由于C没有模板，elem_size在编译时并不知道，所以临时存储必须动态分配，这可能会失败。在这种情况下，qsort()无法对数组进行排序，但也无法报告错误，因此无法知道数组是否在返回时排序。

我失去了一些东西在这里？

来源

2017-06-30 cthl

请您详细说明一下吗？如何更改元素的顺序而无需额外存储至少一个元素？ – cthl

忽略这一点，我很愚蠢，并认为你写了'num_elems'而不是'elem_size'。尽管如此，仍然可以在没有可变数量的临时存储的情况下交换任意数量的内存。只需要以固定大小的单位进行（例如，一次一个字节）。 – Ryan

任何分区算法都需要能够交换两个元素，并且API意味着代码不知道它们在编译时有多大。但是他们不需要整体交换;它们可以一次换成一个字节。（这实际上是memcpy会做什么的。）

下面的注释和宏在Gnu libc实现中的qsort.c开头是正确的。（请注意，代码以LGPL为准）

/* Byte-wise swap two items of size SIZE. */ 
#define SWAP(a, b, size)              \ 
    do                   \ 
    {                   \ 
     size_t __size = (size);             \ 
     char *__a = (a), *__b = (b);           \ 
     do                  \ 
     {                  \ 
      char __tmp = *__a;             \ 
      *__a++ = *__b;              \ 
      *__b++ = __tmp;              \ 
     } while (--__size > 0);            \ 
    } while (0)

来源

2017-06-30 03:45:27 rici

谢谢，这确实解决了这个问题。我想知道为什么我自己没有想到这一点。 – cthl

@cthl：一切都很明显......在看完之后。我们所有人都先踢了很多次，才没有看到它。 – rici

函数不能失败 - 好吧，除非参数是无效的，在这种情况下，它是未定义的行为，并且函数无论如何都无法可靠地检测到。

qsort本身不分配任何内存。（当然，它可以做任何事情，但由于内存分配失败，它不允许失败，所以实现者必须考虑到这一点）。

来源

2017-06-30 03:33:50

但是如何实现一个排序算法*没有内存分配？任何实现都需要改变元素的顺序，因此需要一个地方暂时存储至少一个元素。 – cthl

@cthl：它可以一次交换一个字节 – rici

它可以使用CPU寄存器为例。或者它可以执行XOR技巧。 –

为什么qsort（）没有返回值？

回答

相关问题