關於qsort的compare函數小問題

小弟資質愚鈍，腦筋很不靈光
想知道用qsort時
int compare(const void *a, const void *b)
{
    return (*(int*)a) - (*(int*)b);
}
...

瀏覽完整內容，請先 註冊 或 登入會員

snowflying

這兩個餵給內建的 qsort，應該沒有差別吧?
有沒有完整的程式碼?

除了傳回值範圍之外沒有差別, 對 qsort 而言使用效果相同
建議你把能產生錯誤結果的程式碼貼上來
(通常能隔離出來的話你也抓得到問題所在了)

gitlab

差別在

1.      return (*(int*)a) - (*(int*)b);

複製代碼

可能會溢位

gitlab 大說的沒錯
對一個比對函數而言
這的確是會影響執行結果的最大差異

chevylin0802

inunu 發表於 2016-3-30 06:36 AM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

gitlab 大說的沒錯
對一個比對函數而言
這的確是會影響執行結果的最大差異 ...

...

瀏覽完整內容，請先 註冊 或 登入會員

gitlab

照標準 const void* 轉成 int* 是 undefined behavior

應該寫成
const int b = *(const int*) a

"實務上" int* 去掉 const 會有問題的"機率" ....幾乎是0
而且這也不是兩個函式的差別

碼農不要以管窺天，在任何情況下溢位都是嚴重錯誤，
況且32-bit int 要溢位滿容易的啊，隨便想想就一堆例子
- 學校作業、OJ、競賽一定會有的corner case
- 遊戲的經驗值、金幣、存款
- 不小心把 unsigned 當 signed 使用的時候，例如 timestamp 、ip、buffer 長度
- 矩陣乘法或指數運算
更別說其實 int 可能只有 16-bit 了

話說回來, compare function 這個寫法

1. 
   
2. int cmp( const void *lhs, const void *rhs){
   
3.   const int left   = *(const int*) lhs;
   
4.   const int right = *(const int*) rhs;
   
5.   return left - right;
   
6. }

複製代碼

非常簡單漂亮，可以說是人人皆知的idiom，
但因為他有溢位風險，其實是不安全的炫技寫法，知道即可，不太建議使用。

要嘛老老實實的寫

1. if( left < right ) return -1;
   
2. if( left > right ) return 1;
   
3. return 0;

複製代碼

或是更簡潔地：

1. return (left>right) - (left<right);

複製代碼

...

瀏覽完整內容，請先 註冊 或 登入會員

我是覺得一般數值運算不包含 CF OF (借位溢位) 等 flags 的變化可能是教學重點
if() 最後會編譯成 jl je jg 這些指令, 在條件判斷時會帶入 flags, 產生正確的結果
平時使用任何運算都要處理溢位借位的確不太實際
只是這習題本身很可能是已經針對這問題所設計的
因此再去討論發生機率似乎有些離題

chevylin0802

gitlab 發表於 2016-3-30 02:31 PM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

照標準 const void* 轉成 int* 是 undefined behavior

應該寫成

如果你講的是DOS時代的C編譯器
確實還是有16位元整數
...

瀏覽完整內容，請先 註冊 或 登入會員

chevylin0802

inunu 發表於 2016-3-31 04:42 AM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

我是覺得一般數值運算不包含 CF OF (借位溢位) 等 flags 的變化可能是教學重點
if() 最後會編譯成 jl je jg ...

致使程式發生錯誤
...

瀏覽完整內容，請先 註冊 或 登入會員

gitlab

chevylin0802 發表於 2016-3-31 09:47 AM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

如果你講的是DOS時代的C編譯器
確實還是有16位元整數
不過現在還剩下誰在用

...

瀏覽完整內容，請先 註冊 或 登入會員

萬一他每一個傳入的數值本身都是錯的數值的時候呢？
還需要去管它溢位還是不溢位嗎？

這篇討論串一開始就明白指出在比較兩個 compare 函數的差異
Input validation 在實作上很重要沒錯, 但明顯離題, 恕不繼續討論