Set::find()存储对象指针时异常：插入顺序影响查找结果

问题描述 #

使用std::set存储对象指针，自定义仿函数ptr_compare通过对象内容比较，但set::find()在不同插入顺序下表现不一致：按a1、a2、a3插入时能找到a2，按a1、a3、a2插入时找不到a2。

相关代码如下：

比较仿函数 #

template<class T> struct ptr_compare
{
    bool operator()(const T* lhs, const T* rhs) const
    {
        return *lhs < *rhs;
    }
};

样本类A #

class A {
  private:
    string str;
  public:
    A(string s)
    {
        str = s;
    }
    bool operator <(const A& obj) const
    {
        return this->str.compare(obj.get_str());
    }
    
    string get_str() const
    {
        return str;
    }
};

问题根源 #

问题不在指针比较的方式，而是类A的operator<违反了std::set要求的严格弱序规则。

std::string::compare()的返回值是int：

• 小于0：当前字符串小于参数字符串
• 等于0：两个字符串相等
• 大于0：当前字符串大于参数字符串

但你直接把这个int返回给bool类型的operator<，会导致：

• 当当前字符串大于参数字符串时，compare()返回正数，转换成bool是true，这就会让a < b和b < a同时为true，完全破坏了严格弱序的要求。

std::set依赖严格弱序维护内部平衡树结构，一旦比较规则失效，容器行为就变成未定义的——不同插入顺序触发不同的未定义行为，便出现了有时能找到、有时找不到的情况。

修复方案 #

修改类A的operator<，确保它正确实现严格弱序：

方案1：直接使用字符串的<运算符 #

bool operator <(const A& obj) const
{
    return this->str < obj.get_str();
}

方案2：正确判断compare()的返回值 #

bool operator <(const A& obj) const
{
    return this->str.compare(obj.get_str()) < 0;
}

修正后，std::set的内部结构能正确维护，无论插入顺序如何，find()都能正常工作。

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