memcmp排序

Question

我有一个缓冲区和几个指向它的指针。 我想根据指针指向的缓冲区中的字节对指针进行排序。

qsort() 和 stl::sort() 可以被赋予自定义比较函数。 例如，如果缓冲区是零终止的，我可以使用 strcmp：

int my_strcmp(const void* a,const void* b) {
  const char* const one = *(const char**)a,
  const two = *(const char**)b;
  return ::strcmp(one,two);
}

但是，如果缓冲区不是零终止的，我必须使用需要长度参数的 memcmp() 。

有没有一种整洁、有效的方法可以在不使用全局变量的情况下将缓冲区的长度输入到我的比较函数中？

Answer 1

使用 std::sort，您可以使用像这样的 Functor：

struct CompString {
    CompString(int len) : m_Len(len) {}
    bool operator<(const char *a, const char *b) const {
        return std::memcmp(a, b, m_Len);
    }
private:
    int m_Len;
};

然后您可以执行以下操作：

std::sort(begin(), end(), CompString(4)); // all strings are 4 chars long

编辑： 来自注释建议（我猜这两个字符串都在公共缓冲区中？）：

struct CompString {
    CompString (const unsigned char* e) : end(e) {}
    bool operator()(const unsigned char *a, const unsigned char *b) const {
        return std::memcmp(a, b, std::min(end - a, end - b)) < 0;
    }
private:
    const unsigned char* const end;
};

Answer 2

对于 C 函数 qsort()，不，如果不使用全局变量，就无法将长度传递给比较函数，这意味着它不能以线程安全的方式完成。 有些系统有 qsort_r() 函数（r 代表可重入），它允许您传递额外的上下文参数，然后将其传递给比较函数：

int my_comparison_func(void *context, const void *a, const void *b)
{
    return memcmp(*(const void **)a, *(const void **)b, (size_t)context);
}

qsort_r(data, n, sizeof(void*), (void*)number_of_bytes_to_compare, &my_comparison_func);

Answer 3

是否存在不能以空终止缓冲区的原因？

如果没有，由于您使用的是 C++，您可以编写自己的函数对象：

 struct MyStrCmp {
    MyStrCmp (int n): length(n) { }
    inline bool operator< (char *lhs, char *rhs) {
       return ::strcmp (lhs, rhs, length);
    }
    int length;
 };
 // ...
 std::sort (myList.begin (), myList.end (), MyStrCmp (STR_LENGTH));

Answer 4

您可以将缓冲区指针 + 长度打包到一个结构中，并将该结构的指针作为 void * 传递吗？

Answer 5

您可以使用如下 hack：

int buffcmp(const void *b1, const void *b2)
{
    static int bsize=-1;
    if(b2==NULL) {bsize=*(int*)(b1); return 0;}
    return memcmp(b1, b2, idsize);
}

首先将其调用为 buffcmp(&bsize, NULL)，然后将其作为比较函数传递给 qsort。

当然，您可以通过添加更多 if 语句，使比较在 buffcmp(NULL, NULL) 等情况下表现得更自然。

Answer 6

您可以使用仿函数（将长度赋予仿函数的构造函数）或 Boost.Lambda（就地使用长度）。

Answer 7

我不清楚你在问什么。 但我会尝试，假设

• 您有一个缓冲区
• 您有一个某种类型的指针数组，该数组已经以某种方式处理，以便其部分或全部内容指向缓冲区

这相当于代码：

char *buf = (char*)malloc(sizeof(char)*bufsize);
for (int i=0; i<bufsize; ++i){
    buf[i] = some_cleverly_chosen_value(i);
}

char *ary[arraysize] = {0};
for(int i=0; i<arraysize; ++i){
   ary[i] = buf + some_clever_function(i);
}

/* ...do the sort here */

现在如果您控制缓冲区的分配，您可以

char *buf = (char*)malloc(sizeof(char)*(bufsize+1));
buf[bufsize]='\0';

使用 strcmp 替换并继续。 即使您不控制缓冲区的填充，这也是可能的。

如果您必须忍受其他人交给您的缓冲区，您可以

1. 使用一些全局存储（您要求避免并进行良好的思考）。
2. 为排序函数提供比原始指针（支持额外数据的结构或类的地址）更复杂的东西。 为此，您需要控制上面代码中ary的定义。
3. 使用支持额外输入的排序函数。 Adam 建议的 sort_r 或家庭滚动解决方案（我确实推荐将其作为学生的练习，但在现实生活中不推荐）。 无论哪种情况，额外的数据都可能是指向缓冲区末尾的指针。

Answer 8

memcmp 应该在第一个不相等的字节处停止，因此长度应该很大，即到缓冲区的末尾。 那么它返回零的唯一方法是它确实到达缓冲区的末尾。

（顺便说一句，我自己倾向于合并排序。它稳定且表现良好。）