Я пытаюсь отсортировать вектор предметов. Как указано в комментариях к коду, порядок должен быть:
Участники с большим количеством очков действия (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», что не сработает в моем случае. Есть некоторые, которые кажутся актуальными, но не помогают мне:
Какой самый простой способ добиться того, что мне нужно?
Я просто уйду от комментария в вашем коде и объясню, что с ним не так (если что-нибудь), и как вы это исправите.
// 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;
Причина аварии пока не объяснена. Большинство реализаций std :: sort основаны на быстрой сортировке, в частности, на схеме разделов Hoare, которая сканирует массив слева направо, пока значения элементов < Сводные значения и сканирует массив справа налево, пока значения элемента> сводные значения. Эти сканы рассчитывают на то, что обнаружение элемента value = pivot value остановит сканирование, поэтому нет проверки для сканирования за пределами массива. Если пользователь предоставил функцию сравнения меньше, чем возвращает в случае равных элементов, то любое из сканирований может выйти за границы массива и вызвать сбой.
В случае отладочной сборки можно выполнить тестирование функции сравнения пользователя, чтобы убедиться, что сравнение меньше и не меньше или равно, но для сборки выпуска целью является скорость, поэтому эти проверки не выполняются.