我可以和qsort沿着使用memcmp吗？

9udxz4iz 于 2023-01-08 发布在其他

关注(0)|答案(3)|浏览(107)

我正在做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沿着使用吗？还是必须在内置比较器和内置排序函数之间进行选择？

来源：https://stackoverflow.com/questions/40855385/can-i-use-memcmp-along-with-qsort

3条答案

按热度按时间

qc6wkl3g1#

C11为您提供了一个（当然是可选的）qsort_s function，它旨在处理这种特定情况。它允许您将用户提供的void *值（上下文指针）从调用代码传递到比较器函数。

int (*compar)(const void *x, const void *y, void *context)

在最简单的情况下，您可以将大小值的指针作为上下文传递

#define __STDC_WANT_LIB_EXT1__ 1
#include <stdlib.h>
...

int comparator_callback(const void *x, const void *y, void *context)
{
  size_t elm_size = *(const size_t *) context;
  return memcmp(x, y, elm_size);
}

...
qsort_s(a->array, a->length, a->elm_size, comparator_callback, &a->elm_size);

或者将指向整个数组对象的指针作为上下文传递也是有意义的。
一些基于 * nix的实现已经提供类似的qsort_r function有一段时间了，尽管它不是标准的。

赞(0）回复(0）举报 2023-01-08

x8goxv8g2#

一种非线程安全的方法是使用私有全局变量来传递大小。

static size_t compareSize = 0;

int defaultComparator(const void *p1, const void *p2) {
  return memcmp(p1, p2, compareSize);
}

void array_sort(Array* a, int(*comparator)(const void*, const void*, size_t)) {
    if(comparator == NULL) {
      compareSize = a->elm_size;
      comparator = &defaultComparator;
    }
    // Sorting algorithm should follow
}

可以通过使compareSize成为线程局部变量（__thread）来使其成为线程安全的

赞(0）回复(0）举报 2023-01-08

yjghlzjz3#

qsort() API是一个简单时代的遗产。应该有一个额外的"环境"指针从qsort()调用传递到每个比较。这将允许您以线程安全的方式传递对象大小和任何其他必要的上下文。
但它并不存在。@BryanChen的方法是唯一合理的方法。
我写这个答案的主要原因是要指出，memcmp能发挥作用的情况非常少，按照组成unsigned char的字典顺序进行比较有意义的对象种类并不多。
当然，用这种方式比较struct是危险的，因为填充字节值是未指定的，甚至比较的相等部分也可能失败。

struct foo { int i; };

void bar(void) { 
  struct foo a, b;
  a.i = b.i = 0;
  if (memcmp(&a, &b, sizeof a) == 0) printf("equal!");
}

可以--按照C语言的标准--什么也不打印!
另一个例子：对于像unsigned ints这样简单的东西，您将得到big-endian和little-endian存储顺序的不同排序顺序。

unsigned a = 0x0102;
unsigned b = 0x0201;
printf("%s", memcmp(&a, &b, sizeof a) < 0 ? "Less!" : "More!");

将打印Less或More，具体取决于运行它的计算机。
事实上，我能想象到的唯一一种可以与memcmp进行比较的对象类型是大小相等的无符号字节块，这并不是排序的常见用例。
总之，提供memcmp作为比较函数的库注定是容易出错的，有些人会试图用它来代替专门的比较，而这是获得所需结果的唯一方法。

赞(0）回复(0）举报 2023-01-08

我来回答

我可以和qsort沿着使用memcmp吗？

3条答案

相关问题

热门标签

最新问答