首頁猿問如果比較功能不像運算符<那樣...

如果比較功能不像運算符<那樣，為什么std :: sort會崩潰？

C++ 算法與數(shù)據(jù)結(jié)構(gòu)

鴻蒙傳說 2019-12-05 16:05:37

以下程序是使用VC ++ 2012編譯的。#include <algorithm>struct A{ A() : a() {} bool operator <(const A& other) const { return a <= other.a; } int a;};int main(){ A coll[8]; std::sort(&coll[0], &coll[8]); // Crash!!!}如果我更改return a <= other.a;為，return a < other.a;則程序?qū)⒄＿\行，沒有例外。為什么？

查看完整描述

3 回答

慕桂英3389331

TA貢獻(xiàn)2036條經(jīng)驗獲得超8個贊

std::sort需要其滿足分揀機嚴(yán)格弱排序規(guī)則，這是解釋在這里

因此，您的比較器說，a < b當(dāng)a == b不遵循嚴(yán)格的弱排序規(guī)則時，該算法可能會崩潰，因為它將進(jìn)入無限循環(huán)。

反對回復(fù) 2019-12-05

小怪獸愛吃肉

TA貢獻(xiàn)1852條經(jīng)驗獲得超1個贊

xorguy的答案非常好。

我只是從標(biāo)準(zhǔn)中添加一些報價：

25.4排序及相關(guān)操作[alg.sorting]

為了使25.4.3中描述的算法無法正常工作，comp必須在值上引入嚴(yán)格的弱排序。

術(shù)語“ 嚴(yán)格”是指對非自反關(guān)系的要求（！comp（x，x）對于所有x），而術(shù)語“ 弱于”的要求不如總訂購的要求強，但要強于部分訂購的要求。。

所以xorguy很好地解釋了這一點：您的comp函數(shù)說，a < b當(dāng)a == b哪個不遵循嚴(yán)格的弱排序規(guī)則時...

反對回復(fù) 2019-12-05

開滿天機

TA貢獻(xiàn)1786條經(jīng)驗獲得超13個贊

您必須詳細(xì)了解它要檢查的內(nèi)容，但是標(biāo)準(zhǔn)的排序例程旨在非常非?？斓剡\行，因此它們不必檢查您所做的任何事情就可以了，而只是依靠它。如果您的比較返回不可能的結(jié)果，那么將不可能發(fā)生的事情-說它得到了一些比較的結(jié)果，并將其用作查看位置的索引，只有它“知道”可能的值并“知道”結(jié)果引用將存儲在有效存儲中，因此只需將其提取即可。Kaboom：SIGSEGV運氣不錯。如果運氣不好，它將無聲地管理您的數(shù)據(jù)

反對回復(fù) 2019-12-05