std ::排序比較元素爲空

Question

我有以下排序算法，它將std::vector的唯一armor_set指針排序。通過我的排序算法的某些屬性，它會窒息併發生未定義的行爲，最終將比較有效的lhs與rhs這是一個nullptr。

儘管多次移動算法，我一直無法辨別出問題。我覺得我錯過了一些關於這個算法如何工作的簡單規則。

任何幫助，將不勝感激。

std::vector<armor_set*> armor_sets; 

//insertion of unique armor sets here 

std::sort(armor_sets.begin(), armor_sets.end(), [](armor_set* lhs, armor_set* rhs) 
{ 
    auto lhs_collectible_count = collectible_mgr::get().count(lhs->needed_collectible); 
    auto rhs_collectible_count = collectible_mgr::get().count(rhs->needed_collectible); 

    if(lhs_collectible_count > 0 && rhs_collectible_count == 0) 
    { 
     return true; 
    } 
    else if(lhs_collectible_count == rhs_collectible_count) 
    { 
     return lhs->sort_index > rhs->sort_index; 
    } 
    else 
    { 
     auto lhs_collectibles_needed_count = lhs_collectible_count - lhs->collectibles_needed; 
     auto rhs_collectibles_needed_count = rhs_collectible_count - rhs->collectibles_needed; 

     return lhs_collectibles_needed_count > rhs_collectibles_needed_count; 
    } 
}); 

Answer 1

比較函數必須遵循嚴格弱排序。例如，如果我是排序函數，我給你兩個armor_set指針，問你「哪一個先到？」並返回一個表示哪個值首先出現的真/假值。然後我給你同樣的兩個armor_set指針，但這次改變項目的順序。我問你同樣的問題「哪個先到？」。然後您返回相同的真/假值。猜猜看 - 你輸了。

簡而言之，這是違反嚴格的弱排序。有沒有辦法a < b，並在同一時間b < a。看着你有點複雜的比較功能，我的猜測是你違反了這個規則。

如果您使用的是Visual Studio，那麼調試運行時確實會檢查這種排序違規行爲。比較函數被調用兩次，第一次使用A，B順序，第二次使用B，A順序。比較每個調用的返回值，並且如果存在違規，則會發生assert（）。

Answer 2

比較操作（lambada）是問題所在。 sort中的運算符應確保所定義的順序是嚴格的弱順序。即

1)For all x, it is not the case that x < x (irreflexivity). 
2)For all x, y, if x < y then it is not the case that y < x (asymmetry). 
3)For all x, y, and z, if x < y and y < z then x < z (transitivity). 
4)For all x, y, and z, if x is incomparable with y, and y is incomparable with z, 
    then x is incomparable with z (transitivity of incomparability). 

你的功能似乎錯過了它。例如：

armor_set* lhs{ 
lhs->needed_collectible=0; 
.... 
} 

armor_set* rhs{ 
lhs->needed_collectible=1; 
.... 
} 

當你調用compare(lhr, rhs)，它可能會返回true或false依賴於其他價值。當您撥打compare(rhs, lhs)時，請注意訂單不同，它將始終返回true。 compare(a,b)和compare(b,a)均不允許返回true，這違反了嚴格弱順序的屬性。

Answer 3

具體故障是缺少

if(lhs_collectible_count == 0 && rhs_collectible_count > 0) 
{ 
    return false ; 
} 

這應該是在第二或第三測試。