代码之家 › 专栏 › 技术社区 › archaic

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

assertion operator-keyword sorting c++

6

archaic · 技术社区 · 13 年前

我正在尝试实现一个简单的比较器,用于根据数组“_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中的两个(或多个)条目相等时,随机化排序顺序。有什么帮助吗?

2 回复 | 直到 13 年前

1

7

Michael Burr 13 年前

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)

当量(a,b)&&equiv(b,c)暗示equiv(a,c)

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

equiv是一种等价关系

comp在equiv确定的等价类上导出一个定义良好的关系

诱导关系是一个严格的全序。

尾注]

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

== 是一个等价关系,也就是说,它满足以下条件属性:

对于所有a,a==a。

如果a==b,则b==a。

所以你的 Compare() 运算不会产生等价关系。

获得断言而不是随机丢失数据是一种很好的方式。

一种解决当中有两个(或多个)条目时随机化排序顺序问题的方法 _vec 等于是为那些索引构成随机值,并在索引=>随机值之类的。只要确保跟踪并使用这些随机值,就可以使 比较() 持有

2

3

Sergey Kalinichenko 13 年前

std::sort 希望您的小于运营商提供 及物的 关系,即当排序看到 A < B 是真实的,并且 B < C 是真的暗示那个 A < C 也是如此。

在您的实现中,传递性规则不成立:当两个项相等时,您随机告诉排序,其中一个大于另一个。这将触发调试断言。

如果值相等,则返回false以修复此问题。