Ошибка функции компаратора в C ++ при использовании STL

Question

Я сравниваю две строки в дополнение к расстоянию Хэмминга от "00000".

std::vector<std::string> vecWeaponsRequired;

struct sHammingDistInfo {
        int iHammingDistance;
        int iIndexToWeaponsVector;
};

bool bWeaponStringComparision(std::string strLevel1Weapon, std::string strLevel2Weapon) {

    bool bFirstLevelStringLessThanSecond = false;

    for (unsigned int iIdx = 0; iIdx < strLevel1Weapon.length(); iIdx++) {
        if(strLevel1Weapon[iIdx] == strLevel2Weapon[iIdx]) {
            continue;
        }
        else {
            if(strLevel1Weapon[iIdx] < strLevel2Weapon[iIdx]) {
                bFirstLevelStringLessThanSecond = true;
                break;
            }
        }
    }

    return bFirstLevelStringLessThanSecond;


}


bool hammingDistLessThanOperator (sHammingDistInfo& lhs, sHammingDistInfo& rhs) {

    bool isLess = bWeaponStringComparision(vecWeaponsRequired[lhs.iIndexToWeaponsVector], vecWeaponsRequired[rhs.iIndexToWeaponsVector]);
    int iFirstStringLess  = 0;
    int iSecondStringLess = 0;
    if(isLess) {
        iFirstStringLess = 0;
        iSecondStringLess = 1;
    }
    else {
        iFirstStringLess = 1;
        iSecondStringLess = 0;
    }
    return std::tie(lhs.iHammingDistance, iFirstStringLess) < std::tie(rhs.iHammingDistance, iSecondStringLess);
}

// sort vector of hamming distance according to hamming distance.
std::sort(vecOfHammingDistance.begin(), vecOfHammingDistance.end(), hammingDistLessThanOperator);

Когда я запускаю приведенный выше код для следующих строк

11100
00111
01110

Для всех вышеперечисленных строковое расстояние равно 3, поэтому я хочу, чтобы данные сортировались как

00111
01110
11100

Я получаю отладочную версию, в которой я понимаю, что функция компаратора не является строгим слабым упорядочением. Может ли кто-нибудь дать понять, что является ошибкой в ​​моей функции сравнения, определенной выше как bWeaponStringComparision?

Answer 1

Не дав вам исправления, чтобы ответить на вопрос «может ли кто-нибудь дать подсказку, что является ошибкой в ​​моей функции сравнения»:

В нынешнем виде, для первых двух предметов вы получаете первый меньше второго, а второй меньше первого

hammingDistLessThanOperator(vecOfHammingDistance[0], vecOfHammingDistance[1])
hammingDistLessThanOperator(vecOfHammingDistance[1], vecOfHammingDistance[0])

оба истинны.

У вас не может быть оператора меньше, чем вам говорят x

Вот в чем проблема.

На самом деле вам нужно три свойства :

• Для всех х в S это не тот случай, когда х <х (нерефлексивность). </li>
• Для всех x, y в S, если x
• Для всех x, y, z в S, если x

  (и, строго говоря, четвертое, что несопоставимые предметы также имеют транзитивность). Ваш код нарушает асимметрию (по крайней мере). Для каждого из них стоит добавить небольшой тестовый набор.

Answer 2

"Развертывание" tie и удаление дополнительных переменных дает

return isLess 
     ? lhs.iHammingDistance <= rhs.iHammingDistance 
     : lhs.iHammingDistance < rhs.iHammingDistance;

где немного понятнее, что если вы дадите ему одинаковые строки, результат зависит от порядка ваших аргументов.