除了比较“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

对于以上所有字符串,hammilion距离为3,因此我希望将数据排序为
00111
01110
11100

我得到调试断言,我知道比较器功能不是严格的弱排序。任何人都可以知道上面定义为bWeaponStringComparision的比较器函数中的错误是什么吗?

最佳答案

在不给您任何修复的情况下,回答以下问题:“任何人都可以提供线索,说明我的比较器函数中有什么错误”:

就目前而言,对于前两个项目,您得到的第一个要少于第二个,而第二个要小于第一个

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

两者都是真实的。

如果要严格的弱排序,则不能小于运算符告诉您x
这就是问题所在。

实际上,您需要three properties:
  • 对于S中的所有x,并非x
  • 对于S中的所有x,y,如果x (不对称)。
  • 对于S中的所有x,y,z,如果x (传递性)。

  • (严格来说,第四,不可比拟的项目也具有传递性)。
    您的代码(至少)打破了不对称性。
    值得为每个添加一个小的测试用例以清除这些问题。

    关于c++ - 使用STL的C++中的比较器功能错误,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/50099054/

    10-11 22:44
    查看更多