嚴格的弱排序混淆

我很困惑嚴格的弱排序以及如何在定義運算符<時使用它。我有一對夫婦結構的：嚴格的弱排序混淆

struct Plane 
{ 
    std::string name; 

    int xrudder; 
    int yrudder; 

    int wingwidgets; 

    bool hasLegacyEngine; 
}; 


struct Airport 
{ 
    bool securityCheck; 
    unsigned __int64 capacity; 

    std::vector<Plane> planes; 
};

，我想創造機場的std::set。我需要定義運算符<，它使用嚴格的弱排序，但我不確切地知道這意味着什麼和/或如何去做。

struct cmpless 
{ 
bool operator()(const Airport& left, const Airport& right) 
    { 
     //? 
    } 
}; 

std::set<Airport, cmpless> airportSet;

這是沒有意義的一個機場是「小於」另一個。只有機場根據他們的統計資料是平等的，這纔有意義。

如何確定我的運營商<的定義將遵循嚴格的弱排序？我如何開始考慮在這種情況下定義operator<？

如果可能的話，一個解釋的例子會很棒！

來源

2012-11-27 user974967

我看到你給每架飛機一個名字，但你的機場沒有任何名字。如果您給機場一個名稱，您可以使用詞法字符串比較，因爲它定義了嚴格的弱排序。 – Zeta

如果「沒有意義」一Airport來之前另一Airport然後使用std::set<Airport>沒有按也沒有意義。此容器利用訂單數量元素在O(log(n))操作中找到對象（其中n是容器的大小）。如果您只能通過身份識別對象，則可以實現的最佳複雜度爲O(n)。您可以使用std::find()或std::find_if()和其中一個序列容器的組合，例如std::vector<Airport>或std::deque<Airport>。

因爲你不需要在operator<()來定義的命令，它可能是合理的，只是把Airport s轉換一些爲了在std::set<Airport>定位他們的目的是通過使用不同的比較函數來完成對象比std::less<Airport>。不過，您目前在Airport對象中擁有的屬性看起來並不像合適的鍵。實際上，它們看起來好像都是可變的，也就是說，您可能不會想要std::set<Airport>，因爲您無法修改std::set<T>中的元素（至少，您不應該;是的，我意識到你可以玩mutable，但這必然會打破元素的順序）。

在此基礎上，我建議使用std::map<std:string, Airport>：在std::string用於識別機場，例如，使用像"JFK"的肯尼迪機場在紐約或"LHR"倫敦希思羅機場的代碼。方便的是，在字符串上已經定義了嚴格的弱順序。

也就是說，在一組對象O的定義strict weak order，你需要一個二元關係r(x, y)使得下列條件成立的元素x，y，並且z從O：

漫反射： r(x, x) == false
不對稱：r(x, y) == true意味着r(y, x) == false
傳遞：r(x, y) == true和r(y, z) == true意味着r(x, z) == true
不可比性：r(x, y) == false和r(y, x) == false和r(y, z) == false和r(z, y) == false意味着r(x, z) == false和r(z, x) == false

前三應該足夠簡單。最後一個有點奇怪，但實際上並不那麼難：基本思想是關係並不完全排序元素，而是將它們分組爲等價類。如果您認爲r的關係爲「小於」，那麼只表示如果x小於y或y小於x，則x和y是等效的。無與倫比的元素就是等價的。

標準容器以嚴格的弱順序工作，但例如std::set<T>和std::map<K, V>只保留一個版本的等效密鑰。它是好的，這是足夠的，但它往往是更簡單的只使用其是弱嚴格順序的總訂單，其中對於每對元件x和y要麼r(x, y) == true或r(y, x) == true的（但是，由於不對稱不能同時）。

來源

2012-11-27 00:42:06

「如果你可以通過身份識別對象只，就可以達到最佳的複雜度爲O（N）」，實際上，你可以使用一個基於散列的容器做得更好 – Bwmat

如何做一個哈希幫助你，如果你的測試是'is_identical （x，y）'？聲明相當精確：您可以詢問兩個對象是否相同，而不是更少。如果有其他屬性，你可能會做得更好。鑑於這些屬性似乎是可變的，儘管這看起來和它一樣好，因爲任何散列值都會改變。 –

你說得對，如果你不能下單，我想的更多的是你可以做什麼，而不是你所能做的只是測試身份。 – Bwmat

如果每個人都已經<定義你可以做一些類似於一個lexiographical順序：

struct cmpless 
    { 
    bool operator()(const Airport& left, const Airport& right) 
     { 
      return 
       left.securityCheck < right.securityCheck 
       || ((left.securityCheck == right.securityCheck 
        && left.capacity < right.capacity) 
        || (left.capacity == right.capacity 
         && left.planes < right.planes)); 
     } 
    };

來源

2012-11-27 00:23:17 Pubby

我可能是錯誤的 - 解析布爾表達式是不是我的最強點 - 但我認爲你的括號應該是：'返回 left.securityCheck dhavenith

我認爲dhavenith可能是正確的括號，但我不確定。你可以用他的建議來檢查你的答案，讓我知道你的想法嗎？ – user974967

找到了一個不錯的解決方案上musingstudio blog，以爲我在這裏分享，爲有需要的（即使迪特馬爾可能是正確的，一個地圖是不恰當的）下一個：

bool operator <(const T& rhs) const 
{ 
    if (a < rhs.a) 
    return true; 
    else if (rhs.a < a) 
    return false; 

    if (b < rhs.b) 
    return true; 
    else if (rhs.b < b) 
    return false; 

    // repeat for all child elements c, d, e etc 
    return false; 
}

來源

2017-06-19 19:04:01 jaba

嚴格的弱排序混淆

回答

相關問題