C++中std::set自定义比较器实现按F值排序与坐标判重的问题

核心问题分析 #

你的代码存在两个致命问题导致运行结果不符合预期：

1. 测试用例中的比较器未正确实现坐标判重逻辑：你写的判断条件if(_lhs == _rhs)是直接比较std::pair<Node*, int>本身，也就是比较Node指针地址和F值，完全没有解引用指针比较Node的坐标属性，导致坐标相同但指针不同的元素被判定为不同元素，重复插入。
2. 原比较器不满足严格弱序要求：就算修正了坐标判重逻辑，当两个节点坐标不同但F值相同时，comp(a,b)和comp(b,a)都会返回false，std::set会将二者判定为等价元素，只会保留第一个插入的，导致F值相同的不同坐标节点丢失。

解决方案 #

修改比较器逻辑，在F值相等时追加坐标比较，既保证严格弱序要求，又能实现坐标判重的需求：

• 坐标相同的元素：双向比较都返回false，std::set判定为同一元素，不会重复插入
• 坐标不同的元素：优先按F值排序，F值相同则按坐标排序，保证任意两个不同元素的比较总有一个方向返回true，满足严格弱序

修改后的比较器代码 #

struct NodeComparator
{
    bool operator()(const NodePair &_lhs, const NodePair &_rhs) const
    {
        if (_lhs.first == nullptr || _rhs.first == nullptr)
            return false;
        // 坐标相同直接返回false，实现判重逻辑
        if (*_lhs.first == *_rhs.first) 
            return false;
        // 优先按F值排序
        if (_lhs.second != _rhs.second)
            return _lhs.second < _rhs.second;
        // F值相同则按坐标排序，保证严格弱序
        const Node& lnode = *_lhs.first;
        const Node& rnode = *_rhs.first;
        if (lnode.x != rnode.x)
            return lnode.x < rnode.x;
        if (lnode.y != rnode.y)
            return lnode.y < rnode.y;
        return lnode.z < rnode.z;
    }
};

同时记得给测试用例中的Node类加上你之前定义的operator==友元重载，保证坐标比较逻辑生效。

修改后运行代码即可得到你预期的输出：坐标相同的n4、n6不会被插入，F值为20的n5可以正常插入，整体按F值从小到大排序。

内容的提问来源于stack exchange，提问作者Rafael Rey