2011-03-25 85 views
1

請考慮以下代碼。 它應該按字典順序排列整數向量,即 ,即首先按第一列,然後按第二列排序,依此類推。 在我的應用程序中,我只關心8列中的前6列 所以在前6列的值相等的情況下返回true。使用STL排序時的比較方法問題

它引起了問題(分段故障)。它正在爲1000個數據工作,它崩潰了1001. 示例代碼是玩具,但排序是相當複雜的程序的一部分。 經過長時間的調試,我發現這是造成麻煩的原因。 該程序嘗試使用一個(1,0,...,0)條目對所有零的數組進行排序。

請任何C++專家,你能告訴我原始(列出)程序有什麼問題嗎?

我在32位和32位Windows上編譯32位和64位Linux和Visual Studio。 它總是崩潰。在評論發生變化後,一切似乎都很好。

#include <iostream> 
#include <vector> 
#include <algorithm> 

using namespace std; 

const int COLS = 8; 

bool compare (const vector<int>& r1, const vector<int>& r2) 
{   
    for (int i = 0; i < COLS-2; i++) 
    if (r1[ i ] != r2[ i ]) 
     return (r1[ i ] < r2[ i ]); 
    return true; //if true is replace by r1[ COLS-1 ] < r2[ COLS-1 ] then is OK 
}; 

int main(int argc, char **argv) 
{  
    int Na = 20; 
    vector< vector<int> > v(Na); 

    for (int r = 0; r < v.size(); r++) 
     v[r].resize(COLS, 0); 
    v[0][0] = 1; 

    cout << "Sorting\n"; 
    sort(v.begin(), v.end(), compare); 
    cout << "Eof Sorting\n";   

    return 0; 
} 
+0

代碼註釋已經說明了問題。排序需要比較少於,而不是平等。 – 2011-03-25 22:44:43

+1

@波Persson:這不會導致內存訪問衝突,只是一個不合邏輯的結果。 – Puppy 2011-03-25 22:46:10

+1

@DeadMG - 如果std :: sort無法找到一致的排序,它可能會出現橫行。雖然取決於實施。 – 2011-03-25 22:49:01

回答

4

我想你是在吹煙。排序函數以遞歸方式實現,所以如果您對元素之間的順序關係給出不一致的答案,算法可能無法終止。

0

我希望你跑出了你的一個向量的結尾,在發佈版本中會有未定義的結果。

在linux上,使用優秀的Valgrind運行你的程序。

您也可以讓你的代碼,以便它只是檢查向量中的實際插槽,如:

bool compare (const vector<int>& r1, const vector<int>& r2) 
{ 
    const int max = std::min(r1.size(),r2.size()); 
    for (int i = 0; i<max; i++) 
    if (r1[ i ] != r2[ i ]) 
     return (r1[ i ] < r2[ i ]); 
    return r1.size() < r2.size(); 
}; 

但是,如果你期待插槽的確切數目那麼這是一個邏輯錯誤,使您的比較功能忽略它並不一定是一個好的解決方案。

+0

在真正的程序中有斷言大小是相等的。 – rycho 2011-03-25 23:32:20

4

當輸入相同時,您的比較功能必須返回false,而不是true

+0

那就對了。但我仍然在思考爲什麼,即不完全理解它 – rycho 2011-03-25 23:35:41

+0

@ user677514,我的賭注是在Jollymorphic的答案。 – 2011-03-26 00:00:54

2

的問題是你比較功能:

bool compare (const vector<int>& r1, const vector<int>& r2) 
{   
    for (int i = 0; i < COLS-2; i++) 
    if (r1[ i ] != r2[ i ]) 
     return (r1[ i ] < r2[ i ]); 
    return true; //if true is replace by r1[ COLS-1 ] < r2[ COLS-1 ] then is OK 
}; 

如果元素相等表達r1 < r2false - 但在相等的情況下(在你的情況下,如果前6個整數相等)返回true

1

這不一定與問題(它不會導致崩潰)相關,但代碼跳過一列。代碼比較6(8-2)列,然後(如果使用未註釋的代碼),它會比較最後一列。倒數第二個沒有檢查。但是,這可能是意圖......如果是這樣,但如果代碼必須存在任何時間,評論可能會很好。

1

如果你想在字典順序,你可以使用標準庫進行排序:

bool compare (const vector<int>& r1, const vector<int>& r2) 
{ 
    return std::lexicographical_compare(r1.begin(), r1.begin()+6, r2.begin(), r2.begin()+6); 
}