我正在尝试实现一个简单的比较器,用于根据数组"_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的数组,其中有一些值的排序索引我想计算。总体目标是当vals中的两个(或多个)条目相等时,随机化排序顺序。有什么帮助吗?
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)
[注意:在这些条件下,可以显示
- equiv是一个等价关系
- comp在equiv确定的等价类上引入了一个定义良好的关系
- 诱导关系是一个严格的全序
-尾注]
为了澄清,表28定义了一个等价关系:
==
是一个等价关系,即它满足以下条件属性:
- 对于所有a,a==a
- 如果a==b,则b==a
因此您的Compare()
操作不会产生等价关系。
获得断言而不是随机丢失数据是一种很好的方式。
当_vec
中的两个(或多个)条目相等时,解决随机化排序顺序的问题的一种方法是为这些索引组成一个随机值,并在索引=>随机值之类的映射中跟踪这些随机值。只要确保跟踪并使用这些随机值,就可以保持Compare()
的传递性和等价性。
std::sort
希望小于运算符提供传递性关系,即当排序看到A < B
为真且B < C
为真时,意味着A < C
也为真。
在您的实现中,传递性规则不成立:当两个项相等时,您随机告诉排序其中一个大于另一个。这将触发调试断言。
如果值相等,则返回false以修复此问题。