在與多個字段比較時提供嚴格的排序

如何在具有大量可比字段的對象之間提供嚴格的排序？在與多個字段比較時提供嚴格的排序

假設你有兩個對象x和你有比較y，每3個字段（A，B，C）

bool less(x, y) 
    return x.a < y.a || x.b < y.b || x.c < y.c

好，但這提供弱排序。如果x.a < y.a和y.b < x.b，less(x,y)爲真，less(y, x)也是如此。

我習慣寫

bool less(x, y) 
    return x.a < y.a || (x.a == y.a && x.b < y.b)

但它開始變得非常難看，一旦領域所涉及的數量增長。

bool less(x, y) 
    return x.a < y.a || 
     (x.a == y.a && x.b < y.b) || 
     (x.a == y.a && x.b == y.b && x.c < y.c) || 
     (x.a == y.a && x.b == y.b && x.c == y.c && x.d < y.d);

有人有更好看的算法嗎？

來源

2016-07-25 UmNyobe

我想你需要定義什麼是最重要的領域，什麼是較少的。訂購應該（我認爲）要精確確定。基本上，你首先檢查什麼屬性，什麼是第二，什麼是第三？ –

我很想這樣做，但由於問題的性質，比較*必須*考慮每個領域的某種方式 – UmNyobe

另一種選擇是創建一個函數，對三個（或四個或十個）屬性給你一個值，* *是你比較的。類似於'val_to_compare = 1 * a + 10 * b + 23 * c'。這給你一種附加權重的方法。 –

如果您使用的是C++ 11或更高版本，那麼獲取SWO無需親手寫出就可以獲得很好的技巧。您可以使用std::tuple來打包您的成員，std::tuple將operator<作爲字典順序排列。

所以，你可以這樣寫

struct foo { 
    int x, y, z; 

    bool operator<(const foo& rhs) const { 
     return std::tie(x, y, z) < std::tie(rhs.x, rhs.y, rhs.y); 
    } 
};

和struct foo將字典順序由X，Y，Z進行比較。這仍然是很多寫的，所以你可以改善它有點

struct foo { 
    int x, y, z; 

    auto tied() const { 
     return std::tie(x, y, z); 
    } 

    bool operator<(const foo& rhs) const { 
     return tied() < rhs.tied(); 
    } 
};

這樣可以節省很多，如果你有很多成員打字的，但它假定C++ 14（針對C++ 11 ，你必須手寫出返回類型tied）。

來源

2016-07-25 10:09:24 Xarn

我通常這樣做：

bool operator< (type x, type y) { 
    if (x.a < y.a) return true; 
    if (x.a > y.a) return false; 

    if (x.b < y.b) return true; 
    if (x.b > y.b) return false; 

    return x.c < y.c; 
}

這提供了硬序和儘可能多的元素，你不關心每個元素越來越多的開銷延伸。

來源

2016-07-25 10:00:45

在與多個字段比較時提供嚴格的排序

回答

相關問題