сортировка по 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 вы можете использовать такой функтор:

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 обозначает реентерабельный), которая позволяет передавать дополнительный параметр context , который затем передается для сравнения. функция:

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

Вы можете использовать взломать как:

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.

Конечно, вы можете сделать сравнение более естественным в случае buffcmp(NULL, NULL) и т. Д., Добавив больше операторов if.

Answer 6

memcmp должен останавливаться на первом неравном байте, поэтому длина должна быть большой, то есть до конца буфера. Тогда единственный способ вернуть ноль - это перейти в конец буфера.

(Кстати, я склоняюсь к сортировке слиянием. Она стабильна и хорошо себя ведет.)

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. Используйте функцию сортировки, которая поддерживает дополнительный ввод. Либо sort_r, как предложено Адамом , либо домашнее решение (которое я рекомендую в качестве упражнения для студента и не рекомендую в реальной жизни). В любом случае дополнительные данные, вероятно, являются указателем на конец буфера.

Answer 8

Вы можете использовать функторы (указать длину для конструктора функтора) или Boost.Lambda (использовать длину на месте).