为什么C++ set的两种自定义比较器会出现不同的插入行为？

问题原因分析 #

这一现象是由std::set的等价判断逻辑、以及有序容器对比较器的严格弱序要求共同导致的：

• std::set不会用==运算符判断两个元素是否重复，而是基于传入的比较器comp做等价判定：如果!comp(a,b) && !comp(b,a)的结果为true，就认为a和b是等价元素，不会重复插入。

第一种比较器（<）的情况 #

你的比较器仅判断a.weight < b.weight：
当两个sub_tree实例的weight均为96时：

• comp(a,b)即96 < 96，结果为false
• comp(b,a)即96 < 96，结果也为false
  因此会触发等价判定，set认为两个元素重复，仅保留第一个插入的实例，哪怕二者的nodes成员不同——因为你的比较器逻辑中根本没有对nodes字段做判断。

第二种比较器（<=）的情况 #

首先要明确：用<=作为std::set的比较器是错误行为，违反了严格弱序的核心要求，严格弱序要求对任意元素x，必须满足comp(x,x) == false，而x<=x显然为true，这会导致set的行为出现异常。
此时对于两个weight均为96的实例：

• comp(a,b)即96 <= 96，结果为true
• comp(b,a)即96 <= 96，结果也为true
  因此!comp(a,b) && !comp(b,a)的结果为false，set会判定二者不是等价元素，所以两个实例都会被插入。但这种写法是不符合规范的，后续调用set的查找、遍历等接口都可能出现未定义行为。

正确实现方案 #

如果你希望weight相同的情况下，按nodes内容区分不同元素，只需要把nodes字段加入比较逻辑即可，示例如下：

bool comp(const sub_tree& a, const sub_tree& b)
{
    if (a.weight != b.weight) {
        return a.weight < b.weight;
    }
    // weight相同的情况下比较nodes内容
    return a.nodes < b.nodes;
}

内容的提问来源于stack exchange，提问作者Paawan Angra