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

Question

I'm trying to sort a vector of items. As mentioned in the code comments, the ordering should be:

Participants 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.

The following code (simplified example) crashes on macOS, presumably due to my sort implementation being incorrect:

#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;
}

I've looked into other answers on the topic. Most of them just say "implement it as a > b", which won't work in my case. There are a few that seem relevant but don't help me:

• https://stackoverflow.com/a/16824720/904422 - says that other standard algorithms will work but doesn't mention any concrete examples
• https://stackoverflow.com/a/33508373/904422 - confusing, seems like overkill

What is the simplest way to achieve what I'm after?

Answer 1

I'll just go off of the comment in your code and explain what's wrong with it (if anything), and how you would fix it.

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

Good so far

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

What if both participants have the same disposition as the initiator? Even if you can guarantee that no 2 elements will satisfy this condition, the sort algorithm is allowed to compare an element against itself. This test would return true in that case, violating one of the conditions of a strict-weak ordering, which is that an element must compare equal to itself (i.e. compare(a,a) must always be false).

Perhaps instead you want to say that if a has the same disposition as the initiator, and b does not, then a should be considered less than b. This can be encoded as:

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

So your full test would look like this:

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

The reason for the crash hasn't been explained yet. Most implementations of std::sort are based on quick sort, specifically Hoare partition scheme, which scans an array from left towards the right as long as element values < pivot values, and scans the array from right towards the left as long as element values > pivot values. These scans are counting on the fact that finding an element value = pivot value will stop a scan, so there's no check for scanning beyond the boundaries of an array. If the user supplied less than compare function returns true in the case of equal elements, then either of the scans may go beyond the array boundaries and cause a crash.

In the case of a debug build, testing of the user compare function may be done to ensure that the compare is less than and not less than or equal, but for a release build, the goal is speed, so these checks are not performed.