2016-01-26 45 views
3

所以,我有一個任務,寫一個程序來測試不同排序算法的速度,其中一個是很好的qsort。我需要傳遞一個比較器給它,但不是它期望的那個,但是一些布爾值a-la std::less,而且我知道要使用它以便qsort接受它,我需要實際上通過它,如less(b, a) - less(a,b) --- this方式,它有[-1; 1]的範圍,併產生我所需要的。如何將比較器a-la std :: less傳遞給C風格的Qsort?

問題是這樣的:我不知道如何實際做到這一點!我試圖使用lambda ---和(因爲我需要捕獲比較和qsort不能處理這個)失敗。我試圖創建另一個函數比較我轉換爲qsort的:

int make_comparator(const void* a, const void* b) { 
    return (int)comp(*(int*)b, *(int*)a) - (int)comp(*(int*)a, *(int*)b); 
} 

但我對如何實際的comp傳遞給它不知道(因爲我不能只寫qsort(..., make_comparator(comp, a, b)),可以嗎?)。我試圖使用模板來通過comp,但無法弄清楚如何。

因此,我已經掙扎了一個小時,而且我也沒有接近解決方案。什麼是正確的方法來做到這一點?

+1

您必須使用非捕獲lambda或普通指針指向**非** - 成員函數,就是這樣。 –

+0

@JoachimPileborg,非捕獲的lambda無法使用傳入我的函數的'comp'參數,而這又會使用'qsort',所以這不是選項。 非成員函數也不是一個選項,因爲,同樣,我想不出一種方法來傳遞我的'comp'到它。 我錯過了什麼嗎? – Akiiino

+0

查找'qsort_r'。不是標準的,但描述會告訴你更多關於你想要做什麼。 –

回答

2

你可以嘗試這樣的事情。 qsort_friendly_comparator只是作用於比較對象的包裝。唯一的缺點是您必須手動指定比較器類型及其參數類型。

#include <functional> 
#include <cstdlib> 
#include <cstdio> 

// Assumes Comparator take two arguments of the same type and returns a bool. 
// Have to manually specify the ArgType because it is tricky to deduce without 
// excessive template magic. 
template <typename Comparator, typename ArgType> 
int qsort_friendly_comparator(const void *first, const void *second) 
{ 
    Comparator comp; 

    return (int)comp(*(ArgType*)second, *(ArgType*)first) - 
     (int)comp(*(ArgType*)first, *(ArgType*)second); 
} 

int main() { 
    int data[] = {2, 1, 3, 0}; 

    qsort(data, 
     /*num_elem=*/4, 
     /*size_of_elem=*/sizeof(int), 
     &qsort_friendly_comparator<std::less<int>, int>); 

    for (int i = 0; i < 4; i++) { 
    printf("%d ", data[i]); 
    } 
    printf("\n"); 
} 
+0

哇,太棒了!我不敢相信這很容易。我會嘗試一下,如果一切正常,我會接受 – Akiiino

1

您無法通過qsortcmp更改爲make_comparator。你最好的選擇是有一個功能指針設置爲正確的功能。

bool (*comp)(int a, int b) = nullptr; 

int make_comparator(const void* a, const void* b) { 
    return (int)comp(*(int*)b, *(int*)a) - (int)comp(*(int*)a, *(int*)b); 
} 

後來打電話qsort之前設置comp到一個有效的函數指針

comp = <some function pointer>; 

qsort(ptr, count, size, make_comparator); 

如果選擇採用這種做法,請務必在make_comparator添加檢查,以防止調用cmp時沒有將其設置爲一個有效的功能。

int make_comparator(const void* a, const void* b) { 
    if (comp == nullptr) 
    { 
     // Deal with error 
    } 
    return (int)comp(*(int*)b, *(int*)a) - (int)comp(*(int*)a, *(int*)b); 
} 
+0

我需要做什麼'布爾(* comp)(int a,int b)= nullptr; '能夠比較任何類型,而不僅僅是'int'?我可以使用模板嗎? – Akiiino

+0

@Akiiino,如果你想使用模板,你可以使用'std :: less'。那麼,就沒有必要擁有'comp'了。 –