Сбой в std::sort - сортировка без строгого слабого порядка

Question

Я пытаюсь отсортировать вектор предметов. Как указано в комментариях к коду, порядок должен быть:

Участники с большим количеством очков действия (mAp) иди первый. Когда есть галстук, участники с одинаковым расположением (mDisposition) как инициатор битвы (mBattleInitiator) иди первый.

Следующий код (упрощенный пример) дает сбой в 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;
}

Я смотрел на другие ответы по теме. Большинство из них просто говорят "реализовать это как a > b", что не сработает в моем случае. Есть некоторые, которые кажутся актуальными, но не помогают мне:

• /questions/20546224/razve-stl-sortirovka-ne-trebuet-strogogo-slabogo-poryadka-dlya-rabotyi/20546250#20546250 - говорит, что будут работать другие стандартные алгоритмы, но не приводит никаких конкретных примеров.
• /questions/23768298/sortirovannyij-nabor-bez-strogoj-slaboj-uporyadochennosti/23768310#23768310 - сбивает с толку, кажется излишним

Какой самый простой способ добиться того, что мне нужно?

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 элемента не удовлетворят этому условию, алгоритму сортировки разрешено сравнивать элемент с самим собой. Этот тест вернется true в этом случае нарушается одно из условий строго-слабого упорядочения, заключающееся в том, что элемент должен сравниваться равным самому себе (т.е. 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, которая сканирует массив слева направо, пока значения элементов <значения pivot, и сканирует массив справа налево, пока значения элементов > Сводные значения. Эти сканы рассчитывают на то, что обнаружение элемента value = pivot value остановит сканирование, поэтому нет проверки для сканирования за пределами массива. Если пользователь предоставил функцию сравнения меньше, чем возвращает в случае равных элементов, то любое из сканирований может выйти за границы массива и вызвать сбой.

В случае отладочной сборки можно выполнить тестирование функции сравнения пользователя, чтобы убедиться, что сравнение меньше и не меньше или равно, но для сборки выпуска целью является скорость, поэтому эти проверки не выполняются.