时间戳

首页 > 解决方案 > 使用 STL 的 C++ 中的比较器函数错误

c++ - 使用 STL 的 C++ 中的比较器函数错误

问题描述

除了与“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

对于以上所有字符串hamiltion距离为3，所以我希望数据排序为

00111
01110
11100

我得到调试断言，我知道比较器函数不是严格的弱排序。任何人都可以提供线索我上面定义为的比较器函数中的错误是bWeaponStringComparision什么？

标签： c++stl

解决方案

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

就目前而言，对于前两个项目，你得到的第一个比第二个少，第二个比第一个少

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

两者都是真实的。

如果您想要严格的弱排序，则不能让小于运算符告诉您 x < y 和 y < x。

这就是问题所在。

实际上，您需要三个属性：

  • 对于 S 中的所有 x，不是 x < x（非自反性）的情况。
  • 对于 S 中的所有 x, y，如果 x < y 则不是 y < x（不对称）。
  • 对于 S 中的所有 x、y、z，如果 x < y 且 y < z 则 x < z（传递性）。

（严格来说，无与伦比的项目也具有传递性）。您的代码打破了不对称（至少）。值得为每个测试用例添加一个小测试用例来清除这些东西。

推荐阅读