我正在做C动态数组库,有点。注意我做这个是为了好玩在我空闲的时候,所以请不要推荐现有的库。
我开始实现排序,数组的元素大小是任意的,定义为struct:
typedef struct {
//[PRIVATE] Pointer to array data
void *array;
//[READONLY] How many elements are in array
size_t length;
//[PRIVATE] How many elements can further fit in array (allocated memory)
size_t size;
//[PRIVATE] Bytes per element
size_t elm_size;
} Array;
我最初准备从sort函数开始:
/** sorts the array using provided comparator method
* if metod not provided, memcmp is used
* Comparator signature
* int my_comparator ( const void * ptr1, const void * ptr2, size_t type_size );
**/
void array_sort(Array* a, int(*comparator)(const void*, const void*, size_t)) {
if(comparator == NULL)
comparator = &memcmp;
// Sorting algorithm should follow
}
然而,我了解了qsort
:
void qsort (void* base, size_t num, size_t size, int (*compar)(const void*,const void*));
显然,我可以将内部数组传递给qsort
,我可以调用它:
qsort (a->array, a->length, a->elm_size, comparator_callback);
但是有一个陷阱-qsort
的比较器签名如下所示:
int (*compar)(const void*,const void*)
而memcmp
的签名是:
int memcmp ( const void * ptr1, const void * ptr2, size_t type_size );
qsort
的回调函数中缺少元素大小,这意味着当NULL
作为回调函数传递时,我不能再使用通用的比较器函数,我可以手动生成最大为X字节的元素大小的比较器,但这听起来很难看。qsort
(或其他内置排序函数)可以和memcpy
沿着使用吗?还是必须在内置比较器和内置排序函数之间进行选择?
3条答案
按热度按时间qc6wkl3g1#
C11为您提供了一个(当然是可选的)
qsort_s
function,它旨在处理这种特定情况。它允许您将用户提供的void *
值(上下文指针)从调用代码传递到比较器函数。在最简单的情况下,您可以将大小值的指针作为上下文传递
或者将指向整个数组对象的指针作为上下文传递也是有意义的。
一些基于 * nix的实现已经提供类似的
qsort_r
function有一段时间了,尽管它不是标准的。x8goxv8g2#
一种非线程安全的方法是使用私有全局变量来传递大小。
可以通过使
compareSize
成为线程局部变量(__thread
)来使其成为线程安全的yjghlzjz3#
qsort()
API是一个简单时代的遗产。应该有一个额外的"环境"指针从qsort()
调用传递到每个比较。这将允许您以线程安全的方式传递对象大小和任何其他必要的上下文。但它并不存在。@BryanChen的方法是唯一合理的方法。
我写这个答案的主要原因是要指出,
memcmp
能发挥作用的情况非常少,按照组成unsigned char
的字典顺序进行比较有意义的对象种类并不多。当然,用这种方式比较
struct
是危险的,因为填充字节值是未指定的,甚至比较的相等部分也可能失败。可以--按照C语言的标准--什么也不打印!
另一个例子:对于像
unsigned int
s这样简单的东西,您将得到big-endian和little-endian存储顺序的不同排序顺序。将打印
Less
或More
,具体取决于运行它的计算机。事实上,我能想象到的唯一一种可以与
memcmp
进行比较的对象类型是大小相等的无符号字节块,这并不是排序的常见用例。总之,提供
memcmp
作为比较函数的库注定是容易出错的,有些人会试图用它来代替专门的比较,而这是获得所需结果的唯一方法。