std::sort 中的崩溃 - 没有严格弱排序的排序

Question

我正在尝试对项目向量进行排序。如代码注释中所述，顺序应为：

行动点数多（mAp）的参赛者先行。当出现平局时，与战斗发起者（mBattleInitiator）具有相同倾向（mDisposition）的参与者先行。

以下代码（简化示例）在 macOS 上崩溃，可能是由于我的排序实现不正确：

#include <QtCore>

class AiComponent
{
public:
    enum Disposition {
        Friendly,
        Hostile
    };

    AiComponent(Disposition disposition) : mDisposition(disposition) {}
    ~AiComponent() { qDebug() << "Destroying AiComponent"; }

    Disposition mDisposition;
};

class BattleManager
{
public:
    BattleManager() : mBattleInitiator(AiComponent::Hostile) {}

    class Turn {
    public:
        Turn() : mAp(1) {}

        Turn(QSharedPointer<AiComponent> aiComponent) :
            mAiComponent(aiComponent),
            mAp(1)
        {
        }

        Turn(const Turn &rhs) :
            mAiComponent(rhs.mAiComponent),
            mAp(1)
        {
        }

        QSharedPointer<AiComponent> mAiComponent;
        int mAp;
    };

    void addToTurnQueue(QSet<QSharedPointer<AiComponent>> aiComponents);

    AiComponent::Disposition mBattleInitiator;
    QVector<Turn> mTurnQueue;
    Turn mActive;
};

void BattleManager::addToTurnQueue(QSet<QSharedPointer<AiComponent> > aiComponents)
{
    foreach (auto aiComponent, aiComponents) {
        mTurnQueue.append(Turn(aiComponent));
    }

    // Sort the participants so that ones with more action points (mAp) go first.
    // When there is a tie, participants with the same disposition (mDisposition)
    // as the initiator of the battle (mBattleInitiator) go first.
    std::sort(mTurnQueue.begin(), mTurnQueue.end(), [=](const Turn &a, const Turn &b) {
        if (a.mAp > b.mAp)
            return true;

        if (a.mAp < b.mAp)
            return false;

        // At this point, a.mAp is equal to b.mAp, so we must resolve the tie
        // based on mDisposition.
        if (a.mAiComponent->mDisposition == mBattleInitiator)
            return true;

        if (b.mAiComponent->mDisposition == mBattleInitiator)
            return false;

        return false;
    });
}

int main(int /*argc*/, char */*argv*/[])
{
    BattleManager battleManager;

    for (int i = 0; i < 20; ++i) {
        qDebug() << "iteration" << i;

        QSet<QSharedPointer<AiComponent>> participants;

        AiComponent::Disposition disposition = i % 2 == 0 ? AiComponent::Hostile : AiComponent::Friendly;
        QSharedPointer<AiComponent> ai(new AiComponent(disposition));
        participants.insert(ai);

        battleManager.addToTurnQueue(participants);
    }

    // This should print (1 1), (1 1), ... (1 0), (1 0)
    foreach (auto turn, battleManager.mTurnQueue) {
        qDebug() << "(" << turn.mAp << turn.mAiComponent->mDisposition << ")";
    }

    return 0;
}

我已经研究了关于该主题的其他答案。他们中的大多数人只是说 "implement it as a > b"，这对我来说是行不通的。有一些看起来相关但对我没有帮助：

- 表示其他标准算法也可以工作，但未提及任何具体示例
- 令人困惑，似乎有点矫枉过正

实现我所追求的目标的最简单方法是什么？

Answer 1

我将结束您代码中的注释并解释它有什么问题（如果有的话），以及您将如何解决它。

// Sort the participants so that ones with more action points (mAp) go first.

到目前为止还不错

// When there is a tie, participants with the same disposition (mDisposition) as the initiator of the battle (mBattleInitiator) go first.

如果两个参与者都与发起者有相同的倾向怎么办？即使您可以保证没有 2 个元素满足此条件，也允许排序算法将元素与自身进行比较。在那种情况下，此测试将 return true，违反 strict-weak 排序的条件之一，即元素必须与自身比较相等（即 compare(a,a) 必须始终是假的）。

也许相反你想说如果a与始作俑者有相同的倾向，而b没有，那么a应该被认为小于b.这可以编码为：

return dispositionOfA == mBattleInitiator && dispsitionOfB != mBattleInitiator;

所以你的完整测试应该是这样的：

if (a.mAp > b.mAp)
    return true;
if (a.mAp < b.mAp)
    return false;

return a.mAiComponent->mDisposition == mBattleInitiator &&
       b.mAiComponent->mDisposition != mBattleInitiator;

Answer 2

目前还没有解释崩溃的原因。 std::sort 的大多数实现都基于快速排序，特别是 Hoare 分区方案，只要元素值 < 枢轴值，它就从左向右扫描数组，只要元素从右向左扫描数组值 > 枢轴值。这些扫描依赖于这样一个事实，即找到元素值 = 枢轴值将停止扫描，因此不会检查是否扫描超出数组边界。如果用户提供的比较函数小于 returns 在元素相等的情况下为 true，则任一扫描都可能超出数组边界并导致崩溃。

在调试版本的情况下，可以对用户比较功能进行测试，以确保比较小于且不小于或等于，但对于发布版本，目标是速度，所以这些未执行检查。

std::sort 中的崩溃 - 没有严格弱排序的排序

Crash in std::sort - sorting without strict weak ordering

c++

sorting

strict-weak-ordering