使用快速排序對可能包含無窮大的容器進行排序是否安全？

Question

我已經意識到，爲了快速排序工作，所有的無窮大必須相等。

換言之，這樣的繞圈是不夠的：

class Entity 
{ 
public: 
    float value() const; 
    bool valueIsInfinite() const; 
}; 

class Criterium 
{ 
    bool operator()(Entity left, Entity right)const 
    { 
     if (left.valueIsInfinite()) 
      return false; 
     return left.value() < right.value(); 
    } 
} 

const Criterium criterium; 
QVector<Entity> container; 

qSort<container.begin(), container .end(), criterium> 

此排序失敗，因爲不是所有的無窮根據繞圈是相等的。不平等取決於實體進入運營商的順序。我發現，這樣的排序失敗了。

我需要的是這樣的：

class Criterium 
{ 
    bool operator()(Entity left, Entity right)const 
    { 
     if (left.valueIsInfinite() && right.valueIsInfinite()) 
      return false; 
     if (left.valueIsInfinite() && !right.valueIsInfinite()) 
      return false; 
     if (!left.valueIsInfinite() && right.valueIsInfinite()) 
      return true; 
     return left.value() < right.value(); 
    } 
} 

但是，假如不是

float Entity::value() const; 
    bool Entity::valueIsInfinite() const; 

方法，我想用剛

float Entity::value() const; 

，並讓它返回

std::numeric_limits<float>::infinity(); 

在情況下

bool Entity::valueIsInfinite() const; 

將返回true。

現在我測試了這種方法，它似乎工作。但我擔心無限可能出現的其他方式。例如：

float otherInfinity = exp(std::numeric_limits<float>::infinity()); 

這個無限似乎是一樣的。但我想確定。我知道C++標準沒有提到浮點算法實現的細節，但是如果我使用gcc，在所有情況下都是安全的嗎？我的意思是在gcc中創建的所有infinities都是平等的嗎？對可能包含在不同場合出現的無窮大的浮子集裝箱進行分類是否安全？

Answer 1

沒有NaN的存在，無窮大的罰款與常規操作<：

• +∞< +∞是假的：<是漫反射的;
• 如果+∞< x爲真，那麼x < +∞對於非無窮大值爲假：<是反對稱的;
• 如果+∞< x爲真且x < y爲真，則+∞< y爲真：<是傳遞性的;
• 如果+∞與x無法比較（不小於，不大於），並且x與y不可比，那麼+∞與y無法比較：顯示等價性的變換性。

（類似性質的有效期爲-∞）

鑑於彩車這些屬性operator<沒有的NaN是一個嚴格弱序，因而適用於標準庫風格的排序操作。

但是，對於NaN，反對稱性被破壞：NaN < 1是錯誤的，並且NaN也是錯誤的。您可以通過之前或全部非NaN的訂貨後，將NaN所有以類似於你提出的戰略的方式解決這個問題：

struct Criterion 
{ 
    bool operator()(Entity left, Entity right)const 
    { 
     // NaNs come before non-NaNs 
     if (isnan(left.value()) && isnan(right.value())) 
      return false; 
     if (!isnan(left.value()) && isnan(right.value())) 
      return false; 
     if (isnan(left.value()) && !isnan(right.value())) 
      return true; 
     return left.value() < right.value(); 
    } 
} 

（isnan可以在C++ 11標準庫中找到，還是蠻實施就像return x != x;）

由此，我們得到NaN < 1爲真，並且1 < NaN爲假，而其他屬性仍然成立。

Answer 2

如果使用這樣的：

bool operator()(Entity left, Entity right)const 
{ 
    return !(left.valueIsInfinite() && right.valueIsInfinite()) 
     && left.value() < right.value(); 
} 

然後infinites被視爲同一順序的，因爲沒有來之前一個又一個......