排序中的<运算符断言无效

Question

我正在尝试实现一个简单的比较器,用于根据数组"_vec"中的值对索引进行排序.我收到"无效<运营商"运行时错误消息.我无法理解以下代码有什么问题:

class Compare{
vector<int>& _vec;
public:
    Compare(vector<int>& vec) : _vec(vec) {}
    bool operator()(size_t i, size_t j){
        if(_vec[i] != _vec[j])
        return _vec[i] < _vec[j];
        else
        return (double)rand()/RAND_MAX < 0.5; 
    }
};

我正在使用以下函数调用:

sort(inds.begin(),inds.end(),Compare(vals));

其中inds只是一个包含索引从1到15(比如说)的数组,而vals是长度为15的数组,其中包含一些我希望计算其排序索引的值.总体目标是在val中的两个(或更多)条目相等时随机化排序顺序.有帮助吗？

Answer 1

std::sort()期望比较操作稳定 - 如果比较两个项目时返回特定结果,则比较必须返回相同的结果,如果稍后再次比较这些项目.当你返回一个随机值时,显然不一定会持有.

C++ 03 25.3/4"排序和相关操作"说:

如果我们将equiv(a,b)定义为!comp(a,b)&&!comp(b,a),则要求comp和equiv都是传递关系:

• comp(a,b)&& comp(b,c)意味着comp(a,c)
• equiv(a,b)&& equiv(b,c)意味着equiv(a,c)

[注意:在这些条件下,可以证明

• 等价是一种等价关系
• comp引起由等价确定的等价类的明确定义的关系
• 诱导关系是严格的总排序.

- 尾注]

为澄清,表28定义了等价关系:

== 是等价关系,即它满足以下属性:

• 对于所有a,a == a.
• 如果a == b,那么b == a.

所以你的Compare()操作不会产生等价关系.

获得断言而不是随机丢失数据真是太好了.

当两个(或多个)条目_vec相等时,解决排序顺序随机化问题的一种方法是构成这些索引的随机值,并在index => random value或其他值的映射中跟踪这些随机值.只需确保以这样的方式跟踪和使用这些随机值,即保持的传递和等价属性Compare().