memcmp sort

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

Есть ли причина, по которой вы не можете обнулить нулевые буферы?

Если нет, так как вы используете 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 2

Можете ли вы уложить указатель + длины в структуру и передать указатель этой структуры как void *?

Answer 3

С станд :: сортировать, вы можете использовать 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 

EDIT: от комментариев предложений (I думаю, обе строки в общем буфере):

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 4

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

Answer 5

Я не понимаю, о чем вы просите. Но я буду стараться, если предположить, что

• У вас есть один буфер
• У вас есть массив указателей некоторого рода, которые были обработаны в некотором роде, так что некоторые или все его содержимое указывают в буфер

То есть код, эквивалентный:

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

Answer 6

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

(BTW, я склоняюсь к сортировки слиянием сам. Это стабильный и хорошо себя вели.)

Answer 7

С помощью функции C qsort(), нет, нет никакого способа, чтобы передать длину к вашей функции сравнения без использования глобальной переменная, что означает, что она не может быть выполнена поточно-безопасным способом. Некоторые системы имеют qsort_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 8

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

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 операторов.